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

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

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

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 122 of file BLI_astar.h.

◆ BLI_AStarGNLink

typedef struct BLI_AStarGNLink BLI_AStarGNLink

◆ BLI_AStarGNode

typedef struct BLI_AStarGNode BLI_AStarGNode

◆ BLI_AStarGraph

typedef struct BLI_AStarGraph BLI_AStarGraph

◆ BLI_AStarSolution

typedef struct BLI_AStarSolution BLI_AStarSolution

Function Documentation

◆ BLI_astar_graph_free()

void BLI_astar_graph_free ( BLI_AStarGraph * as_graph )

Definition at line 137 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_data an opaque pointer attached to this link, available e.g. to cost callback function.

Definition at line 121 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_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.

Returns: true if a path was found, false otherwise.

Definition at line 145 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, FLT_MAX, 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_data an opaque pointer attached to this link, available e.g. to cost callback function.

Definition at line 41 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

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