Running code

From RogueBasin
Revision as of 09:01, 18 May 2011 by Quendus (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
* 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