Does Irrlicht provide spatial indexing (searching) utility?

[sfncook]

Hi folks, I am making an RTS and need a quick way to allow units to "see each other" by search through all scene nodes and determining who is within a certain proximity - like radar. I was thinking something along the lines of the octtree as defined by wikipedia (http://en.wikipedia.org/wiki/Octtree) but Irrlicht's octtree does not provide the spatial indexing required (at least I didn't see it in Octtree.h). What tools are you fancy people using for this? Thanks.

[rogerborg]

For proximity testing, I use single-axis spacially ordered lists. I keep a list/array of objects ordered by X (or Y, or Z, whichever will tend to best reduce clumping), then each object only needs to check the other objects in each direction until it finds one with a delta larger than its area of interest, at which point it can stop testing.

I prefer this over an octree because:

1) Keeping the list in-order can be done with a bubble sort (unidirectional or bidirectional depending on how many processing passes you're doing). Before you gasp in horror at the naivety of that, consider that the ordering of objects won't tend to change much, so this will be one or two if() test in most cases, making sorting relatively cheap.

2) With an octree, you have to go up the tree until you find an area big enough to cover your area of interest. Depending on the position of the testing object, the size of the octree nodes, and your area of interest, this can lead to you checking more objects (sometimes a lot more) than you really need to.

On the downside, when you get a situation where a lot of objects have similar X values (when you're ordering by X) then single-axis sorted lists become inefficient. However, with an octree, any objects whose area of interest spans any centre axis of the top level of the octree will end up checking against every other object, so neither is perfect.

Horses for courses though; what works for me may not be ideal for your requirements.

[Frosty Topaz]

Slight aside, but for an RTS you'd probably just need a quad tree as there's not really a height component. Unless it's in space/underwater with spaceships/submarines that can go up and down.

But unless you're expecting thousands of units rogerborg's solution should be more than good enough. An you may want to consider having different lists for each player. I can think of a couple situations where you wouldn't need to check for friendly units.

[rogerborg]

Out of interest, why would a oct- or quad-tree scale better than a single axis list in practice? I'm open to persuasion.

[sfncook]

In fact, it *is* a 3d space-based RTS and I am considering a unit count on par with Supreme Commander. So, ~5000 units max (all teams) would be about right. I'm thinking that the unit positions will tend to be very "clumpy" - that is many units will tend to be clustered around resources or bases (like battleships or spacestations). I think this leads to Rogerborg's question. I mean if a few clumps happen to be in line with one another then you have just increased the work for sensing by these units by a few magnitude. Where as with a quadtree or octtree there is not so much of a risk. Roger, I don't really understand your second point but this may just be my limited understanding of how to design an octtree. Would you care to elaborate?

Thanks for the help, guys.

[keless]

To conceptualize an octtree, think of a cube that encompasses your ENTIRE game area. Now cut that into 8 smaller cubes (one for each corner of the original cube). Now cut THOSE each into 8 smaller cubes, and so on.

Now, lets say your smallest cubes are 100 'units' wide. You have a unit at x position 99, that needs to sense things in a 10 unit wide area around it. It is inside of an octtree leaf we will call "a". This leaf has a parent we will call "A" (note the capital).


[ octtree node A contains 8 children: [ a ] [c] [d] [e] [f] [g] [h] ]

Since the unit is near the border between 'a' and another octtree leaf (lets assume its 'b', and since the radius of your search extends past the border of 'a' into that other octtree leaf 'b', we have to increase our search area from one leaf 'a' to eight leaves (all of the children of "A").

That was only across one border, lets consider an even worse scenario: the octtree node 'A' has seven brothers: 'B', 'C'.. etc.

Lets say your search is on a corner of the leaf A:h where your radius punches beyond A:h -- now you are potentially checking 64 leaflets (which you will hopefully be able to whittle down to a maximum of 8 again based on the radius of your search.

[sfncook]

Ah, I see. Sounds like I'm heading for a single axis search algorithm. Thanks guys!

[Frosty Topaz]

Out of interest, why would a oct- or quad-tree scale better than a single axis list in practice? I'm open to persuasion.

I would think that tree structure would work better for cases where you expect "clumping" to occur. Imagine a case of a fully sorted 1 dimensional list if you have 100 units in the same area all trying to move around each other to some target. That would cause a lot of resorting to have to occur. A tree may work better in this case as objects would naturally be placed in bins. The observant reader will note that you could also sort a single list loosely into bins and save a lot of sorting at the cost of some checks.

A tree is also a bit more general as it doesn't rely on a spread tending to be along a single axis, but more easily handles an even distribution along as many axes as you like.

All that said there will be points where a tree will not perform so well. Such as when a unit is near a corner of one of the tree's leaves/cubes.

An interesting idea I once heard of (in theory, I haven't seen this tested) was a series of overlapping spheres rather than cubes (again stored in memory as a tree). IIRC the idea was that an object moving from one sphere's area into the next would for some time be in both spheres and belong to both which allowed it to quickly check each sphere's contents without it having to decide where to check when it was "looking", only when it moved (and then by a quick distance check to the center of neighboring spheres). I think the application this was considered for also had an AI that looked forward, not all around, so when in two spheres it could sometimes drop one if it was behind the unit. As I said an interesting idea, but I'm not sure how useful it would be.

Back to the main point. I would say a tree will out-perform a sorted list in the situations where there is more clumping and/or where many things may be happening off the main axis. While a list is much simpler to implement/maintain and for more linear problems would be much better suited and probably perform better. Not all of that was on-topic and I apologize.

[rogerborg]

I think it's very much on topic for the thread, just not for the forum area.

I freely admit that I haven't performance tested alternative implementations with real data, so I'm largely talking out of my hat here.

Imagine a case of a fully sorted 1 dimensional list if you have 100 units in the same area all trying to move around each other to some target. That would cause a lot of resorting to have to occur. A tree may work better in this case as objects would naturally be placed in bins. The observant reader will note that you could also sort a single list loosely into bins and save a lot of sorting at the cost of some checks.

With buckets, you have to 'sort' every object anyway, i.e. check that it's in still in the correct bucket each and every time that it moves. Testing the sorting of a single axis list just requires two ifs() per object (or just one if you can use a unidirectional sort) rather than four or six for a 2d/3d bucket check, and even with heavy clumping it's still likely that testing will dominate over swapping. Actual swapping is a relatively cheap operation: it's just a swap of two pointers (and telling two objects their new indices if you're using an array).

Clumping does provide a problem for testing a single axis list though, no argument there, and I do agree that you should certainly consider ameliorating the worst case rather than optimising the modal one, depending on your application.

Regarding octrees, something that I've been chewing over is whether it's better to go up the octree and check all children of a large enough node (which may be the tree root in some edge cases), or whether you should dump the tree and just use spacial buckets (i.e. equivalent to the final leaves of an octree).

With regular 3d grid of spacial buckets (or 2d tiling in a 2d game) it would be fairly cheap to calculate which zones are within your area of interest. This would be more precise than going up and then down an octree and checking child leaves which aren't actually in your area of interest.

Something that I've never come up with a good solution for is the problem of object size. Using any sort of spacial partitioning, an object with a non-zero size could span several buckets. I don't have a clear idea of how best to deal with that. You could actually add it to multiple buckets (which will result in duplicate checking and a more complex implementation) or increase each area of interest by the size of the largest possible object to ensure that none of them are missed (which will sometimes lead to you checking more buckets than necessary). Any thoughts?

[Frosty Topaz]

Unless you have very large objects an object with size 0 (a vertex for the mathematically challenged (often enough me)) is a decent enough approximation.

I would argue that it's faster to test if an object is in a bin (for 1D a single division can give you the bin number, then you just need 1 if) than to check exactly which order it's in. Especially in a clumped situation where an object may move past 10, 20, ??? units as that could require many pointer swaps.

Code: Select all

binNum = static_cast<s32>(Pos.X) / binSize;

if (binNum != bin->getNumber())
{
     // Change bins
}

A spatial grid would actually be my choice of implementations anyway. I've done them with both arrays and maps. Arrays tend to be faster while maps tend to be smaller.

Also (for trees) I'm not sure you'd ever HAVE to check all the children of the larger node... why not use multiple traversals? Thus you could always get down to checking 4 (for quad) or 8 (for oct) nodes. Assuming of course that your leaf nodes are larger than a unit's "scanning radius".

[keless]

Wouldn't a hash<int, vector<obj_reference>> be better than a sorted array for the 1D buckets?

[sfncook]

I think hash<int, list<obj_reference>> would make it a little quicker to remove items from a bucket.

Also, in terms of a spatial grid, would an R-Tree be too costly to maintain? (http://en.wikipedia.org/wiki/R-tree)

[Frosty Topaz]

I think, based on the quick read-through I just did, that if you wrote a fairly smart R-Tree implementation it could work. The ideal would be to have leaf nodes that follow the clumps of units that tend to pop up in RTS games. A simple way to do it would be to have each team be a node under the root. As you create units you place them in the "clump node" that they're nearest to, up to a certain maximum distance, or create a new clump node, beyond that distance.

You may find that maintaining the clumps becomes kinda heavy at times. Moving them is simple enough, but separating/merging units out of/into other clump nodes may be too costly. Again check the distance from the center of the clump, if it's too far take it out, see if another clump would work or make a new clump. It'd be interesting to try it out and see how the performance actually goes.

It could be done, but a spatial grid is far simpler.

The word "clump" is beginning to lose all meaning...

[rogerborg]

I'd need to see the numbers to be convinced by an R-tree. It looks to be suitable for static objects, but I don't think that it would cope well with moving ones; you'd end up doing a lot of testing and altering of regions each and every time an object moves, and you're still left with the issue of very inefficient tests whenever your region of interests crosses the boundary of a top level region.

I wonder who'll be the first to crack and do actual performance testing of all these alternatives. I bet it's Vitek.

[Vsk]

Why not a loose axes aline octree?
The loose part can resolve most of intersection to crosses the boundary of a top level region.
If fact if one object is close to the "center" of your spacial organization and crosse due to its size the loose aproach will handle this in most cases.
I have perform test with 10.000 "objetct" (withoug graphyci part)in random positions with random bounding boxex and test it for example for collissions and it reduces for less than 10% (consider that I had a 10.000 unitis space size with bounding boxes about 50 unit average) so 10% is quite good for 10.000 objects. So if you have less object or bigger relative level you can have about 5% or less object for checking after the octree test!!!.

About the reorganization of the loose octree.... well that part I have had not test it and can no talk about it... but, again the loose aproach reduce this modification cause and object (even moving) will not go away of its region so quick. So again I think it will be good, besides it is easy to implement.
Another important thing, choosee a GOOD SPACIAL CENTER, so you don't degenerate the loose octree into a loose list, cause then your search test will pass from O(log2 n) to O(n2).
I create the loose octree from this reference book:

http://www.amazon.com/Real-Time-Renderi ... 1568811829

But this subject (loose occtree) is almos in anybook related.

I hope it helps.