Anticipating wall-following pathfinder

The algorithm described below attempts to guide a monster, step by step, to the goal of given, fixed coordinates. 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 by the virtual bug and the monster 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 monster M has no LOS to the centres of the cells marked '?'. 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 algorithm can be modified to allow it to handle transparent impassable terrain. If such terrain is present, it is possible for the virtual bug to run into places where it can't be reached by the monster walking a direct (straight) path, even if it still can be seen. It is however possible to run the virtual bug as far as it can be seen, and to remember the last place where it was directly reachable, The bug can get in and out of reach several times. When the bug finally gets out of sight (or gets to the goal), if there is no direct path to it, its last directly reachable state can be restored, so the monster knows how to get to it.

The main loop of the algorithm in such case looks as follows:

 if there exists a straight path to the goal:
   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.
 if the bug got out of reach, restore it to the last directly 
    reachable state
 take a direct step towards the bug.

An alternative way to handle transparent impassable terrain would be to run the A* or the Dijkstra algorithm limited to the monster's FOV. It would probably give better results, but might also decrease performance and increase complexity.

The source: [1]

A sample path is shown below. Walls are represented by '#', windows (impassable but transparent) by '=' and floor by '.'. The path is indicated with letters in alphabetical order. The sight range was 10.

............................jk..................................
.....mnopqrstuvwxyzabcdefghi....................................
....l########################################################...
....k=.................#.........#.........#..........#.....#...
....j=.................#.........#.........#......a...#.........
....i=.................#.........#.........#......b...#.........
....h=........ponmlkj..#.........#.........#......c...#.....#...
....g=.......qrstuvw.i.#.........#...q.....#.....d....#.....#...
....f=..............xyh#====.====#####r#####=====e====#.....#...
....e=................zafedcbazyxwvuts.onmlkjihgf...........#...
....d=.................#b...................................#...
....c###################c....==..................#####......#...
....b#...b..#...#..#...d......====..======.......#####......#...
....a#..c#az#xwv...#....e...===..====..=.=..................#...
....z#.d#...y###u.###...f...=.......=....=..................#...
....y###gh.#....t.#.####.g....=.=.....==.=.......=====......#...
....x#.f.#i###..s##....##h....=.==.=..=..=.......=====......#...
....w#...#.j.##..rst...#i....==..=.=.==..=..................#...
....v###.###k.###r.#un##j.....=....=.....=................###...
.....ut###.lmnopq.##vw#k......=.====..====..............###.....
.......sr#######..#...xyz.......=........=........#######.......
.........qp....##########a.########################.............
...........onmlkjihgfedcb.......................................

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 generate very long paths in some cases, even worse than

the blind algorithms

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.