Running code

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)