RTS unit handling

KiroNeem
Unregistered

Post: #1
Recently I have been building a piece of code for a 3D real time strategy game. I have most of the fundamentals down, although one piece eludes me on the design aspect. I'm trying to figure out a fast way for one unit to see what unit's are around him. It must be fast because the AI will be running this task many times on many units. I sure don't want to be collision detecting all units on the map, so I'm stuck trying to find a way around that.

So far I came to the conclusion that I could have an grid of lists, so say if the map is
128x128 in size, I could split that up into a 6x6 grid of lists, each telling which units are inside of them. Then I could just check the units inside of that grid and neighbor grids. So far this as seemed like the best idea, although I'm not sure if there is any other way.

Any ideas?
Sage
Posts: 1,403
Joined: 2005.07
Post: #2
loop for each unit (i)
loop for each unit after i (j)
check if the square distance from unit i to unit j is less than some distance squared.

you dont need square roots that way, you can also optimise by only rechecking the distance for ones that have moved (against all the others).

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Sage
Posts: 1,199
Joined: 2004.10
Post: #3
Also, it depends on what you consider to be an "occluder". Is the ground an occluder, or is it mostly flat? Are large objects occluders? Small objects?

I'm working on an idea for pathfinding in my environment, which is a fairly large terrain with lots of trees, boulders, etc. My plan is to make a large grid, the "occupation grid" which would, for each cell, have:

1) The type of terrain in this spot. E.g., normal ground, water, etc.
2) The slope of the terrain in this spot.
3) The height of the terrain in the spot.
4) A list of Entities occupying the spot.

For pathfinding, an Entity would determine if it could cross the particular terrain, e.g., can I cross water? Can I traverse a slope of magnitude X? Is there something big occupying the spot ( each entity has an AABB so I can quickly determine size ).

The reason I bring it up, is with a grid like this, you could use a simple brezenham line interpolator to check each point in the grid between your character and a potential enemy and determine if it would be visible or not, and wether you could go that direction or not.

Now, how you minimize the number of enemies to check against: I'd recommend a quadtree approach. Very fast for determining subsets based on position. I've already got a fast quadtree implementation for my visibility determination, and it only took a few days to write ( admittedly, I've written them before ).

Another thing -- don't worry about performance. This kind of stuff can be *very* fast even without much optimization, so long as your algorithms are sane. In my experience drawing the scene is much more expensive than this kind of work.
Member
Posts: 41
Joined: 2006.01
Post: #4
KiroNeem Wrote:So far I came to the conclusion that I could have an grid of lists, so say if the map is
128x128 in size, I could split that up into a 6x6 grid of lists, each telling which units are inside of them. Then I could just check the units inside of that grid and neighbor grids. So far this as seemed like the best idea, although I'm not sure if there is any other way.

That's what I've done, my map area is broken up into 64x64 lists. Moving the objects means re-linking them, but the collision detection runs much faster.
Moderator
Posts: 869
Joined: 2003.01
Post: #5
Creating a grid is just primitive space partitioning
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
DoG Wrote:Creating a grid is just primitive space partitioning

Exactly, that's why I brought up quadtrees. They make it fast & easy to find a subset on a grid.
Sage
Posts: 1,487
Joined: 2002.09
Post: #7
Spatial hashing is a simple extension of the grid idea and is quite a bit easier than quadtrees.

I made a no frills implementation of that in a few hours. The benefit of this over a grid is that it isn't bounded, and you can adjust it's memory usage.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Luminary
Posts: 5,143
Joined: 2002.04
Post: #8
It also doesn't have the pathologically stupid cases that Quadtrees do...

Outnumbered started with a Quadtree, and had to move to spatial hashing for performance reasons. The code was slightly shorter and substantially less buggy, too
Sage
Posts: 1,199
Joined: 2004.10
Post: #9
I've encountered the pathologically stupid situations, I know what you're talking about.

But -- that said -- I came up with a pretty good way around it. Instead of saying that a node intersects, or doesn't intersect my frustum ( and it could work for any region, but in my situation I was dealing with view-frustum intersection ) I instead checked wether a node was completely inside, intersected, or was completely outside the frustum.

Then, if a node was completely inside, I could traverse down to all the leaves and add their contents, I could skip fursther checks altogether. If a node was completely outside, I'd stop recursing there. And if the node intersected, I would continue recursion to its four children.

This brought my worst cases ( where, for example, the camera could see the entire world ) from *thousands* of AABB/frustum intersection checks to 1. My average case was about 80 to 100.

Just sayin -- quadtrees aren't the cats pajamas, but they're not bad either.

( P.S. I might not be talking about the same pathologically stupid case of course )
Luminary
Posts: 5,143
Joined: 2002.04
Post: #10
the pathologically stupid cases I'm thinking of are the ones where an object sits exactly in the center of the map, for example... then it's in the root of the tree, and therefore getting checked against everything else in the world all the time.
Moderator
Posts: 869
Joined: 2003.01
Post: #11
I once implemented a nifty octree to get around such stupid situations. Its boxes had different bounds for objects to be checked against it, and objects to be added. Basically, each object that was touching the original box was added, and the box's 'checking' dimensions were expanded, or shrunk, depending on the objects it contained. This way, objects were partitioned, but there were no degenerate cases where an object would sit very high in the hierarchy and each box had quite efficient bounds. The drawback was the extra logic necessary, but it worked quite allright.
Sage
Posts: 1,199
Joined: 2004.10
Post: #12
Yeah, I'm a little confused by OSC's degenerate case as well. I've seen ( and solved ) some pathologically bad situations, but I've not seen *that* (this is me, keeping my fingers crossed ).

My Quadtree also gracefully handles expansion/shrinking as objects move or are reparented to the leaf nodes. Over the last couple days I've been profling and optimizing it, such that I've actually brought up my average FPS by 10. Awesome.
KiroNeem
Unregistered

Post: #13
This thread has gotten very interesting. I have yet to implement any quadtrees myself, even though I find them fascinating. Realistically what does anyone find most cumbersome or excellent about it over other methods?
Moderator
Posts: 869
Joined: 2003.01
Post: #14
Quadtrees or Octrees reduce the complexity of your collision detection from O(n^2) to O(n log n) usually.

That hashing algorithm claims O(n), which would be fantastic, but I can't quite believe it. Has anybody got a simple explanation of that claim? As far as I read so far, I didn't really get it.
Sage
Posts: 1,199
Joined: 2004.10
Post: #15
It also depends on your circumstances. ODE offers both quadtrees and hashing to speed up collision detection, and it's the users choice which to take advantage of. In my experience ( using Shark to see how much time is spent in ODE's dCollide routines ), large terrain situations ( e.g, 2.5D ) fare much better with ODE's quadtree. On the other hand, true 3D fares better with the hash.

Of course, you could use an Octree in that situation. What I was talking about above is my own Quadtree implementation which I use for visibility determination ( which is still collision detection, since I'm using a quadtree to collide a frustum with the world's contents ).

Anyway, we've derailed quite a bit...