Простой лабиринт алгоритм решения


Я хотел написать простую программу, лабиринт решатель, который принимает входной файл, обозначающий лабиринт начальную и конечную точки, и структура самого лабиринта. Спецификации были держать его как можно более простым, так что не нужно все усложнять решение. Мое решение ниже. Я думаю buildMaze() метод может определенно быть сделано лучше. Я не был уверен, как читать в новую строку каждый раз и пишу ввода новых переменных, так что это решение я нашел в интернете, что работал, но я хотел бы улучшить его, если бы мог.

Здесь были спецификации для входного файла и вывод:

INPUT:
<WIDTH> <HEIGHT><CR>
<START_X> <START_Y><CR>     (x,y) location of the start. (0,0) is upper left and (width-1,height-1) is lower right
<END_X> <END_Y><CR>     (x,y) location of the end
<HEIGHT> <WIDTH> {0,0} rows where each row has integers space delimited

OUTPUT:
 The maze with a path from start to end
 Walls marked by '#', passages marked by ' ', path marked by 'X', start/end marked by 'S'/'E'

Образец лабиринт имя входного файла:

10 10
1 1
8 8
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 1 0 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 1
1 0 1 1 0 1 0 1 1 1
1 0 1 0 0 1 0 1 0 1
1 0 1 0 0 0 0 0 0 1
1 0 1 1 1 0 1 1 1 1
1 0 1 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

1 - обозначает стен

0 - непроходимый проход

SAMPLE OUTPUT:
##########
#SXX     #
# #X######
# #XX    #
# ##X# ###
# # X# # #
# # XX   #
# ###X####
# #  XXXE#
##########

Код

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class MazeSolver {

    private char [][] maze = null;
    private BufferedReader br = null;
    private File f;
    private static int startX = 0;
    private static int startY = 0;
    private int endX = 0;
    private int endY = 0;
    private int height = 0;
    private int width = 0;

    public static void main(String[] args) {

        MazeSolver ms = new MazeSolver();
        String fileName = args[0];
        ms.buildMaze(fileName);
        ms.formatMaze();
        if(ms.solve(startX, startY)) {
            ms.printMaze();
        }
        else {
            System.out.println("The maze could not be solved");
        }               
    }   


    /**
     * Populates the 2d maze with the input from the given file
     * @param file
     */
    private void buildMaze(String file) {

        char temp;
        String line = null;
        int count = 1;
        int heightCounter = 0;
        try {
            f = new File(file);
            if(!f.exists() || f.isDirectory()) {
                throw new FileNotFoundException();
            }

            //Read each file line to populate necessary variables and maze coordinates
            br = new BufferedReader(new FileReader(file));
            while((line = br.readLine()) != null) {
                switch (count) {
                case (1):
                    width = Integer.parseInt(line.substring(0, line.indexOf(' ')));
                    height = Integer.parseInt((line.substring(line.indexOf(' ')+1)));
                    maze = new char[height][width];
                    break;
                case (2):
                    temp = line.charAt(0);
                    startY = Character.getNumericValue(temp);
                    temp = line.charAt(2);
                    startX = Character.getNumericValue(temp);
                    break;
                case (3):
                    endY = Integer.parseInt(line.substring(0, line.indexOf(' ')));
                    endX = Integer.parseInt((line.substring(line.indexOf(' ') +1 )));
                    break;
                default:
                    int counter = 0;
                    for (int i = 0; i < line.length(); i++){
                        if(line.charAt(i) != ' '){
                            maze[heightCounter][counter] = line.charAt(i);
                            counter++;
                        }
                    }
                    heightCounter++;
                    break;
                }
                count++;
            }
        }
        catch(FileNotFoundException fnfe) {
            System.out.println("The file : " + f.getName() + " does not exist" );
            fnfe.printStackTrace();         
        }
        catch(IOException ioe) {
            ioe.printStackTrace();
        }
        catch(ArrayIndexOutOfBoundsException aioob){
            aioob.printStackTrace();
        }
    }


    /**
     * Formats the maze
     * Replaces 1s with '#' and 0s with ' '
     * Also sets start and end values 'S' and 'E'
     */
    private void formatMaze() {

        maze[startX][startY] = 'S';
        maze[endX][endY] = 'E'; 

        for (int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {

                if(maze[i][j] == '1') {
                    maze[i][j] = '#';
                }

                if(maze[i][j] == '0') {
                    maze[i][j] = ' ';
                }
            }  
        }       
    }


    /**
     * Finds the path to the exit by marking each visited point and
     * recursively calling the method with new coordinates until the exit
     * is reached
     * @param i     - x coordinate
     * @param j     - y coordinate
     * @return      - true when maze is solved
     */
    private boolean solve(int i, int j) { 

        if (maze[i][j] == '#') {
            return false;
        }

        if (maze[i][j] == 'E') {
            return true;
        }

        if (maze[i][j] == 'X') {
            return false;
        }

        maze[i][j] = 'X';

        //South
        if ((solve(i + 1, j)) == true) {
            return true;
        }
        //West
        if ((solve(i, j - 1)) == true) {
            return true;
        }
        //East
        if ((solve(i , j + 1)) == true) {
            return true;
        }
        //North
        if ((solve(i - 1 , j)) == true) {
            return true;
        }       

        maze[i][j] = ' ';
        return false;
    }


    /**
     * Prints the solved maze path
     */
    private void printMaze() {

        maze[startX][startY] = 'S';
        for (int i = 0; i < maze.length; i++) {
            System.out.println(maze[i]);
        }
    }
}


Комментарии
1 ответ

Поскольку вы говорили о buildMaze способ, я начну есть.

Хотя следующий тест может показаться полезным :
if(!f.exists() || f.isDirectory()) { это на самом деле уже подразумевается FileReader, так что вы должны пропустить его.

Не перехватывать исключения в MazeSolver для того, чтобы просто использовать печатные на них. Пусть пузырь до тех пор, пока у вас есть слой, который может "бороться с ними"... в вашем случае, вы можете справиться с ними в main метод.

Вы должны также контролировать действия пользователей вход как можно скорее, если, например, стартовая позиция находится вне границ не обнаружить его до solve метод. То же самое идет для начала/окончания позиции, которая находится в стене.

Также во втором случае в ваш выключатель будет давать плохой стартовой позиции, если один из значение >= 10.

Есть несколько выкройка на входе. ИМО Scanner (https://docs.oracle.com/javase/8/docs/api/java/util/Scanner.html) класс лучше подходит для вашего варианта использования, чем цикл с переключателем, как я покажу ниже.

Наконец, читатель (сейчас сканер) должны быть закрыты в коде, в противном случае ресурсы могут течь (ну, впринцепе, файл будет автоматически закрыт после окончания программы, но лучше использовать "чистый" путь с самого начала).

Есть 2 способа, чтобы закрыть читателя :


  1. вызывая явного метода close

  2. с помощью try-with-resource

Мы не будем использовать первый вариант, он многословен, нецелесообразно при работе с исключениями и... просто реклама ^^

Поэтому в итоге код должен выглядеть так :

int heightCounter = 0;
try (Scanner sc = new Scanner(file)) {
width = sc.nextInt(); // this will throw an exception if the next token cannot be parsed as an int
height = sc.nextInt();
maze = new char[width][height];
startX = sc.nextInt();
startY = sc.nextInt();
endX = sc.nextInt();
endY = sc.nextInt();
sc.nextLine(); // necessary to get rid of the final line-feed
while (sc.hasNext()) {
String line = sc.nextLine();
// same logic than your default case here
}
// don't forget to control the start and end position
}


Ну, давайте перейдем к другой части вашего кода :

Вы не должны установить StartX и starty, чтобы быть статичным. Вы только использовать это, чтобы быть в состоянии назвать ms.solve(startX, startY)... чтобы избежать этой проблемы, вы могли бы дать solve метод, который не принимает никаких параметров и делегатов на ваш "настоящий" решить так :

public boolean solve() {
return solve(startX, startY);
}

Это довольно опрятно, потому что это новое решение дает лучшее абстракция ; две птицы с одним камнем, в основном ^^

Делаешь условий такой : if ((solve(XXXX, YYYY)) == true) { не является полезным, вы должны предпочитают просто писать if (solve(i + 1, j)) { ;)

В более общем плане, есть что-то, что меня беспокоит в вашем стиле :
в MazeSolver это гораздо больше, чем простой помощник : он на самом деле магазины лабиринте он пытается решить, и это также отвечает за печать.
Он делает слишком много.

Для первой части, вы должны рассмотреть перемещение сетки в собственный Maze класс, buildMaze метод может быть static method что возвращает новый Maze от данного файла. В MazeSolver теперь решить данный лабиринт такой :

MazeSolver solver = new MazeSolver(Maze.buildFrom(filename));
if (solver.solve()) {
// print something here....

В Maze может выглядеть так :

public class Maze {
private char[][] maze;
private int startX;
private int startY;
private int endX;
private int endY;

public Maze(final char[][] maze, final int startX, final int startY, final int endX, final int endY) {
// set the fields here and validates the data
}

// getter, setters...

public static Maze buildFrom(final String filename) throws IOException {
int heightCounter = 0;
try (Scanner sc = new Scanner(new File(filename))) {
int width = sc.nextInt();
int height = sc.nextInt();
char[][] maze = new char[width][height];
int startX = sc.nextInt();
int startY = sc.nextInt();
int endX = sc.nextInt();
int endY = sc.nextInt();
sc.nextLine(); // necessary to get rid of the final line-feed
while (sc.hasNext()) {
String line = sc.nextLine();
// same logic than your default case here
}
return new Maze(maze, startX, startY, endX, endY);
} catch (InputMismatchException e) {
throw new IOException("Input cannot be parsed", e);
}
}
}

О втором этапе printMaze способ также проблема ИМО. MazeSolver не знать о консоли... ни он должен знать что-нибудь о печати, фактически... же справедливо и для нового Mazeобъект(ы) если вы решили добавить его.
Таким образом, вы должны заменить этот метод с методом, который дает вам String и это будет абонента обязаны что-то делать с возвращенной строки... либо распечатать его на консоль, как вы уже делаете (с System.out.println) или, может быть, положить его в файл... или даже отправить его в Твиттер :Р


Надеюсь, что это помогает. Если вы хотите, вы можете предоставить обновленную версию ваш код в новый вопрос ;)

3
ответ дан 7 февраля 2018 в 07:02 Источник Поделиться