From 2692a63cd1b58b3f6ad90cf7541b0843fd799164 Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Mon, 28 May 2012 23:19:24 +0200 Subject: digital/avr/modules/path/astar: new algorithm to evaluate many goals --- digital/avr/modules/path/astar/astar.h | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'digital/avr/modules/path/astar/astar.h') diff --git a/digital/avr/modules/path/astar/astar.h b/digital/avr/modules/path/astar/astar.h index ee82b2cc..873ffba0 100644 --- a/digital/avr/modules/path/astar/astar.h +++ b/digital/avr/modules/path/astar/astar.h @@ -92,4 +92,30 @@ uint8_t astar (struct astar_node_t *nodes, uint8_t nodes_nb, uint8_t initial, uint8_t goal); +/** Not A* algorithm, to be used when a large number of goals must be tested. + * - nodes: array of all nodes. + * - nodes_nb: number of nodes. + * - initial: initial node index. + * - goal: goal node index, this node is not ready yet. + * + * This function will prepare nodes so that a large number of goal can be + * tested using the astar_dijkstra_finish function. The goal node is never + * inspected as it is not supposed to be ready yet. + * + * This is not using the A* algorithm, but put here anyway as it uses the same + * structures and callbacks. */ +void +astar_dijkstra_prepare (struct astar_node_t *nodes, uint8_t nodes_nb, + uint8_t initial, uint8_t goal); + +/** Not A* algorithm, to be called after astar_dijkstra_prepare to get the + * weight of the path to the goal node in a efficient way when a large number + * of goals must be tested. + * - nodes: array of all nodes. + * - nodes_nb: number of nodes. + * - goal: goal node index. */ +uint16_t +astar_dijkstra_finish (struct astar_node_t *nodes, uint8_t nodes_nb, + uint8_t goal); + #endif /* astar_h */ -- cgit v1.2.3