46 const int node1_index,
47 const int node2_index,
55 link->
nodes[0] = node1_index;
56 link->
nodes[1] = node2_index;
76 size_t node_num = (size_t)as_graph->
node_num;
80 as_solution->
mem = mem;
84 as_solution->
steps = 0;
97 if (as_solution->
mem) {
101 as_solution->
steps = 0;
114 if (as_solution->
mem) {
145 const int node_index_src,
146 const int node_index_dst,
156 float *g_costs = r_solution->
g_costs;
157 int *g_steps = r_solution->
g_steps;
159 r_solution->
steps = 0;
160 prev_nodes[node_index_src] = -1;
163 g_costs[node_index_src] = 0.0f;
164 g_steps[node_index_src] = 0;
166 if (node_index_src == node_index_dst) {
172 f_cost_cb(as_graph, r_solution,
NULL, -1, node_index_src, node_index_dst),
187 if (max_steps && g_steps[node_curr_idx] > max_steps) {
191 if (node_curr_idx == node_index_dst) {
193 r_solution->
steps = g_steps[node_curr_idx] + 1;
206 float g_cst = g_costs[node_curr_idx] + link->
cost;
208 if (g_cst < g_costs[node_next_idx]) {
209 prev_nodes[node_next_idx] = node_curr_idx;
210 prev_links[node_next_idx] = link;
211 g_costs[node_next_idx] = g_cst;
212 g_steps[node_next_idx] = g_steps[node_curr_idx] + 1;
217 f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst),
An implementation of the A* (AStar) algorithm to solve shortest path problem.
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)
#define BLI_BITMAP_TEST(_bitmap, _index)
#define BLI_BITMAP_ENABLE(_bitmap, _index)
#define BLI_BITMAP_NEW_MEMARENA(_mem, _num)
void BLI_bitmap_set_all(BLI_bitmap *bitmap, bool set, size_t bits)
A min-heap / priority queue ADT.
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
void BLI_addtail(struct ListBase *listbase, void *vlink) ATTR_NONNULL(1)
void copy_vn_fl(float *array_tar, int size, float val)
void BLI_memarena_free(struct MemArena *ma) ATTR_NONNULL(1)
struct MemArena * BLI_memarena_new(size_t bufsize, const char *name) ATTR_WARN_UNUSED_RESULT ATTR_RETURNS_NONNULL ATTR_NONNULL(2) ATTR_MALLOC
#define BLI_MEMARENA_STD_BUFSIZE
void * BLI_memarena_alloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
void void BLI_memarena_clear(MemArena *ma) ATTR_NONNULL(1)
void * BLI_memarena_calloc(struct MemArena *ma, size_t size) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1) ATTR_MALLOC ATTR_ALLOC_SIZE(2)
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
Read Guarded memory(de)allocation.
void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data)
void BLI_astar_solution_clear(BLI_AStarSolution *as_solution)
void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data)
void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, 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)
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)
void BLI_astar_solution_free(BLI_AStarSolution *as_solution)
void BLI_astar_graph_free(BLI_AStarGraph *as_graph)
int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx)
struct ListBase neighbor_links
BLI_AStarGNLink ** prev_links