Hi, 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?
Please log in or register to post a reply.
You could edit a (directed, weighted) navigation graph manually. The A*
algorithm isn’t really the best for this, though. Look up Dijkstra’s
algorithm. There are several free implementations you could use.
Otherwise you might want tot try implementing some sort of navigation
mesh. It describes the area where your entities can walk, so you could
cut holes in it where static obstacles are placed, and make sure no
navigation mesh border is smaller than the width of your collision
Well sure I can remove nodes/edges from my navgraph but that doesn’t
help anything with the problem I’m having that different agents have
different collision geometry. Why would A* not be able to do this?
Dijkstra is basically A* without the heuristic cost.
A navmesh might be a more elegant solution (although I struggle to see
how this would fix my problem with the different collision geometry) but
I’d prefer not to use it, because my entire system is currently relying
I think I would keep the collision size with the character and just
request it, or have a table of each unit’s collision size. That is, if
you were using a spherical collision at the base, which is all I would
As geon mentioned, I would fallback to Dijkstra’s algorithm. As you
know, it’s simply A* without the heuristic, but this is a good thing.
You want to wrap around the area and find multiple paths, not just one.
Then divide and conquer your units. Continue to divide your armies
intelligently and create groups that can fit. You can continue to divide
it down so 1 group = 1 unit, but that might not be efficient. You may
want 2x2 groups or even 5x2 groups (paired lines). Some may travel down
the narrow corridor, others might walk around the obstacle, if possible.
You will know how many units you can fit in a single line by calculating
the areas Dijkstra finds. You will want to implement a priority queue
where each group navigates through the corridor in turn. Have your units
reunite in formation once they overcome the blockade before you continue
to move them as a group. Also, don’t use OBB for a single unit. That’s
way too expensive. A unit in an RTS has a dedicated spot on the ground.
All you need is a simple circle check. To speed things up, discard the
square root operation and instead square your distance. c\^2= a\^2 +
b\^2 instead of c = sqrt(a\^2 + b\^2). Just with mesh collision
detection, you don’t want to check each polygon. Your entire group will
form a single box test. As you divide your armies up, you also divide
the box, keeping the collision tests to a minimum. In real life, armies
don’t push or force their way through the line, so you would naturally
implement the same behaviour. Keep them in formation. Rotate the
formation, then move them. You can “salt and pepper” the formation a bit
so it doesn’t look too artificial. Take a look at some of the YouTube
the Total War series. They’re well known to provide epic scale battles,
and often times they ignore collisions. For example, calvary running
though infantry. It’s done intelligently though. The infantry will
spread themselves out a tiny bit, giving leeway for the calvary. An
astute gamer will still notice runovers, but it’s not something you’re
actively looking for and the spacing is generally good enough to cover
up some flaws.