aboutsummaryrefslogtreecommitdiff
path: root/src/main/java/fr
diff options
context:
space:
mode:
Diffstat (limited to 'src/main/java/fr')
-rw-r--r--src/main/java/fr/umlv/java/wallj/board/Board.java14
-rw-r--r--src/main/java/fr/umlv/java/wallj/board/PathFinder.java138
-rw-r--r--src/main/java/fr/umlv/java/wallj/board/TileVec2.java4
3 files changed, 156 insertions, 0 deletions
diff --git a/src/main/java/fr/umlv/java/wallj/board/Board.java b/src/main/java/fr/umlv/java/wallj/board/Board.java
index 015a4c0..112f7a5 100644
--- a/src/main/java/fr/umlv/java/wallj/board/Board.java
+++ b/src/main/java/fr/umlv/java/wallj/board/Board.java
@@ -3,7 +3,11 @@ package fr.umlv.java.wallj.board;
3import fr.umlv.java.wallj.model.BlockType; 3import fr.umlv.java.wallj.model.BlockType;
4import fr.umlv.java.wallj.utils.Matrix; 4import fr.umlv.java.wallj.utils.Matrix;
5 5
6import java.util.AbstractMap;
6import java.util.Arrays; 7import java.util.Arrays;
8import java.util.Map;
9import java.util.stream.IntStream;
10import java.util.stream.Stream;
7 11
8/** 12/**
9 * An immutable BlockType matrix. 13 * An immutable BlockType matrix.
@@ -67,6 +71,16 @@ public final class Board {
67 return TileVec2.of(Matrix.getWidth(map), Matrix.getHeight(map)); 71 return TileVec2.of(Matrix.getWidth(map), Matrix.getHeight(map));
68 } 72 }
69 73
74 /**
75 * @return a stream of block types and their associated tile position vectors
76 */
77 public Stream<Map.Entry<TileVec2, BlockType>> stream() {
78 TileVec2 dim = getDim();
79 return IntStream.range(0, dim.getRow() * dim.getCol())
80 .mapToObj(i -> TileVec2.of(i % dim.getCol(), i / dim.getCol()))
81 .map(v -> new AbstractMap.SimpleImmutableEntry<>(v, getBlockTypeAt(v)));
82 }
83
70 @Override 84 @Override
71 public boolean equals(Object o) { 85 public boolean equals(Object o) {
72 if (this == o) return true; 86 if (this == o) return true;
diff --git a/src/main/java/fr/umlv/java/wallj/board/PathFinder.java b/src/main/java/fr/umlv/java/wallj/board/PathFinder.java
new file mode 100644
index 0000000..9c509f3
--- /dev/null
+++ b/src/main/java/fr/umlv/java/wallj/board/PathFinder.java
@@ -0,0 +1,138 @@
1package fr.umlv.java.wallj.board;
2
3import java.util.*;
4import java.util.function.BiFunction;
5import java.util.stream.Collectors;
6
7/**
8 * Utility to find your way in this a-maze-ing world.
9 *
10 * @author Pacien TRAN-GIRARD
11 */
12public class PathFinder {
13
14 private static final int LEAP_COST = 1;
15 private static final List<TileVec2> NEIGHBOR_OFFSETS = Arrays.asList(
16 TileVec2.of(0, -1),
17 TileVec2.of(-1, 0),
18 TileVec2.of(0, 1),
19 TileVec2.of(1, 0));
20
21 private static class Node<T> {
22 final T val;
23 final Map<Node<T>, Integer> neighbors;
24
25 Node(T val) {
26 this.val = val;
27 this.neighbors = new HashMap<>();
28 }
29 }
30
31 private static class NodeSearchData<T> {
32 final Node<T> predecessor;
33 final double actualCost, estimatedCost;
34
35 NodeSearchData(Node<T> predecessor, double actualCost, double estimatedCost) {
36 this.predecessor = predecessor;
37 this.actualCost = actualCost;
38 this.estimatedCost = estimatedCost;
39 }
40 }
41
42 private static double euclideanDistance(TileVec2 a, TileVec2 b) {
43 return Math.sqrt(Math.pow(a.getRow() - b.getRow(), 2) +
44 Math.pow(a.getCol() - b.getCol(), 2));
45 }
46
47 private static <T> double cost(Map<Node<T>, NodeSearchData<T>> searchData, Node<T> node) {
48 return Optional.ofNullable(searchData.get(node)).map(n -> n.actualCost).orElse(Double.POSITIVE_INFINITY);
49 }
50
51 private static <T> Node<T> predecessor(Map<Node<T>, NodeSearchData<T>> searchData, Node<T> node) {
52 return Optional.ofNullable(searchData.get(node)).map(n -> n.predecessor).orElse(null);
53 }
54
55 private static <T> List<T> buildPath(Map<Node<T>, NodeSearchData<T>> searchData, Node<T> last) {
56 LinkedList<T> path = new LinkedList<>();
57
58 for (Node<T> node = last; node != null; node = predecessor(searchData, node))
59 path.addFirst(node.val);
60
61 return Collections.unmodifiableList(path);
62 }
63
64 private static <T> List<T> findPath(Node<T> start, T target, BiFunction<T, T, Double> heuristic) {
65 Map<Node<T>, NodeSearchData<T>> searchData = new HashMap<>();
66 TreeSet<Node<T>> discovered = new TreeSet<>(Comparator.comparingDouble(n -> searchData.get(n).estimatedCost));
67 Set<Node<T>> visited = new HashSet<>();
68
69 searchData.put(start, new NodeSearchData<>(null, 0, heuristic.apply(start.val, target)));
70 discovered.add(start);
71
72 Node<T> current;
73 while (!discovered.isEmpty()) {
74 current = discovered.pollFirst();
75 if (target.equals(current.val)) return buildPath(searchData, current);
76
77 for (Map.Entry<Node<T>, Integer> neighborEntry : current.neighbors.entrySet()) {
78 if (visited.contains(neighborEntry.getKey())) continue;
79
80 double challengeCost = cost(searchData, current) + neighborEntry.getValue();
81 double currentCost = cost(searchData, neighborEntry.getKey());
82 if (challengeCost < currentCost)
83 searchData.put(neighborEntry.getKey(), new NodeSearchData<>(current, challengeCost,
84 challengeCost + heuristic.apply(neighborEntry.getKey().val, target)));
85
86 discovered.add(neighborEntry.getKey());
87 }
88
89 visited.add(current);
90 }
91
92 throw new IllegalArgumentException("Destination target unreachable.");
93 }
94
95 private static Map<TileVec2, Node<TileVec2>> buildGraph(Board b) {
96 Map<TileVec2, Node<TileVec2>> map = b.stream()
97 .filter(e -> e.getValue().isTraversable())
98 .map(e -> new AbstractMap.SimpleEntry<>(e.getKey(), new Node<>(e.getKey())))
99 .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
100
101 for (Node<TileVec2> node : map.values())
102 NEIGHBOR_OFFSETS.stream()
103 .map(offsetVector -> map.get(node.val.add(offsetVector)))
104 .filter(Objects::nonNull)
105 .forEach(neighbor -> node.neighbors.put(neighbor, LEAP_COST));
106
107 return map;
108 }
109
110 private final Map<TileVec2, Node<TileVec2>> graph;
111
112 /**
113 * Builds a new path finder for the supplied board.
114 * A well-build (validated) board should be fully connected.
115 *
116 * @param board the board
117 */
118 public PathFinder(Board board) {
119 graph = buildGraph(Objects.requireNonNull(board));
120 }
121
122 /**
123 * Returns a path from a starting point to a target if it exists,
124 * or throw an IllegalArgumentException if any of the given coordinates are invalid.
125 * The returned path may not be the same between executions.
126 *
127 * @param origin the origin coordinates
128 * @param target the target coordinates
129 * @return a path
130 * @implNote uses A* with euclidean distance heuristic
131 */
132 public List<TileVec2> findPath(TileVec2 origin, TileVec2 target) {
133 Node<TileVec2> startNode = graph.get(origin);
134 if (startNode == null) throw new IllegalArgumentException("Invalid starting point.");
135 return findPath(startNode, target, PathFinder::euclideanDistance);
136 }
137
138}
diff --git a/src/main/java/fr/umlv/java/wallj/board/TileVec2.java b/src/main/java/fr/umlv/java/wallj/board/TileVec2.java
index b00c044..70beed9 100644
--- a/src/main/java/fr/umlv/java/wallj/board/TileVec2.java
+++ b/src/main/java/fr/umlv/java/wallj/board/TileVec2.java
@@ -58,6 +58,10 @@ public final class TileVec2 {
58 return new Vec2(col * TILE_DIM, row * TILE_DIM); 58 return new Vec2(col * TILE_DIM, row * TILE_DIM);
59 } 59 }
60 60
61 public TileVec2 add(TileVec2 v) {
62 return TileVec2.of(col + v.col, row + v.row);
63 }
64
61 @Override 65 @Override
62 public boolean equals(Object o) { 66 public boolean equals(Object o) {
63 if (this == o) return true; 67 if (this == o) return true;