1 package nl.tudelft.jpacman.npc.ghost;
2
3 import java.util.ArrayList;
4 import java.util.HashSet;
5 import java.util.List;
6 import java.util.Set;
7
8 import nl.tudelft.jpacman.board.Board;
9 import nl.tudelft.jpacman.board.Direction;
10 import nl.tudelft.jpacman.board.Square;
11 import nl.tudelft.jpacman.board.Unit;
12
13 /**
14 * Navigation provides utility to navigate on {@link Square}s.
15 *
16 * @author Jeroen Roosen
17 */
18 public final class Navigation {
19
20 private Navigation() {
21 }
22
23 /**
24 * Calculates the shortest path. This is done by BFS. This search ensures
25 * the traveller is allowed to occupy the squares on the way, or returns the
26 * shortest path to the square regardless of terrain if no traveller is
27 * specified.
28 *
29 * @param from
30 * The starting square.
31 * @param to
32 * The destination.
33 * @param traveller
34 * The traveller attempting to reach the destination. If
35 * traveller is set to <code>null</code>, this method will ignore
36 * terrain and find the shortest path whether it can actually be
37 * reached or not.
38 * @return The shortest path to the destination or <code>null</code> if no
39 * such path could be found. When the destination is the current
40 * square, an empty list is returned.
41 */
42 public static List<Direction> shortestPath(Square from, Square to,
43 Unit traveller) {
44 if (from.equals(to)) {
45 return new ArrayList<>();
46 }
47
48 List<Node> targets = new ArrayList<>();
49 Set<Square> visited = new HashSet<>();
50 targets.add(new Node(null, from, null));
51 while (!targets.isEmpty()) {
52 Node node = targets.remove(0);
53 Square square = node.getSquare();
54 if (square.equals(to)) {
55 return node.getPath();
56 }
57 visited.add(square);
58 addNewTargets(traveller, targets, visited, node, square);
59 }
60 return null;
61 }
62
63 private static void addNewTargets(Unit traveller, List<Node> targets,
64 Set<Square> visited, Node node, Square square) {
65 for (Direction direction : Direction.values()) {
66 Square target = square.getSquareAt(direction);
67 if (!visited.contains(target)
68 && (traveller == null || target.isAccessibleTo(traveller))) {
69 targets.add(new Node(direction, target, node));
70 }
71 }
72 }
73
74 /**
75 * Finds the nearest unit of the given type and returns its location. This
76 * method will perform a breadth first search starting from the given
77 * square.
78 *
79 * @param type
80 * The type of unit to search for.
81 * @param currentLocation
82 * The starting location for the search.
83 * @return The nearest unit of the given type, or <code>null</code> if no
84 * such unit could be found.
85 */
86 public static Unit findNearest(Class<? extends Unit> type,
87 Square currentLocation) {
88 List<Square> toDo = new ArrayList<>();
89 Set<Square> visited = new HashSet<>();
90
91 toDo.add(currentLocation);
92
93 while (!toDo.isEmpty()) {
94 Square square = toDo.remove(0);
95 Unit unit = findUnit(type, square);
96 if (unit != null) {
97 assert unit.hasSquare();
98 return unit;
99 }
100 visited.add(square);
101 for (Direction direction : Direction.values()) {
102 Square newTarget = square.getSquareAt(direction);
103 if (!visited.contains(newTarget) && !toDo.contains(newTarget)) {
104 toDo.add(newTarget);
105 }
106 }
107 }
108 return null;
109 }
110
111 /**
112 * Finds a subtype of Unit in a level.
113 * This method is very useful for finding the ghosts in the parsed map.
114 *
115 * @param clazz the type to search for.
116 * @param board the board to find the unit in.
117 * @param <T> the return type, same as the type in clazz.
118 *
119 * @return the first unit found of type clazz, or null.
120 */
121 public static <T extends Unit> T findUnitInBoard(Class<T> clazz, Board board) {
122 for (int y = 0; y < board.getHeight(); y++) {
123 for (int x = 0; x < board.getWidth(); x++) {
124 final T ghost = Navigation.findUnit(clazz, board.squareAt(x, y));
125 if (ghost != null) {
126 return ghost;
127 }
128 }
129 }
130
131 return null;
132 }
133
134 /**
135 * Determines whether a square has an occupant of a certain type.
136 *
137 * @param type
138 * The type to search for.
139 * @param square
140 * The square to search.
141 * @param <T>
142 * the type of unit we searched for.
143 *
144 * @return A unit of type T, iff such a unit occupies this square, or
145 * <code>null</code> of none does.
146 */
147 @SuppressWarnings("unchecked")
148 public static <T extends Unit> T findUnit(Class<T> type, Square square) {
149 for (Unit unit : square.getOccupants()) {
150 if (type.isInstance(unit)) {
151 assert unit.hasSquare();
152 return (T) unit;
153 }
154 }
155 return null;
156 }
157
158 /**
159 * Helper class to keep track of the path.
160 *
161 * @author Jeroen Roosen
162 */
163 private static final class Node {
164
165 /**
166 * The direction for this node, which is <code>null</code> for the root
167 * node.
168 */
169 private final Direction direction;
170
171 /**
172 * The parent node, which is <code>null</code> for the root node.
173 */
174 private final Node parent;
175
176 /**
177 * The square associated with this node.
178 */
179 private final Square square;
180
181 /**
182 * Creates a new node.
183 *
184 * @param direction
185 * The direction, which is <code>null</code> for the root
186 * node.
187 * @param square
188 * The square.
189 * @param parent
190 * The parent node, which is <code>null</code> for the root
191 * node.
192 */
193 Node(Direction direction, Square square, Node parent) {
194 this.direction = direction;
195 this.square = square;
196 this.parent = parent;
197 }
198
199 /**
200 * @return The direction for this node, or <code>null</code> if this
201 * node is a root node.
202 */
203 private Direction getDirection() {
204 return direction;
205 }
206
207 /**
208 * @return The square for this node.
209 */
210 private Square getSquare() {
211 return square;
212 }
213
214 /**
215 * @return The parent node, or <code>null</code> if this node is a root
216 * node.
217 */
218 private Node getParent() {
219 return parent;
220 }
221
222 /**
223 * Returns the list of values from the root of the tree to this node.
224 *
225 * @return The list of values from the root of the tree to this node.
226 */
227 private List<Direction> getPath() {
228 if (parent == null) {
229 return new ArrayList<>();
230 }
231 List<Direction> path = parent.getPath();
232 path.add(getDirection());
233 return path;
234 }
235 }
236 }