#### Archived

This topic is now archived and is closed to further replies.

# Spatial Sorting For AI

This topic is 5380 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What are the better spatial sorting schemes for use with AI? I am looking to develop a space dog fighting AI and I am very aware that fast ''is ship Y near ship X'' queries are going to be required. I''ve looked at the usual octree and BSP methods but they don''t seem to be quite what I am after. I''ve been thinking of dividing space up into zones or bins (I think it was refered to in 1 paper) and sort the ships into the bins depending on locations and using the bins to speed up the search. Any suggestions? Cheers, Convict@Large

##### Share on other sites
That''s actually a decent approach. It''s almost an LOD style forumula. However, you have to make sure that the zones either overlap or that you check neighboring zones otherwise you risk having 2 units straddling a line where neither knows about the other.

Dave Mark - President and Lead Designer
Intrinsic Algorithm -
"Reducing the world to mathematical equations!"

##### Share on other sites
Actually, you''ve already gone past the data structure you need! An oct-tree would be perfect for partitioning of 3-D space. The oct-tree is just a special case of the more general k-dimensional tree. The search algorithm you want to use is the m-Nearest Neighbour Search (NNS). Here nearest neighbours are not necessarily spacially nearest, although that is the most obvious distance measure used. You can use any metric you want so long as the tree is partitioned on the correct state space.

NNS is very fast on k-d trees, even for large numbers of things in your tree. I''ve recently implemented k-d tree code capable of variable dimensionality, covering 10s of thousands of data objects. Search in the tree is blindingly quick (measured in milliseconds). Building the tree takes a little longer (a couple of seconds), but if you have only a few dozen to a few hundred items then tree construction should be much quicker (proportional to number of items). However, if you only have a few to a few dozen ships, then brute force testing of all inter-ship distances would end up being just as quick.

If you need help understanding how to go about nearest neighbour search, or help finding resources, holler!

Cheers,

Timkin

##### Share on other sites
RE: InnocuousFox

I suppose I could use a bounding sphere for the searching ship to represent the search area, and if the area is not contained by the current bin, we know we need to widen our search to included the neighbouring bins?

##### Share on other sites
Sorry to butt in, but I would be interested in some reading on the k-d trees, Timkin. Could you post some info? Perhaps some references, etc?

Thanks!

-Kirk

EDIT: Asked for references for clarity.

[edited by - KirkD on March 26, 2003 10:58:18 AM]

Convict@Large

##### Share on other sites
quote:
Original post by Convict@Large
RE: InnocuousFox

I suppose I could use a bounding sphere for the searching ship to represent the search area, and if the area is not contained by the current bin, we know we need to widen our search to included the neighbouring bins?

That is basically how m-Nearest Neighbour Search works on a tree structure. The size of the sphere is defined by the distance to the mth nearest neighbour found so far.

As for references... the starting point is Jerome Friedman''s paper:

Friedman, J. H., Bentley, J. L. & Finkel, R. A. ''An Algorithm for Finding Best Matches in Logarithmic Expected Time''. ACM Transactions on Mathematical Software, Vol 3, No 3, September 1977. pp 209-226.

There are plenty of other resources (papers) out there which are derived from this work, or approximation schemes for achieving similar results in stupidly large data sets!

If you need more references, just holler...

Cheers,

Timkin

##### Share on other sites
I''m having problems tracking down that paper on google is there a better search engine to use for finding papers?

Convict@Large - Slayer of Bugs

##### Share on other sites
I''d actually stay away from any kind of tree for such dynamic entities. The more they move, the worse it gets. You''ll end up with having to update and modify the tree at runtime, an that can be ugly for cache access (no matter how clever your memory allocation is). Go badger the ROAM people if you don''t believe me

For flocking (even more demanding), I''ve personally used arrays of sorted coordinates along each dimension (2D with X & Y often enough). You can keep these arrays upto date VERY quickly with an insertion sort. Each coordinate points to it''s owner (entity), so you can traverse the sorted array (in the nearby range of any entity) and get the entities in proximity. You can do that on multiple dimensions and combine the searches with a bitfield (actually quite small - just 1D in my case).

Artificial Intelligence Depot - Maybe it''s not all about graphics...

##### Share on other sites
Certainly for small numbers of entities I would agree with Alex's approach. Using tree structures for partitioning data sets is really only advantageous when there are LOTS of entities and/or lots of possible state space locations (large attribute domain) for them.

Cheers,

Timkin

[edited by - Timkin on March 27, 2003 10:49:33 PM]

##### Share on other sites
Well I went with a simple sorting of axis-aligned bounding box coordinates, having each corner belong to 3 special linked lists, one for each axis. I use a simple sort because it is fairly quick when you have reasonable frame-to-frame coherency, meaning it doesn't take a lot of CPU effort to keep things sorted because spatial relations don't change drastically from frame to frame.

Pseudo-code:

            struct Corner{   union   {      float Position[3];      struct { float x, y, z; };   };   Corner* Prev[3];   Corner* Next[3];   int Order[3];};struct AABB{   Corner LowerCorner;   Corner UpperCorner;};

Link together and maintain sort of all LowerCorner.x and UpperCorner.x,
Link together and maintain sort of all LowerCorner.y and UpperCorner.y,
Link together and maintain sort of all LowerCorner.z and UpperCorner.z,

While sorting, keep track of sort order along each axis so that you know how many corner elements between the lower corner and upper corner components. Choose the one with the least number, and then check for collision only with those corner elements between the lower corner and upper corner along the chosen axis.

I had tolerable performance even with 1500 rapidly moving entities.

Value of good ideas: 10 cents per dozen.
Implementation of the good ideas: Priceless.

Proxima Rebellion - A 3D action sim with a hint of strategy

[edited by - BS-er on March 27, 2003 11:31:55 PM]