# How to pathfind over an obstacle?

How to represent the following situation best - agent (@) needs to get to the goal($). The path is blocked by a moat(~~~). A rake (or some other device, like waterwalking boots) is available that will make it possible to cross the obstacle. .....~~~... . ground ...=.~~~... = rake .....~~~.$.   ~ water
.@...~~~...   @ agent
.....~~~...   $goal  How to properly pathfind from @ to $ provided there is no immediately available path? Should my path have not only cost but also prerequisites?

UPD: The problem is the goal is not accessible and rake is just one of many possible objects on the map. Question then is "how to make the agent understand that it needs the rake?"

• I think you should clarify your use case because that would affect the approach one takes to solving this problem. For example, if the use case is to calculate paths for enemies then you should probably first see if the goal can be reached currently, if not have the enemies get the rake (ie. the rake IS the goal) and then pathfind to the first goal again. – jhocking May 16 '12 at 13:39

I'm thinking about a stack of goals, pathfinding will have to be annotated:

• Start with a goal get $ • Try find path to $ - path exists with waterwalking capability required.
• Push goal get waterwalking.
• Goal stack is now get waterwalking, get $ • Somehow find that rake gives waterwalking, let's rename it to boat. • Path to rake. Top goal reached, pop it from stack, goal is get$.
• Path to $ - now we have capability and can reach goal. • +1 I did something similar with my game, and wrote a little post about it a while back under Unit Tasks and pathfinding. – MichaelHouse May 16 '12 at 13:24 • @byte66 doesn't handle special case when there is a path without using rake but, using the rake results in shorter path – Ali1S232 May 16 '12 at 13:35 • @Gajet you're right. Guess will need a different approach for that. – zzandy May 16 '12 at 13:56 • It's just a matter of adding additional cost. When you encounter water, add the cost of getting the water-walking item to the path. A* will skip the water-walking until it becomes the cheapest path. – MichaelHouse May 16 '12 at 16:45 The whole path finding stuff is just a search for shortest path over a graph. to solve your problem the only change you need to apply is to add some extra edges (representing the path boat can take), and do a simple path find algorithm. it doesn't matter whether you use BFS, Dijkstra or A*, just implement a normal path finding algorithm with some extra edges. for more information about path finding in a graph check wiki page • +1 Make your rake a one-way link to the water, with water-to-ground beeing one-way links as well. – Laurent Couvidou May 16 '12 at 12:43 • I don't have clear understanding how to bind together geometrical search and feature search. How to go from no path from @ to$ to goto rake, bring it to water, place it, goto \$. – zzandy May 16 '12 at 13:03
• @zzandy while path finding, for each tile you go to nearest tiles if possible. you just need to add a condition that if the current node is a rake, you can directly add a node from other side of the river to open list. – Ali1S232 May 16 '12 at 13:06
• But what if you can carry the device? I thought that's what he meant (and hence my answer.) – kaoD May 16 '12 at 13:06
• Yes, I mean the device can (and must) be caried. @kaoD, your answer does not include the step when an agent gets the idea it needs the rake. – zzandy May 16 '12 at 13:14

I'd do this with some kind of behavior tree solution - you path to the goal, and take note of all the obstacles that has been blocking your A*. If you fail, you check if there are objects that can help overcome those obstacles, in that case, path to that object. Repeat. This means that the agent needs to try to path to the goal and fail before getting the idea of using tools though, which might take time, especially if there's a huge world of tiles that all need to be checked. Might not look too out of place that the agent takes some time to contemplate on how to solve the problem though.

I can imagine a real, hardcore solution however. Add another dimension to you path finding grid. So in the case of a 2D map, you make the pathfinding grid 3D. In this simple example this new dimension would only have a depth of two, but in a real game it would get large quickly.

At z=0 you map the terrain during normal circumstances, meaning that water tiles are considered impassable.

At z=1 you map the terrain as it is while having the rake, meaning that water tiles are considered walkable (but if you have for example wall tiles, those might remain solid).

The path finding is an ordinary A* in the x and y dimensions, meaning that every grid cell is considered to have access to its neighbors. In the z dimension however, the A* is NOT allowed to spread.

Except where the rake is. The rake object acts as an opening between z=0 and z=1 in the path finding grid.

This means that the A* will flood fill outward in z=0, hit the water, and run out of options - then it'll spread to z=1 through the rake tile, and at z=1 (where water is walkable) find its way to the goal. The effect is that the NPC whithout hesitation moves to the rake, and then moves the shortest path to the goal.

• I've been treating the rake more like "water walking boots" in my example, meaning an object that if you have it makes you able to travel over water tiles. If the rake needs to be actually "built" as a piece of terrain, and covers a limited amount of tiles that might or might not be enough to reach across the water, the problem is more difficult. My solution does allow for one-use items though, if you make movement in z=1 automatically drop down to z=0 again. – Joar Jakobsson Sep 10 '14 at 2:25