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:

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

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_GRID grid, 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.

Function Documentation

◆ 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 45 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(), n_astar_grid_set_walkable(), and reconstruct_path().

Here is the caller graph for this function:

◆ heap_free()

static void heap_free ( ASTAR_HEAP * h )

static

Definition at line 79 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 85 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 65 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 124 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 101 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 95 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 57 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 50 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:

◆ reconstruct_path()

static ASTAR_PATH * reconstruct_path	(	ASTAR_CELL *	cells,
		const ASTAR_GRID *	grid,
		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 359 of file n_astar.c.

References ASTAR_PATH::cost, ASTAR_GRID::depth, ASTAR_CELL::g, grid_index(), ASTAR_GRID::height, ASTAR_PATH::length, ASTAR_PATH::nodes, ASTAR_CELL::parent_x, ASTAR_CELL::parent_y, ASTAR_CELL::parent_z, ASTAR_GRID::width, 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 415 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 420 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 430 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 437 of file n_astar.c.

Referenced by n_astar_find_path().

Functions

Variables

Detailed Description

Function Documentation

◆ grid_index()

◆ heap_free()

◆ heap_grow()

◆ heap_new()

◆ heap_pop()

◆ heap_push()

◆ heap_swap()

◆ iabs()

◆ in_bounds()

◆ reconstruct_path()

Variable Documentation

◆ dir2d_cardinal

◆ dir2d_diagonal

◆ dir3d_cardinal

◆ dir3d_diagonal