diff options
author | Adam NAILI | 2018-01-14 15:22:08 +0100 |
---|---|---|
committer | Adam NAILI | 2018-01-14 15:22:08 +0100 |
commit | b81db47a693f69f522ad0e31fd2354bed1d2ea00 (patch) | |
tree | 37bf40df2728216d4263d1b9825a5069568627d3 | |
parent | c639cf1a706f46372acef471eecd652153ac76be (diff) | |
parent | c9c4f27367039c315c6137cbea1099df3716206f (diff) | |
download | wallj-b81db47a693f69f522ad0e31fd2354bed1d2ea00.tar.gz |
Merge branch 'master' of https://github.com/pacien/upem-java-wallj
-rw-r--r-- | src/docs/class.puml | 8 | ||||
-rw-r--r-- | src/docs/user.md | 4 | ||||
-rw-r--r-- | src/main/java/fr/umlv/java/wallj/board/Board.java | 14 | ||||
-rw-r--r-- | src/main/java/fr/umlv/java/wallj/board/PathFinder.java | 138 | ||||
-rw-r--r-- | src/main/java/fr/umlv/java/wallj/board/TileVec2.java | 4 | ||||
-rw-r--r-- | src/main/java/fr/umlv/java/wallj/utils/PathFinder.java | 5 | ||||
-rw-r--r-- | src/test/java/fr/umlv/java/wallj/board/PathFinderTest.java | 60 | ||||
-rw-r--r-- | src/test/resources/maps/island.txt | 10 |
8 files changed, 233 insertions, 10 deletions
diff --git a/src/docs/class.puml b/src/docs/class.puml index 50e55fb..6a527ae 100644 --- a/src/docs/class.puml +++ b/src/docs/class.puml | |||
@@ -3,10 +3,6 @@ | |||
3 | skinparam linetype ortho | 3 | skinparam linetype ortho |
4 | 4 | ||
5 | package utils { | 5 | package utils { |
6 | class PathFinder { | ||
7 | static List<Vec2> findPath(Board, TileVec2, TileVec2) | ||
8 | } | ||
9 | |||
10 | class Matrix { | 6 | class Matrix { |
11 | static int getWidth(...) | 7 | static int getWidth(...) |
12 | static int getHeight(...) | 8 | static int getHeight(...) |
@@ -129,6 +125,10 @@ package board { | |||
129 | TileVec2(col, row) | 125 | TileVec2(col, row) |
130 | Vec2 toPixelPos() | 126 | Vec2 toPixelPos() |
131 | } | 127 | } |
128 | |||
129 | class PathFinder { | ||
130 | static List<TileVec2> findPath(Board, TileVec2, TileVec2) | ||
131 | } | ||
132 | } | 132 | } |
133 | 133 | ||
134 | package model { | 134 | package model { |
diff --git a/src/docs/user.md b/src/docs/user.md index 96303ff..bb24c53 100644 --- a/src/docs/user.md +++ b/src/docs/user.md | |||
@@ -106,13 +106,15 @@ A world is defined as valid if its blocks fulfill the following criteria: | |||
106 | 106 | ||
107 | * The bounding box of the defined world must be made of bounding blocks. | 107 | * The bounding box of the defined world must be made of bounding blocks. |
108 | * The interior space formed by bounding blocks must be unique and simple. | 108 | * The interior space formed by bounding blocks must be unique and simple. |
109 | * Reachable blocks are either be adjacent or belong to the interior space. | 109 | * Reachable blocks are either adjacent or belong to the interior space. |
110 | * The world must contain at least one trash can and one garbage block. | 110 | * The world must contain at least one trash can and one garbage block. |
111 | 111 | ||
112 | Only valid worlds can be loaded into the game. | 112 | Only valid worlds can be loaded into the game. |
113 | 113 | ||
114 | The validity of a world may not guaranty the solvability of the puzzle. | 114 | The validity of a world may not guaranty the solvability of the puzzle. |
115 | 115 | ||
116 | \newpage | ||
117 | |||
116 | __Example of invalid world definition:__ | 118 | __Example of invalid world definition:__ |
117 | ``` | 119 | ``` |
118 | WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW | 120 | WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW |
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; | |||
3 | import fr.umlv.java.wallj.model.BlockType; | 3 | import fr.umlv.java.wallj.model.BlockType; |
4 | import fr.umlv.java.wallj.utils.Matrix; | 4 | import fr.umlv.java.wallj.utils.Matrix; |
5 | 5 | ||
6 | import java.util.AbstractMap; | ||
6 | import java.util.Arrays; | 7 | import java.util.Arrays; |
8 | import java.util.Map; | ||
9 | import java.util.stream.IntStream; | ||
10 | import 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 @@ | |||
1 | package fr.umlv.java.wallj.board; | ||
2 | |||
3 | import java.util.*; | ||
4 | import java.util.function.BiFunction; | ||
5 | import 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 | */ | ||
12 | public 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 in |