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
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.
No comments:
Post a Comment