feat: added MazeGrid as a traversable grid

AlmasB · AlmasB · commit f4937ff36f71 · 2024-03-21T18:25:20.000Z
diff --git a/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/astar/AStarPathfinder.java b/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/astar/AStarPathfinder.java
@@ -126,15 +126,15 @@ public List<T> findPath(T[][] grid, T start, T target, NeighborDirection neighbo
             }
         }
 
-        Set<AStarCell> open = new HashSet<>();
-        Set<AStarCell> closed = new HashSet<>();
+        Set<T> open = new HashSet<>();
+        Set<T> closed = new HashSet<>();
 
-        AStarCell current = start;
+        T current = start;
 
         boolean found = false;
 
         while (!found && !closed.contains(target)) {
-            for (AStarCell neighbor : getValidNeighbors(current, neighborDirection, busyNodes)) {
+            for (T neighbor : getValidNeighbors(current, neighborDirection, busyNodes)) {
                 if (neighbor == target) {
                     target.setParent(current);
                     found = true;
@@ -171,9 +171,9 @@ public List<T> findPath(T[][] grid, T start, T target, NeighborDirection neighbo
                 if (open.isEmpty())
                     return Collections.emptyList();
 
-                AStarCell acc = null;
+                T acc = null;
 
-                for (AStarCell a : open) {
+                for (T a : open) {
                     if (acc == null) {
                         acc = a;
                         continue;
@@ -213,10 +213,10 @@ private List<T> buildPath(T start, T target) {
      * @param busyNodes nodes which are busy, i.e. walkable but have a temporary obstacle
      * @return neighbors of the node
      */
-    private List<T> getValidNeighbors(AStarCell node, NeighborDirection neighborDirection, AStarCell... busyNodes) {
+    private List<T> getValidNeighbors(T node, NeighborDirection neighborDirection, AStarCell... busyNodes) {
         var result = grid.getNeighbors(node.getX(), node.getY(), neighborDirection);
         result.removeAll(Arrays.asList(busyNodes));
-        result.removeIf(cell -> !cell.isWalkable());
+        result.removeIf(cell -> !grid.isTraversableInSingleMove(node, cell));
         return result;
     }
 
diff --git a/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/astar/TraversableGrid.java b/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/astar/TraversableGrid.java
@@ -40,4 +40,12 @@ public List<T> getWalkableCells() {
                 .filter(c -> c.getState().isWalkable())
                 .collect(Collectors.toList());
     }
+
+    /**
+     * @return given neighbors [source] and [target], true if we can move from [source] to [target] in a single action,
+     * i.e. there exists a path of size 1
+     */
+    public boolean isTraversableInSingleMove(T source, T target) {
+        return target.isWalkable();
+    }
 }
diff --git a/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/maze/MazeCell.java b/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/maze/MazeCell.java
@@ -6,20 +6,21 @@
 
 package com.almasb.fxgl.pathfinding.maze;
 
-import com.almasb.fxgl.core.collection.grid.Cell;
+import com.almasb.fxgl.pathfinding.CellState;
+import com.almasb.fxgl.pathfinding.astar.AStarCell;
 
 /**
  * Represents a single cell in a maze.
  *
  * @author Almas Baimagambetov (AlmasB) (almaslvl@gmail.com)
  */
-public class MazeCell extends Cell {
+public class MazeCell extends AStarCell {
 
     private boolean topWall = false;
     private boolean leftWall = false;
 
     public MazeCell(int x, int y) {
-        super(x, y);
+        super(x, y, CellState.WALKABLE);
     }
 
     /**
diff --git a/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/maze/MazeGrid.java b/fxgl-entity/src/main/java/com/almasb/fxgl/pathfinding/maze/MazeGrid.java
@@ -6,7 +6,7 @@
 
 package com.almasb.fxgl.pathfinding.maze;
 
-import com.almasb.fxgl.core.collection.grid.Grid;
+import com.almasb.fxgl.pathfinding.astar.TraversableGrid;
 
 import java.util.Arrays;
 import java.util.Collections;
@@ -19,15 +19,15 @@
  *
  * @author Almas Baimagambetov (AlmasB) (almaslvl@gmail.com)
  */
-public class Maze extends Grid<MazeCell> {
+public class MazeGrid extends TraversableGrid<MazeCell> {
 
     /**
      * Constructs a new maze with given width and height.
      *
      * @param width maze width
      * @param height maze height
      */
-    public Maze(int width, int height) {
+    public MazeGrid(int width, int height) {
         super(MazeCell.class, width, height);
 
         int[][] maze = new int[width][height];
@@ -45,6 +45,43 @@ public Maze(int width, int height) {
         });
     }
 
+    @Override
+    public boolean isTraversableInSingleMove(MazeCell source, MazeCell target) {
+        var isTraversable = super.isTraversableInSingleMove(source, target);
+        if (!isTraversable)
+            return false;
+
+        // move is vertical
+        if (source.getX() == target.getX()) {
+            // source
+            //   |
+            //   V
+            // target
+            if (source.getY() < target.getY())
+                return !target.hasTopWall();
+
+            // target
+            //   ^
+            //   |
+            // source
+            if (source.getY() > target.getY())
+                return !source.hasTopWall();
+        }
+
+        // move is horizontal
+        if (source.getY() == target.getY()) {
+            // source -> target
+            if (source.getX() < target.getX())
+                return !target.hasLeftWall();
+
+            // target <- source
+            if (source.getX() > target.getX())
+                return !source.hasLeftWall();
+        }
+
+        return true;
+    }
+
     @SuppressWarnings("PMD.UselessParentheses")
     private void generateMaze(int[][] maze, int cx, int cy) {
         DIR[] dirs = DIR.values();
diff --git a/fxgl-entity/src/test/java/com/almasb/fxgl/pathfinding/maze/MazeGridTest.java b/fxgl-entity/src/test/java/com/almasb/fxgl/pathfinding/maze/MazeGridTest.java
@@ -10,10 +10,10 @@
 
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
-public class MazeTest {
+public class MazeGridTest {
     @Test
     public void TestMaze() {
-        var maze = new Maze(8,5);
+        var maze = new MazeGrid(8,5);
 
         var atLeastOneHasLeftWall = maze.getCells()
                 .stream()
diff --git a/fxgl-samples/src/main/java/sandbox/ai/pathfinding/MazeGenSample.java b/fxgl-samples/src/main/java/sandbox/ai/pathfinding/MazeGenSample.java
@@ -0,0 +1,119 @@
+/*
+ * FXGL - JavaFX Game Library. The MIT License (MIT).
+ * Copyright (c) AlmasB (almaslvl@gmail.com).
+ * See LICENSE for details.
+ */
+
+package sandbox.ai.pathfinding;
+
+import com.almasb.fxgl.app.GameApplication;
+import com.almasb.fxgl.app.GameSettings;
+import com.almasb.fxgl.core.math.FXGLMath;
+import com.almasb.fxgl.dsl.components.RandomAStarMoveComponent;
+import com.almasb.fxgl.pathfinding.CellMoveComponent;
+import com.almasb.fxgl.pathfinding.astar.AStarCell;
+import com.almasb.fxgl.pathfinding.astar.AStarMoveComponent;
+import com.almasb.fxgl.pathfinding.astar.TraversableGrid;
+import com.almasb.fxgl.pathfinding.dungeon.DungeonGrid;
+import com.almasb.fxgl.pathfinding.maze.MazeGrid;
+import javafx.scene.paint.Color;
+import javafx.scene.shape.Line;
+import javafx.scene.shape.Rectangle;
+import javafx.util.Duration;
+
+import static com.almasb.fxgl.dsl.FXGL.addUINode;
+import static com.almasb.fxgl.dsl.FXGL.entityBuilder;
+
+/**
+ * @author Almas Baim (https://github.com/AlmasB)
+ */
+public class MazeGenSample extends GameApplication {
+    @Override
+    protected void initSettings(GameSettings settings) {
+        settings.setWidth(1280);
+        settings.setHeight(720);
+    }
+
+    @Override
+    protected void initGame() {
+        var dungeon = new MazeGrid(30, 26);
+
+        var scale = 40;
+
+        var agent = entityBuilder()
+                .viewWithBBox(new Rectangle(scale, scale, Color.BLUE))
+                .with(new CellMoveComponent(scale, scale, 150))
+                .with(new AStarMoveComponent<>(dungeon))
+                .zIndex(1)
+                .anchorFromCenter()
+                .buildAndAttach();
+
+        for (int y = 0; y < 26; y++) {
+            for (int x = 0; x < 30; x++) {
+                var finalX = x;
+                var finalY = y;
+
+                var tile = dungeon.get(x, y);
+
+                var rect = new Rectangle(scale, scale, Color.WHITE);
+
+                if (tile.hasLeftWall()) {
+                    var line = new Line(x*scale, y*scale, x*scale, (y+1)*scale);
+                    line.setStrokeWidth(2);
+                    line.setStroke(Color.DARKGRAY);
+
+                    addUINode(line);
+                }
+
+                if (tile.hasTopWall()) {
+                    var line = new Line(x*scale, y*scale, (x+1) * scale, y*scale);
+                    line.setStrokeWidth(2);
+                    line.setStroke(Color.DARKGRAY);
+
+                    addUINode(line);
+                }
+
+                if (!tile.isWalkable()) {
+                    rect.setFill(Color.GRAY);
+                } else {
+                    rect.setFill(Color.WHITE);
+                    agent.getComponent(AStarMoveComponent.class).stopMovementAt(finalX, finalY);
+
+                    rect.setOnMouseClicked(e -> {
+                        agent.getComponent(AStarMoveComponent.class).moveToCell(finalX, finalY);
+                    });
+
+                    if (FXGLMath.randomBoolean(0.09)) {
+                        spawnNPC(x, y, dungeon);
+                    }
+                }
+
+                entityBuilder()
+                        .at(x*scale, y*scale)
+                        .view(rect)
+                        .buildAndAttach();
+            }
+        }
+    }
+
+    private void spawnNPC(int x, int y, TraversableGrid<?> grid) {
+        var view = new Rectangle(40, 40, FXGLMath.randomColor().brighter().brighter());
+        view.setStroke(Color.BLACK);
+        view.setStrokeWidth(2);
+
+        var e = entityBuilder()
+                .zIndex(2)
+                .viewWithBBox(view)
+                .anchorFromCenter()
+                .with(new CellMoveComponent(40, 40, 150))
+                .with(new AStarMoveComponent<>(grid))
+                .with(new RandomAStarMoveComponent<AStarCell>(1, 7, Duration.seconds(1), Duration.seconds(3)))
+                .buildAndAttach();
+
+        e.getComponent(AStarMoveComponent.class).stopMovementAt(x, y);
+    }
+
+    public static void main(String[] args) {
+        launch(args);
+    }
+}

Original file line number	Diff line number	Diff line change
`@@ -40,4 +40,12 @@ public List<T> getWalkableCells() {`
`40`	`40`	`.filter(c -> c.getState().isWalkable())`
`41`	`41`	`.collect(Collectors.toList());`
`42`	`42`	`}`
	`43`	`+`
	`44`	`+ /**`
	`45`	`+ * @return given neighbors [source] and [target], true if we can move from [source] to [target] in a single action,`
	`46`	`+ * i.e. there exists a path of size 1`
	`47`	`+ */`
	`48`	`+ public boolean isTraversableInSingleMove(T source, T target) {`
	`49`	`+ return target.isWalkable();`
	`50`	`+ }`
`43`	`51`	`}`