BSPs for RTS Units.
Author
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]
Author
Basically I need a tree that balances mild imbalances quickly and gives good results for a nearest neighbor type search.
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.
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.
Author
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".
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.
Author
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.
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.
Author
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.
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.
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.
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.
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
