|
Blender V5.3
|
An implementation of the A* (AStar) algorithm to solve shortest path problem. More...
#include <algorithm>#include "BLI_sys_types.hh"#include "BLI_heap_simple.hh"#include "BLI_listbase.hh"#include "BLI_math_vector_c.hh"#include "BLI_memarena.hh"#include "BLI_astar.hh"Go to the source code of this file.
Namespaces | |
| namespace | blender |
| BMesh Iterators. | |
Functions | |
| void | blender::BLI_astar_node_init (BLI_AStarGraph *as_graph, int node_index, void *custom_data) |
| void | blender::BLI_astar_node_link_add (BLI_AStarGraph *as_graph, int node1_index, int node2_index, float cost, void *custom_data) |
| int | blender::BLI_astar_node_link_other_node (BLI_AStarGNLink *lnk, int idx) |
| void | blender::BLI_astar_solution_init (BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data) |
| void | blender::BLI_astar_solution_clear (BLI_AStarSolution *as_solution) |
| void | blender::BLI_astar_solution_free (BLI_AStarSolution *as_solution) |
| void | blender::BLI_astar_graph_init (BLI_AStarGraph *as_graph, int node_num, void *custom_data) |
| void | blender::BLI_astar_graph_free (BLI_AStarGraph *as_graph) |
| bool | blender::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) |
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.cc.