Opened 8 years ago

Last modified 6 years ago

#963 new change

Pathfinding

Reported by: KZK Owned by:
Milestone: v4 Keywords: ai
Cc:

Description

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:

  1. 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:
http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html#S2

and Here:
http://theory.stanford.edu/~amitp/GameProgramming/

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)).

  1. 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.
  1. 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).

  1. 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).
  1. 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).
  1. Continue until both potential paths reach a maximum number of steps. (Avoid infinite loops).
  1. 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.

Attachments (4)

Diagram.txt (124 bytes) - added by KZK 8 years ago.
Diagram
Diagram2.txt (650 bytes) - added by KZK 8 years ago.
Diagram 2
Diagram3.txt (282 bytes) - added by KZK 8 years ago.
Diagram4.txt (238 bytes) - added by KZK 8 years ago.

Download all attachments as: .zip

Change History (16)

Changed 8 years ago by KZK

Diagram

Changed 8 years ago by KZK

Diagram 2

comment:1 Changed 8 years ago by KZK

Some quick clarifications on The KZK Edgesearch Algorithm. I didn't really deal with how to navigate to exits once found, particularly if other creatures are in the way. Needs to be a little bit better than just going in a straight line towards the exit. On keeping track of the Player (or other monster known to kill weaker creatures) the Monster running away should keep relative track of where the player is and where he is expected to go. I would do this by using a simple vector to indicate which direction the player has moved and by how much from it original position, and then it can be compared to see if the player is doing what is expected or not. Also every 10 or step moved by the Fleeing monster it would probably be best to recalculate paths.

As for the case where the monster is moving toward the player, again keep a vector of the player's position (and don't worry about recalculating the path path as long as the player is within say, a 7 floorspace radius of his original position). Probably need to recalculate the entire path every 15-20 steps taken. Also when walking the chosen path try to recognize when you are in rooms following an edge and cut across the room instead, see Diagram # 2. The path chosen is only loosely what the monster should follow particularly when the monster gets close to the player, it should try to move straight toward the player. Anyway, you get the idea.

comment:2 Changed 8 years ago by KZK

Creatures that are immateriel should flee towards the nearest wall that is away from the player. I saw an elder vampire flee away from my player straight down a hallway, allowing me keep blasting it with rods. (This happened because I got the vampire to chase me for one step down the hallway. How's that for exploiting known weaknesses in the game programming? Had I not taken that one step backward at that point the Vampire would likely have fled diagonally back into the wall when I smited it. Immateriel creatures don't need to pathfind to come at the player, but they do need to be better at hiding in walls when fleeing.

Another point, powerful creatures didn't get to be powerful or ancient by continuing to fight losing battles. Currently a powerful creature will flee when near death, but then return after a few turns and then is ussually killed. That is not how it should work. They should flee, and keep fleeing until their HP returns to 80+%. Also they should flee sooner, as smarter creatures would notice that they are losing a battle, I say at 25 to 30% of HP. The Smarter the creature, the higher % of HP when it should decide to flee.

I suggest adding these Flags to Monsters: _NoPath_, _WallFlee_, _KZKPath_, _AStarPath_, and _DijikstraPath_.

I suggest the best way to keep track of a current path is to store it as changes in direction (Vector Pairs), Namely a pair of integers, the first of which is direction, the second is steps taken, say 15-30 pairs max for regular creatures, 100 pairs max for powerful creatures, and unlimited pairs for a select few creatures (Morgoth, etc.). The nice thing about using this approach is when searching the paths it would be easy to detect Doubling back or 'triangles'/'squares' (See Diagram 2 for explanation) by comparing the vectors that are 2, 3, and 4 spots back in the list, thus making better paths.

comment:3 Changed 8 years ago by KZK

Something I think should be imported from Zangband is how some long distance attackers try to keep a fixed distance from the player. As the player moved toward them they moved away. Vanilla angband should probably also have more purely long distance magical attackers, arrow shooters, etc.

comment:4 Changed 8 years ago by zaimoni@…

Cf. Zaiband's flow.c and how it is used in pathfinding. The C memory management may not be acceptable in V (it's mocking up a C99 Variable Length Array).

comment:5 Changed 8 years ago by KZK

Now if Zaimoni can provide some statistics about his Dijkstra implementation, that would be helpful.

  1. Processing time for minimal search (2 Steps)
  1. Processing time for maximal search (opposite corners of a very complex full sized dungeons (scumm for that), averaged over 10-50 trials for different randomly generated dungeons.)
  1. Avg processing time for searches in 10 step radius (absolute value) increments, averaged over 10-50 trials, for generated dungeons.

Now, I really haven't delved into the Angband code much in the last 15 years, so I assume that a Dungeon is stored as an array of [MaxDungeonX][MaxDungeonY][Z], Where Z is Floor type, Flags (Lighting, occupied space, etc), Item, Item List Pointer, OccupiedBy?, Etc. as necessary. Now if you add an extra increment to the 'Z' Variables, you can do some interesting things that make searching/pathfinding faster/more efficient at Dungeon creation. You can set a flag as to if a current floor space is a room or passageway, and you can set a breadcrumbs flag where doors/exits are. That would certainly speed up finding better paths and cutting across rooms.

Using Telepathy to see the monsters you can get an absurd scenario like in Diagram 3, where the monster(s) cannot find a way to get to you.

Changed 8 years ago by KZK

Changed 8 years ago by KZK

comment:6 Changed 8 years ago by zaimoni@…

Sorry, the testing system I use is too fast to give useful timings. I am not taking perceptible lag from recalculating everything all of the time. I haven't checked all greater vaults.

The statistics I care about:

  • I use an incoming array of unsigned char as the working buffer. This sets a maximum radius from the "flow point" of 127 (UCHAR_MAX/2, probably worth a code cleanup at some point). The whole-dungeon request is not possible, although the maximum telepathy range of any monster in V/Zaiband (the tiger, range 40) is possible.
  • There is some inefficiency from the total isolation of the pathfinder from the map data structures.
  • The outward floodfill is worst-case linear in the number of accessible squares. It stops the instance the destination (whether a coordinate or a goal) is found. Possible sources of inefficiency are the incoming function that tests square accessibility, and for goal searches the function that checks whether the goal is satisfied.
  • The pruneback to identify the actual path(s) is inefficient. The entire pathfinding working space (which consumes (2*radius+1)² bytes) is scanned for each distance reset to 0. (First the inaccessible signal 255 i.e. UCHAR_MAX, then all wrong-destinations at the range of the destination, then working backwards), leading to an algorithm with Theta(maximum distance*(scan radius squared)).
  • Note that this generates paths even if the target is *not* found. In that case, the monster will randomly choose between all distinct moves that actually make progress towards some square at maximum range. (This improves door-handling monster behavior in pits and vaults.)

Of course, minor translation from C++ to C is required.

comment:7 Changed 8 years ago by magnate

  • Keywords ai added; Pathfinding removed

comment:8 Changed 8 years ago by magnate

See also http://angband.oook.cz/forum/showthread.php?t=2575 for a bug in pathfinding by monsters with PASS_WALL.

comment:9 Changed 8 years ago by KZK

I see that I forgot about Permanent walls/vaults in dungeons. Since this effects only creatures with PASS_WALL and my Proposed _WALLFLEE_ flag, 2 logic pathways can be created. First at dungeon creation check if any permanant walls exist within the dungeon, and set a Flag (_PERM_WALLS_IN_DUNGEON_) to true if their are, to false if their aren't. If their are no permanent walls in a dungeon, use the code pathway already described above. If their are permanent walls then the creature will have to pathfind it's way around them to get to the player, and when fleeing have to pathfind it's way around them to get to safe non-permanent rock. It also seems like it would be a good AI choice to have fleeing monsters with PASS_WALL, tend to want to flee to areas outside of permanent rock enclosures, which can become death traps for them (but that is true of all monsters in a permanent rock enclosure, as a player who controls the only exit (ignoring teleport etc.) can handily kill any creatures 1 at a time, with proper conditions), etc.

comment:10 Changed 7 years ago by magnate

  • Milestone changed from Triage to Future

comment:11 Changed 7 years ago by magnate

  • Type changed from task to change

comment:12 Changed 6 years ago by magnate

  • Milestone changed from Future to 4.0

Initial assignment to v4 per http://trac.rephial.org/roadmap

Note: See TracTickets for help on using tickets.