View Javadoc

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 algoritm.
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 }