Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I understand the A* algorithm, but I have some trouble doing it in 3D to suit the needs of my RTS

Basically, in the game I'm making, there will be agents with different sizes of OBB collision boxes.

I can use steering behaviours for avoiding other agents, so I don't need complete dynamic pathfinding. However, there is a problem because different agents have different collision geometry, and structures can be placed in almost any place. This means that there might be a gap between two structures where some agents can go through and some can't.

A solution I have found to this problem is to do a sweep of the collision geometry of the agent from start node of the edge the pf algorithm is currently testing, to the end node of that edge. But this is probably a bit overkill since every edge the algorithm tests would also have to create and test with a collision geometry sweep.

What are some reasonable approaches to this problem? I should mention that I'd prefer not to use navmeshes, I prefer waypoints because my entire system is based on it atm.

share|improve this question
up vote 2 down vote accepted

Since you're talking about combining waypoint path-finding and steering behaviours I strongly suggest you take a look at the Corridor Map Method (CMM), if you aren't already.

It creates a waypoint graph that includes clearance information which is helpful for constraining the steering behaviours.

A derivative method that just popped in my head, which might be less of a hassle to implement than the CMM (no expensive off-line processing phase), is to use your current waypoint graph and add chokepoint waypoints with clearance data where necessary.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.