Path finding classes for day 15

SimonBaars · SimonBaars · commit 41f686caba37 · 2019-12-15T13:49:55.000+01:00
diff --git a/src/main/java/com/sbaars/adventofcode2019/pathfinding/Grid2d.java b/src/main/java/com/sbaars/adventofcode2019/pathfinding/Grid2d.java
@@ -0,0 +1,127 @@
+package com.sbaars.adventofcode2019.pathfinding;
+
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Creates nodes and neighbours from a 2d grid. Each point in the map has an
+ * integer value that specifies the cost of crossing that point. If this value
+ * is negative, the point is unreachable.
+ * 
+ * If diagonal movement is allowed, the Chebyshev distance is used, else
+ * Manhattan distance is used.
+ * 
+ * @author Ben Ruijl
+ * 
+ */
+public class Grid2d {
+	private final double[][] map;
+	private final boolean allowDiagonal;
+
+	/**
+	 * A node in a 2d map. This is simply the coordinates of the point.
+	 * 
+	 * @author Ben Ruijl
+	 * 
+	 */
+	public class MapNode implements Node<MapNode> {
+		private final int x, y;
+
+		public MapNode(int x, int y) {
+			this.x = x;
+			this.y = y;
+		}
+
+		public double getHeuristic(MapNode goal) {
+			if (allowDiagonal) {
+				return Math.max(Math.abs(x - goal.x), Math.abs(y - goal.y));
+			} else {
+				return Math.abs(x - goal.x) + Math.abs(y - goal.y);
+			}
+		}
+
+		public double getTraversalCost(MapNode neighbour) {
+			return 1 + map[neighbour.y][neighbour.x];
+		}
+
+		public Set<MapNode> getNeighbours() {
+			Set<MapNode> neighbours = new HashSet<MapNode>();
+
+			for (int i = x - 1; i <= x + 1; i++) {
+				for (int j = y - 1; j <= y + 1; j++) {
+					if ((i == x && j == y) || i < 0 || j < 0 || j >= map.length
+							|| i >= map[j].length) {
+						continue;
+					}
+
+					if (!allowDiagonal &&
+					         ((i < x && j < y) ||
+					                 (i < x && j > y) ||
+					                 (i > x && j > y) ||
+					                 (i > x && j < y))) {
+						continue;
+					}
+
+					if (map[j][i] == 1) {
+						continue;
+					}
+
+					// TODO: create cache instead of recreation
+					neighbours.add(new MapNode(i, j));
+				}
+			}
+
+			return neighbours;
+		}
+
+		@Override
+		public String toString() {
+			return "(" + x + ", " + y + ")";
+		}
+
+		@Override
+		public int hashCode() {
+			final int prime = 31;
+			int result = 1;
+			result = prime * result + getOuterType().hashCode();
+			result = prime * result + x;
+			result = prime * result + y;
+			return result;
+		}
+
+		@Override
+		public boolean equals(Object obj) {
+			if (this == obj)
+				return true;
+			if (obj == null)
+				return false;
+			if (getClass() != obj.getClass())
+				return false;
+			MapNode other = (MapNode) obj;
+			if (!getOuterType().equals(other.getOuterType()))
+				return false;
+			if (x != other.x)
+				return false;
+			if (y != other.y)
+				return false;
+			return true;
+		}
+
+		private Grid2d getOuterType() {
+			return Grid2d.this;
+		}
+
+	}
+
+	public Grid2d(double[][] map, boolean allowDiagonal) {
+		this.map = map;
+		this.allowDiagonal = allowDiagonal;
+	}
+
+	public List<MapNode> findPath(int xStart, int yStart, int xGoal, int yGoal) {
+		return PathFinding.doAStar(new MapNode(xStart, yStart), new MapNode(
+				xGoal, yGoal));
+	}
+
+}
diff --git a/src/main/java/com/sbaars/adventofcode2019/pathfinding/Node.java b/src/main/java/com/sbaars/adventofcode2019/pathfinding/Node.java
@@ -0,0 +1,40 @@
+package com.sbaars.adventofcode2019.pathfinding;
+import java.util.Set;
+
+/**
+ * A node in a graph, useful for pathfinding.
+ * 
+ * @author Ben Ruijl
+ * 
+ * @param <T>
+ *            Actual type of the node
+ */
+public interface Node<T> {
+	/**
+	 * The heuristic cost to move from the current node to the goal. In most
+	 * cases this is the Manhattan distance or Chebyshev distance.
+	 * 
+	 * @param goal
+	 * @return
+	 */
+	double getHeuristic(T goal);
+
+	/**
+	 * The cost of moving from the current node to the neighbour. In most cases
+	 * this is just the distance between the nodes, but additional terrain cost
+	 * can be added as well (for example climbing a mountain is more expensive
+	 * than walking on a road).
+	 * 
+	 * @param neighbour
+	 *            Neighbour of current node
+	 * @return Traversal cost
+	 */
+	double getTraversalCost(T neighbour);
+
+	/**
+	 * Gets the set of neighbouring nodes.
+	 * 
+	 * @return Neighbouring nodes
+	 */
+	Set<T> getNeighbours();
+}
diff --git a/src/main/java/com/sbaars/adventofcode2019/pathfinding/PathFinding.java b/src/main/java/com/sbaars/adventofcode2019/pathfinding/PathFinding.java
@@ -0,0 +1,86 @@
+package com.sbaars.adventofcode2019.pathfinding;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+/**
+ * Helper class containing pathfinding algorithms.
+ * 
+ * @author Ben Ruijl
+ * 
+ */
+public class PathFinding {
+
+	/**
+	 * A Star pathfinding. Note that the heuristic has to be monotonic:
+	 * {@code h(x) <=
+	 * d(x, y) + h(y)}.
+	 * 
+	 * @param start
+	 *            Starting node
+	 * @param goal
+	 *            Goal node
+	 * @return Shortest path from start to goal, or null if none found
+	 */
+	public static <T extends Node<T>> List<T> doAStar(T start, T goal) {
+		Set<T> closed = new HashSet<T>();
+		Map<T, T> fromMap = new HashMap<T, T>();
+		List<T> route = new LinkedList<T>();
+		Map<T, Double> gScore = new HashMap<T, Double>();
+		final Map<T, Double> fScore = new HashMap<T, Double>();
+		PriorityQueue<T> open = new PriorityQueue<T>(11, new Comparator<T>() {
+
+			public int compare(T nodeA, T nodeB) {
+				return Double.compare(fScore.get(nodeA), fScore.get(nodeB));
+			}
+		});
+
+		gScore.put(start, 0.0);
+		fScore.put(start, start.getHeuristic(goal));
+		open.offer(start);
+
+		while (!open.isEmpty()) {
+			T current = open.poll();
+			if (current.equals(goal)) {
+				while (current != null) {
+					route.add(0, current);
+					current = fromMap.get(current);
+				}
+
+				return route;
+			}
+
+			closed.add(current);
+
+			for (T neighbour : current.getNeighbours()) {
+				if (closed.contains(neighbour)) {
+					continue;
+				}
+
+				double tentG = gScore.get(current)
+						+ current.getTraversalCost(neighbour);
+
+				boolean contains = open.contains(neighbour);
+				if (!contains || tentG < gScore.get(neighbour)) {
+					gScore.put(neighbour, tentG);
+					fScore.put(neighbour, tentG + neighbour.getHeuristic(goal));
+
+					if (contains) {
+						open.remove(neighbour);
+					}
+
+					open.offer(neighbour);
+					fromMap.put(neighbour, current);
+				}
+			}
+		}
+
+		return null;
+	}
+
+}
