Поиск пути в JavaFX

Question

Я создал игру-лабиринт в JavaFX, где пользователь может создать свой собственный лабиринт и играть в него.Лабиринт построен с использованием кнопок с CSS-идентификаторами в зависимости от двумерного массива, в котором временно хранится уровень.

Проблема возникает со следующей частью проекта.Я создал алгоритм, который генерирует случайный лабиринт.Для того, чтобы уровень был возможен, мне нужно проверить, является ли лабиринт разрешимым (то есть вы можете добраться от начала (0, 3) до конца (6, 3)).

Я создал отдельный проект с таким же алгоритмом отображения, классы ниже:

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;
}

Как я могу обойти решение лабиринта, в то время как показывать визуально?Если лабиринт разрешим, я хотел бы, чтобы лабиринт отображался после его завершения, но я хотел бы, чтобы программа генерировала новый лабиринт, чтобы проверить его неразрешимо.

Спасибо

Answer 1

Вот очень простая реализация Поиск в ширину .Его можно скопировать, вставить в один файл (Maze.java) и выполнить.Он использует Main.css, опубликованные в вопросе (хотя чаще всего, если он не используется).Кнопки активны: нажатие кнопки меняет состояние и перезапускает процесс решения.Пожалуйста, просмотрите комментарии:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;   
import javafx.application.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;
import src.tests.Cell.CellState;

public class Maze 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 buttonGrid = 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, 700, 700);          
        maze.getStylesheets().add(getClass().
                             getResource("Main.css").toExternalForm());
        makeBlankButton();
        mazeGrid.getChildren().add(buttonGrid);
        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.setId("button-array-clicked");
                    cell.setState(CellState.WALL);
                } else if (level[row][column] == 0) {
                    cell.setId("button-array-blank");
                }
                buttonGrid.getChildren().add(cell);
                GridPane.setConstraints(buttonGrid, 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) {
            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();}
    }
}