diff options
Diffstat (limited to 'source/blender/blenlib/BLI_astar.h')
-rw-r--r-- | source/blender/blenlib/BLI_astar.h | 50 |
1 files changed, 50 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_astar.h b/source/blender/blenlib/BLI_astar.h index fe5c4ddad69..a1d4e28dad9 100644 --- a/source/blender/blenlib/BLI_astar.h +++ b/source/blender/blenlib/BLI_astar.h @@ -76,18 +76,52 @@ typedef struct BLI_AStarGraph { struct MemArena *mem; /* Memory arena. */ } BLI_AStarGraph; +/** + * Initialize a node in A* graph. + * + * \param custom_data: an opaque pointer attached to this link, + * available e.g. to cost callback function. + */ void BLI_astar_node_init(BLI_AStarGraph *as_graph, const int node_index, void *custom_data); +/** + * Add a link between two nodes of our A* graph. + * + * \param cost: The 'length' of the link + * (actual distance between two vertices or face centers e.g.). + * \param custom_data: An opaque pointer attached to this link, + * available e.g. to cost callback function. + */ void BLI_astar_node_link_add(BLI_AStarGraph *as_graph, const int node1_index, const int node2_index, const float cost, void *custom_data); +/** + * \return The index of the other node of given link. + */ int BLI_astar_node_link_other_node(BLI_AStarGNLink *lnk, const int idx); +/** + * Initialize a solution data for given A* graph. Does not compute anything! + * + * \param custom_data: an opaque pointer attached to this link, available e.g + * . to cost callback function. + * + * \note BLI_AStarSolution stores nearly all data needed during solution compute. + */ void BLI_astar_solution_init(BLI_AStarGraph *as_graph, BLI_AStarSolution *as_solution, void *custom_data); +/** + * 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. + */ void BLI_astar_solution_clear(BLI_AStarSolution *as_solution); +/** + * Release the memory allocated for this solution. + */ void BLI_astar_solution_free(BLI_AStarSolution *as_solution); /** @@ -108,8 +142,24 @@ typedef float (*astar_f_cost)(BLI_AStarGraph *as_graph, const int node_idx_next, const int node_idx_dst); +/** + * Initialize an A* graph. Total number of nodes must be known. + * + * Nodes might be e.g. vertices, faces, ... etc. + * + * \param custom_data: an opaque pointer attached to this link, + * available e.g. to cost callback function. + */ void BLI_astar_graph_init(BLI_AStarGraph *as_graph, const int node_num, void *custom_data); void BLI_astar_graph_free(BLI_AStarGraph *as_graph); +/** + * Solve a path in given graph, using given 'cost' callback function. + * + * \param 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. + * \return true if a path was found, false otherwise. + */ bool BLI_astar_graph_solve(BLI_AStarGraph *as_graph, const int node_index_src, const int node_index_dst, |