A* Pathfinding implementation for 2D and 3D grids. More...

#include "nilorea/n_astar.h"
#include <string.h>
#include <math.h>

Include dependency graph for n_astar.c:

Data Structures
struct	ASTAR_BOX
	Search window: the bounding box of (start, goal) expanded by ASTAR_SEARCH_MARGIN and clamped to the grid. More...

Functions
static int	box_index (const ASTAR_BOX *b, int x, int y, int z)
	Flat index into the window-local ASTAR_CELL array.

static int	grid_index (const ASTAR_GRID *grid, int x, int y, int z)
	Convert 3D coordinates to flat array index.

static void	heap_free (ASTAR_HEAP *h)

static int	heap_grow (ASTAR_HEAP *h)

static ASTAR_HEAP *	heap_new (int capacity)

static ASTAR_HEAP_NODE	heap_pop (ASTAR_HEAP *h)

static void	heap_push (ASTAR_HEAP *h, int x, int y, int z, int f)

static void	heap_swap (ASTAR_HEAP_NODE a, ASTAR_HEAP_NODE b)

static int	iabs (int v)
	Absolute value for integers.

static int	in_bounds (const ASTAR_GRID *grid, int x, int y, int z)
	Check if coordinates are within grid bounds.

static int	in_box (const ASTAR_BOX *b, int x, int y, int z)
	Check if coordinates fall inside the search window.

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.

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.

uint8_t	n_astar_grid_get_walkable (const ASTAR_GRID *grid, int x, int y, int z)
	Get a cell's walkability.

ASTAR_GRID *	n_astar_grid_new (int width, int height, int depth)
	Create a new grid for A* pathfinding.

void	n_astar_grid_set_cost (ASTAR_GRID *grid, int x, int y, int z, int cost)
	Set a cell's movement cost multiplier.

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 (wall)

void	n_astar_grid_set_walkable (ASTAR_GRID *grid, int x, int y, int z, uint8_t walkable)
	Set a cell's walkability.

int	n_astar_heuristic (int x1, int y1, int z1, int x2, int y2, int z2, ASTAR_HEURISTIC heuristic)
	Compute heuristic distance between two 3D points.

void	n_astar_path_free (ASTAR_PATH *path)
	Free a path returned by n_astar_find_path.

static ASTAR_PATH *	reconstruct_path (ASTAR_CELL cells, const ASTAR_BOX box, int sx, int sy, int sz, int gx, int gy, int gz)
	Build path from goal back to start following parent pointers.

Variables
static const int	dir2d_cardinal [][2]

static const int	dir2d_diagonal [][2]

static const int	dir3d_cardinal [][3]

static const int	dir3d_diagonal [][3]

Detailed Description

A* Pathfinding implementation for 2D and 3D grids.

Uses a binary min-heap as the open list priority queue for O(log n) insert/extract operations, and a flat array for O(1) closed-set membership checks.

Based on:

GameDev.net Article 2003: "A* Pathfinding for Beginners"
Red Blob Games: "Implementation of A*"

Author: Castagnier Mickael

Version: 1.0

Date: 01/03/2026

Definition in file n_astar.c.

Data Structure Documentation

◆ ASTAR_BOX

struct ASTAR_BOX

Search window: the bounding box of (start, goal) expanded by ASTAR_SEARCH_MARGIN and clamped to the grid.

The per-call ASTAR_CELL working set is allocated for this window only, NOT the whole grid, so a short path on a huge map costs a few KB instead of width*height*depth cells. The grid's own walkable[] / cost[] planes stay full-size and are still indexed by the absolute grid_index().

Definition at line 61 of file n_astar.c.

Collaboration diagram for ASTAR_BOX:

Data Fields
int	bd	window dimensions in cells
int	bh
int	bw
int	minx
int	miny
int	minz	window origin (absolute grid coords)

Function Documentation

◆ box_index()

static int box_index	(	const ASTAR_BOX *	b,
		int	x,
		int	y,
		int	z
	)

inlinestatic

Flat index into the window-local ASTAR_CELL array.

Definition at line 67 of file n_astar.c.

References ASTAR_BOX::bh, ASTAR_BOX::bw, ASTAR_BOX::minx, ASTAR_BOX::miny, and ASTAR_BOX::minz.

Referenced by n_astar_find_path(), and reconstruct_path().

Here is the caller graph for this function:

◆ grid_index()

static int grid_index	(	const ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z
	)

inlinestatic

Convert 3D coordinates to flat array index.

Definition at line 44 of file n_astar.c.

References ASTAR_GRID::height, and ASTAR_GRID::width.

Referenced by n_astar_find_path(), n_astar_grid_get_cost(), n_astar_grid_get_walkable(), n_astar_grid_set_cost(), and n_astar_grid_set_walkable().

Here is the caller graph for this function:

◆ heap_free()

static void heap_free ( ASTAR_HEAP * h )

static

Definition at line 99 of file n_astar.c.

References ASTAR_HEAP::data.

Referenced by n_astar_find_path().

Here is the caller graph for this function:

◆ heap_grow()

static int heap_grow ( ASTAR_HEAP * h )

static

Definition at line 105 of file n_astar.c.

References ASTAR_HEAP::capacity, and ASTAR_HEAP::data.

Referenced by heap_push().

Here is the caller graph for this function:

◆ heap_new()

static ASTAR_HEAP * heap_new ( int capacity )

static

Definition at line 85 of file n_astar.c.

References ASTAR_HEAP::capacity, ASTAR_HEAP::data, and ASTAR_HEAP::size.

Referenced by n_astar_find_path().

Here is the caller graph for this function:

◆ heap_pop()

static ASTAR_HEAP_NODE heap_pop ( ASTAR_HEAP * h )

static

Definition at line 144 of file n_astar.c.

References ASTAR_HEAP::data, ASTAR_HEAP_NODE::f, heap_swap(), and ASTAR_HEAP::size.

Referenced by n_astar_find_path().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ heap_push()

static void heap_push	(	ASTAR_HEAP *	h,
		int	x,
		int	y,
		int	z,
		int	f
	)

static

Definition at line 121 of file n_astar.c.

References ASTAR_HEAP::capacity, ASTAR_HEAP::data, ASTAR_HEAP_NODE::f, heap_grow(), heap_swap(), ASTAR_HEAP::size, ASTAR_HEAP_NODE::x, ASTAR_HEAP_NODE::y, and ASTAR_HEAP_NODE::z.

Referenced by n_astar_find_path().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ heap_swap()

static void heap_swap	(	ASTAR_HEAP_NODE *	a,
		ASTAR_HEAP_NODE *	b
	)

static

Definition at line 115 of file n_astar.c.

Referenced by heap_pop(), and heap_push().

Here is the caller graph for this function:

◆ iabs()

static int iabs ( int v )

inlinestatic

Absolute value for integers.

Definition at line 79 of file n_astar.c.

Referenced by n_astar_heuristic().

Here is the caller graph for this function:

◆ in_bounds()

static int in_bounds	(	const ASTAR_GRID *	grid,
		int	x,
		int	y,
		int	z
	)

inlinestatic

Check if coordinates are within grid bounds.

Definition at line 49 of file n_astar.c.

References ASTAR_GRID::depth, ASTAR_GRID::height, and ASTAR_GRID::width.

Referenced by n_astar_find_path(), n_astar_grid_get_cost(), n_astar_grid_get_walkable(), n_astar_grid_set_cost(), and n_astar_grid_set_walkable().

Here is the caller graph for this function:

◆ in_box()

static int in_box	(	const ASTAR_BOX *	b,
		int	x,
		int	y,
		int	z
	)

inlinestatic

Check if coordinates fall inside the search window.

Definition at line 72 of file n_astar.c.

References ASTAR_BOX::bd, ASTAR_BOX::bh, ASTAR_BOX::bw, ASTAR_BOX::minx, ASTAR_BOX::miny, and ASTAR_BOX::minz.

Referenced by n_astar_find_path().

Here is the caller graph for this function:

◆ reconstruct_path()

static ASTAR_PATH * reconstruct_path	(	ASTAR_CELL *	cells,
		const ASTAR_BOX *	box,
		int	sx,
		int	sy,
		int	sz,
		int	gx,
		int	gy,
		int	gz
	)

static

Build path from goal back to start following parent pointers.

Definition at line 373 of file n_astar.c.

References ASTAR_BOX::bd, ASTAR_BOX::bh, box_index(), ASTAR_BOX::bw, ASTAR_PATH::cost, ASTAR_CELL::g, ASTAR_PATH::length, ASTAR_PATH::nodes, ASTAR_CELL::parent_x, ASTAR_CELL::parent_y, ASTAR_CELL::parent_z, ASTAR_NODE::x, ASTAR_NODE::y, and ASTAR_NODE::z.

Referenced by n_astar_find_path().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ dir2d_cardinal

const int dir2d_cardinal[][2]

static

Initial value:

= {
    {0, -1},
    {0, 1},
    {1, 0},
    {-1, 0}}

Definition at line 427 of file n_astar.c.

Referenced by n_astar_find_path().

◆ dir2d_diagonal

const int dir2d_diagonal[][2]

static

Initial value:

= {
    {1, -1},
    {-1, -1},
    {1, 1},
    {-1, 1}}

Definition at line 432 of file n_astar.c.

Referenced by n_astar_find_path().

◆ dir3d_cardinal

const int dir3d_cardinal[][3]

static

Initial value:

= {
    {1, 0, 0},
    {-1, 0, 0},
    {0, 1, 0},
    {0, -1, 0},
    {0, 0, 1},
    {0, 0, -1}}

Definition at line 440 of file n_astar.c.

Referenced by n_astar_find_path().

◆ dir3d_diagonal

const int dir3d_diagonal[][3]

static

Initial value:

= {
    {1, 1, 0},
    {1, -1, 0},
    {-1, 1, 0},
    {-1, -1, 0},
    {1, 0, 1},
    {1, 0, -1},
    {-1, 0, 1},
    {-1, 0, -1},
    {0, 1, 1},
    {0, 1, -1},
    {0, -1, 1},
    {0, -1, -1},
    {1, 1, 1},
    {1, 1, -1},
    {1, -1, 1},
    {1, -1, -1},
    {-1, 1, 1},
    {-1, 1, -1},
    {-1, -1, 1},
    {-1, -1, -1}}

Definition at line 447 of file n_astar.c.

Referenced by n_astar_find_path().

Data Structures

Functions

Variables

Detailed Description

Data Structure Documentation

◆ ASTAR_BOX

Function Documentation

◆ box_index()

◆ grid_index()

◆ heap_free()

◆ heap_grow()

◆ heap_new()

◆ heap_pop()

◆ heap_push()

◆ heap_swap()

◆ iabs()

◆ in_bounds()

◆ in_box()

◆ reconstruct_path()

Variable Documentation

◆ dir2d_cardinal

◆ dir2d_diagonal

◆ dir3d_cardinal

◆ dir3d_diagonal