• Advertisement
Sign in to follow this  

BSPs for RTS Units.

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a program I'm working on. For the regards of this problem, let's pretend its a RTS. Each unit is on a 2D plane. Each unit has a maximum viewable distance. Anything past it is invisible. It also has a view angle, such that it can only see to either side of where it's looking 45 degrees. I want a BSP to help me search to find what unit can see what other unit. I'm thinking in terms of 1000 units in the general case. For my proof-of-concept, I just did the naive O(n^2) method where I check every unit against every other unit. It worked, and now I'm ready for optimization. I'm thinking of implementing either a kd-tree or a quad tree, but I need to know what the best way to solve the problem is. Since the units can move around, the O(nlogn) construction time for a kd-tree makes me think perhaps the quad tree is better. But the quad tree has some issues too... (units are going to generally be clumped, not distributed evenly). What's the best BSP to use, and I guess why? I know there are other BSPs besides just kd-trees and quad trees, but I don't know anything about them. Would one of them be better? How hard would it be to extend this to the 3D case? [Edited by - Numsgil on October 9, 2005 8:44:38 PM]

Share this post


Link to post
Share on other sites
Advertisement
Basically I need a tree that balances mild imbalances quickly and gives good results for a nearest neighbor type search.

Share this post


Link to post
Share on other sites
You could look into vantage point trees (vp-trees) and multiple vantage point trees.

You could also rely on a simple grid structure to detect close objects, and maybe
use a run length encoding system on that grid to skip areas in which there are no units. If done correctly, it would result in an O(1) amortized overhead when moving an unit on the grid and an O(k+t) worst-case search time in a square area of radius r containing k units.

Share this post


Link to post
Share on other sites
I can't seem to find anything on VP trees through google or through wikipedia. Mentions of vp trees, just no "this is what a VP tree is".

Share this post


Link to post
Share on other sites
For a simple solution, you could just devide the terrain up into, say, 512x512 pixel squares and just store for each square pointers to the units that are in that square. That would be very easy and you should be able to avoid checking most of the units because they wont be in the nearby squares. You could use that for rendering too, so you don't need to render things in the offscreen squares.

Share this post


Link to post
Share on other sites
Yes, that is a solution I considered. I'm just not sure it'd be optimum.

The problem smacks of some brilliant tree or skip list solution, or something along those lines.

If no one else has ever really looked into what the optimal solution is, maybe I should write up some sort of demo that tests different kinds.

Share this post


Link to post
Share on other sites
Due to not being able to find any resources on this matter, I've come to the conlcusion that none exist!

So I'm going to make a little demo program to test different techniques to see which is better for this particular use. Since from cycle to cycle the relative order of units change very little, it may not necessarily be kd tree (which, if I understand correctly, would need to be rebuilt every cycle).

So, what sort of techniques do I need to test? Here's my partial list:

kd tree
quad tree
Buckets (that is, sort of what me22 suggested.)
simple linked list (sorted along, say, the x axis)
naive approach (the brute force test everything against everything method)

Any other ideas for good algorithms to use? From what I can tell vp trees are more for non-general metric spaces. For 2 and 3D cases they perform on par with kd trees and have similar restrictions.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Sounds a lot like collision detection...so here's another idea based on a collision detection algorithm

The collision detection algorithm goes something like this: for each axis you maintain a linked list. For each object there are two nodes on each list, to mark the boundaries of its axis aligned bounding box on that axis. The lists are sorted (bubblesort works well here unless the objects are moving quickly). Then the lists are traversed, and overlaps between objects in each axis are stored in some structure (which can be preallocated if the maximum number of objects is known beforehand, otherwise or to save space hash tables can be used, I guess). Actually I think the bubblesorting and traversal can be combined into one step, whenever nodes are swapped an overlap is marked or unmarked. If two objects overlap in all dimensions, then they are added to a list of colliding objects.

For this problem, well you can really use this algorithm unaltered, or you can try modifying it to suit the problem. I think adding a third node to each list to represent the position of each unit, and modifying the bounding box to bound the visible area. Then look for positions that are inside bounding boxes.

Share this post


Link to post
Share on other sites
I actually thought of something very similar to that. Linked lists have the advantage that rebalancing/reordering them is really easy...

This will be interesting to see what algorithm is best for what need. I can see alot of potential complexity from all sorts of angles.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement