ASTAR: A* pathfinding for 2D/3D grids

Data Structures
struct	ASTAR_CELL
	Internal node data used during pathfinding. More...
struct	ASTAR_GRID
	Grid structure holding walkability, costs, and dimensions. More...
struct	ASTAR_HEAP
	Binary min-heap (priority queue) for the open list. More...
struct	ASTAR_HEAP_NODE
	Min-heap entry for the open list priority queue. More...
struct	ASTAR_NODE
	A single node in the resulting path. More...
struct	ASTAR_PATH
	The computed path result. More...

Macros
#define	ASTAR_ALLOW_DIAGONAL   1
	Movement mode: 8-dir (2D) or 26-dir (3D)
#define	ASTAR_CARDINAL_ONLY   0
	Movement mode: 4-dir (2D) or 6-dir (3D)
#define	ASTAR_COST_CARDINAL   1000
	Default cost for straight movement (fixed-point x1000)
#define	ASTAR_COST_DIAGONAL   1414
	Default cost for 2D diagonal movement (sqrt(2)*1000)
#define	ASTAR_COST_DIAGONAL3D   1732
	Default cost for 3D diagonal movement (sqrt(3)*1000)
#define	ASTAR_NODE_CLOSED   2
	Node has been fully evaluated.
#define	ASTAR_NODE_NONE   0
	Node has not been visited.
#define	ASTAR_NODE_OPEN   1
	Node is in the open list.

Enumerations
enum	ASTAR_HEURISTIC { ASTAR_HEURISTIC_MANHATTAN = 0 , ASTAR_HEURISTIC_EUCLIDEAN , ASTAR_HEURISTIC_CHEBYSHEV }
	Heuristic function selection for h(n) estimation. More...

Functions
ASTAR_PATH *	n_astar_find_path (const ASTAR_GRID *grid, int sx, int sy, int sz, int gx, int gy, int gz, int diagonal, ASTAR_HEURISTIC heuristic)
	find a path using A* search, returns NULL if no path exists
void	n_astar_grid_free (ASTAR_GRID *grid)
	free a grid and all its internal data
int	n_astar_grid_get_cost (const ASTAR_GRID *grid, int x, int y, int z)
	get a cell's movement cost multiplier (x1000)
uint8_t	n_astar_grid_get_walkable (const ASTAR_GRID *grid, int x, int y, int z)
	get a cell's walkability (1=passable, 0=blocked, 0 if out of bounds)
ASTAR_GRID *	n_astar_grid_new (int width, int height, int depth)
	create a new grid for pathfinding, all cells default to walkable
void	n_astar_grid_set_cost (ASTAR_GRID *grid, int x, int y, int z, int cost)
	set a cell's movement cost multiplier (x1000)
void	n_astar_grid_set_rect_blocked (ASTAR_GRID *grid, int x1, int y1, int z1, int x2, int y2, int z2)
	set a rectangular region as blocked
void	n_astar_grid_set_walkable (ASTAR_GRID *grid, int x, int y, int z, uint8_t walkable)
	set a cell's walkability (1=passable, 0=blocked)
int	n_astar_heuristic (int x1, int y1, int z1, int x2, int y2, int z2, ASTAR_HEURISTIC heuristic)
	compute heuristic distance between two points (x1000)
void	n_astar_path_free (ASTAR_PATH *path)
	free a path returned by n_astar_find_path

Detailed Description

---

Data Structure Documentation

ASTAR_CELL

struct ASTAR_CELL

Internal node data used during pathfinding.

Definition at line 123 of file n_astar.h.

Collaboration diagram for ASTAR_CELL:

Data Fields
int	f	g + h
int	g	cost from start to this cell
int	h	heuristic estimate to goal
int	parent_x	parent cell X (-1 if none)
int	parent_y	parent cell Y
int	parent_z	parent cell Z
uint8_t	status	ASTAR_NODE_NONE / OPEN / CLOSED.

ASTAR_GRID

struct ASTAR_GRID

Grid structure holding walkability, costs, and dimensions.

Examples

ex_gui_isometric.c, and ex_iso_astar.c.

Definition at line 147 of file n_astar.h.

Collaboration diagram for ASTAR_GRID:

Data Fields
int *	cost	per-cell movement cost multiplier (x1000)
int	depth	grid depth (Z axis, 1 for 2D)
int	height	grid height (Y axis)
uint8_t *	walkable	walkability map: 1=passable, 0=blocked
int	width	grid width (X axis)

ASTAR_HEAP

struct ASTAR_HEAP

Binary min-heap (priority queue) for the open list.

Definition at line 140 of file n_astar.h.

Collaboration diagram for ASTAR_HEAP:

Data Fields
int	capacity	allocated capacity
ASTAR_HEAP_NODE *	data	heap array
int	size	current number of elements

ASTAR_HEAP_NODE

struct ASTAR_HEAP_NODE

Min-heap entry for the open list priority queue.

Definition at line 134 of file n_astar.h.

Collaboration diagram for ASTAR_HEAP_NODE:

Data Fields
int	f	priority (f = g + h)
int	x
int	y
int	z	grid coordinates

ASTAR_NODE

struct ASTAR_NODE

A single node in the resulting path.

Definition at line 109 of file n_astar.h.

Collaboration diagram for ASTAR_NODE:

Data Fields
int	x	grid X coordinate
int	y	grid Y coordinate
int	z	grid Z coordinate (0 for 2D)

ASTAR_PATH

struct ASTAR_PATH

The computed path result.

Examples

ex_gui_isometric.c, and ex_iso_astar.c.

Definition at line 116 of file n_astar.h.

Collaboration diagram for ASTAR_PATH:

Data Fields
int	cost	total path cost (x1000 fixed-point)
int	length	number of nodes in the path
ASTAR_NODE *	nodes	array of path nodes from start to goal

Macro Definition Documentation

ASTAR_ALLOW_DIAGONAL

#define ASTAR_ALLOW_DIAGONAL   1

Movement mode: 8-dir (2D) or 26-dir (3D)

Examples

ex_gui_isometric.c, and ex_iso_astar.c.

Definition at line 77 of file n_astar.h.

ASTAR_CARDINAL_ONLY

#define ASTAR_CARDINAL_ONLY   0

Movement mode: 4-dir (2D) or 6-dir (3D)

Examples

ex_iso_astar.c.

Definition at line 75 of file n_astar.h.

ASTAR_COST_CARDINAL

#define ASTAR_COST_CARDINAL   1000

Default cost for straight movement (fixed-point x1000)

Examples

ex_iso_astar.c.

Definition at line 80 of file n_astar.h.

ASTAR_COST_DIAGONAL

#define ASTAR_COST_DIAGONAL   1414

Default cost for 2D diagonal movement (sqrt(2)*1000)

Definition at line 82 of file n_astar.h.

ASTAR_COST_DIAGONAL3D

#define ASTAR_COST_DIAGONAL3D   1732

Default cost for 3D diagonal movement (sqrt(3)*1000)

Definition at line 84 of file n_astar.h.

ASTAR_NODE_CLOSED

#define ASTAR_NODE_CLOSED   2

Node has been fully evaluated.

Definition at line 91 of file n_astar.h.

ASTAR_NODE_NONE

#define ASTAR_NODE_NONE   0

Node has not been visited.

Definition at line 87 of file n_astar.h.

ASTAR_NODE_OPEN

#define ASTAR_NODE_OPEN   1

Node is in the open list.

Definition at line 89 of file n_astar.h.

Enumeration Type Documentation

ASTAR_HEURISTIC

enum ASTAR_HEURISTIC

Heuristic function selection for h(n) estimation.

Enumerator
ASTAR_HEURISTIC_MANHATTAN	sum of axis deltas (optimal for 4-dir)
ASTAR_HEURISTIC_EUCLIDEAN	straight-line distance
ASTAR_HEURISTIC_CHEBYSHEV	max of axis deltas (optimal for 8-dir)

Definition at line 98 of file n_astar.h.

Function Documentation

n_astar_find_path()

ASTAR_PATH * n_astar_find_path	(	const ASTAR_GRID *	grid,
		int	sx,
		int	sy,
		int	sz,
		int	gx,
		int	gy,
		int	gz,
		int	diagonal,
		ASTAR_HEURISTIC	heuristic
	)

find a path using A* search, returns NULL if no path exists

find a path using A* search, returns NULL if no path exists

Parameters

grid	the grid to search
sx	start X
sy	start Y
sz	start Z
gx	goal X
gy	goal Y
gz	goal Z
diagonal	ASTAR_CARDINAL_ONLY or ASTAR_ALLOW_DIAGONAL
heuristic	heuristic function to use

Returns

path from start to goal, or NULL if no path exists. Caller must free with n_astar_path_free().

Definition at line 477 of file n_astar.c.

References ASTAR_COST_CARDINAL, ASTAR_COST_DIAGONAL, ASTAR_COST_DIAGONAL3D, ASTAR_NODE_CLOSED, ASTAR_NODE_NONE, ASTAR_NODE_OPEN, ASTAR_PATH::cost, ASTAR_GRID::cost, ASTAR_GRID::depth, dir2d_cardinal, dir2d_diagonal, dir3d_cardinal, dir3d_diagonal, ASTAR_CELL::f, ASTAR_CELL::g, grid_index(), ASTAR_CELL::h, heap_free(), heap_new(), heap_pop(), heap_push(), ASTAR_GRID::height, in_bounds(), ASTAR_PATH::length, n_astar_heuristic(), ASTAR_PATH::nodes, ASTAR_CELL::parent_x, ASTAR_CELL::parent_y, ASTAR_CELL::parent_z, reconstruct_path(), ASTAR_HEAP::size, ASTAR_CELL::status, ASTAR_GRID::walkable, ASTAR_GRID::width, ASTAR_NODE::x, ASTAR_HEAP_NODE::x, ASTAR_NODE::y, ASTAR_HEAP_NODE::y, ASTAR_NODE::z, and ASTAR_HEAP_NODE::z.

Referenced by demo_astar(), demo_astar_standalone(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_grid_free()

void n_astar_grid_free

(

ASTAR_GRID *

grid

)

free a grid and all its internal data

free a grid and all its internal data

Parameters

grid	grid to free (safe to pass NULL)

Definition at line 255 of file n_astar.c.

References ASTAR_GRID::cost, and ASTAR_GRID::walkable.

Referenced by demo_astar(), demo_astar_standalone(), and main().

Here is the caller graph for this function:

n_astar_grid_get_cost()

int n_astar_grid_get_cost	(	const ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z
	)

get a cell's movement cost multiplier (x1000)

get a cell's movement cost multiplier (x1000)

Parameters

grid	the grid
x	cell X coordinate
y	cell Y coordinate
z	cell Z coordinate

Returns

cost multiplier (x1000), or 0 if out of bounds

Definition at line 309 of file n_astar.c.

References ASTAR_GRID::cost, grid_index(), and in_bounds().

Here is the call graph for this function:

n_astar_grid_get_walkable()

uint8_t n_astar_grid_get_walkable	(	const ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z
	)

get a cell's walkability (1=passable, 0=blocked, 0 if out of bounds)

get a cell's walkability (1=passable, 0=blocked, 0 if out of bounds)

Parameters

grid	the grid
x	cell X coordinate
y	cell Y coordinate
z	cell Z coordinate

Returns

1 if passable, 0 if blocked or out of bounds

Definition at line 283 of file n_astar.c.

References grid_index(), in_bounds(), and ASTAR_GRID::walkable.

Referenced by demo_astar_standalone(), and main().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_grid_new()

ASTAR_GRID * n_astar_grid_new	(	int	width,
		int	height,
		int	depth
	)

create a new grid for pathfinding, all cells default to walkable

create a new grid for pathfinding, all cells default to walkable

Parameters

width	grid width (X)
height	grid height (Y)
depth	grid depth (Z, use 1 for 2D)

Returns

new grid or NULL. All cells default to walkable with cost 1000.

Definition at line 219 of file n_astar.c.

References ASTAR_COST_CARDINAL, ASTAR_GRID::cost, ASTAR_GRID::depth, ASTAR_GRID::height, ASTAR_GRID::walkable, and ASTAR_GRID::width.

Referenced by demo_astar(), and demo_astar_standalone().

Here is the caller graph for this function:

n_astar_grid_set_cost()

void n_astar_grid_set_cost	(	ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z,
		int	cost
	)

set a cell's movement cost multiplier (x1000)

set a cell's movement cost multiplier (x1000)

Parameters

grid	the grid
x	cell X coordinate
y	cell Y coordinate
z	cell Z coordinate
cost	cost multiplier (x1000)

Definition at line 296 of file n_astar.c.

References ASTAR_GRID::cost, grid_index(), and in_bounds().

Referenced by demo_astar().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_grid_set_rect_blocked()

void n_astar_grid_set_rect_blocked	(	ASTAR_GRID *	grid,
		int	x1,
		int	y1,
		int	z1,
		int	x2,
		int	y2,
		int	z2
	)

set a rectangular region as blocked

set a rectangular region as blocked

Parameters

grid	the grid
x1	start corner X (inclusive)
y1	start corner Y (inclusive)
z1	start corner Z (inclusive)
x2	end corner X (inclusive)
y2	end corner Y (inclusive)
z2	end corner Z (inclusive)

Definition at line 324 of file n_astar.c.

References n_astar_grid_set_walkable().

Referenced by demo_astar_standalone().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_grid_set_walkable()

void n_astar_grid_set_walkable	(	ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z,
		uint8_t	walkable
	)

set a cell's walkability (1=passable, 0=blocked)

set a cell's walkability (1=passable, 0=blocked)

Parameters

grid	the grid
x	cell X coordinate
y	cell Y coordinate
z	cell Z coordinate
walkable	1=passable, 0=blocked

Definition at line 270 of file n_astar.c.

References grid_index(), in_bounds(), and ASTAR_GRID::walkable.

Referenced by demo_astar(), and n_astar_grid_set_rect_blocked().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_heuristic()

int n_astar_heuristic	(	int	x1,
		int	y1,
		int	z1,
		int	x2,
		int	y2,
		int	z2,
		ASTAR_HEURISTIC	heuristic
	)

compute heuristic distance between two points (x1000)

compute heuristic distance between two points (x1000)

Parameters

x1	first point X
y1	first point Y
z1	first point Z
x2	second point X
y2	second point Y
z2	second point Z
heuristic	the heuristic to use

Returns

estimated distance in fixed-point (x1000)

Definition at line 166 of file n_astar.c.

References ASTAR_COST_CARDINAL, ASTAR_COST_DIAGONAL, ASTAR_COST_DIAGONAL3D, ASTAR_HEURISTIC_CHEBYSHEV, ASTAR_HEURISTIC_EUCLIDEAN, ASTAR_HEURISTIC_MANHATTAN, and iabs().

Referenced by n_astar_find_path().

Here is the call graph for this function:

Here is the caller graph for this function:

n_astar_path_free()

void n_astar_path_free

(

ASTAR_PATH *

path

)

free a path returned by n_astar_find_path

free a path returned by n_astar_find_path

Parameters

path	path to free (safe to pass NULL)

Definition at line 707 of file n_astar.c.

References ASTAR_PATH::nodes.

Referenced by demo_astar(), demo_astar_standalone(), and main().

Here is the caller graph for this function: