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?
\$\begingroup\$
\$\endgroup\$
2
-
1\$\begingroup\$ Worth checking out, in case you haven't yet. redblobgames.com/pathfinding/tower-defense \$\endgroup\$– Lince AssassinoMar 20, 2016 at 20:53
-
3\$\begingroup\$ It's about reuse. If you pathfind from the goal to the monster, you can also record paths from the goal to other monster locations. That way, when you need paths for those other monsters, you don't have to run pathfinding again. If you did it the other way around, you'd be able to reuse the monster's path to other goals. But you don't have lots of goals. You have lots of monsters. See the link Lince posted for a demo (disclaimer: I wrote that page). \$\endgroup\$– amitpMar 21, 2016 at 5:15
Add a comment
|
2 Answers
\$\begingroup\$
\$\endgroup\$
2
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.
-
\$\begingroup\$ Would this mean that in a open grid tower defence game, where the path is defined by the player, the difference between the 2 methods doesn't matter? Also, would it be better if you were to run both direction's pathfinding simultaneously and stops when either finds a solution? \$\endgroup\$ Mar 20, 2016 at 13:04
-
2\$\begingroup\$ @DarkDestry When the map layout is completely beyond your control, then you are indeed wasting your energy by thinking about this. You could look if your game mechanics encourage your playtesters to build certain geometries, but you won't have any reliable data about that until your game is very close to finished. If you decide to start searching from both directions simultaneously, A* can be adapted for this. \$\endgroup\$– PhilippMar 20, 2016 at 13:14
\$\begingroup\$
\$\endgroup\$
5
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.
-
1\$\begingroup\$ In retrospect, I think if I was designing the system I would make key to door a unidirectional off-mesh link as you have to gind the key first. If the key was found before the door, then we know that a door exists and the cost of the link is the cost of the shortest path from key to door. If the door is found first, no backtracking would be needed as a link exist. \$\endgroup\$ Apr 21, 2017 at 13:53
-
\$\begingroup\$ If the door is found first, the creature still might need to find the creature-key path (even though the key-door path is known), since it's better to take a short detour to collect the key before going to the door than to go to the door, leave for the key, and return to the door again. But I admit that's a good solution for the example if one prefers forwards. \$\endgroup\$ Apr 21, 2017 at 14:07
-
\$\begingroup\$ Although the off-mesh link between the door and the key would be very helpful for the backwards A*, too, and can be used to guarantee again that each node is only visited once by the algorithm \$\endgroup\$ Apr 21, 2017 at 14:29
-
1\$\begingroup\$ Ah I haven't considered that the path to the key might not be considered due to heuristics \$\endgroup\$ Apr 21, 2017 at 14:29
-
1\$\begingroup\$ You can avoid the complications of re-visiting nodes by instead thinking of two parallel universes: one in which you've used a key you might not have and one in which you haven't. Pathing from the goal through the locked door puts you in the "key debt" parallel universe, which has its own nodes. Pathing from here to the key gives a link back into the "no key debt" layer of reality, whereupon you can continue pathing back to the character position (if a key-free path doesn't beat you to it). Similar to this pathing question about using bombs. \$\endgroup\$– DMGregory ♦Apr 21, 2017 at 17:11