n_astar.h

Go to the documentation of this file.

/*
 * 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 */