n_astar.h

Go to the documentation of this file.

/*
 * Nilorea Library
 * Copyright (C) 2005-2026 Castagnier Mickael
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */
 
#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
 
/*---------------------------------------------------------------------------
 * 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 */