Blender
V3.3
|
An implementation of the A* (AStar) algorithm to solve shortest path problem. More...
Go to the source code of this file.
Classes | |
struct | BLI_AStarGNLink |
struct | BLI_AStarGNode |
struct | BLI_AStarSolution |
struct | BLI_AStarGraph |
Typedefs | |
typedef struct BLI_AStarGNLink | BLI_AStarGNLink |
typedef struct BLI_AStarGNode | BLI_AStarGNode |
typedef struct BLI_AStarSolution | BLI_AStarSolution |
typedef struct BLI_AStarGraph | BLI_AStarGraph |
typedef float(* | astar_f_cost) (BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, int node_idx_curr, int node_idx_next, int node_idx_dst) |
Functions | |
void | BLI_astar_node_init (BLI_AStarGraph *as_graph, int node_index, void *custom_data) |
void | BLI_astar_node_link_add (BLI_AStarGraph *as_graph, int node1_index, int node2_index, float cost, void *custom_data) |
int | BLI_astar_node_link_other_node (BLI_AStarGNLink *lnk, 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, int node_num, void *custom_data) |
void | BLI_astar_graph_free (BLI_AStarGraph *as_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) |
An implementation of the A* (AStar) algorithm to solve shortest path problem.
Definition in file BLI_astar.h.
typedef float(* astar_f_cost) (BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, BLI_AStarGNLink *link, int node_idx_curr, int node_idx_next, int node_idx_dst) |
Callback computing the current cost (distance) to next node, and the estimated overall cost to destination node (A* expects this estimation to always be less or equal than actual shortest path from next node to destination one).
link | the graph link between current node and next one. |
node_idx_curr | current node index. |
node_idx_next | next node index. |
node_idx_dst | destination node index. |
Definition at line 119 of file BLI_astar.h.
typedef struct BLI_AStarGNLink BLI_AStarGNLink |
typedef struct BLI_AStarGNode BLI_AStarGNode |
typedef struct BLI_AStarGraph BLI_AStarGraph |
typedef struct BLI_AStarSolution BLI_AStarSolution |
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().