Running code
Jump to navigation
Jump to 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)