include/nilorea/n_astar.h

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

Structures

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

Detailed Description

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

Author: Castagnier Mickael

Version: 1.0

Date: 01/03/2026

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);

Source code

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
 * implied. See the License for the specific language governing
 * permissions and limitations under the License.
 *
 * SPDX-License-Identifier: Apache-2.0
 */

#ifndef N_ASTAR_H
#define N_ASTAR_H

#ifdef __cplusplus
extern "C" {
#endif


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

/* Constants */

#define ASTAR_CARDINAL_ONLY 0
#define ASTAR_ALLOW_DIAGONAL 1

#define ASTAR_COST_CARDINAL 1000
#define ASTAR_COST_DIAGONAL 1414
#define ASTAR_COST_DIAGONAL3D 1732

#define ASTAR_NODE_NONE 0
#define ASTAR_NODE_OPEN 1
#define ASTAR_NODE_CLOSED 2

#ifndef ASTAR_SEARCH_MARGIN
#define ASTAR_SEARCH_MARGIN 128
#endif

/* Heuristic Types */

typedef enum {
    ASTAR_HEURISTIC_MANHATTAN = 0, 
    ASTAR_HEURISTIC_EUCLIDEAN,     
    ASTAR_HEURISTIC_CHEBYSHEV      
} ASTAR_HEURISTIC;

/* Data Structures */

typedef struct ASTAR_NODE {
    int x; 
    int y; 
    int z; 
} ASTAR_NODE;

typedef struct ASTAR_PATH {
    ASTAR_NODE* nodes; 
    int length;        
    int cost;          
} ASTAR_PATH;

typedef struct ASTAR_CELL {
    int g;          
    int h;          
    int f;          
    int parent_x;   
    int parent_y;   
    int parent_z;   
    uint8_t status; 
} ASTAR_CELL;

typedef struct ASTAR_HEAP_NODE {
    int x, y, z; 
    int f;       
} ASTAR_HEAP_NODE;

typedef struct ASTAR_HEAP {
    ASTAR_HEAP_NODE* data; 
    int size;              
    int capacity;          
} ASTAR_HEAP;

typedef struct ASTAR_GRID {
    int width;         
    int height;        
    int depth;         
    uint8_t* walkable; 
    int* cost;         
} ASTAR_GRID;

/* API Functions */

ASTAR_GRID* n_astar_grid_new(int width, int height, int depth);
void n_astar_grid_free(ASTAR_GRID* grid);
void n_astar_grid_set_walkable(ASTAR_GRID* grid, int x, int y, int z, uint8_t walkable);
uint8_t n_astar_grid_get_walkable(const ASTAR_GRID* grid, int x, int y, int z);
void n_astar_grid_set_cost(ASTAR_GRID* grid, int x, int y, int z, int cost);
int n_astar_grid_get_cost(const ASTAR_GRID* grid, int x, int y, int z);
void n_astar_grid_set_rect_blocked(ASTAR_GRID* grid,
                                   int x1,
                                   int y1,
                                   int z1,
                                   int x2,
                                   int y2,
                                   int z2);
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);
void n_astar_path_free(ASTAR_PATH* path);
int n_astar_heuristic(int x1, int y1, int z1, int x2, int y2, int z2, ASTAR_HEURISTIC heuristic);


#ifdef __cplusplus
}
#endif

#endif /* N_ASTAR_H */