5 Replies Latest reply on May 22, 2012 10:39 PM by Rothrock

# Create smart hit test checks?

I'm working on a TD game, nothing special but to learn flash.

What I am currently doing is placing monsters on the map, and each monster loops through an array of the towers ranges each frame to see if it's in range of any of the towers.  It works well but I'm wondering if there's a way to make it better.

Is there a way to make the hit test smarter where every monster doesn't need to hit-test every tower? The only things I have been able to come up with involve further checking that would end up being more complicated then the simple hit test.

Note: I'm not using hitTest(), I'm using different maths to figure it out.

Thanks in advance.

• ###### 1. Re: Create smart hit test checks?

If you show what you are currently doing it will be easier to tell if there is a smarter way.  If there is a chance that any monster can be in range of any tower, then you need to check every tower.

One idea as an alternative would be to add invisible (alpha = 0) portions surrounding the towers that represents the range and use a hitTest to detect when they are within range, but I still see a need to check against all towers, at least all towers within a region.

In terms of regions you could have different regions defined/.assigned to each monster when they get planted such that you only check towers within the region.

• ###### 2. Re: Create smart hit test checks?

Recursive dimensional clustering http://lab.polygonal.de/?p=120

Quadtree http://lab.polygonal.de/?p=202

1 person found this helpful
• ###### 3. Re: Create smart hit test checks?

@Ned:  I'm not exactly looking for a better way of doing the hit-test, I think I have it down but it would be great to see someone else say so.

_root.range_list is an array of objects to hit test.

_root.monster_list is second array of objects to hit test.

The hit test itself is very easy, the object is a circle so I test if the "diameter" of the object to be hit tested is smaller then the diameter of the circle being hit tested.  If it's smaller then it's within the circle, if it's bigger it's not.

in a nutshell -

if(it's able to hit test)

{    while(do hit test)

{

if(hit test)

{

if(ready to shoot)

{  - shoot -  }

- end hit test -

}

}}

_root.range_list[x].onEnterFrame = function() {

if (!_root.tower_list[this.tower].placing) {

monster_counter = 0;

this.shoot_counter++;

while (monster_counter < _root.monster_list.length) {

hitDif_x = this._x - _root.monster_list[monster_counter]._x;

hitDif_y = this._y - _root.monster_list[monster_counter]._y;

if ((hitDif_x * hitDif_x) + (hitDif_y * hitDif_y) < (this._width + 15) * (this._width + 15) / 4) {

if (this.shoot_counter > 10) {

_root.placeBullet(monster_counter,this);

this.shoot_counter = 0;

}

monster_counter = _root.monster_list.length;

}

monster_counter++;

}

}

-----------------------------------------------

@Rothhrock: I was thinking of doing something like that, the quadtree, but wasn't coming up with anything that would be less work then just doing the hit test on everything.  Breaking the larger sections down...that could work.

(added)
Rothhrock, how would a quadtree work?  I am thinking having multiple monster arrays, moving the monsters between the arrays as it moves between game sections and then testing the arrays those objects are in, but I'm not sure if the management would be any less work.

• ###### 4. Re: Create smart hit test checks?

I've never implemented one. So I'm not sure of all the details. There are lots of demos out there (mostly in other languages, but the ideas should be pretty similar.) I would probably start here: http://www.gamedev.net/page/resources/_/technical/graphics-programming-and-theory/quadtree s-r1303

Remember that some kinds of operations are more "expensive" than others. So managing some arrays (or vectors) is likely to take less time than performing hit tests.