# 3D RTS pathfinding

4 replies to this topic

### #1Xcrypt

New Member

• Members
• 144 posts
• LocationBelgium

Posted 15 April 2012 - 03:05 PM

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?

### #2geon

Senior Member

• Members
• 939 posts

Posted 15 April 2012 - 05:28 PM

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.

### #3Xcrypt

New Member

• Members
• 144 posts
• LocationBelgium

Posted 15 April 2012 - 05:41 PM

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.

### #4fireside

Senior Member

• Members
• 1587 posts

Posted 16 April 2012 - 12:20 AM

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.
Currently using Blender and Unity.

### #5TheNut

Senior Member

• Moderators
• 1699 posts
• LocationThornhill, ON

Posted 16 April 2012 - 02:25 AM