Implementing collision detection in RTS

#1 That is about the best way of doing it. I haven't got around to it yet, but thats the way I'm going to do it.

#2 Hi all,

first let me say that i'm just trying to pickup the basics of the engine. and it's pretty much code, so please have a bit of patience with me :)

i just had time to play a bit with the editors and to take a quick look at the code. cd is one of the things i've already on my list, so i thought i stop by and ask a few questions if you don't mind :)

well, it sounds a bit expensive to loop through all buildings/units to do (even basic) cd. so i was wondering if there's no space partitioning of some kind that could be used to reduce the number of objects? my first guess was the scenegraph, but it seems like the 'outside world' is just one zone, so i guess it can't be used.

did i miss something?

#3 The main reason collision was stripped out of the RTS SK actually has nothing to do with collision (and to ansher Phillipp's question, TAP has a very nice system for segmenting collision checks), but with pathfinding.

Since you don't directly control units in the RTS-SK, but simply give them movement orders, you need collision avoidance and reconciliation functionality that handles 3-D world space--and that isn't trivial.

Re-integrating collision, and including a game agnostic pathfinding capability is on the plan for the RTS-SK, but there is no deadline at this time (and it's going to be months, not weeks).

#4 Justin, good thoughts. No, there isn't a default collision scheme in the RTS SK. For more info on the subject, please see my posts these threads:
www.garagegames.com/mg/forums/result.thread.php?qt=23286
www.garagegames.com/mg/forums/result.thread.php?qt=24900

I'd love to see a community resource on RTS SK collision, so if you are up to working on this project, that'd be great. Personally, I'd implement a system similar to what you're talking about. AABB or pure radius-based collision is what most RTS games use, and the processing is pretty simple. There are lots and lots of good articles online regarding implementing super-fast simple collision checks like these.

To give you and idea of the complexity involved, if you are an experienced C++ coder, are already familiar w/ collision detection coding, and know Torque's C++ structure a little, this wouldn't even take a week to fully code, test, and package up for release. If you aren't as experienced in these areas, it'd take longer, but it'd be a fantastic learning experience.

#5 Josh, thanks very much for the links. I ended up coding a *very* basic collision-detection scheme that gets invoked for each unit during ProcessTick. It basically highjacks the server-side object list from the VisManager, loops through all the units and does a quick radius-based test. It seems to be working too. :-)

VectorF foo;
SimSet& objectList = gServerVisManager->getObjectList();

for (U32 i = 0; i < objectList.size(); i++)
{
	RTSUnit* unit = (RTSUnit*)objectList[i];
	if(unit == this) continue;
	
	Point3F dist = this->getPosition() - unit->getPosition();
	if(dist.lenSquared() < 4.0f)
	{
		queueCollision(unit, foo);
	}
}

At the moment it's hard-coded to assume a 2 meter radius (I'll be expanding this at some point to use a datablock-stored value of course), and the vector passed to queueCollision is just a dummy vector because I don't have a use for it at the moment.

Obviously this approach has some efficiency "issues". For one thing it checks unit A against unit B, and then at some point unit B will be tested against unit A, which is redundant. But that's somewhat unavoidable if I use this approach instead of writing a function that tests all the collisions for all units in one shot. (But I'm not even sure if it's "bad" to be redundant in this case anyway.)

The above should work ok for "infantry" type units, but in the long run I'm sure I'll have to implement an AABB or OBB scheme to handle vehicles like buses that aren't as "symmetrical" (i.e. longer than they are wide).

#6 That's a nice start.

and illustrates why i asked for space partioning. instead of testing the whole object list you'd only have to check against objects nearby.

stephen mentioned a system for cd segmentation. details appreciated.

#7 Deep in the stock 1.3 collision code is the concept of bins, IIRC used for large scale collision culling. I'm not (currently!) an expert by any means on any form of collision, but the code is there if you can stomach searching for it!

#8 Space partitioning is fine yeah. Torque has an example space partition implementation, as does T2D. There's lots of examples available online too.

Justin, that's the start. You probably don't want to do that loop for each unit's processtick though, as that gets repetitive. Rather, if you did that once globally per tick (once on server and once on client), that'd work fine too.

Essentially, the visibility list is the same algorithm as this. Checking visibility vs checking collisions, in this simplistic scheme, is just a matter of changing the value used. So, you could just loop through objects once, and store visibilities and collisions in one-pass. Or, you could store and sort a distance table for all visible units, and then just pull entries from that for various collisions.

Lots of ways to go about it. And, again, a broad-phase space-partition checking pass might make sense. But I'd just get it going w/ a real basic implementation like you have here at first, yeah.

Btw, unless I'm cracking out right now (which is possible since it's late and I've been here for 17 hours :), the visibility manager in the current public RTS SK release has lots of problems. It was not implemented to anywhere near the spec I defined for it, and we didn't have time to bring it up to snuff before release. Thanks to Stephen Zepp and his team, and some additional work by Wes Beary, we have an updated version of the RTS SK visibility manager in our internal repository here. This will be making it out to you guys in the form of a resource, if not a full-on RTS SK update... sometime. :) (wish I could say more exactly when, but I'm not sure at this point).

Anyway, point being: the current vismanager has lots of problems, so you'll want to be careful about relying on it too much. If it's working for your purposes here though, great.

Guh... rambling post, sorry. Like I say, been here a long time, I'm very tired. :) Good work so far, glad you got some collision going. You're on a good starting track... and hey, if you get it going well enough for use in your project, then great.

Please keep the community up to date on your progress, sharing good stuff like this is always very much appreciated!

#9 Thanks, Josh. And I agree with everything you said. I'm somewhat familiar with the issues with the VisManager (and very much looking forward to an updated version!) but IIRC those issues have more to do with the logic being applied than the actual object list, which is all I'm using. I actually did consider doing my collision checks in the VisManager code, but decided against it for just that reason; I figured the VisManager would get updated eventually and then I'd reconsider adding my CD stuff to it.

#10 Interestingly, the revised visManager my team put together has two primary issues:

1) VC 7 doesn't like the way we used multi-dimensional arrays. We had it working very well (functionality wise) for months, but when we tried to compile out on VC 7, we got some serious re-write requirements out of it. We do have a re-write hack for this, but it thrashes memory pretty badly, and I'm not happy with it.

2) It uses a pretty performance poor (in the big picture--we actually never saw any serious performance problems, but the design shows that they can be there with 1,000's of units) algorithm.

We're actually working on a design for a bin based system that theoretically will be single pass, and an extreme performance increase, but it's in the very rough early design stages, and the guy that came up with the algorithm is our primary persistence guy, so he's going to be busy for a while!

#11 Per Josh
"Justin, that's the start. You probably don't want to do that loop for each unit's processtick though, as that gets repetitive. Rather, if you did that once globally per tick (once on server and once on client), that'd work fine too."

Can some one please tell me in which files these global ticks on server and client are located.

I thought that if you check only units that are in motion during unit's processtick for unit's prospective new location at end of tick against existing unit positions this would allow for motion to be stopped BEFORE it enters collision space of another unit.

#12 Hi Swaroop,

The global tick code is in engine/game/gameProcess.cc - ProcessList::advanceObjects() gets called once for each global tick. It gets called by both client & server, and there's a member variable mIsServer which I assume tells you whether which one you're on.

But I think that even if you test only moving units, it's still going to be too slow, unless you really don't have that many moving. I'd recommend that each game tile keep a list of the units that are in it. Then when you want to test for collisions, you only need to test against the other units in your same tile, plus the units in the 8 surrounding tiles.

I'm not familiar with Torque's binning code, but I imagine it does roughly that.

#13 Instead of doing a comparison of the distances between each unit, would a containerRadiusSearch for each unit be quicker? I think that kind of search uses the bins for more efficient culling.

I implemented flocking and basic repulsion-based obstacle avoidance for my units that way, and I've had over 100 of them in game with acceptable performance. You don't need to do the check every tick either - 30 times per second is overkill, 5 or 10 times per second should be more than adequate depending on the movement speed of your units.

#14 Thanks for your input Geom and Guy.

I have already created a grid so that I will be checking only the surrounding tiles.

Guy
Where are you doing containerRadiusSearch. Are you "scheduling" every x ms in script or are you doing it in the process tick for the unit? How are you repelling the units back when they cross into their collision radii.

#15 Has anyone gotten a container search to work? I found some nice containers in sceneObject.h and tried to use one in the "PROFILE_START(RTSUnit_UpdatePos)", but it seems ti be ignoring the bitmasks:

Container radiusSearch;
U32 mask = InteriorObjectType | PlayerObjectType | VehicleObjectType | StaticShapeObjectType | WaterObjectType | TriggerObjectType;
radiusSearch.initRadiusSearch(mLastPos, 3, mask);
int foundID = radiusSearch.containerSearchNext();

The above code seems to always evaluate foundID to 0, and I can't seem to figure out why.


BTW, I did try the collision detection found in this thread: http://www.garagegames.com/mg/forums/result.thread.php?qt=34401 and it worked once you add in a Z-axis relocator to "Player::updatePos()"

#16 Collision avoidance using something like a radius search is definately the way to go, rather than collision detection which doesn't really have a place in your typical RTS. You want your units to be looking for potential collisions and adjusting their movement to avoid them, rather than allowing your units to move anywhere then reacting to collisions once they've happened. Very few RTS genre games use collision detection, most use some kind of prediction/avoidance scheme.

Looking at your code, I don't think you're setting up the radius search correctly. A few pointers -

Only perform the radius search on the server. So wherever you're doing the search you need to check that the unit is on the server:

if (isServerObject())
{
     search............
}

then for the search, you need to actually specify that you want to search the servers container, so your code might read:

Container radiusSearch = gServerContainer;
U32 mask = ................
radiusSearch.initRadiusSearch(.........................
while(U32 foundID = radiusSearch.containerSearchNext()) // note- use torques dataTypes eg U32 not int/float
{
     do something...
}

For simple obstacle avoidance, I was using a similar scheme called from within processTick before the units position is calculated, and using the results of the search to compute a vector that was added to the units desired movement vector, and this caused the unit to steer around an obstacle.

Hope this helps