[Bf-blender-cvs] [88ee44a] master: BLI: add 'A*' (AStar) shortest path solver algorithm.
Bastien Montagne
noreply at git.blender.org
Fri Jan 9 13:04:33 CET 2015
Commit: 88ee44a9ac3676db44181c5dac9bab442c2a6e1a
Author: Bastien Montagne
Date: Fri Jan 9 10:56:17 2015 +0100
Branches: master
https://developer.blender.org/rB88ee44a9ac3676db44181c5dac9bab442c2a6e1a
BLI: add 'A*' (AStar) shortest path solver algorithm.
Needed for transfer data.
===================================================================
A source/blender/blenlib/BLI_astar.h
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/intern/astar.c
===================================================================
diff --git a/source/blender/blenlib/BLI_astar.h b/source/blender/blenlib/BLI_astar.h
new file mode 100644
index 0000000..b99a253
--- /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__ */
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index c8f0e1b..fa08856 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -52,6 +52,7 @@ set(SRC
intern/BLI_memarena.c
intern/BLI_mempool.c
intern/DLRB_tree.c
+ intern/astar.c
intern/boxpack2d.c
intern/buffer.c
intern/callbacks.c
@@ -113,6 +114,7 @@ set(SRC
BLI_alloca.h
BLI_args.h
BLI_array.h
+ BLI_astar.h
BLI_bitmap.h
BLI_blenlib.h
BLI_boxpack2d.h
diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c
new file mode 100644
index 0000000..b7b41d2
--- /dev/null
+++ b/source/blender/blenlib/intern/astar.c
@@ -0,0 +1,294 @@
+/*
+ * ***** 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 *****
+ */
+
+/** \file blender/blenlib/intern/astar.c
+ * \ingroup bli
+ * \brief An implementation of the A* (AStar) algorithm to solve shortest path problem.
+ *
+ * This library implements the simple A* (AStar) algorithm, an optimized version of
+ * classical dijkstra shortest path solver. The difference is that each future possible
+ * path is weighted from its 'shortest' (smallest) possible distance to destination,
+ * in addition to distance already walked. This heuristic allows more efficiency
+ * in finding optimal path.
+ *
+ * Implementation based on Wikipedia A* page [http://en.wikipedia.org/wiki/A*_search_algorithm].
+ *
+ * Note that most memory handling here is done through two different MemArena's. Those should also be used to allocate
+ * custom data needed to a specific use of A*.
+ * The first one, owned by BLI_AStarGraph, is for 'static' data that will live as long as the graph.
+ * The second one, owned by BLI_AStarSolution, is for data used during a single path solve. It will be cleared
+ * much more often than graph's one.
+ */
+
+#include <limits.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_sys_types.h"
+#include "BLI_compiler_attrs.h"
+
+#include "BLI_alloca.h"
+#include "BLI_heap.h"
+#include "BLI_listbase.h"
+#include "BLI_math.h"
+#include "BLI_memarena.h"
+
+#include "BLI_astar.h"
+
+/**
+ * Init a node in A* graph.
+ *
+ * \param custom_data an opaque pointer attached to this link, available e.g. to cost callback function.
+ */
+void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data)
+{
+ as_graph->nodes[node_index].custom_data = custom_data;
+}
+
+/**
+ * Add a link between two nodes of our A* graph.
+ *
+ * \param cost the 'length' of the link (actual distance between two vertices or face centers e.g.).
+ * \param custom_data an opaque pointer attached to this link, available e.g. to cost callback function.
+ */
+void BLI_astar_node_link_add(
+ BLI_AStarGraph *as_graph, const int node1_index, const int node2_index, const float cost, void *custom_data)
+{
+ MemArena *mem = as_graph->mem;
+ BLI_AStarGNLink *link = BLI_memarena_alloc(mem, sizeof(*link));
+ LinkData *ld = BLI_memarena_alloc(mem, sizeof(*ld) * 2);
+
+ link->nodes[0] = node1_index;
+ link->nodes[1] = node2_index;
+ link->cost = cost;
+ link->custom_data = custom_data;
+
+ ld[0].data = ld[1].data = link;
+
+ BLI_addtail(&(as_graph->nodes[node1_index].neighbor_links), &ld[0]);
+ BLI_addtail(&(as_graph->nodes[node2_index].neighbor_links), &ld[1]);
+}
+
+/**
+ * \return The index of the other node of given link.
+ */
+int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx)
+{
+ return (lnk->nodes[0] == idx) ? lnk->nodes[1] : lnk->nodes[0];
+}
+
+/**
+ * Initialize a solution data for given A* graph. Does not compute anything!
+ *
+ * \param custom_data an opaque pointer attached to this link, available e.g. to cost callback function.
+ *
+ * \note BLI_AStarSolution stores nearly all data needed during solution compute.
+ */
+void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data)
+{
+ MemArena *mem = as_solution->mem;
+ size_t node_num = (size_t)as_graph->node_num;
+
+ if (mem == NULL) {
+ mem = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+ as_solution->mem = mem;
+ }
+ /* else memarena should be cleared */
+
+ as_solution->steps = 0;
+ as_solution->prev_nodes = BLI_memarena_alloc(mem, sizeof(*as_solution->prev_nodes) * node_num);
+ as_solution->prev_links = BLI_memarena_alloc(mem, sizeof(*as_solution->prev_links) * node_num);
+
+ as_solution->custom_data = custom_data;
+
+ as_solution->done_nodes = BLI_BITMAP_NEW_MEMARENA(mem, node_num);
+ as_solution->g_costs = BLI_memarena_alloc(mem, sizeof(*as_solution->g_costs) * node_num);
+ as_solution->g_steps = BLI_memarena_alloc(mem, sizeof(*as_solution->g_steps) * node_num);
+}
+
+/**
+ * Clear given solution's data, but does not release its memory. Avoids having to recreate/allocate
+ * a memarena in loops, e.g.
+ *
+ * \note This *has to be called* between each path solving.
+ */
+void BLI_astar_solution_clear(BLI_AStarSolution *as_solution)
+{
+ if (as_solution->mem) {
+ BLI_memarena_clear(as_solution->mem);
+ }
+
+ as_solution->steps = 0;
+ as_solution->prev_nodes = NULL;
+ as_solution->prev_links = NULL;
+
+ as_solution->custom_data = NULL;
+
+ as_solution->done_nodes = NULL;
+ as_solution->g_costs = NULL;
+ as_solution->g_steps = NULL;
+}
+
+/**
+ * Release the memory allocated for this solution.
+ */
+void BLI_astar_solution_free(BLI_AStarSolution *as_solution)
+{
+ if (as_solution->mem) {
+ BLI_memarena_free(as_solution->mem);
+ as_solution->mem = NULL;
+ }
+}
+
+/**
+ * Callback computing the current cost (distance) to next node, and the estimated overall cost to destination node
+ * (
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list