diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2015-01-09 12:56:17 +0300 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2015-01-09 15:03:55 +0300 |
commit | 88ee44a9ac3676db44181c5dac9bab442c2a6e1a (patch) | |
tree | 463929a7a141f7a1f227db6aa3b1eac915e12e9d /source/blender/blenlib/BLI_astar.h | |
parent | 2f16098d208058dce7701d6e49ed9052445553f5 (diff) |
BLI: add 'A*' (AStar) shortest path solver algorithm.
Needed for transfer data.
Diffstat (limited to 'source/blender/blenlib/BLI_astar.h')
-rw-r--r-- | source/blender/blenlib/BLI_astar.h | 98 |
1 files changed, 98 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_astar.h b/source/blender/blenlib/BLI_astar.h new file mode 100644 index 00000000000..b99a2534d33 --- /dev/null +++ b/source/blender/blenlib/BLI_astar.h @@ -0,0 +1,98 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * 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 2 + * 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, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * The Original Code is Copyright (C) 2014 Blender Foundation. + * All rights reserved. + * + * The Original Code is: all of this file. + * + * Contributor(s): Bastien Montagne. + * + * ***** END GPL LICENSE BLOCK ***** + */ + +#ifndef __BLI_ASTAR_H__ +#define __BLI_ASTAR_H__ + +/** \file BLI_astar.h + * \ingroup bli + * \brief An implementation of the A* (AStar) algorithm to solve shortest path problem. + */ + +#include "BLI_utildefines.h" + +#include "BLI_bitmap.h" + +/* -------------------------------------------------------------------- */ + +typedef struct BLI_AStarGNLink { + int nodes[2]; + float cost; + + void *custom_data; +} BLI_AStarGNLink; + +typedef struct BLI_AStarGNode { + struct ListBase neighbor_links; + + void *custom_data; +} BLI_AStarGNode; + +typedef struct BLI_AStarSolution { + /* Final 'most useful' data. */ + int steps; /* Number of steps (i.e. walked links) in path (nodes num, including start and end, is steps + 1). */ + int *prev_nodes; /* Store the path, in reversed order (from destination to source node), as indices. */ + BLI_AStarGNLink **prev_links; /* Indices are nodes' ones, as prev_nodes, but they map to relevant link. */ + + void *custom_data; + + /* Mostly runtime data. */ + BLI_bitmap *done_nodes; + float *g_costs; + int *g_steps; + + struct MemArena *mem; /* Memory arena. */ +} BLI_AStarSolution; + +typedef struct BLI_AStarGraph { + int node_num; + BLI_AStarGNode *nodes; + + void *custom_data; + + struct MemArena *mem; /* Memory arena. */ +} BLI_AStarGraph; + +void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data); +void BLI_astar_node_link_add( + BLI_AStarGraph *as_graph, const int node1_index, const int node2_index, const float cost, void *custom_data); +int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx); + +void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data); +void BLI_astar_solution_clear(BLI_AStarSolution *as_solution); +void BLI_astar_solution_free(BLI_AStarSolution *as_solution); + +typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, + const int node_idx_curr, const int node_idx_next, const int node_idx_dst); + +void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data); +void BLI_astar_graph_free(BLI_AStarGraph *as_graph); +bool BLI_astar_graph_solve( + BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, astar_f_cost f_cost_cb, + BLI_AStarSolution *r_solution, const int max_steps); + +#endif /* __BLI_ASTAR_H__ */ |