Blender V5.3
astar.cc File Reference

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)

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