1 package cz.cuni.amis.utils.astar;
2
3 import java.util.ArrayList;
4 import java.util.Collection;
5 import java.util.HashMap;
6 import java.util.HashSet;
7 import java.util.List;
8 import java.util.Stack;
9
10 /**
11 * This class is returned by AStar.aStar().
12 * It contains results from the search as well as method for
13 * finding
14 * the path from the startNode to the goalNode.
15 *
16 * It contains all data structures the AStar is using during the work.
17 * Everything is made public here so that AStar (during work) and you (for
18 * browsing the results) may use it.
19 */
20 public class AStarResult<NODE> {
21
22 /**
23 * Used by getPath() and filled by A* algorithm (AStar.aStar()).
24 * Keys are nodes and values are 'parent-nodes' (from where we've come to the key node
25 * on the path from startNode to key-node).
26 */
27 public HashMap<NODE, NODE> previousNode = new HashMap<NODE, NODE>();
28
29 /**
30 * List of nodes which is opened -> was touched by the algorithm and are
31 * subjects of examination.
32 *
33 * Initialized by AStar.aStar()
34 */
35 public Collection<NODE> openList;
36
37 /**
38 * Nodes which were examined by the algoritm.
39 * At the end of work of AStar contains all the nodes which were examined.
40 * If AStar successful -> at least contains nodes on the shortest path from
41 * startNode to goalNode.
42 */
43 public Collection<NODE> closeList = new HashSet<NODE>();
44
45 /**
46 * Used and filled by A* algorithm (AStar.aStar()).
47 * Here we store the real cost from the startNode to the 'key'.
48 */
49 public HashMap<NODE, Integer> pathCost = new HashMap<NODE, Integer>();
50
51 /**
52 * Used and filled by A* alorithm (AStar.aStar()).
53 * Here we store estimated cost of the path from 'key' to the goal.
54 */
55 public HashMap<NODE, Integer> estimatedCost = new HashMap<NODE, Integer>();
56
57 /**
58 * Contains the number of iterations made by A* search.
59 * One iteration means evaluating of the one node ("touching" each of the neighbours)
60 * Is 0-based ... if startGoal == goalNode or startGoal then this will be 0.
61 */
62 public long interations = 0;
63
64 /**
65 * Start node of the A*.
66 */
67 public NODE startNode = null;
68
69 /**
70 * Node which was marked as a goalNode by AStarMap. (Note that you theoreticaly may have many
71 * goal nodes but A* searches only for the first one.)
72 * It's filled only if A* found the goalNoda! (success == true)
73 */
74 public NODE goalNode = null;
75
76 /**
77 * Whether goalNode was found during the A* run.
78 * If this is true then goalNode is not null.
79 */
80 public boolean success = false;
81
82 /**
83 * Used by getPath() to cache the path from startNode to goalNode once it has
84 * been found.
85 */
86 private List<NODE> path = null;
87
88 /**
89 * Used by getPath() method when creating a list of nodes (the path) from startNode
90 * to goalNode.
91 * @param node
92 * @return previous node of supplied node | null
93 */
94 public NODE getPreviousNode(NODE node){
95 if (previousNode.containsKey(node)) return previousNode.get(node);
96 else return null;
97 }
98
99 /**
100 * Assing 'previous' as an previous node for 'node' (the path from 'startNode' to 'node' goes across 'previous').
101 * @param node
102 * @param previous
103 */
104 public void putPreviousNode(NODE node, NODE previous){
105 previousNode.put(node, previous);
106 }
107
108 /**
109 * Returns cost of the path from startNode to node if the node was touched
110 * by A* algorithm (if A* was successful, then this always contains the goalNode
111 * and every node on the path).
112 *
113 * If node wasn't touched by A* algorithm, then it returns -1.
114 *
115 * @param node
116 * @return cost of the path from startNode to node
117 */
118 public int getCostToNode(NODE node){
119 if (pathCost.containsKey(node))
120 return ((Integer)pathCost.get(node)).intValue();
121 else
122 return -1;
123 }
124
125 /**
126 * Assing cost of the path from startNode to node.
127 * @param node
128 * @param cost
129 */
130 public void putCostToNode(NODE node, Integer cost){
131 pathCost.put(node, cost);
132 }
133
134 /**
135 * Returns estimated cost of the path from startNode to goal through node.
136 * If the node was touched by A* algorithm then it has this value stored here
137 * (if A* was successful, then this always contains the goalNode
138 * and every node on the path).
139 *
140 * If node wasn't touched by A* algorithm, then it returns -1.
141 *
142 * @param node
143 * @return cost of the path from startNode to node
144 */
145 public int getEstimatedCostToNode(NODE node){
146 if (estimatedCost.containsKey(node))
147 return estimatedCost.get(node);
148 else
149 return -1;
150 }
151
152 /**
153 * Assing estimated cost of the path from startNode to goalNode through node.
154 * @param node
155 * @param cost
156 */
157 public void putEstimatedCostToNode(NODE node, Integer cost){
158 estimatedCost.put(node, cost);
159 }
160
161 /**
162 * Returns the path from startNode to goalNode. (Don't change it as it's cached,
163 * if you want to alter it - then copy it :-)
164 *
165 * First item is startNode and the last item is goalNode.
166 * If startNode == goalNode then it contains only one item.
167 * For each index ... path[index] has neighbour path[index+1].
168 *
169 * If the path doesn't exist - returns null.
170 */
171 public List<NODE> getPath(){
172 if (path != null)
173 return path;
174 if (!success)
175 return null;
176
177 Stack<NODE> tempPath = new Stack<NODE>();
178 tempPath.push(goalNode);
179
180 NODE node = goalNode;
181 while (node != startNode){
182 node = getPreviousNode(node);
183 if (node == null)
184 return null; // path doesn't exist
185 tempPath.push(node);
186 }
187
188 path = new ArrayList<NODE>();
189
190 while (!tempPath.empty()){
191 path.add(tempPath.pop());
192 }
193
194 return path;
195 }
196
197 /**
198 * If the AStar succeeded then it returns the distance to the goal.
199 * Returns -1 otherwise.
200 * @return distance | -1
201 */
202 public int getDistanceToGoal(){
203 if (!this.success) return -1;
204 return ((Integer) this.pathCost.get(goalNode)).intValue();
205 }
206 }