Average Density: 0.07
  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 }