It turns out I need a quad tree for cols(or do I?)

Hello friends;

I am working on an rts game where player (and the computer) each might have up to a few hundreds of units. (I know, it sounds like bad design, but it's not, you will believe me when I show you the game:))

And since most, if not all, units will need to react to enemy units when they are in range, I will need a real or pseude collision detection between the few hundred player objects and few hundred computer objects. Add to that the terrain pieces, which is a rather large terrain by the way, and you see I got myself in trouble. I am not even mentioning that each player unit currently doesn't check against collision for eachother, so they are able to pass through eachother.

Now, I have tested this up to a 300 player units against 50 terrain objects and pc is able to handle this very well. But beyond this it will become bad, and I will not be able to expand.

After some research I am convinced quadtrees may help me here. I have read some posts by Ashley where he says collision performance is on to do list but low priority. But I think I can create my own quadtree system via events and thats where I need help.

First, check this beauty up:

mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation

Now, then, any idea where / how to start :)

EDIT: or this spatial hashing, which looks easier to implement:

conkerjo.wordpress.com/2009/06/13/spatial-hashing-implementation-for-fast-2d-collisions

Kind regards and thanks in advance;

-Wind.

I tried to implement a quadtree, but picking elements before checking for collisions takes as much performance away as you get in return from doing less collision checks.

Thinking out loud:

Say yo have lots of units and lots of levelobjects you want to test collisions with.

disable collisions on those units.

add a for each for units

distance unit to levelobject < varible : enable collisions

distance unit to levelobject > variable : disable collisions

Not sure if this works as I have in my head, but in theory, the space < variable, should create a void in collisions detection, which might reduce load more then the load generated by the for each loop, giving a performance increase.

Just theory, you would have to try it out to see if it works ....

lennaert: I've meddled around with the foreach and distance expression before, but the saved performance wasn't really astounding. Here an example:

s000.tinyupload.com/index.php (the used variable will prevent duplicate comparisons)

click on the text to dial through the different collision detections.

Your suggestion only compares against a single point, so it is not really useful but I've added it as well.

mindfaQ have you tried something similair without families ?

Nope. You are free to give it a try and post your results ofc.

(just noticed that it is possible to skip the used-variable/function and instead use family1 for each ordered by uid, pick family2 by comparison family2 uid > family1 uid)

Well one of the collision models you can do In C2 is this.

break up your collision types.

unit with terrain(UwT)

unit with unit(UwU)

unit with weapon fire(UwW)

var collision_test = 0

Then instead of checking for collision as normal try this.

Every Tick

-if collision_test = 3

-->collision_test = 0

-> If collision_test = 0

--> Unit collided with Terrain

-> if collision_test = 1

--> Unit collied with unit

-> if collion_test = 2

--> Unit collided with weapon

collision_test++

this however is only a temporary stop gap. And is not an ideal solution.

I've informely asked Ashley each time this subject comes up; that Ashley please use Mike chambers quadtree collision with C2 rather the current brute force method of each object checking for collision against each other. This is because this feature should be inherent in the engine for the purpose of how he works collision with sprits. But alas no such luck yet.

So at this time it seems unlikely that C2 will ever use a better collision detection system without far more clamour :(

Also building in this engine in C2 would require a different way of design that what you tried. Don't build it around picking out sprites. You would have to build a C2 Quadtree around using Arrays and only arrays. And doing so would be so much array management that you probably wouldn't get much performance out it anyways.

The other option is to use a behaviour or plugin that uses this. This can work well and for your game would be fine. but in the long run Platformer and all the other cool behaviours still are missing the benefits.

I will try and build some testing methods —

there is also the other option, having game mechanics preventing such a situation from happening in the first place   ^_^

Thanks for the replies, everyone. I tried to implement the spatial hashing, but picking cost seems to be higher then the actual collision checks (that, or I really effed up in the events).

So for now, I will try to design with lower counts of objects. And my grid based, real time map system will have to change completely...

How nice would it be if someone could come up with a plugin or behaviour for this, as both the quad-tree and spatial hashing seem to be easy to implement...