3D RTS pathfinding

Xcrypt 101 Apr 15, 2012 at 15:05

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?

4 Replies

Please log in or register to post a reply.

geon 101 Apr 15, 2012 at 17:28

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 geometry.

Xcrypt 101 Apr 15, 2012 at 17:41

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 on waypoints.

fireside 141 Apr 16, 2012 at 00:20

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 do.

TheNut 179 Apr 16, 2012 at 02:25

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 videos on 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.