diff options
author | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 19:14:40 +0300 |
---|---|---|
committer | Alexander Gavrilov <angavrilov@gmail.com> | 2018-11-05 20:49:17 +0300 |
commit | fee6ab18e7e9a38203bf8eb95d114ac837578aa7 (patch) | |
tree | 8dc1830ce6dabf781e8d0c2d709db76fab1fd1b9 /source/blender/blenlib/intern/astar.c | |
parent | a120b120ce380017324e982c2277cb8fca52f39d (diff) |
BLI_heap: implement a limited but faster version of heap.
If the user only needs insertion and removal from top, there is
no need to allocate and manage separate HeapNode objects: the
data can be stored directly in the main tree array.
This measured a 24% FPS increase on a ~50% heap-heavy workload.
Reviewers: brecht
Differential Revision: https://developer.blender.org/D3898
Diffstat (limited to 'source/blender/blenlib/intern/astar.c')
-rw-r--r-- | source/blender/blenlib/intern/astar.c | 24 |
1 files changed, 12 insertions, 12 deletions
diff --git a/source/blender/blenlib/intern/astar.c b/source/blender/blenlib/intern/astar.c index 86c1faad096..54c80def972 100644 --- a/source/blender/blenlib/intern/astar.c +++ b/source/blender/blenlib/intern/astar.c @@ -206,7 +206,7 @@ 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) { - Heap *todo_nodes; + FastHeap *todo_nodes; BLI_bitmap *done_nodes = r_solution->done_nodes; int *prev_nodes = r_solution->prev_nodes; @@ -225,13 +225,13 @@ bool BLI_astar_graph_solve( return true; } - todo_nodes = BLI_heap_new(); - BLI_heap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), - POINTER_FROM_INT(node_index_src)); + todo_nodes = BLI_fastheap_new(); + BLI_fastheap_insert(todo_nodes, + f_cost_cb(as_graph, r_solution, NULL, -1, node_index_src, node_index_dst), + POINTER_FROM_INT(node_index_src)); - while (!BLI_heap_is_empty(todo_nodes)) { - const int node_curr_idx = POINTER_AS_INT(BLI_heap_pop_min(todo_nodes)); + while (!BLI_fastheap_is_empty(todo_nodes)) { + const int node_curr_idx = POINTER_AS_INT(BLI_fastheap_pop_min(todo_nodes)); BLI_AStarGNode *node_curr = &as_graph->nodes[node_curr_idx]; LinkData *ld; @@ -249,7 +249,7 @@ bool BLI_astar_graph_solve( /* Success! Path found... */ r_solution->steps = g_steps[node_curr_idx] + 1; - BLI_heap_free(todo_nodes, NULL); + BLI_fastheap_free(todo_nodes, NULL); return true; } @@ -269,14 +269,14 @@ bool BLI_astar_graph_solve( g_steps[node_next_idx] = g_steps[node_curr_idx] + 1; /* We might have this node already in heap, but since this 'instance' will be evaluated first, * no problem. */ - BLI_heap_insert(todo_nodes, - f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), - POINTER_FROM_INT(node_next_idx)); + BLI_fastheap_insert(todo_nodes, + f_cost_cb(as_graph, r_solution, link, node_curr_idx, node_next_idx, node_index_dst), + POINTER_FROM_INT(node_next_idx)); } } } } - BLI_heap_free(todo_nodes, NULL); + BLI_fastheap_free(todo_nodes, NULL); return false; } |