[HELP] Accurate Optimized Hittest

[UnknownGuy]

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...

[iopred]

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.

[UnknownGuy]

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

[St. Nick]

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...

[metanet]

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

[UnknownGuy]

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.

[iopred]

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.

[slight]

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

[iopred]

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.

[slight]

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.

[UnknownGuy]

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...

[lesli_felix]

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?

[metanet]

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

[iopred]

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.

[BlinkOk]

you gotta MX version of that?

[iopred]

Done.

[slight]

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

[iopred]

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

[BlinkOk]

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.

[UnknownGuy]

---Bad Question---