Running code

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(needs *s removed)
 
m (*s removed)
Line 1: Line 1:
* Basically, once you start running, you keep moving until something
+
Basically, once you start running, you keep moving until something
* interesting happens.  In an enclosed space, you run straight, but
+
interesting happens.  In an enclosed space, you run straight, but
* you follow corners as needed (i.e. hallways).  In an open space,
+
you follow corners as needed (i.e. hallways).  In an open space,
* you run straight, but you stop before entering an enclosed space
+
you run straight, but you stop before entering an enclosed space
* (i.e. a room with a doorway).  In a semi-open space (with walls on
+
(i.e. a room with a doorway).  In a semi-open space (with walls on
* one side only), you run straight, but you stop before entering an
+
one side only), you run straight, but you stop before entering an
* enclosed space or an open space (i.e. running along side a wall).
+
enclosed space or an open space (i.e. running along side a wall).
  *
+
   
* All discussions below refer to what the player can see, that is,
+
All discussions below refer to what the player can see, that is,
* an unknown wall is just like a normal floor.  This means that we
+
an unknown wall is just like a normal floor.  This means that we
* must be careful when dealing with "illegal" grids.
+
must be careful when dealing with "illegal" grids.
  *
+
   
* No assumptions are made about the layout of the dungeon, so this
+
No assumptions are made about the layout of the dungeon, so this
* algorithm works in hallways, rooms, town, destroyed areas, etc.
+
algorithm works in hallways, rooms, town, destroyed areas, etc.
  *
+
   
* In the diagrams below, the player has just arrived in the grid
+
In the diagrams below, the player has just arrived in the grid
* marked as '@', and he has just come from a grid marked as 'o',
+
marked as '@', and he has just come from a grid marked as 'o',
* and he is about to enter the grid marked as 'x'.
+
and he is about to enter the grid marked as 'x'.
  *
+
   
* Running while confused is not allowed, and so running into a wall
+
Running while confused is not allowed, and so running into a wall
* is only possible when the wall is not seen by the player.  This
+
is only possible when the wall is not seen by the player.  This
* will take a turn and stop the running.
+
will take a turn and stop the running.
  *
+
   
* Several conditions are tracked by the running variables.
+
Several conditions are tracked by the running variables.
  *
+
   
p_ptr->run_open_area (in the open on at least one side)
+
    p_ptr->run_open_area (in the open on at least one side)
p_ptr->run_break_left (wall on the left, stop if it opens)
+
    p_ptr->run_break_left (wall on the left, stop if it opens)
p_ptr->run_break_right (wall on the right, stop if it opens)
+
    p_ptr->run_break_right (wall on the right, stop if it opens)
  *
+
   
* When running begins, these conditions are initialized by examining
+
When running begins, these conditions are initialized by examining
* the grids adjacent to the requested destination grid (marked 'x'),
+
the grids adjacent to the requested destination grid (marked 'x'),
* two on each side (marked 'L' and 'R').  If either one of the two
+
two on each side (marked 'L' and 'R').  If either one of the two
* grids on a given side is a wall, then that side is considered to
+
grids on a given side is a wall, then that side is considered to
* be "closed".  Both sides enclosed yields a hallway.
+
be "closed".  Both sides enclosed yields a hallway.
  *
+
   
*    LL                    @L
+
    LL                    @L
*    @x      (normal)      RxL  (diagonal)
+
    @x      (normal)      RxL  (diagonal)
*    RR      (east)          R    (south-east)
+
    RR      (east)          R    (south-east)
  *
+
   
* In the diagram below, in which the player is running east along a
+
In the diagram below, in which the player is running east along a
* hallway, he will stop as indicated before attempting to enter the
+
hallway, he will stop as indicated before attempting to enter the
* intersection (marked 'x').  Starting a new run in any direction
+
intersection (marked 'x').  Starting a new run in any direction
* will begin a new hallway run.
+
will begin a new hallway run.
  *
+
   
* #.#
+
  #.#
* ##.##
+
  ##.##
* o@x..
+
  o@x..
* ##.##
+
  ##.##
* #.#
+
  #.#
  *
+
   
* Note that a minor hack is inserted to make the angled corridor
+
Note that a minor hack is inserted to make the angled corridor
* entry (with one side blocked near and the other side blocked
+
entry (with one side blocked near and the other side blocked
* further away from the runner) work correctly. The runner moves
+
further away from the runner) work correctly. The runner moves
* diagonally, but then saves the previous direction as being
+
diagonally, but then saves the previous direction as being
* straight into the gap. Otherwise, the tail end of the other
+
straight into the gap. Otherwise, the tail end of the other
* entry would be perceived as an alternative on the next move.
+
entry would be perceived as an alternative on the next move.
  *
+
   
* In the diagram below, the player is running east down a hallway,
+
In the diagram below, the player is running east down a hallway,
* and will stop in the grid (marked '1') before the intersection.
+
and will stop in the grid (marked '1') before the intersection.
* Continuing the run to the south-east would result in a long run
+
Continuing the run to the south-east would result in a long run
* stopping at the end of the hallway (marked '2').
+
stopping at the end of the hallway (marked '2').
  *
+
   
* ##################
+
  ##################
* o@x      1
+
  o@x      1
* ########### ######
+
  ########### ######
* #2          #
+
  #2          #
* #############
+
  #############
  *
+
   
* After each step, the surroundings are examined to determine if
+
After each step, the surroundings are examined to determine if
* the running should stop, and to determine if the running should
+
the running should stop, and to determine if the running should
* change direction.  We examine the new current player location
+
change direction.  We examine the new current player location
* (at which the runner has just arrived) and the direction from
+
(at which the runner has just arrived) and the direction from
* which the runner is considered to have come.
+
which the runner is considered to have come.
  *
+
   
* Moving one grid in some direction places you adjacent to three
+
Moving one grid in some direction places you adjacent to three
* or five new grids (for straight and diagonal moves respectively)
+
or five new grids (for straight and diagonal moves respectively)
* to which you were not previously adjacent (marked as '!').
+
to which you were not previously adjacent (marked as '!').
  *
+
   
...!              ...
+
    ...!              ...
.o@!  (normal)    .o.!  (diagonal)
+
    .o@!  (normal)    .o.!  (diagonal)
...!  (east)      ..@!  (south east)
+
    ...!  (east)      ..@!  (south east)
*                      !!!
+
                      !!!
  *
+
   
* If any of the newly adjacent grids are "interesting" (monsters,
+
If any of the newly adjacent grids are "interesting" (monsters,
* objects, some terrain features) then running stops.
+
objects, some terrain features) then running stops.
  *
+
   
* If any of the newly adjacent grids seem to be open, and you are
+
If any of the newly adjacent grids seem to be open, and you are
* looking for a break on that side, then running stops.
+
looking for a break on that side, then running stops.
  *
+
   
* If any of the newly adjacent grids do not seem to be open, and
+
If any of the newly adjacent grids do not seem to be open, and
* you are in an open area, and the non-open side was previously
+
you are in an open area, and the non-open side was previously
* entirely open, then running stops.
+
entirely open, then running stops.
  *
+
   
* If you are in a hallway, then the algorithm must determine if
+
If you are in a hallway, then the algorithm must determine if
* the running should continue, turn, or stop.  If only one of the
+
the running should continue, turn, or stop.  If only one of the
* newly adjacent grids appears to be open, then running continues
+
newly adjacent grids appears to be open, then running continues
* in that direction, turning if necessary.  If there are more than
+
in that direction, turning if necessary.  If there are more than
* two possible choices, then running stops.  If there are exactly
+
two possible choices, then running stops.  If there are exactly
* two possible choices, separated by a grid which does not seem
+
two possible choices, separated by a grid which does not seem
* to be open, then running stops.  Otherwise, as shown below, the
+
to be open, then running stops.  Otherwise, as shown below, the
* player has probably reached a "corner".
+
player has probably reached a "corner".
  *
+
   
*    ###            o##
+
    ###            o##
*    o@x  (normal)  #@!  (diagonal)
+
    o@x  (normal)  #@!  (diagonal)
*    ##!  (east)    ##x  (south east)
+
    ##!  (east)    ##x  (south east)
  *
+
   
* In this situation, there will be two newly adjacent open grids,
+
In this situation, there will be two newly adjacent open grids,
* one touching the player on a diagonal, and one directly adjacent.
+
one touching the player on a diagonal, and one directly adjacent.
* We must consider the two "option" grids further out (marked '?').
+
We must consider the two "option" grids further out (marked '?').
* We assign "option" to the straight-on grid, and "option2" to the
+
We assign "option" to the straight-on grid, and "option2" to the
* diagonal grid.  For some unknown reason, we assign "check_dir" to
+
diagonal grid.  For some unknown reason, we assign "check_dir" to
* the grid marked 's', which may be incorrectly labelled.
+
the grid marked 's', which may be incorrectly labelled.
  *
+
   
*    ###s
+
    ###s
*    o@x?  (may be incorrect diagram!)
+
    o@x?  (may be incorrect diagram!)
*    ##!?
+
    ##!?
  *
+
   
* If both "option" grids are closed, then there is no reason to enter
+
If both "option" grids are closed, then there is no reason to enter
* the corner, and so we can cut the corner, by moving into the other
+
the corner, and so we can cut the corner, by moving into the other
* grid (diagonally).  If we choose not to cut the corner, then we may
+
grid (diagonally).  If we choose not to cut the corner, then we may
* go straight, but we pretend that we got there by moving diagonally.
+
go straight, but we pretend that we got there by moving diagonally.
* Below, we avoid the obvious grid (marked 'x') and cut the corner
+
Below, we avoid the obvious grid (marked 'x') and cut the corner
* instead (marked 'n').
+
instead (marked 'n').
  *
+
   
*    ###:              o##
+
    ###:              o##
*    o@x#  (normal)    #@n    (maybe?)
+
    o@x#  (normal)    #@n    (maybe?)
*    ##n#  (east)      ##x#
+
    ##n#  (east)      ##x#
*                      ####
+
                        ####
  *
+
   
* If one of the "option" grids is open, then we may have a choice, so
+
If one of the "option" grids is open, then we may have a choice, so
* we check to see whether it is a potential corner or an intersection
+
we check to see whether it is a potential corner or an intersection
* (or room entrance).  If the grid two spaces straight ahead, and the
+
(or room entrance).  If the grid two spaces straight ahead, and the
* space marked with 's' are both open, then it is a potential corner
+
space marked with 's' are both open, then it is a potential corner
* and we enter it if requested.  Otherwise, we stop, because it is
+
and we enter it if requested.  Otherwise, we stop, because it is
* not a corner, and is instead an intersection or a room entrance.
+
not a corner, and is instead an intersection or a room entrance.
  *
+
   
*    ###
+
    ###
*    o@x
+
    o@x
*    ##!#
+
    ##!#
  *
+
   
* I do not think this documentation is correct.
+
I do not think this documentation is correct.
  
 
From pathfind.c in the Angband 3.1.2v2 source code (GPL)
 
From pathfind.c in the Angband 3.1.2v2 source code (GPL)

Revision as of 09:05, 18 May 2011

Basically, once you start running, you keep moving until something interesting happens. In an enclosed space, you run straight, but you follow corners as needed (i.e. hallways). In an open space, you run straight, but you stop before entering an enclosed space (i.e. a room with a doorway). In a semi-open space (with walls on one side only), you run straight, but you stop before entering an enclosed space or an open space (i.e. running along side a wall).

All discussions below refer to what the player can see, that is, an unknown wall is just like a normal floor. This means that we must be careful when dealing with "illegal" grids.

No assumptions are made about the layout of the dungeon, so this algorithm works in hallways, rooms, town, destroyed areas, etc.

In the diagrams below, the player has just arrived in the grid marked as '@', and he has just come from a grid marked as 'o', and he is about to enter the grid marked as 'x'.

Running while confused is not allowed, and so running into a wall is only possible when the wall is not seen by the player. This will take a turn and stop the running.

Several conditions are tracked by the running variables.

   p_ptr->run_open_area (in the open on at least one side)
   p_ptr->run_break_left (wall on the left, stop if it opens)
   p_ptr->run_break_right (wall on the right, stop if it opens)

When running begins, these conditions are initialized by examining the grids adjacent to the requested destination grid (marked 'x'), two on each side (marked 'L' and 'R'). If either one of the two grids on a given side is a wall, then that side is considered to be "closed". Both sides enclosed yields a hallway.

    LL                     @L
    @x      (normal)       RxL   (diagonal)
    RR      (east)          R    (south-east)

In the diagram below, in which the player is running east along a hallway, he will stop as indicated before attempting to enter the intersection (marked 'x'). Starting a new run in any direction will begin a new hallway run.

 #.#
 ##.##
 o@x..
 ##.##
 #.#

Note that a minor hack is inserted to make the angled corridor entry (with one side blocked near and the other side blocked further away from the runner) work correctly. The runner moves diagonally, but then saves the previous direction as being straight into the gap. Otherwise, the tail end of the other entry would be perceived as an alternative on the next move.

In the diagram below, the player is running east down a hallway, and will stop in the grid (marked '1') before the intersection. Continuing the run to the south-east would result in a long run stopping at the end of the hallway (marked '2').

 ##################
 o@x       1
 ########### ######
 #2          #
 #############

After each step, the surroundings are examined to determine if the running should stop, and to determine if the running should change direction. We examine the new current player location (at which the runner has just arrived) and the direction from which the runner is considered to have come.

Moving one grid in some direction places you adjacent to three or five new grids (for straight and diagonal moves respectively) to which you were not previously adjacent (marked as '!').

   ...!              ...
   .o@!  (normal)    .o.!  (diagonal)
   ...!  (east)      ..@!  (south east)
                      !!!

If any of the newly adjacent grids are "interesting" (monsters, objects, some terrain features) then running stops.

If any of the newly adjacent grids seem to be open, and you are looking for a break on that side, then running stops.

If any of the newly adjacent grids do not seem to be open, and you are in an open area, and the non-open side was previously entirely open, then running stops.

If you are in a hallway, then the algorithm must determine if the running should continue, turn, or stop. If only one of the newly adjacent grids appears to be open, then running continues in that direction, turning if necessary. If there are more than two possible choices, then running stops. If there are exactly two possible choices, separated by a grid which does not seem to be open, then running stops. Otherwise, as shown below, the player has probably reached a "corner".

    ###             o##
    o@x  (normal)   #@!   (diagonal)
    ##!  (east)     ##x   (south east)

In this situation, there will be two newly adjacent open grids, one touching the player on a diagonal, and one directly adjacent. We must consider the two "option" grids further out (marked '?'). We assign "option" to the straight-on grid, and "option2" to the diagonal grid. For some unknown reason, we assign "check_dir" to the grid marked 's', which may be incorrectly labelled.

    ###s
    o@x?   (may be incorrect diagram!)
    ##!?

If both "option" grids are closed, then there is no reason to enter the corner, and so we can cut the corner, by moving into the other grid (diagonally). If we choose not to cut the corner, then we may go straight, but we pretend that we got there by moving diagonally. Below, we avoid the obvious grid (marked 'x') and cut the corner instead (marked 'n').

    ###:               o##
    o@x#   (normal)    #@n    (maybe?)
    ##n#   (east)      ##x#
                       ####

If one of the "option" grids is open, then we may have a choice, so we check to see whether it is a potential corner or an intersection (or room entrance). If the grid two spaces straight ahead, and the space marked with 's' are both open, then it is a potential corner and we enter it if requested. Otherwise, we stop, because it is not a corner, and is instead an intersection or a room entrance.

    ###
    o@x
    ##!#

I do not think this documentation is correct.

From pathfind.c in the Angband 3.1.2v2 source code (GPL)

Personal tools