Change IceFill from bfs to dfs

2 files changed, 136 insertions, 28 deletions

diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
index 7ab96d78..166047b2 100644
--- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java
@@ -120,50 +120,131 @@ public class IceFill extends DungeonPuzzle {
         return boardChanged;
     }
 
-    private void solve(boolean[][] iceFillBoard, List<Vector2ic> iceFillPath) {
+    void solve(boolean[][] iceFillBoard, List<Vector2ic> iceFillPath) {
         Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2);
         int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum();
 
-        Queue<List<Vector2ic>> queue = new ArrayDeque<>();
-        queue.add(List.of(start));
-        while (!queue.isEmpty()) {
-            List<Vector2ic> path = queue.poll();
-            Vector2ic pos = path.get(path.size() - 1);
-            if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && path.size() == count) {
-                iceFillPath.clear();
-                iceFillPath.addAll(path);
-                return;
-            }
+        List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start)));
+        if (newPath != null) {
+            iceFillPath.clear();
+            iceFillPath.addAll(newPath);
+        }
+    }
 
-            Vector2i posMutable = pos.add(1, 0, new Vector2i());
-            if (posMutable.x() < iceFillBoard.length && !iceFillBoard[posMutable.x()][posMutable.y()]) {
-                addQueue(queue, path, posMutable);
+    private List<Vector2ic> solveDfs(boolean[][] iceFillBoard, int count, List<Vector2ic> path) {
+        Vector2ic pos = path.get(path.size() - 1);
+        if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) {
+            return path;
+        }
+
+        Vector2ic newPos = pos.add(1, 0, new Vector2i());
+        if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+            path.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            if (newPath != null) {
+                return newPath;
+            } else {
+                path.remove(path.size() - 1);
             }
+        }
 
-            posMutable = pos.add(-1, 0, new Vector2i());
-            if (posMutable.x() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) {
-                addQueue(queue, path, posMutable);
+        newPos = pos.add(-1, 0, new Vector2i());
+        if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+            path.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            if (newPath != null) {
+                return newPath;
+            } else {
+                path.remove(path.size() - 1);
             }
+        }
 
-            posMutable = pos.add(0, 1, new Vector2i());
-            if (posMutable.y() < iceFillBoard[0].length && !iceFillBoard[posMutable.x()][posMutable.y()]) {
-                addQueue(queue, path, posMutable);
+        newPos = pos.add(0, 1, new Vector2i());
+        if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+            path.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            if (newPath != null) {
+                return newPath;
+            } else {
+                path.remove(path.size() - 1);
             }
+        }
 
-            posMutable = pos.add(0, -1, new Vector2i());
-            if (posMutable.y() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) {
-                addQueue(queue, path, posMutable);
+        newPos = pos.add(0, -1, new Vector2i());
+        if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) {
+            path.add(newPos);
+            List<Vector2ic> newPath = solveDfs(iceFillBoard, count - 1, path);
+            if (newPath != null) {
+                return newPath;
+            } else {
+                path.remove(path.size() - 1);
             }
         }
+
+        return null;
+    }
+
+    /*
+    void solve(boolean[][] iceFillBoard, List<Vector2ic> iceFillPath) {
+        Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2);
+        int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum();
+
+        Vector2ic[] newPath = solveDfs(iceFillBoard, count - 1, new Vector2ic[]{start});
+        if (newPath != null) {
+            iceFillPath.clear();
+            iceFillPath.addAll(Arrays.asList(newPath));
+        }
     }
 
-    private void addQueue(Queue<List<Vector2ic>> queue, List<Vector2ic> path, Vector2ic newPos) {
-        if (!path.contains(newPos)) {
-            List<Vector2ic> newPath = new ArrayList<>(path);
-            newPath.add(newPos);
-            queue.add(newPath);
+    private Vector2ic[] solveDfs(boolean[][] iceFillBoard, int count, Vector2ic[] path) {
+        Vector2ic pos = path[path.length - 1];
+        if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) {
+            return path;
+        }
+
+        Vector2ic newPos = pos.add(1, 0, new Vector2i());
+        if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
+            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
+            newPath[path.length] = newPos;
+            newPath = solveDfs(iceFillBoard, count - 1, newPath);
+            if (newPath != null) {
+                return newPath;
+            }
+        }
+
+        newPos = pos.add(-1, 0, new Vector2i());
+        if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
+            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
+            newPath[path.length] = newPos;
+            newPath = solveDfs(iceFillBoard, count - 1, newPath);
+            if (newPath != null) {
+                return newPath;
+            }
+        }
+
+        newPos = pos.add(0, 1, new Vector2i());
+        if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
+            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
+            newPath[path.length] = newPos;
+            newPath = solveDfs(iceFillBoard, count - 1, newPath);
+            if (newPath != null) {
+                return newPath;
+            }
         }
+
+        newPos = pos.add(0, -1, new Vector2i());
+        if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) {
+            Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1);
+            newPath[path.length] = newPos;
+            newPath = solveDfs(iceFillBoard, count - 1, newPath);
+            if (newPath != null) {
+                return newPath;
+            }
+        }
+
+        return null;
     }
+     */
 
     @Override
     public void render(WorldRenderContext context) {
diff --git a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java
new file mode 100644
index 00000000..511d1148
--- /dev/null
+++ b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java
@@ -0,0 +1,27 @@
+package de.hysky.skyblocker.skyblock.dungeon.puzzle;
+
+import org.joml.Vector2ic;
+import org.junit.jupiter.api.Test;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class IceFillTest {
+    private static final boolean[][] iceFillBoard = new boolean[][]{
+            {false, false, true, false, false, false, false},
+            {false, false, false, false, false, false, false},
+            {false, false, false, true, true, false, false},
+            {false, false, false, false, false, false, false},
+            {false, false, false, false, false, false, false},
+            {false, false, false, false, false, false, false},
+            {true, false, false, false, false, false, false},
+    };
+    private static final List<Vector2ic> iceFillPath = new ArrayList<>();
+
+    @Test
+    void testIceFillSolve() {
+        IceFill.INSTANCE.solve(iceFillBoard, iceFillPath);
+        System.out.println(iceFillPath);
+        System.out.println(iceFillPath.size());
+    }
+}