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

#include <stdlib.h>
#include <stdint.h>

Include dependency graph for n_astar.h:

This graph shows which files directly or indirectly include this file:

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

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

Implements the A* search algorithm for grid-based pathfinding, supporting both 2D grids (with 4 or 8 directional movement) and 3D grids (with 6 or 26 directional movement).

Designed to integrate with the isometric engine (n_iso_engine): populate an ASTAR_GRID from the MAP cell walkability data, find a path, and optionally feed the resulting waypoints into a TRAJECTORY for smooth movement.

Based on:

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

Usage (2D):

ASTAR_GRID *grid = n_astar_grid_new(width, height, 1);
n_astar_grid_set_walkable(grid, 5, 3, 0, 0);  // block cell (5,3)
ASTAR_PATH *path = n_astar_find_path(grid, 0,0,0, 9,9,0,
                                      ASTAR_ALLOW_DIAGONAL,
                                      ASTAR_HEURISTIC_CHEBYSHEV);
if (path) {
    for (int i = 0; i < path->length; i++)
        printf("(%d,%d)\n", path->nodes[i].x, path->nodes[i].y);
    n_astar_path_free(path);
}
n_astar_grid_free(grid);

Author: Castagnier Mickael

Version: 1.0

Date: 01/03/2026

Definition in file n_astar.h.

Data Structures

Macros

Enumerations

Functions

Detailed Description