Blender  V3.3
Functions
astar.c File Reference

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)
 

Detailed Description

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.

Function Documentation

◆ BLI_astar_graph_free()

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().

◆ BLI_astar_graph_init()

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.

Parameters
custom_dataan 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().

◆ BLI_astar_graph_solve()

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.

Parameters
max_stepsmaximum number of nodes the found path may have. Useful in performance-critical usages. If no path is found within given steps, returns false too.
Returns
true if a path was found, false otherwise.

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().

◆ BLI_astar_node_init()

void BLI_astar_node_init ( BLI_AStarGraph as_graph,
int  node_index,
void custom_data 
)

Initialize a node in A* graph.

Parameters
custom_dataan 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().

◆ BLI_astar_node_link_add()

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.

Parameters
costThe 'length' of the link (actual distance between two vertices or face centers e.g.).
custom_dataAn 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().

◆ BLI_astar_node_link_other_node()

int BLI_astar_node_link_other_node ( BLI_AStarGNLink lnk,
int  idx 
)
Returns
The index of the other node of given link.

Definition at line 66 of file astar.c.

References BLI_AStarGNLink::nodes.

Referenced by BLI_astar_graph_solve().

◆ BLI_astar_solution_clear()

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.

Note
This has to be called between each path solving.

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().

◆ BLI_astar_solution_free()

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().

◆ BLI_astar_solution_init()

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!

Parameters
custom_dataan opaque pointer attached to this link, available e.g . to cost callback function.
Note
BLI_AStarSolution stores nearly all data needed during solution compute.

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().