[Disc]multiple collisions

[zervell]

I was looking at the rts thread and I was thinking about the battles in rts games. I was thinking that there must be a better way of testing collisions. I think a lot of people use a dual loop to test all the collisions. I was thinking how slow it would be in an rts game to use a loop to find collisions. I was wondering if any one has came up with a better way of testing multiple collisions. I have a theory and was woudering what are your thoughts on mass collisions.

[mr_malee]

the easiest method is to check a small space around the object which it can reach. This usually comes in the form of a grid. To further simplfy the checking in this grid the following method seems like something i will adopt.

http://lab.polygonal.de/articles/rec...al-clustering/

objects add themselves to grids, either square or section/ zone based/ landscape based

then perform additional interval checking to split checking into groups.

multiple unit selection will also be detected with intervals

[zervell]

My theory questions why are multiple collisions multiple? I was thinking why not put all the bullets in one movie clip and all baddies in one movie clip?[it will be a hierarchy] then they will only use one hitTest. Do you think there are set back to doing this?

[Djugan]

Organizing all the bullets and enemies in their own MC wouldn't work because the second you add more than one bullet or enemy to the MC, the boundary box is going to expand to include both instances. The problem with that is that anything inside that box, whether it's actually hitting the MCs or not, is going to register as hitting.

For example, if you've got two tanks, in opposite corners of the map. If they both fire, and you attach two bullet MCs inside the MC that will contain all bullets, the parent MC's boundary box is going to stretch to include both bullets from the two tanks. That box is going to take up the entire map, and any unit within the map is going to be "hit" by those bullets.

[alillm]

It will work one way. For example you can put all the enemies into one movieclip and then do a point-movieclip hitTest with each bullet. If the collision is found, then you loop through the enemies and see which one was hit. In an RTS though you wouldn’t want to be checking every enemy for every bullet, like mr malee says, there are methods of narrowing down the collisions.

Ali

[oronll]

Here are some of my tips for faster collision detection .

1. be sure to only check collision on screen and not off screen .

2. Arrays work very well . checking the collision against an array ONCE is a lot faster than checking each object on screen .

[VENGEANCE MX]

This is the fastest way I've used:

yQuadrants = 10;
xQuadrants = 10;
quadrantWidth = 30;
quadrantHeight = 30;
for (i=0;i<yQuadrants;i++) {
	quadrants.push(new Array(xQuadrants));
	for (j=0;j<xQuadrants;j++) {
		quadrants[ i ][j]=new Array();
	}
}

That should set up a 10x10 grid of collision quadrants. Now, inside the enterFrame event, we start off by resetting the array (admittedly we don't need to do this on frame 1, but it's no big deal):

for (i=0;i<yQuadrants;i++) {
		for (j=0;j<xQuadrants;j++) {
			quadrants[ i ][j]=new Array();
		}
 }

Now, when we're looping through our troops, we've gotta push them into the right quadrants. Here's how:

xQuadrant = Math.max(0, Math.min(xQuadrants, Math.round(x/quadrantWidth)));
yQuadrant = Math.max(0, Math.min(yQuadrants, Math.round(y/quadrantHeight)));
quadrantPointer[yQuadrant][xQuadrant].push(this);

Finally, on the bullets, here's the collision check:

xQuadrant = Math.max(0, Math.min(xQuadrants, Math.round(x/quadrantWidth)));
yQuadrant = Math.max(0, Math.min(yQuadrants, Math.round(y/quadrantHeight)));
arrayIndex = quadrantPointer[yQuadrant][xQuadrant];
if (arrayIndex.length>0) {
arrayIndex[0].die();
arrayIndex.splice(0,1);
}

So, what's so special about this method? Well, an ordinary for..in loop, just checking every bullet against every troop, with 100 bullets and 400 troops, would be 40,000 hitTest()s. Ouch. My way, we cut that down to 0, and ditch the hitTest()-based collision.

[alillm]

Wouldn’t it be slightly faster to just update the arrays each frame instead of having to do a nested loop each frame to clear the old data? So when you add an enemy to the array you give it a number based on the position in the array it just got added to, then you just have to check each frame if the enemy has changed quadrant, if it has then splice it from the array using the number you stored and then add it to the new quadrant. Of course you would then have to loop through the rest of the array and decrease the number of the rest of the enemies by 1.

The way your doing it you are creating 100 new arrays each frame which isn't really necessary

But nit picking aside, yes, that’s how I would do it too

Ali

[alillm]

Stupid 10 min edit thing.

Just wanted to say that with the numbers of enemies you are talking about it probably would be faster to clear the arrays each frame. With less enemies though it would be faster to just update the arrays.

Ali

[WilloughbyJackson]

I've gotten really good speed combining both the all the bullets in one clip method, bitmap data, and grid methods.

[zervell]

Turning a theory to a reality. 140 movie clips hitting each other at 30 fps without the use of dual loops. I call it h.h.t or hierarchy hittest.

[NOTE] if I didn't make the MCs transparent the frame rate would be higher

thanks to Madokan of the ActionScript.org Forum for the frame rate code

see it in action

download it

tell me what you think. Do you think this method is worth perfecting?

[VENGEANCE MX]

Zervell, I get 16-20 fps on that. :s

[mr_malee]

Stupid 10 min edit thing.

Just wanted to say that with the numbers of enemies you are talking about it probably would be faster to clear the arrays each frame. With less enemies though it would be faster to just update the arrays.

Ali

associative arrays baby.

delete grid[x][y][name]

[alillm]

12-22 fps. I think you should try the other methods suggested here and see what happens. Also, why use transparent movieclips if you know its going to slow things down?

Ali

[alillm]

associative arrays baby.

delete grid[x][y][name]

Didn't even think of that lol that would work nicely.

Ali

[VENGEANCE MX]

Yeah, in performance tests, it's an unwritten law that everything must be bitmapped.