Blender  V3.3
Classes | Typedefs | Functions
BLI_astar.h File Reference

An implementation of the A* (AStar) algorithm to solve shortest path problem. More...

#include "BLI_utildefines.h"
#include "BLI_bitmap.h"

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)
 

Detailed Description

An implementation of the A* (AStar) algorithm to solve shortest path problem.

Definition in file BLI_astar.h.

Typedef Documentation

◆ astar_f_cost

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

Parameters
linkthe graph link between current node and next one.
node_idx_currcurrent node index.
node_idx_nextnext node index.
node_idx_dstdestination node index.

Definition at line 119 of file BLI_astar.h.

◆ BLI_AStarGNLink

◆ BLI_AStarGNode

◆ BLI_AStarGraph

◆ BLI_AStarSolution

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