java - Pathfinding in JavaFX

Question

I have created a maze game in JavaFX where a user can create their own maze and play it. The maze is built using buttons with CSS IDs depending on the 2-dimensional array the level is temporarily stored in.

The problem arises with the next part of the project. I have created an algorithm which generates a random maze. In order for the level to be possible, I need to check if the maze is solvable (i.e. you can get from the start (0, 3) to the finish (6, 3)).

I have created a separate project with the same display algorithm, the classes are below:

Main.java

import javafx.application.Application;
import javafx.scene.control.*;
import javafx.stage.Stage;
import javafx.scene.Scene;
import javafx.scene.layout.GridPane;

public class Main extends Application{

    int[][] level = {{1, 1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1, 1}};
    public static boolean[][] status = new boolean[7][7];
    public static Button[][] blankButtons = new Button[7][7];

    public static Runner[][] runners = new Runner[7][7];

    boolean solvable = false;

    GridPane buttonGrid = new GridPane();

    public static void main(String[] args){launch(args);}

    public void start(Stage primaryStage) throws Exception {
        Stage window = primaryStage;

        for (int i = 0; i < 7; i++){
            for (int j = 0; j < 7; j++){
                if (level[i][j] == 1){
                    status[i][j] = false;
                } else if (level[i][j] == 0){
                    status[i][j] = true;
                }
            }
        }

        GridPane mazeGrid = new GridPane();
        Scene maze = new Scene(mazeGrid, 700, 700);
        maze.getStylesheets().add("Main.css");

        for(int i = 0; i < 7; i++){
            for(int j = 0; j < 7; j++){
                makeBlankButton(i, j);
            }
        }
//MY PREVIOUS ATTEMPT AT A FLOOD SOLVER// 

//        for(int i = 0; i < 7; i++){
//            for(int j = 0; j < 7; j++){
//                runners[i][j] = new Runner(i, j);
//                runners[i][j].alive = false;
//            }
//        }
//        Runner finish = new Runner(3, 6);
//        finish.alive = false;
//
//
//        runners[3][0].alive = true;
//        runners[3][0].run();
//        for(int i = 0; i < 7; i++){
//            for(int j = 0; j < 7; j++){
//                if(runners[i][j].alive){
//                    runners[i][j].run();
//                }
//                if(runners[3][1].alive){
//                    solvable = true;
//                    System.out.println(solvable);
//
//                }
//                System.out.println(solvable);
//            }
//        }

        mazeGrid.getChildren().add(buttonGrid);
        window.setScene(maze);
        window.show();
    }

    public void makeBlankButton(int row, int column){
        blankButtons[row][column] = new Button();
        GridPane.setConstraints(blankButtons[row][column], column, row);
        if (level[row][column] == 1){
            blankButtons[row][column].setId("button-array-clicked");
        } else if (level[row][column] == 0) {
            blankButtons[row][column].setId("button-array-blank");
        }
        buttonGrid.getChildren().add(blankButtons[row][column]);
        GridPane.setConstraints(buttonGrid, 0, 1);

        if (row == 3){
            if (column == 0){
                blankButtons[row][column].setId("button-start");
            } else if(column == 6){
                blankButtons[row][column].setId("button-end");
            }
        }
    }
}

Runner.java

public class Runner {
    int x, y;
    boolean alive;

    Runner(int x, int y){
        this.x = x;
        this.y = y;
        this.alive = false;
        if(this.alive) {
            Main.blankButtons[x][y].setId("button-water");
        }
    }

    public void run(){
        if (this.alive) {
            if (Main.status[x + 1][y]) {
//                Main.runners[x + 1][y] = new Runner(x + 1, y);
                Main.runners[y + 1][x].alive = true;
                Main.status[x][y] = false;
                this.alive = false;
            } else if (Main.status[y][x + 1]) {
//                Main.runners[x][y + 1] = new Runner(x, y + 1);
                Main.runners[x][y + 1].alive = true;
                Main.status[x][y] = false;
                this.alive = false;
            } else if (Main.status[y][x-1]) {
//                Main.runners[x - 1][y] = new Runner(x - 1, y);
                Main.runners[x - 1][y].alive = true;
                Main.status[x][y] = false;
                this.alive = false;
            } else if (Main.status[y][x-1]) {
//                Main.runners[x][y - 1] = new Runner(x, y - 1);
                Main.runners[x][y - 1].alive = true;
                Main.status[x][y] = false;
                this.alive = false;
            }
        }
    }

}

Main.css

#button-array-clicked{
    -fx-pref-width: 100px;
    -fx-pref-height: 100px;
    -fx-border-width: 1px;
    -fx-border-color: #00aa00;
    -fx-background-color: #000000;
    -fx-font-size: 10px;
}

#button-array-blank{
    -fx-pref-width: 100px;
    -fx-pref-height: 100px;
    -fx-border-width: 1px;
    -fx-border-color: #00aa00;
    -fx-background-color: #ffffff;
    -fx-font-size: 10px;
}

#button-start{
    -fx-pref-width: 100px;
    -fx-pref-height: 100px;
    -fx-border-width: 1px;
    -fx-border-color: #00aa00;
    -fx-background-color: #00bbff;
    -fx-font-size: 10px;
}

#button-end{
    -fx-pref-width: 100px;
    -fx-pref-height: 100px;
    -fx-border-width: 1px;
    -fx-border-color: #00aa00;
    -fx-background-color: #cc00aa;
    -fx-font-size: 10px;
}

#button-water{
    -fx-pref-width: 100px;
    -fx-pref-height: 100px;
    -fx-border-width: 1px;
    -fx-border-color: #00aa00;
    -fx-background-color: #0000ff;
    -fx-font-size: 10px;
}

How could I go around solving the maze, while showing visibly? If the maze is solvable, I would like it to display the maze once it is complete, but I would like the program to generate a new maze to check of it is unsolvable.

Thank you

Answer 1

Here is a very basic implementation of Breadth First Search. It can be copy pasted into one file ( Maze.java ) and executed. It uses Main.css posted in the question (although most of if it is not used).
Buttons are active: button click changes state and restarts solve process. Please review the comments :

import java.util.*;
import java.util.concurrent.*;
import bfs.Cell.CellState;
import javafx.application.*;
import javafx.beans.property.SimpleObjectProperty;
import javafx.beans.value.ChangeListener;
import javafx.scene.Scene;
import javafx.scene.control.Button;
import javafx.scene.layout.GridPane;
import javafx.stage.Stage;

public class BsfVisualizationFx extends Application{

    final int[][] level = {
            {1, 1, 1, 1, 1, 1, 1},
            {1, 0, 0, 0, 0, 0, 1},
            {1, 0, 1, 1, 1, 1, 1},
            {1, 0, 1, 0, 0, 0, 1},
            {1, 0, 1, 0, 1, 0, 1},
            {1, 0, 0, 0, 1, 0, 1},
            {1, 1, 1, 1, 1, 1, 1}};

    //represents moving in 4 directions
    private final int[][] directions = {{1,0},{-1,0}, {0,1}, {0,-1}}; //down, up, right, left
    private final Cell[][] cells = new Cell[level.length][level[0].length];
    private final GridPane grid = new GridPane();
    private BreadthFirst algo;

    //Single Thread Executor guarantees that task (searches) do not run concurrently
    final ExecutorService exService = Executors.newSingleThreadExecutor();

    @Override
    public void start(Stage primaryStage) throws Exception {
        Stage window = primaryStage;
        GridPane mazeGrid = new GridPane();
        Scene maze = new Scene(mazeGrid);
        maze.getStylesheets().add (getClass().getResource("BsfVisualizationFx.css").toExternalForm());
        makeBlankButton();
        mazeGrid.getChildren().add(grid);
        window.setScene(maze);
        window.show();
        solve();
    }

    void solve(){
        algo = new BreadthFirst(cells[5][5]) ;
        exService.execute(()->  algo.solve(cells[1][1]));
    }

    void reSolve(){
        stopSolve();
        resetCellsState();
        solve();
    }

    private void stopSolve(){
        if(algo != null) {
            algo.stop();
        }
    }

    private void resetCellsState() {
        for(int row = 0; row < level.length; row++){
            for(int column = 0; column < level[0].length; column++){
                if( cells[row][column].getState() != CellState.WALL) {
                    cells[row][column].setState(CellState.IDLE);
                }
            }
        }
    }

    public void makeBlankButton(){

        //listen to cell state changes. If cell changed from or to WALL restart solve
        ChangeListener<CellState> listener = (obs , oldValue, newValue)->{
            if(oldValue == CellState.WALL || newValue == CellState.WALL) {
                reSolve();
            }
        };

        for(int row = 0; row < level.length; row++){
            for(int column = 0; column < level[0].length; column++){
                Cell cell = new Cell(row, column);
                GridPane.setConstraints(cell, column, row);
                if (level[row][column] == 1){
                    cell.setState(CellState.WALL);
                }
                grid.getChildren().add(cell);
                GridPane.setConstraints(grid, 0, 1);

                if (row == 3){
                    if (column == 0){
                        cell.setId("button-start");
                    } else if(column == 6){
                        cell.setId("button-end");
                    }
                }

                cell.addStateListener(listener);
                cells[row][column] = cell;
            }
        }
    }

    private List<Cell> getNeighbors(Cell cell) {

        List<Cell> neighbors = new ArrayList<>();
        int row = cell.getRow(), col = cell.getCol();
        for(int[] dir : directions){
            int newRow = row + dir[0] ; int newCol = col + dir[1];
            if(isValidAddress(newRow, newCol)) {
                neighbors.add(cells[newRow][newCol]);
            }
        }
        return neighbors;
    }

    private boolean isValidAddress(int row, int col) {

        if(row < 0 || col < 0) return false;
        if(row >= level.length || col >= level[row].length) return false;
        return true;
    }

    public static void main(String[] args){launch(args);}

    class BreadthFirst {

        private static final long DELAY = 1000;
        private final LinkedList<Cell> path;
        private final Cell target;
        private volatile boolean isStopped;

        public BreadthFirst(Cell target) {
            this.target = target;
            path = new LinkedList<>();
            isStopped = false;
        };

        public boolean solve(Cell cell) {

            if(cell == null || isStopped) return false;

            // queue holds a nodes collections. each collection represents the path through
            //which a cell has been reached, the cell being the last element in the collection
            final Queue<List<Cell>> queue = new LinkedList<>(); //initialize queue

            //a collection to hold the path through which a cell has been reached
            //the cell it self is the last element in that collection
            List<Cell> pathToCell = new ArrayList<>();
            pathToCell.add(cell);

            //queue does not hold a cell, but rather the whole path to a cell
            //where the cell is stored as the last element
            queue.add(pathToCell);

            while (! queue.isEmpty() && ! isStopped) {

                pathToCell = queue.remove();
                //get cell (last element) from queue
                cell = pathToCell.get(pathToCell.size()-1);
                if(cell == null) return false;

                //skip if cell is wall, or is/was explored or in path
                if( cell.getState() != CellState.IDLE ) { continue; }

                setCellState(cell, CellState.IS_EXPLORED);

                addToPath(pathToCell);

                Wait.millis(DELAY);

                if(isSolved(cell))  return true;

                List<Cell> nb = getNeighbors(cell);
                Collections.shuffle(nb);

                //loop over neighbors
                for(final Cell nextCell : nb){

                    if(isStopped)
                        return false;
                    if(nextCell.getState() == CellState.WALL) { continue; }

                    final List<Cell> pathToNextCell = new ArrayList<>(pathToCell);
                    pathToNextCell.add(nextCell);
                    queue.add(pathToNextCell); //add collection to the queue
                }

                Collections.reverse(pathToCell);
                for(final Cell c : pathToCell) {
                    backTrack(c);
                }
            }
            return false;
        }

        private void setCellState(Cell cell, CellState state) {
            Platform.runLater(()->cell.setState(state));
        }

        /**
         * Append collection to path
         */
        private void addToPath(Collection<Cell> pathToCell) {

            for(Cell c : pathToCell) {
                if(isStopped)
                    return;
                addToPath(c);
            }
        }

        /**
         * Append Cell to path
         */
        private void addToPath(Cell node) {
            path.push(node);
            setCellState(node, CellState.PATH);
        }

        /**
         *Is maze solved
         */
        private boolean isSolved(Cell cell) {
            return cell.equals(target);
        }

        private void backTrack(Cell cell) {

            //no backtracking if back to origin
            if(path.size()<=1 || isStopped) return ;

            setCellState(cell, CellState.WAS_EXPLORED);

            //remove from stack
            if( path.peek().equals(cell)) {
                path.pop();
                return;
            }

            throw new IllegalStateException(cell+" isn't at the top of the stack");
        }

        void stop(){
            isStopped = true;
        }
    }
}

class Cell extends Button{

    private final SimpleObjectProperty<CellState> stateProperty
    = new SimpleObjectProperty<>(CellState.IDLE);
    private final int row, col;

    Cell(int row, int col){
        this.row = row; this.col = col;
        setOnAction(e -> toggleState());
    }

    public enum CellState {
        WALL  ("black"),
        IDLE  ("white") ,      //No activity is or was performed on node
        IS_EXPLORED ("blue"),  //node is evaluated by path finder
        WAS_EXPLORED ("grey"), //node was evaluated by path finder
        PATH ("green");        // node was evaluated by path finder and added to path

        public String color;
        CellState(String color) {this.color = color;}
    }

    void toggleState(){
        setState(getState() == CellState. WALL ?  CellState. IDLE : CellState. WALL );
    }

    void setState(CellState state){
        stateProperty.set(state);
        setStyle("-fx-background-color:" + state.color);
    }

    void addStateListener(ChangeListener<CellState> listener) {
        stateProperty.addListener(listener);
    }

    @Override
    public String toString() {
        return  getState()+" at "+ getRow() +" - " + getCol() ;
    }

    @Override
    public boolean equals(Object cell) {

        if (cell == null || !(cell instanceof Cell))
            return false;

        return ((Cell) cell).getRow() == row  &&  ((Cell) cell).getCol() == col;
    }

    @Override
    public int hashCode() {
        return  31*(row+1) + 17*(col+1);
    }

    int getRow() {  return row; }
    int getCol() {  return col;}
    CellState getState() {return stateProperty.get();}
}

class Wait {

    public static void millis(final long millis) {

        try {
            TimeUnit.MILLISECONDS.sleep(millis);

        } catch (final InterruptedException ex) {ex.printStackTrace();}
    }
}

---