Blender
V3.3
|
An implementation of the A* (AStar) algorithm to solve shortest path problem. More...
#include <limits.h>
#include "MEM_guardedalloc.h"
#include "BLI_compiler_attrs.h"
#include "BLI_sys_types.h"
#include "BLI_heap_simple.h"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_memarena.h"
#include "BLI_astar.h"
Go to the source code of this file.
Functions | |
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) |
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) |
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: https://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.
Definition in file astar.c.
void BLI_astar_graph_free | ( | BLI_AStarGraph * | as_graph | ) |
Definition at line 136 of file astar.c.
References BLI_memarena_free(), BLI_AStarGraph::mem, and NULL.
Referenced by BKE_mesh_remap_calc_loops_from_mesh().
void BLI_astar_graph_init | ( | BLI_AStarGraph * | as_graph, |
int | node_num, | ||
void * | custom_data | ||
) |
Initialize an A* graph. Total number of nodes must be known.
Nodes might be e.g. vertices, faces, ... etc.
custom_data | an opaque pointer attached to this link, available e.g. to cost callback function. |
Definition at line 120 of file astar.c.
References BLI_memarena_calloc(), BLI_memarena_new(), BLI_MEMARENA_STD_BUFSIZE, BLI_AStarGraph::custom_data, BLI_AStarGraph::mem, BLI_AStarGraph::node_num, BLI_AStarGraph::nodes, and NULL.
Referenced by mesh_island_to_astar_graph().
bool BLI_astar_graph_solve | ( | BLI_AStarGraph * | as_graph, |
int | node_index_src, | ||
int | node_index_dst, | ||
astar_f_cost | f_cost_cb, | ||
BLI_AStarSolution * | r_solution, | ||
int | max_steps | ||
) |
Solve a path in given graph, using given 'cost' callback function.
max_steps | maximum number of nodes the found path may have. Useful in performance-critical usages. If no path is found within given steps, returns false too. |
Definition at line 144 of file astar.c.
References BLI_astar_node_link_other_node(), BLI_BITMAP_ENABLE, BLI_bitmap_set_all(), BLI_BITMAP_TEST, BLI_heapsimple_free(), BLI_heapsimple_insert(), BLI_heapsimple_is_empty(), BLI_heapsimple_new(), BLI_heapsimple_pop_min(), copy_vn_fl(), BLI_AStarGNLink::cost, LinkData::data, BLI_AStarSolution::done_nodes, ListBase::first, BLI_AStarSolution::g_costs, BLI_AStarSolution::g_steps, BLI_AStarGNode::neighbor_links, LinkData::next, BLI_AStarGraph::node_num, BLI_AStarGraph::nodes, NULL, POINTER_AS_INT, POINTER_FROM_INT, BLI_AStarSolution::prev_links, BLI_AStarSolution::prev_nodes, and BLI_AStarSolution::steps.
Referenced by BKE_mesh_remap_calc_loops_from_mesh().
void BLI_astar_node_init | ( | BLI_AStarGraph * | as_graph, |
int | node_index, | ||
void * | custom_data | ||
) |
Initialize a node in A* graph.
custom_data | an opaque pointer attached to this link, available e.g. to cost callback function. |
Definition at line 40 of file astar.c.
References BLI_AStarGNode::custom_data, and BLI_AStarGraph::nodes.
Referenced by mesh_island_to_astar_graph_edge_process().
void BLI_astar_node_link_add | ( | BLI_AStarGraph * | as_graph, |
int | node1_index, | ||
int | node2_index, | ||
float | cost, | ||
void * | custom_data | ||
) |
Add a link between two nodes of our A* graph.
cost | The 'length' of the link (actual distance between two vertices or face centers e.g.). |
custom_data | An opaque pointer attached to this link, available e.g. to cost callback function. |
Definition at line 45 of file astar.c.
References BLI_addtail(), BLI_memarena_alloc(), BLI_AStarGNLink::cost, BLI_AStarGNLink::custom_data, LinkData::data, BLI_AStarGraph::mem, BLI_AStarGNode::neighbor_links, BLI_AStarGNLink::nodes, and BLI_AStarGraph::nodes.
Referenced by mesh_island_to_astar_graph_edge_process().
int BLI_astar_node_link_other_node | ( | BLI_AStarGNLink * | lnk, |
int | idx | ||
) |
Definition at line 66 of file astar.c.
References BLI_AStarGNLink::nodes.
Referenced by BLI_astar_graph_solve().
void BLI_astar_solution_clear | ( | BLI_AStarSolution * | as_solution | ) |
Clear given solution's data, but does not release its memory. Avoids having to recreate/allocate a memarena in loops, e.g.
Definition at line 95 of file astar.c.
References BLI_memarena_clear(), BLI_AStarSolution::custom_data, BLI_AStarSolution::done_nodes, BLI_AStarSolution::g_costs, BLI_AStarSolution::g_steps, BLI_AStarSolution::mem, NULL, BLI_AStarSolution::prev_links, BLI_AStarSolution::prev_nodes, and BLI_AStarSolution::steps.
Referenced by BKE_mesh_remap_calc_loops_from_mesh().
void BLI_astar_solution_free | ( | BLI_AStarSolution * | as_solution | ) |
Release the memory allocated for this solution.
Definition at line 112 of file astar.c.
References BLI_memarena_free(), BLI_AStarSolution::mem, and NULL.
Referenced by BKE_mesh_remap_calc_loops_from_mesh().
void BLI_astar_solution_init | ( | BLI_AStarGraph * | as_graph, |
BLI_AStarSolution * | as_solution, | ||
void * | custom_data | ||
) |
Initialize a solution data for given A* graph. Does not compute anything!
custom_data | an opaque pointer attached to this link, available e.g . to cost callback function. |
Definition at line 71 of file astar.c.
References BLI_BITMAP_NEW_MEMARENA, BLI_memarena_alloc(), BLI_memarena_new(), BLI_MEMARENA_STD_BUFSIZE, BLI_AStarSolution::custom_data, BLI_AStarSolution::done_nodes, BLI_AStarSolution::g_costs, BLI_AStarSolution::g_steps, if(), BLI_AStarSolution::mem, BLI_AStarGraph::node_num, NULL, BLI_AStarSolution::prev_links, BLI_AStarSolution::prev_nodes, and BLI_AStarSolution::steps.
Referenced by BKE_mesh_remap_calc_loops_from_mesh().