1 /* 2 * This program is free software; you can redistribute it and/or 3 * modify it under the terms of the GNU General Public License 4 * as published by the Free Software Foundation; either version 2 5 * of the License, or (at your option) any later version. 6 * 7 * This program is distributed in the hope that it will be useful, 8 * but WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * GNU General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program; if not, write to the Free Software Foundation, 14 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 15 * 16 * The Original Code is Copyright (C) 2014 Blender Foundation. 17 * All rights reserved. 18 */ 19 20 #pragma once 21 22 /** \file 23 * \ingroup bli 24 * \brief An implementation of the A* (AStar) algorithm to solve shortest path problem. 25 */ 26 27 #include "BLI_utildefines.h" 28 29 #include "BLI_bitmap.h" 30 31 #ifdef __cplusplus 32 extern "C" { 33 #endif 34 35 /* -------------------------------------------------------------------- */ 36 37 typedef struct BLI_AStarGNLink { 38 int nodes[2]; 39 float cost; 40 41 void *custom_data; 42 } BLI_AStarGNLink; 43 44 typedef struct BLI_AStarGNode { 45 struct ListBase neighbor_links; 46 47 void *custom_data; 48 } BLI_AStarGNode; 49 50 typedef struct BLI_AStarSolution { 51 /* Final 'most useful' data. */ 52 /** Number of steps (i.e. walked links) in path 53 * (nodes num, including start and end, is steps + 1). */ 54 int steps; 55 /** Store the path, in reversed order (from destination to source node), as indices. */ 56 int *prev_nodes; 57 /** Indices are nodes' ones, as prev_nodes, but they map to relevant link. */ 58 BLI_AStarGNLink **prev_links; 59 60 void *custom_data; 61 62 /* Mostly runtime data. */ 63 BLI_bitmap *done_nodes; 64 float *g_costs; 65 int *g_steps; 66 67 struct MemArena *mem; /* Memory arena. */ 68 } BLI_AStarSolution; 69 70 typedef struct BLI_AStarGraph { 71 int node_num; 72 BLI_AStarGNode *nodes; 73 74 void *custom_data; 75 76 struct MemArena *mem; /* Memory arena. */ 77 } BLI_AStarGraph; 78 79 void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data); 80 void BLI_astar_node_link_add(BLI_AStarGraph *as_graph, 81 const int node1_index, 82 const int node2_index, 83 const float cost, 84 void *custom_data); 85 int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx); 86 87 void BLI_astar_solution_init(BLI_AStarGraph *as_graph, 88 BLI_AStarSolution *as_solution, 89 void *custom_data); 90 void BLI_astar_solution_clear(BLI_AStarSolution *as_solution); 91 void BLI_astar_solution_free(BLI_AStarSolution *as_solution); 92 93 /** 94 * Callback computing the current cost (distance) to next node, 95 * and the estimated overall cost to destination node 96 * (A* expects this estimation to always be less or equal than actual shortest path 97 * from next node to destination one). 98 * 99 * \param link: the graph link between current node and next one. 100 * \param node_idx_curr: current node index. 101 * \param node_idx_next: next node index. 102 * \param node_idx_dst: destination node index. 103 */ 104 typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, 105 BLI_AStarSolution *as_solution, 106 BLI_AStarGNLink *link, 107 const int node_idx_curr, 108 const int node_idx_next, 109 const int node_idx_dst); 110 111 void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data); 112 void BLI_astar_graph_free(BLI_AStarGraph *as_graph); 113 bool BLI_astar_graph_solve(BLI_AStarGraph *as_graph, 114 const int node_index_src, 115 const int node_index_dst, 116 astar_f_cost f_cost_cb, 117 BLI_AStarSolution *r_solution, 118 const int max_steps); 119 120 #ifdef __cplusplus 121 } 122 #endif 123