Anticipating wall-following pathfinder
The algorithm described below attempts to guide a monster, step by step, to a given goal. The map on which the movement takes place is a rectangular grid, with two types of cells: FLOOR (passable and transparent) and WALL (impassable and opaque). The monster can take discrete steps in eight directions. It is assumed that the monster has only a few integers of memory (state), and no knowledge of any part of the map outside its sight range, apart from the coordinates of the goal.
The problem of navigating around obstacles is a clasical one in robotics, although it is usually considered on a non-gridded plane. The simplest solutions are probably the 'blind' wall following algorithms Bug1 and Bug2.
Bug1 tries to go straight to the goal; when blocked, it starts following the blocking wall looking for the minimum of the distance to the goal - this requires going around the obstacle, and then the way to the minimum. Then it resumes going straight towards the goal, and so on.
Bug2, when the straight path to the goal is blocked, remembers the line between its position and the goal, as well as the distance to the goal; it then follows the obstacle that blocked the way, until it crosses the line closer to the goal than when it started. Then it resumes going straight towards the goal, and so on.
The paths generated by these algorithms look ugly because they are, well, following the wall. If visual information is available, it can be used to improve performance. The simplest of the algorithms that do so, VisBug, predicts the path a virtual Bug2 would have taken, and makes shortcuts.
The algorithm described below uses the same general principle as VisBug, but relies on the gridded nature of the map. Distances are measured as:
dist(A, B) = maximum(abs(xA-xB), abs(yA-yB)).
Visibility is defined by the symmetrized Bresenham LOS, together with the euclidean sight range threshold. This is probably not essential, it was chosen for consistency with the rest of the game; other ways of defining visibility would probably work too (and might actually be easier to handle, see below).
When the monster wants to navigate to a new goal, it starts the virtual bug at its own location, with the wall_following_flag cleared and the min_dist = dist(monster, goal). Then at each subsequent step proceeds as follows:
if the goal is in LOS: reset the virtual bug to the current monster location, clear the wall_following_flag, min_dist = dist(monster, goal) run the virtual bug until it reaches the goal, or a step fails take a direct step towards the virtual bug.
The virtual bug uses the following algorithm:
if dist(bug, goal) < min_dist
clear wall_following_flag
min_dist = minimum(min_dist, dist(bug, goal))
if wall_following_flag is not set
try taking a direct step to the goal,
if it fails,
set wall_following_flag, and remember the blocking cell
if wall_following_flag is set
try taking a wall following step
if it fails
return failure
if the new place is not visible to the monster
withdraw the step
return failure
return success
When starting wall following, it is necessary to choose the side on which to follow: this is done by trying both ways (as long as can be seen by the monster), and choosing the one that leads closer to the goal.
If a path to the goal exists, and the direct step towards the goal is blocked, following the offending obstacle must eventually lead the bug closer to the goal. Of course, the path may be blocked again - even by the same obstacle if maliciously shaped - but, since min_dist can only decrease (except when the bug is reset), the bug should get to the goal in the end. The bug can be reset by the monster only if the goal can be seen by the monster - but then no further wall following is needed.
It is also necessary to prevent a problem that can happen when the path does not exist. If the monster can see all the room with no exits, it will just run its virtual bug round and round ;-) The solution used in the implementation below is to impose an artificial limit (4 times the range of sight) on the number of steps the virtual bug can take in one call of the anticipating part. One could also, for example, detect repetitions in the state of the bug.
The 'direct step' used both in the bug and in the anticipating part is actually somewhat complicated. The monster must be able to get to the position of its virtual bug, or the previously seen goal, using only direct steps. We must ensure that a series of direct steps gets the monster from A to B, if only it can see B from A.
An annoying property of the symmetrized Bresenham LOS is that it is possible to lose LOS to a cell while taking a step towards it. Suppose that B is to the right and down of A, and that abs(xA-xB) is not smaller than abs(yA-yB) - other cases can be reduced to this one. For any cell, lets call the vertical line dividing it in half - the cell's midline. If we have a LOS from A to B, a beam of (virtual) light from the centre of B illuminates some part of A's midline, including the centre. If B is seen through a narrow opening between obstacles however, the cells to the right and right-down from A may have their centres in shadow - so when we step into either we lose the LOS to B.
We can however proceed in such manner that the beam keeps illuminating _some_ part of the current cell's midline, even if the centre is no longer illuminated. An alternative solution would be to remember the cell from which we saw B, and ask Bresenham for guidance.
If the 'beam-guided' step described above is not possible, other possibilities that decrease at least one of the coordinate differences to B are tried; only when all that fails, direct step fails too.
The wall following step is simpler. We remember the direction from the bug to the wall cell it is following, and the side on which it should follow. We check the 8 cells around the bug, starting with the one at the remembered direction, clockwise or anticlockwise (depending on the side), and take a step into the first passable cell found, updating the direction appropriately. To be strictly correct, we should check if the cells around the bug are visible from the monster's location. Apart from the cost of 8 LOS calls this has an unpleasant effect when the monster is next to a wall:
....M.... ???###???
The centres of the cells marked ? are not in the LOS of M. This means in such a (common, in practice) case the virtual bug can't get very far from the monster. It doesn't break the algorithm, but makes it much less effective. A 'cheating' solution used in the implementation below is to assume that, when the monster can see a floor cell, it knows the passability of all the neighbouring cells, if only they are in range.
The source: [1]
A sample path (sight range 10) indicated with letters:
................................................................ ................................................................ ...................########################################..... ..........................................................#..... ..........................................................#..... .............#.........................#..................#..... .............#abcdefghijkl.............#..................#..... ....###################...mnop###################.........#..... .............#................qrstu....#..................#..... .............#.....................vwxy#..................#..... ...................xwvutsrqponmlkjihgfedcbazyxwvutsrqponm.#..... ..................y######################################l#..... ...................z......#............#...............jk.#..... ....................a.....#............#.............hit..#..... .....................b....#............#...........fg.u...#..... ......................c...#...k........#.......bcde..v....#..... .......................d..#..j.l.......#........azyxw.....#..... ........................e.#.inm........#..................#..... .........................f#po..........#..................#..... ...................xwvutsrq............#..................#..... ..................y########################################..... ...................zabcdefghijklmnopqrstuvwxyzabcdefghijklm..... ...........................................................no...
The advantages of this algorithm:
- faster than A* on a large map (doesn't depend on map size);
- doesn't assume the monster knows all the map;
- very little state needed for the monster;
- the paths usually look better than those generated by the 'blind'
- wall following algorithms.
Drawbacks:
- can't handle different movement costs
- can be generate very long paths in some cases, even worse than
- the blind algorithms
The algorithm as described here handles only two kinds of terrain: passable and transparent FLOOR, and impassable and opaque WALL. Passable, but opaque terrain (clouds of smoke, doors) seems relatively easy to implement - actually I have a version that handles doors, but it relies too much on other code in the game to be presented here. I think impassable transparent terrain (deep water, lava etc) could probably be handled if A* limited to the FOV was used instead of the 'direct step'.