Forward A-star pathfinding vs Reverse A-star pathfinding

Question

Under what condition does doing Forward path finding or Reverse pathfinding get better result? Most tutorials for open grid tower defence games says to pathfind from the Goal to the monster. Why is it so?

Answer 1

There is no definitive answer, because depending on the scene either can be faster.

But A* relies on a heuristics function which usually states closer = better = evaluate first. Let's take this example from the Wikipedia article on A*:

In this particular case, the "closer = better" heuristic leads the algorithm right into a trap. A* keeps moving on the direct line from red to green and fails very late, short before reaching green. It then wastes time with exploring the interior of the wedge until it has iterated it completely. Only then will it try the path around it.

If you'd have started from green, A* would have explored towards red, quickly found the wall, explored around the wall, and then head straight towards the destination.

That means in this particular situation, starting from green would give you a much faster solution.

So what you need to consider is: Does my level design tend to have "traps" like this which always face into one particular direction? Then you should avoid starting the A* search from that direction.

Answer 2

It's worth noting that pathfinding backwards (from the goal to the creature) helps when some actions may need to be taken to get to the goal, or may optionally be taken for an even better path.

Examples of this include doors with locks or switches, or gaps that can be crossed with a ladder, or mobility power ups that can be found in the environment.

This may not apply to your specific case, but as a general answer to the question of whether to pathfind forwards or backwards, this is hopefully worth considering.

As a simple example, if you're pathfinding forwards and you come across a locked door, you don't yet know if it would've been worth it to detour to pick up the appropriate key before coming here (which would require pathfinding to start over), or if continuing to search would still yield a better result.

However, if we pathfind backwards from the goal and come across the locked door, we can treat it as unlocked and continue expanding through that node, but towards the key instead of the creature. If it's faster to find a long way around instead of going to the key and then the door, then good A* will find its way back to the creature before the locked-door-sub-path has found its way all the way back to the creature with the key it needs. But if the locked-door-sub-path gets to the creature first, the creature knows to first go get the key, and then go to the locked door before heading to the goal.

This requires some modification -- normally, A* needn't ever visit a node twice, as once a node is visited, its fastest sub-path has been found (whether forwards or backwards). But if the sub-path changes objective (collecting a key, for example), nodes may be visited by both the key-collecting sub-path and the path that goes around the door if collecting the key is too much of a detour to be optimal.