summaryrefslogtreecommitdiff
path: root/digital/avr/modules/path/astar/astar.h
blob: 873ffba01c54ae5c409688f235f17ff7ce9fd7ac (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#ifndef astar_h
#define astar_h
/* astar.h */
/* avr.path.astar - A* path finding module. {{{
 *
 * Copyright (C) 2010 Nicolas Schodet
 *
 * APBTeam:
 *        Web: http://apbteam.org/
 *      Email: team AT apbteam DOT org
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 * }}} */

/** Used instead of score for a unvisited node. */
#define ASTAR_NODE_SCORE_UNVISITED ((uint16_t) 0xffff)
/** Used instead of score for a node in the closed set. */
#define ASTAR_NODE_SCORE_CLOSED ((uint16_t) 0xfffe)
/** Test whether a node is in the open set. */
#define ASTAR_NODE_SCORE_OPEN(score) ((score) < ASTAR_NODE_SCORE_CLOSED)

/** Node information.  Instantiated by the client in an array to store
 * information on every nodes in the graph. */
struct astar_node_t
{
    /** Previous node in path. */
    uint8_t prev;
    /** Score of this node (often named g(x) in A* literature),
     * ASTAR_NODE_SCORE_UNVISITED if unvisited, or ASTAR_NODE_SCORE_CLOSED if
     * in the closed set.  Score is the sum of all weights from the initial
     * node to this node.  Every nodes with a score are in the open set. */
    uint16_t score;
    /** Heuristic weight from this node to the goal (often named h(x) in A*
     * literature).  It will be computed only once, so this is initialised to
     * 0 and set using a user provided function. */
    uint16_t heuristic;
};

/** Information filled by the user neighbor callback. */
struct astar_neighbor_t
{
    /** Neighbor node to inspect. */
    uint8_t node;
    /** Weight of the arc between the requested node and this neighbor
     * node. */
    uint16_t weight;
};

/** Neighbor callback.
 * - node: currently inspected node.
 * - neighbors: array to be filled by this callback.
 * - returns: number of neighbors.
 * This callback is to be provided by the user.  It should fill the neighbor
 * array with all neighbors reachable from the requested node. */
uint8_t
AC_ASTAR_NEIGHBOR_CALLBACK (uint8_t node, struct astar_neighbor_t *neighbors);

/** Heuristic callback.
 * - node: considered node.
 * - returns: heuristic weight from the considered node to the goal.
 * This callback is to be provided by the user.  This should be an optimistic
 * heuristic or A* may not found the best path. */
uint16_t
AC_ASTAR_HEURISTIC_CALLBACK (uint8_t node);

/** A* algorithm.
 * - nodes: array of all nodes.
 * - nodes_nb: number of nodes.
 * - initial: initial node index.
 * - goal: goal node index.
 * - returns: non zero if a path is found.
 * If a path is found, user can extract the found path by following the prev
 * member, starting from the goal node.
 *
 * It may be more convenient to invert initial and goal so that the path can
 * be followed from the starting point to the destination point instead of the
 * other way round. */
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 */