Angband
Macros | Functions | Variables
player-path.c File Reference

Pathfinding and running code. More...

#include "angband.h"
#include "cmds.h"
#include "cave.h"
#include "init.h"
#include "mon-util.h"
#include "obj-ignore.h"
#include "obj-util.h"
#include "player-path.h"
#include "player-util.h"

Macros

#define MAX_PF_RADIUS   50
 

Pathfinding code


#define MAX_PF_LENGTH   250
 Maximum distance to consider in the pathfinder.
#define MARK_DISTANCE(c, d)

Functions

static bool is_valid_pf (int y, int x)
static void fill_terrain_info (void)
bool findpath (int y, int x)
int pathfind_direction_to (struct loc from, struct loc to)
 Compute the direction (in the angband 123456789 sense) from a point to a point.
static int see_wall (int dir, int y, int x)
 Hack – Check for a "known wall" (see below)
static void run_init (int dir)
 Initialize the running algorithm for a new direction.
static bool run_test (void)
 Update the current "run" path.
void run_step (int dir)
 Take one step along the current "run" path.

Variables

static int terrain [MAX_PF_RADIUS][MAX_PF_RADIUS]
static char pf_result [MAX_PF_LENGTH]
static int pf_result_index
static int ox
static int oy
static int ex
static int ey
static int dir_search [8] = {2,4,6,8,1,3,7,9}
int run_cur_dir
 

Running code


int run_old_dir
bool run_unused
bool run_open_area
bool run_break_right
bool run_break_left
static const byte cycle []
 Hack – allow quick "cycling" through the legal directions.
static const byte chome []
 Hack – map each direction into the "middle" of the "cycle[]" array.

Detailed Description

Pathfinding and running code.

Copyright (c) 1988 Christopher J Stuart (running code) Copyright (c) 2004-2007 Christophe Cavalaria, Leon Marrick (pathfinding)

This work is free software; you can redistribute it and/or modify it under the terms of either:

a) the GNU General Public License as published by the Free Software Foundation, version 2, or

b) the "Angband licence": This software may be copied and distributed for educational, research, and not for profit purposes provided that this copyright and statement are included in all such copies. Other copyrights may also apply.

Macro Definition Documentation

#define MARK_DISTANCE (   c,
 
)
Value:
if ((c <= MAX_PF_LENGTH) && (c > d)) \
{ c = d; try_again = (TRUE); }

Referenced by findpath().

#define MAX_PF_LENGTH   250

Maximum distance to consider in the pathfinder.

Referenced by fill_terrain_info(), and findpath().

#define MAX_PF_RADIUS   50


Pathfinding code

Maximum size around the player to consider in the pathfinder

Referenced by fill_terrain_info().

Function Documentation

static void fill_terrain_info ( void  )
static
bool findpath ( int  y,
int  x 
)
static bool is_valid_pf ( int  y,
int  x 
)
static
int pathfind_direction_to ( struct loc  from,
struct loc  to 
)

Compute the direction (in the angband 123456789 sense) from a point to a point.

We decide to use diagonals if dx and dy are within a factor of two of each other; otherwise we choose a cardinal direction.

References ABS, DIR_E, DIR_N, DIR_NE, DIR_NONE, DIR_NW, DIR_S, DIR_SE, DIR_SW, DIR_UNKNOWN, DIR_W, loc::x, and loc::y.

Referenced by test_dir_to(), and textui_get_rep_dir().

static void run_init ( int  dir)
static

Initialize the running algorithm for a new direction.

Diagonal Corridor – allow diaginal entry into corridors.

Blunt Corridor – If there is a wall two spaces ahead and we seem to be in a corridor, then force a turn into the side corridor, must be moving straight into a corridor here. (?)

Diagonal Corridor Blunt Corridor (?)

#x# # . p

References chome, cycle, ddx, ddy, FALSE, i, player::px, player::py, row, run_break_left, run_break_right, run_cur_dir, run_old_dir, run_open_area, player_upkeep::running_firststep, see_wall(), TRUE, and player::upkeep.

Referenced by run_step().

void run_step ( int  dir)
static bool run_test ( void  )
static
static int see_wall ( int  dir,
int  y,
int  x 
)
static

Hack – Check for a "known wall" (see below)

References cave, ddx, ddy, FALSE, square_in_bounds(), square_ismark(), square_seemslikewall(), and TRUE.

Referenced by run_init(), and run_test().

Variable Documentation

const byte chome[]
static
Initial value:
{ 0, 8, 9, 10, 7, 0, 11, 6, 5, 4 }

Hack – map each direction into the "middle" of the "cycle[]" array.

Referenced by run_init(), and run_test().

const byte cycle[]
static
Initial value:
{ 1, 2, 3, 6, 9, 8, 7, 4, 1, 2, 3, 6, 9, 8, 7, 4, 1 }

Hack – allow quick "cycling" through the legal directions.

Referenced by run_init(), and run_test().

int dir_search[8] = {2,4,6,8,1,3,7,9}
static

Referenced by findpath().

int ex
static

Referenced by fill_terrain_info(), and findpath().

int ey
static

Referenced by fill_terrain_info(), and findpath().

int ox
static
int oy
static
char pf_result[MAX_PF_LENGTH]
static

Referenced by findpath(), and run_step().

int pf_result_index
static

Referenced by findpath(), and run_step().

bool run_break_left

Referenced by run_init(), and run_test().

bool run_break_right

Referenced by run_init(), and run_test().

int run_cur_dir


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.

run_open_area (in the open on at least one side) run_break_left (wall on the left, stop if it opens) 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 (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..

.

#.#

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 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 (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.

s

o? (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# (normal) #
(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

!

I do not think this documentation is correct.

Referenced by run_init(), run_step(), and run_test().

int run_old_dir

Referenced by run_init(), and run_test().

bool run_open_area

Referenced by run_init(), and run_test().

bool run_unused
int terrain[MAX_PF_RADIUS][MAX_PF_RADIUS]
static

Referenced by fill_terrain_info(), and findpath().