A Fast KD-Tree or Unity Alternative

Sure, finding the nearest neighbour was exactly what I was doing.

I suggest trying a few solutions, benchmarking them, and see what's up. With a performant algorithm and some clever optimisation (don't do this every frame for every unit, run in separate thread) you should be able to get some great results.

 

That's impressive but perhaps you could make it simpler by only doing the calculations for the entities that the camera is actually looking at and doing some simplified calculations for what the we don't see instead of doing the AI for every character. I am quite keen on the idea of Level Of Detail (LOD) based AI. That is AI that adjusts how clever it is based on if the player is actually looking at it. I come from the world of military simulation and we would aggregate the entities when we got to that many units and only do individual AI when the camera is actually looking at them.Does that make sense?

K

 

Hi Karl and npsf3000, that's interesting to hear. I already did some simplifications. One of it is that I use coroutine with timer of about 0.1 s. I also tested additional breaks when kdtrees getting larger. Another approach was to scale pause times for coroutines to actual FPS rates. However, most of these tricks are like crunching to the wall. The heavy part begins when front line starts fighting. Dead units are falling and their attackers need to find new targets. So there is always data flow through kdtree. If I increase time spend in pauses, during this time lists becoming bigger due to pending search. So the main issue remains how to pass data flow through kdtree faster.

Dealing with calculations only which are on the view of camera looks quite interesting idea. But in that case if you would move out camera, lets say to look what is happening in base, or just to spawn more troops, the front battle, which is not visible to camera would eventually freeze, as attackers would kill their targets and new targets would be not assigned. How you would deal with such issue?

 

Is your find code running on another thread? What is happening every 0.1s?

Some random idea's:

• Multiple KD trees.
• If you're not already, minimise updates (e.g. don't update position every frame).
• Getting approximate nearest neighbor, rather than absolute.
• Get a list of nearest neighbors rather than closest, if your target is killed first see if any of the others are in range before returning to list.

LOD simply suggest you spend less resources computing a result the less important it is (e.g. far away from camera). Not that you don't compute at all (that's culling).

 

I suspect they are running on the same thread. I am usually using webplayer builds for my games and in future will probably switch to WebGL, so I am not sure if multithreading is well supported for these platforms. Every 0.1s it is rebuilding the tree and searching neighbours for attackers, which do not have targets assigned.

These looks very interesting suggestions and I have some questions. Does kdtree, which Karl used calculate approximate nearest neighbour? The one I am using doesn't and I was looking for ages for solutions which would work for Unity, but still didn't found any. Do you know if there is any working solution, which would be searching ANN instead of NN for Unity?

The kdtree I am using doesn't have implemented searches for 2, 3.. k-th nearest neighbours (I also tried to implement it myself, but it didn't worked correctly), so the same question - does kdtree, which Karl used support this?

Sounds interesting - I will check it too.

 

I just managed to implement the same kdtree
http://home.wlu.edu/~levys/software/kd/
as Karl did. Interestingly I can say, that this kdtree seems to be much slower than this one:
http://forum.unity3d.com/threads/point-nearest-neighbour-search-class.29923/
I ran some tests for 0.2 s and levys kdtree seems to be moving down FPS to ~30 with 10000 points and just 100 queries running (without rebuilding tree). Andeee's static kdtree runs with 10000 points and 10000 queries (without rebuilding) at nearly 40-50 FPS. I still didn't managed to implement kdsharp one, as this one looks more tricky.
It's very interesting to see that different versions of kdtrees can be so much different in performance as well