|Reported by:||KZK||Owned by:|
Angband and Zangband have very poorly written pathfinding. This ticket is to address these severe shortcomings. Watching in angband as creatures attempt fleeing from my character by running straight into a wall as if they can get away by not moving is absurd, especially in some cases where a door or passageway is two spaces away! Seeing creatures trying to come straight through a wall or obstacle to get to my character, and not being able to even when their is opening door or passageway a catcorner away, is even more absurd (especially in Zangband). In general the current method of pathfinding in Angband is very simple: Monsters basically try and move in a straight line towards the player when seeking him out and move in a straight line away from the player when fleeing/afraid (it's actually a little better than that but not by much). In order to rectify this I suggest a Four prong approach:
- Dijkstra's Algorithm. In a perfect world where efficiency concerns are absent, all pathfinding in all instances by almost all creatures would use Algorithm # 1, Dijkstra's Algorithm (make this an option in the option menu, namely that most creatures are forced to use algorithms # 1 or # 2, bad for efficiency good for monster intelligence).
Please Read and understand the theory behind Dijkstra's algorithm Here:
In addition to the above suggested forced option, All high level creatures above a certain point should use Dijkstra's algorithm in all cases (Ancient dragons, High level demons, uniques, smart creatures, Morgoth, etc.).
(As an aside: a simplified version of Dijkstra's algorithm can determine if all areas in a dungeon are reachable or if their are unreachable areas (unless there are destroyed areas where single isolated floor spaces exist)).
- The A* Algorithm. (Use the Above Links to also understand the A* Algorithm). The A* Algorithm is good enough for most creatures, but has some flaws. Mid level creatures should use the A* algorithm or above.
- KZK's Edgesearch algorithm: I have written this algorithm to be used when efficiency is more important, otherwise the other algorithms are way better.
I will ignore the effect of obstacles (other creatures, which most creature should be able to 'push past' like in Zangband. They are important in determining if the player can reach the monster that is fleeing, and how risky any movement option is).
We will assume that a monster is fleeing from the player, and are in a moderate size room: First order of business is to find all viable exits, so search for edges by checking each floor moving in a direction straight away from the creature and the player (Straight away from the player towards the monster, because finding exits on the arc that is away from the player is more useful than finding exits that are on the other side of the player, unless the creature is enough faster than the character that he can pass him viably without being hit), until you reach a wall/edge. When you find the edge you will then search along it (an edge is where an empty floor space/door intersects a wall) in 5 floor space increments alternating between both directions along the wall until you find a change of direction in the wall. This change of direction will either be a corner, an opening to a passageway/door or a protrusion. You should find all openings along that wall, if any. Secondary are locating exits that are along adjoining walls (on this side of the player, it's important to be able to calculate the monsters ability to get to the exit ahead of the player.
This diagram needs to use fixed width font:
See Text file for fixed width diagram beacause Trac doesn't like Fixed width text diagrams with returns.
Summary so far: Search and find the point (*) along the wall, then find the exits to the NW and the corner then find the exit SE and other possible exits (within reason). Determine that The exit SE is risky, and then determine that the exit to the NW is better.
Now that you've found the exit, you must test it for viability. It is easy to follow a passageway for some distance and to determine if it's worth going there or is a dead end.
In the case where only the risky SE passageway exists, you will need to determine if it is worth it to attempt to flee that way, or to do something else. Obviously you will need to extend the search to the area's on the other side of the character and try and see if their is a viable way to get to one of those exits (obstacles/other creatures).
In the case of the only exit being on the other side of the player again have to determine if it best to try and pass the player, to move straight towards a wall (in the direction away from the player and closest to the exit), or do something else.
The Algorithm as described so far should work pretty well in passageways.
Now the reverse: Getting to the player. This will use a different approach. Basically determine the position of the monster and the player, counting every 'step' taken search in a straight line from the monster (to the player) until you reach a wall. Counting every 'step' taken search in a straight line from the player (to the monster) until you reach a wall. Follow the edge from the monster in one direction until you reach a change in direction. Follow the edge from the player in one direction until you reach a change in direction. Do the same for the alternate direction of the wall edge from the monster (keeping a third different count of steps). Do the same for the alternate direction of the wall edge from the player (keeping a fourth different count of steps).
- Continue until one of the paths from the monster meets one of the paths from the player, add the two step counts together, if it less then adding the current steps from adding the second monster path to either of the player paths, then you have found the path that monster will take. If it is greater than either of the other two incomplete paths, continue searching the other incomplete paths until either they have taken more steps than the already complete path, or one of them connects with fewer steps (take that path instead).
- Continue until both paths from the monster return to the point where it first intersects the wall (you are unable to find a path, probably because it would require hidden doors).
- Continue until both potential paths reach a maximum number of steps. (Avoid infinite loops).
- The Existing algorithm. Fine for stupid creatures. Also fine for extremely short term effects (fear that lasts 5 or fewer turns), not long term effects. I would add a randomness to it so that creatures can sometimes accidentally find doors and escape sometimes.