Difference between revisions of "Anticipating wall-following pathfinder"

From RogueBasin
Jump to navigation Jump to search
m (fixed a broken link)
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
The algorithm described below attempts to guide a monster, step by
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
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
cells: FLOOR (passable and transparent) and WALL (impassable and
opaque). The monster can take discrete steps in eight directions. It is
opaque). The monster can take discrete steps in eight directions. It is
Line 27: Line 27:
well, following the wall. If visual information is available, it can be
well, following the wall. If visual information is available, it can be
used to improve performance. The simplest of the algorithms that do so,
used to improve performance. The simplest of the algorithms that do so,
'''VisBug''', predicts the path a virtual '''Bug2''' would have taken, and makes  
'''VisBug''', predicts the path a virtual '''Bug2''' would have taken, and makes shortcuts.
shortcuts.


The algorithm described below uses the same general principle as
The algorithm described below uses the same general principle as
VisBug, but relies on the gridded nature of the map. Distances are
VisBug, but relies on the gridded nature of the map. Distances are
measured as:  
measured as:  
   dist(A, B) = maximum(abs(x_A - x_B), abs(y_A - y_B)).
   dist(A, B) = maximum(abs(xA-xB), abs(yA-yB)).
Visibility is defined by the symmetrized Bresenham LOS, together with
Visibility is defined by the symmetrized Bresenham LOS, together with
the ''euclidean'' sight range threshold. This is probably not essential,
the ''euclidean'' sight range threshold. This is probably not essential,
Line 39: Line 38:
defining visibility would probably work too (and might actually be
defining visibility would probably work too (and might actually be
easier to handle, see below).
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:
The virtual bug uses the following algorithm:
   if dist(bug, goal) < min_dist
   if dist(bug, goal) < min_dist
     clear wall_following_flag
     clear wall_following_flag
Line 58: Line 65:
   return success
   return success


When starting wall following, it is necessary to chose the side on
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
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  
seen by the monster), and choosing the one that leads closer to the  
Line 67: Line 74:
closer to the goal. Of course, the path may be blocked again - even by
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
the same obstacle if maliciously shaped - but, since min_dist can only
decrease, the bug should get to the goal in the end.
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.
When the monster wants to navigate to a new goal, it starts the virtual
bug at its own location, and then at each 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.
 
Note that resetting the virtual bug may increase its min_dist;
this can happen only if the goal is in LOS, so no further wall
following should be necessary.


It is also necessary to prevent a problem that can happen when the
It is also necessary to prevent a problem that can happen when the
Line 89: Line 83:
the range of sight) on the number of steps the virtual bug can take in  
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  
one call of the anticipating part. One could also, for example, detect  
repeatitions in the state of the bug.
repetitions in the state of the bug.


The 'direct step' used both in the bug and in the anticipating part is
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  
actually somewhat complicated. The monster must be able to get to the  
position of its virtual bug, or the previously seen goal, using only   
position of its virtual bug, or the previously seen goal, using only   
Line 99: Line 93:
An annoying property of the symmetrized Bresenham LOS is that it is
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
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
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
abs(x_A - x_B) >= abs(y_A - y_B). For any cell, lets call the vertical
line dividing it in half - the cell's midline. If we have a LOS from A
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  
to B, a beam of (virtual) light from the centre of B illuminates some  
part of the A's midline, including the centre. If B is seen through a  
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   
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   
right-down from A may have their centres in shadow - so when we step   
Line 126: Line 119:
location. Apart from the cost of 8 LOS calls this has an unpleasant
location. Apart from the cost of 8 LOS calls this has an unpleasant
effect when the monster is next to a wall:
effect when the monster is next to a wall:
  ....m....
  ....M....
  ???###???
  ???###???
The centres of the cells marked ? are not in the LOS of m. This means
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.
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:
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.
[http://www.nakido.com/B29BDCAD72CCFE17A7C55C4F413437FD5FFCC89F]


A sample path (sight range 10) indicated with letters:
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
  .............#abcdefghijkl.............#..................#.....
    reachable state
  ....###################...mnop###################.........#.....
  take a direct step towards the bug.
.............#................qrstu....#..................#.....
 
  .............#.....................vwxy#..................#.....
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.
...................xwvutsrqponmlkjihgfedcbazyxwvutsrqponm.#.....
 
..................y######################################l#.....
The source (antransp_rgb.c) can be found at:
...................z......#............#...............jk.#.....
[http://kusigrosz.jimdo.com/roguelike-related/]
....................a.....#............#.............hit..#.....
 
  .....................b....#............#...........fg.u...#.....
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.
  ......................c...#...k........#.......bcde..v....#.....
............................jk..................................
.......................d..#..j.l.......#........azyxw.....#.....
.....mnopqrstuvwxyzabcdefghi....................................
........................e.#.inm........#..................#.....
  ....l########################################################...
.........................f#po..........#..................#.....
  ....k=.................#.........#.........#..........#.....#...
  ...................xwvutsrq............#..................#.....
  ....j=.................#.........#.........#......a...#.........
  ..................y########################################.....
  ....i=.................#.........#.........#......b...#.........
...................zabcdefghijklmnopqrstuvwxyzabcdefghijklm.....
  ....h=........ponmlkj..#.........#.........#......c...#.....#...
  ...........................................................no...
  ....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:
The advantages of this algorithm:
Line 173: Line 174:
Drawbacks:
Drawbacks:
* can't handle different movement costs
* can't handle different movement costs
* can be generate very long paths in some cases, even worse than
* can generate very long paths in some cases, even worse than
:the blind algorithms
:the blind algorithms


The algorithm as described here handles only two kinds of terrain:
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.
passable and transparent FLOOR, and impassable and opaque WALL. 
 
Passable, but opaque terrain (clouds of smoke, doors) seems relatively
[[Category:Articles]]
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'.

Latest revision as of 09:09, 23 October 2013

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 (antransp_rgb.c) can be found at: [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.