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