How can I find the nearest walkable node to a position in astar pathfinding?

Unity Engine
,
1

I have units flying and fighting each other in 3d space. The units are using astar pathfinding to find each other. The units use rigidbodies and they follow the paths made quite loosely and so, due to this, they can end up in parts of the grid that are marked unwalkable. If either the start node or target node is an unwalkable node and it asks for a path, no path gets made by my algorithm. However, a path from the nearest available walkable start node to nearest available end node would still be very useful.

What are ways I can find the nearest walkable node to a given position in an astar grid?

2

Do a BFS/FloodFill/Djikstra traversal from the current node until you find a node that is marked “walkable”. That is your closest walkable node.

Obviously the consideration of what is “walkable” needs to be different for this particular execution of the algorithm.

1 Like
3

If your map doesn’t change at all, you could also just pre-calculate the nearest “walkable” node for each of the “unwalkable” nodes and store them.

1 Like
4

This worked. Appreciate it!