[HELP] Accurate Optimized Hittest

I'm currently working on a space shooter game, and am trying to figure out an accurate(and optimized) way of hittesting. They way I'm doing it so far only works with rectangle and squares and the code I'm using for that is

code:

---

 //Movement has already occured before this, so the x and y are updated(the enemy is going to be removed so I don't think it matters) 

function shiptoenemytest(ob){

	for (prop1 in enemylist){

		if(_mathabs(ob.row-_mathceil(enemylist[prop1]._y/colandrowinfo.enemytoshiprow))<2){

			

			if(_mathabs(ob.column-_mathceil(enemylist[prop1]._x/colandrowinfo.enemytoshipcol))<2){

				hiTcollsions(ob,enemylist[prop1],prop1)

				}}}}											   

function hiTcollsions(ob1,ob2,name){

	

	if(ob1._x<=ob2._x){

		

		if(ob1._x+ob1._width>ob2._x){

			if(ob1._y<=ob2._y){

				

				if(ob1._y+ob1._height>=ob2._y){

					enemyrammed(ob1,ob2,name)

					}

			}else if(ob1._y<=ob2._y+ob2._height){

					enemyrammed(ob1,ob2,name)}

			}

		}

	else {

		if(ob1._x<ob2._x+ob2._width){

			

			if(ob1._y<=ob2._y){

				//ob1 is lower

				if(ob1._y+ob1._height>=ob2._y){

					enemyrammed(ob1,ob2,name)}

			}else if(ob1._y<=ob2._y+ob2._height){

					enemyrammed(ob1,ob2,name)

					

					}

			}

		}}

---

As you can probably tell(I hope)this only checks for the perimeters of the objects.
So what I'm planning to do is use something similar to this Kirupa tutorial. Except I'm planning to make a ring of dots every pixel around both objects and use a for in loop within a for in loop to test if the x and y coordinates of any of the dots are equal(or very very close). This check would be called where it says enemyrammed in the actionscript, after all the others...
What I want to know is, is there a better way of doing what I want, or is there a way of improving what I'm trying to do?
If this is really confusing just say so, and I'll try to clarify...
P.S. I'm trying not to use Hittest(the built in one) and find a more optimized way...

Me and Squize did some tests a while ago. HitTest is the fastest your going to get, its about 7 times faster than checking bounds. Currently there is no 'perfect' way to do collision checking, without testing lots of points against the object.

Find a way to get hitTest to work, by either having multiple segments on the enemies, or shrinking the hit box down by placing a smaller clip inside the enemy, and checking the hit on that.

But wouldn't it be faster just to check the outside of each? Have a separate movieclip for each pixel around the outside and loop through those using a for in loop. Doesn't a hittest check each pixel? If you did this you just be checking the exterior pixels, cutting out quite a bit...plz correct me if I'm wrong...

Edit: Here's a link to an example I was working on and here's the .fla
There's some weird bug with it,(its checking the collision between the two dots) and it only sets it false if you align it again with y coords...if anyone could figure it out I would be very helpful....Thanks

If you hitTest every pixel on the perimeter, you have to hitTest a LOT. Your for loop would be huge, and slow if you try to implement it into a game. Plus, each of those pixels would have to be individual movie clips, instead of say just 3 bigger ones.
That's how I understand it anyways...

iopred -- could you provide any more details? like.. were you hittesting point-vs-MC or MC-vs-MC? and how was the actionscripted test written?

raigan

The thing is I'm not hittesting each rectangle on the perimiter, I'm just checking if the x vaules of two rectangles(and y) from different shapes are the same(so I'm just checking two variables per rectangle) which unless I'm really confused is better than hittesting...I hope you know what I mean.

Edit: Spelling + If you look at the .fla I posted it should become clearer.

meta, I was simply recoding hitTest, it wasnt anything more spectacular than a simple bounding check.

code:

---

if(clip1right > clip2left){

if(clip1left < clip2right){

if(clip1bottom > clip2top){

if(clip1top < clip2bottom){

return 1;

}

}

}

}

return 0;

---

It was in a prototype, and used getbounds(so it was perfect for any sized shape), and the bounds were vars, so they'd be registered in FMX2K4 [eg. var a = this.getBounds(); var b = clip.getBounds()]
The if's were expanded like that for speed.

hitTest destroyed the prototype.

I'll recode it tonight if you dont want to do your own testing. Beleive me I was extrememly suprised, Squize even more so !

It worked exactly the same as hitTest, just slower.

Just out of curiosity iopred, did you also profile distance squared collision testing?

Nope, cause thats circle collisions, I was just reproducing the bounding box only.

I would assume that may also be slower too, because of the squareroot involved.

Fair enough. I use distance squared collision usually, (yes, circle collision) probably because I come from a non-flash background. The speed is a tradeoff, box collision can be faster or slower - from one to four if statements, whereas distance squared is *always* one if, two minuses, an add and two multiplies. The advantage being it is always consistant on CPU load. (plus I like circles better) I've never really bothered to speed test it in flash though.

There's no square root when you check for distance squared and not the actual distance.

Iopred are you saying that 4 if statements are slower than hittesting? If so, that's really surprising...
I guess normal hittest would be more effective if that's true...

If it's built in to flash, then it's very likely to be faster, as it's coded in whatever language the player was built in (probably c++)

Oh, one other thing, has anybody discovered the hack that allows you to check collision between a circle and an irregular shape using just one hittest? :cool:

hey,
i guess the hittest must be implemented in native code then.. i still can't beleive it's so fast.

thanks for the info!
raigan

Okies, heres a little test0r, each hitTest was tried 10,000 times the results went like this:

HitCheckWithBounds: High: 599, Low: 513, Average: 550
HitCheckNoBounds: High: 353, Low: 320, Average: 325
DistanceSquared: High: 284, Low: 243, Average: 250
HitTest: High: 142, Low: 120, Average: 127

Now the only two which I would use however, is the check with bounds, or hitTest, simply because they work no matter where the origin of the shape is, or what size the shape is. The noBounds and distanceSquared checks needs the object centered.

From this I take that hitTest is coded internally. its just that much faster, it is remarkably fast considering the bad press it gets. Average 120ms for 10,000 tests is good in my books.

I do wonder if it was slower before the Flash7 player. Maybe someone wants to test it on that player.

Anyways.

you gotta MX version of that?

Done.

thanks iopred, that was extremely informative.
here's some results in flash player 6...

empty loop: 182 ( just counts to 10000 )
empty function: 753 ( passes a mc to a function which just returns false )
hitCheck: 2199
hitCheckNB: 2337
dist2: 1545
hitTest: 432

wow, one thing which is suprising there, is that hitTest is faster than passing an mc to a function, which makes so little sense!

to be fair you would put the hittest in a function. in a real world situation it would probably be within a function. also the other functions constantly get and re-evaluate mc _height and _width, in a real world case you would prolly store them on the initial pass. these are trivial points coz they don't affect the outome too much.

---Bad Question---

Edit: Horribly wrong on the whole test, oh well :rolleyes: ...

Yeah, that is right. Instead of flash having to look through all of its commands 10,000 times, it only needs to do it once. Then in the rest of the code, it just has to find the variable in the local variables. Since there is only 2 local variables it has to look through it is much faster. You should do that with all math functions.

That's where I got the idea was the math functions, just never seen anyone do that before ;).

You should post it into the optimzation thread mate, it's always nice to give that a 6 month bump, and that way it won't get lost.

Squize.

I was just thinking that...

UnknownGuy, does that code really work?

You call one.hit(), but is that actually defined? Does not look like it from the code you posted.

LOL, whoops I forgot the brackets, but I compared them both on the same comp and they were virtually equal(150ms on my 3ghz machine....), Now I have to make edits ;).

Thanks for catching that...

With the brackets it will definitely not work, since you then call hitTest and store the return value (true/false) in the variable "hit".

What I was trying to say was that hitTest is a MovieClip method, and you assign it to the variable "hit", but "hit" is not defined as a movie clip method, which means you can't call one.hit(). Try:

code:

---

trace(one.hit);

---

and it will return undefined.

SO wait... I thought you said you tested it from ~300 down to 220? So where's the code that did that? Just copy paste that please :)

Strilles point is valid, because your defining the method 'hit' as 'hitTest' however, when you call it:
one.hit(two); the flash is looking for the hit method inside one, which it isnt (you defined hit, in the root, not the MC), therefore you were just calling a undefined function, hence the speed increase.

The correct way to do it is:

code:

---

MovieClip.prototype.hit = hitTest;

---

However I have tested this, and it bears no speed increase.

I even tested:

code:

---

_global.hitt = hitTest

MovieClip.prototype.hit = hitt

---

Trying to suck a little more from the global cheat, but no beef. Seems that hitTest is as fast as its going to get (but damned fast by others comparatively)

Whats amazing is that hitTest is only 2.5 times slower than a blank function

hey,
this thread has been bugging me for a while, so i finally got off my ass.

(use flashplayer7, NOT run in the IDE)

here's a speed test which i think shows a normal usage of three different hittest methods: hitTest(), seperating-axis based, and radius-based ("circle" collision). the time displayed is per-call.

when the shapes are seperated in x, sepaxis is just as fast at hitTest(). when overlapping in x, the difference between hitTest() and sepaxis is very small (<0.01ms per call).

anyway, both sepaxis- and radius-based methods are so close as to be almost identical to hitTest. the differenece would only be felt if you were colliding 1000s of objects per frame, which isn't feasible anyway. this test uses 150 which is still WAY too many.

since in most games the majority of objects are NOT colliding in x each frame, sepaxis could be considered "as fast".

ALSO, both sepaxis and radius-based collision provide you with additional results (about the nature of the collision.. such as the direction to push the objects out of collision).

if you need this "extra" collision information -- which is often the case if you want anything to bounce or slide along a surface -- and are using hitTest(), you'll need to run the sepaxis or radius code anyway in order to get that info. so, hitTest() could end up running _slower_ than sepaxis.

anyway, hitTest() is useful sometimes, maybe. however, i don't think it's really "the best" since, while fast, the results are virtually useless; if you want useless collision results, using an empty function is even faster ;)

raigan

Code:

---

function Box(x,y,xw,yw,col,dep)
{
        var mc = _root.attachMovie("testMC", "mc"+dep, dep);
        var temp = new Color(mc);
        temp.setRGB(col);
       
        this.x = x;
        this.y = y;
        this.xw = xw;
        this.yw = yw;
       
        mc._xscale = 2*xw;
        mc._yscale = 2*yw;
        mc._x = x;
        mc._y = y;
       
        this.mc = mc;
}
Box.prototype.SetPos = function(x,y)
{
        this.x = x;
        this.y = y;       
        this.mc._x = x;
        this.mc._y = y;       
}
//movieclip-based hittest
Box.prototype.Collide_MC = function(b)
{
        return this.mc.hitTest(b.mc);       
}
//sepaxis-based hittest
Box.prototype.Collide_SA = function(b)
{
        var dx = this.x - b.x;
        if(Math.abs(dx) < (this.xw + b.xw))
        {
                var dy = this.y - b.y;
                if(Math.abs(dy) < (this.yw + b.yw))
                {               
                        //hit
                        return true;
                }
        }
        return false;
}
//radius-based hittest
Box.prototype.Collide_RD = function(b)
{
        var dx = this.x - b.x;
        var dy = this.y - b.y;
        var r2 = this.xw + b.xw;
        r2 *= r2;
        if((dx*dx + dy*dy) < r2)
        {
                return true;
        }
        return false;
}

//make two collision structs
box0 = new Box(100, 100, 20, 20, 0x882222, 100);
box1 = new Box(200, 200, 30, 30, 0x222288, 200);

NUMITS = 200;//number of samples per frame for each test
function TickTest()
{
//user input: z for red, x for blue
        if(Key.isDown(90))
        {
                box0.SetPos(_xmouse, _ymouse);
        }
        else if(Key.isDown(88))
        {
                box1.SetPos(_xmouse, _ymouse);
        }               
       
       
//speed test
       
        //mc-based
        var t0 = getTimer();
        var n = NUMITS;
        var res_mc = false;
        while(n--)
        {
                res_mc = box0.Collide_MC(box1);       
        }
        var t_mc = getTimer() - t0;
        t_mc /= NUMITS;
       
        //sa-based
        var t0 = getTimer();
        var n = NUMITS;
        var res_sa = false;
        while(n--)
        {
                res_sa = box0.Collide_SA(box1);       
        }
        var t_sa = getTimer() - t0;
        t_sa /= NUMITS;       
               
        //radius-based
        var t0 = getTimer();
        var n = NUMITS;
        var res_rd = false;
        while(n--)
        {
                res_rd = box0.Collide_RD(box1);       
        }
        var t_rd = getTimer() - t0;       
        t_rd /= NUMITS;
       
//dump results to screen       
        var str = "";
        str += "mc-based: " + t_mc + " .. " + res_mc + "\n";
        str += "sa-based: " + t_sa + " .. " + res_sa + "\n";
        str += "rd-based: " + t_rd + " .. " + res_rd + "\n";
       
        _root.output = str;
}
_root.onEnterFrame = TickTest;

---

In regards to your results. I find that when a collision detection is all that is needed, and the responce is simple, hitTest is the way to go (and in so, use it myself). Additionally, the 2 methods you described depend on the object being centred, and that they define variables (needed a fixed structure for objects). HitTest works off the objects bounds, with no need to know anything about the object, for a physics simulated environment, this is a bad situation, but for twitch games, is all that is needed.

Secondly there is a small discrepancy as your wrapping hitTest in its own function, where it doesnt need to be.

Anyways, I strongly dissagree to your 'virtually useless' results, simply because the function does exactly what we ask, it checks for collision, it gives a response (in what I have found to be) faster than any function I can code.

Either way, the speed differences being discussed are moot, in actual gameplay nothing will be noticed, however, my main issue is having the collision work on the objects bounds, which only hitTest, and a method scripted to use the objects actual bounds will do, in this cause hitTest is a much faster function.

Quote:

---

Secondly there is a small discrepancy as your wrapping hitTest in its own function, where it doesnt need to be.

---

well, in a game i tend to give each type of object its own .Collide() function, which will do various things in addition to testing for the collision.

right now, all it does is test for collision, so it looks a bit useless.

Quote:

---

Either way, the speed differences being discussed are moot, in actual gameplay nothing will be noticed, however, my main issue is having the collision work on the objects bounds, which only hitTest, and a method scripted to use the objects actual bounds will do, in this cause hitTest is a much faster function.

---

well.. collision detection _can_ often be the bottleneck. though admittedly, speeding up the obj-vs-obj testing won't help nearly as much as not doing as many tests.

so, agreed that it's moot. but AFAIK you can only test vs. the actual bounds if you use points.. what would you use a point-vs-shape test for? this has always seemed useless to me, aside from mouse-selection type stuff.

also, i bet i could get a convex shape test running just as fast as hittest if the objects don't collide: just start with the x-axis test as i did.

my problem with the built-in methods is that people struggle trying to get good results out of them, when it's simply impossible to do. they end up using a bunch of point-vs-shape tests, or multiple boxes, etc. which is ridiculous as it undermines the reason for using the built-methods, which is speed. once you test more than a couple points per object, it's faster to do it yourself.

(i'm specifically thinking of racing games, where people for some reason never get the cars to slide against obstacles in a nice way)

anyway, i simply wanted to play the devil's advocate and argue that hitTest(), under typical conditions, isn't any better than other hand-made methods. since the only thing it has going for it is speed.. if it's not much faster, there isn't much recommending it over other methods.

raigan

Quote:

---

so, agreed that it's moot. but AFAIK you can only test vs. the actual bounds if you use points.. what would you use a point-vs-shape test for? this has always seemed useless to me, aside from mouse-selection type stuff.

---

Using getBounds, as in my first example, you can use the bounds, without points.

Quote:

---

my problem with the built-in methods is that people struggle trying to get good results out of them, when it's simply impossible to do.

---

I agree whole heartedly, its a shame that people tend to try and force hitTest(x,y,true) to their advantage, when infact, the point hitTest, is very slow. My argument was more for only rectangle vs rectangle.

Quote:

---

There isn't much recommending it over other methods.

---

Other than ease of use, and its dependance on nothing more than 2 mc's

I'm a fan of rectangle vs rectangle simply for its simplicity, I mean, its a simple 4 line function, and you can do alot with it in action games, you dont usuall need indepth collision checking, usually rectangle will do (squize will definately agree), the reason I use hitTest is because its faster than defining my own function for it, for a single line check, it is, as my first example showed, alot faster than another method (as long as its not wrapped etc.). Again, my only point is that for a one line general purpose rectangle vs rectangle collision routine, hitTest seems to be the fastest.

I hardly want (or need) to argue the point, do not think I am saying hitTest is the end all of anything, its only good for what it does, and its never good when your trying to get more out of it then there is to be got.

Besides, whos going to use stupid old rectangle collision when nothing can compare to the sweet ragdollness of N.
*still jealous*

Quote:

---

they end up using a bunch of point-vs-shape tests, or multiple boxes, etc. which is ridiculous as it undermines the reason for using the built-methods, which is speed. once you test more than a couple points per object, it's faster to do it yourself.

---

Probably true, but not eveyone is a math genius and knows how to do this.

Err....That was a bad mistake, forgot that it was a movieclip method, my bad :(. Now I'll have to go and edit things ;).
It was fun while it lasted!:rolleyes:

"usually rectangle will do (squize will definately agree)"

I so do :)

It's very, very rare that I ever use a really accurate collision check, the only example I can think of off the top of my head is the platform checking in uxb. Something like that needs to be fairly spot on, but in saying that I still cheat a bit to improve the feel.

People seem to have a hang up about everything being pixel perfect ( Raigan that's not aimed at you, just a generalisation ), where most of the time it helps the game play to cheat.

Squize.

hey,
actually i'd never want pixel-perfect collision -- convex shapes usually behave a lot better. ;)

it's not the precision of the bounding shape i'm arguing for as much as the fact that (for sliding or bouncing) you need more than a yes/no result.

raigan