用Java创建迷宫求解算法-Java 学习之路

我被赋予了在Java中创建迷宫求解器的任务 . 这是作业：

Write an application that finds a path through a maze.  
The maze should be read from a file.  A sample maze is shown below.

O O O O O X O
X X O X O O X
O X O O X X X
X X X O O X O
X X X X O O X
O O O O O O O
X X O X X X O

字符“X”表示墙壁或阻挡位置，字符“O”表示打开位置 . 你可以假设迷宫的入口总是在右下角，出口总是在左上角 . 您的程序应将其输出发送到文件 . 如果找到路径，则输出文件应包含路径 . 如果未找到路径，则应将消息发送到该文件 . 请注意，迷宫可能有多个解决方案路径，但在本练习中，您只需要找到一个解决方案，而不是所有解决方案 .

您的程序应该使用堆栈来记录它正在探索的路径，并在它到达阻塞位置时回溯 .

在编写代码之前，请务必编写完整的算法 . 您可以随意创建任何可帮助您完成作业的其他课程 .

Here's my Algorithm:
1)Initialize array list to hold maze
2)Read text file holding maze in format
    o x x x x o
    o o x o x x
    o o o o o x
    x x x x o o
3)Create variables to hold numbers of columns and rows
3)While text file has next line
    A. Read next line
    B. Tokenize line
    C. Create a temporary ArrayList
    D. While there are tokens
        i. Get token
        ii. create a Point
        iii. add point to temp ArrayList
        iv. increment maximum number of columns
    E. Add temp to maze arraylist, increment max rows
    F. initialize a hold of points as max rows - 1
    G. Create a start point with x values as maximum number of rows - 1, and y values as maximum number of columns - 1
    H. Create stack of points and push starting location
    I. While finished searching is not done
        i. Look at top of stack and check for finish
        ii. check neighbors
        iii. is there an open neighbor?
            - if yes, update flags and push
            - if no, pop from stack
    J. Print solution
4. Done is true

无论如何，我设置的是一个Points类，它设置/获取在所有基本方向上行进的方法，这些方法将返回如图所示的布尔值：

public class Points<E>
{
private int xCoord;
private int yCoord;
private char val;
private boolean N;
private boolean S;
private boolean E;
private boolean W;

public Points()
{
    xCoord =0;
    yCoord =0;
    val =' ';
    N = true;
    S = true;
    E = true;
    W = true;

}

public Points (int X, int Y)
{
        xCoord = X;
        yCoord = Y;

}

public void setX(int x)
{
    xCoord = x;
}
public void setY(int y)
{
    yCoordinate = y;
}

public void setNorth(boolean n)
{
    N = n;
}
public void setSouth(boolean s)
{
    S= s;
}
public void setEast(boolean e)
{
    E = e;
}

public void setWest(boolean w)
{
    W = w;
}

public int getX()
{
    return xCoord;

}

public int getY()
{
    return yCoord;
}
public char getVal()
{
    return val;
}

public boolean getNorth()
{
    return N;
}
public boolean getSouth()
{
    return S;
}

public boolean getEast()
{
    return E;
}
public boolean getWest()
{
    return W;
}

public String toString1()
{
    String result = "(" + xCoord + ", " +yCoord + ")";
    return result;
}

}

我只是在主要的实际解决方面遇到了问题 . 这就是我所拥有的：

import java.io.*;
import java.util.*;
import java.lang.*;
import java.text.*;


public class MazeSolve1
{
  public static void main(String[] args)
  {
//Create arrayList of Points
ArrayList<ArrayList<Points>> MAZE = new ArrayList<ArrayList<Points>>();
Scanner in = new Scanner(System.in);

//Read File in
System.out.print("Enter the file name: ");
String fileName = in.nextLine();
fileName = fileName.trim();
FileReader reader = new FileReader(fileName+".txt");
Scanner in2 = new Scanner(reader);

//Write file out
FileWriter writer = new FileWriter("Numbers.out");
PrintWriter out = new PrintWriter(writer);
boolean done = false;
int maxCol = 0;
int maxRow = 0;

while(!done) {

    //creating array lists
    while (in2.hasNextLine()) {
        //Read next line
        String nextLine = in2.nextLine();
        //Tokenize Line
        StringTokenizer st = new StringTokenizer(nextLine, " ");
        //Create temp ArrayList
        ArrayList<ArrayList<Points>> temp = new ArrayList<ArrayList<Points>>();

        //While there are more tokens
        while (st.hasNextToken()) {
            String token = st.nextToken();
            Points pt = new Points();
            temp.add(pt);
            maxCol++
        }
        MAZE.add(temp);
        maxRow++;
    }

    //create hold arraylist for max rows of maze -1 
    //create variables for start x and y coordinates
    ArrayList<ArrayList<Points>> hold = new ArrayList<ArrayList<Points>>();
    hold = MAZE.get(maxRow - 1);
    int startColumn = hold.get(maxCol - 1);
    int startRow = hold.get(maxRow - 1);
    Point start = new Point();
    start.setX(startColumn);
    start.setY(startRow);

    //initialize stack, and push the start position
    MyStack<Points> st = new ArrayStack<Points>();
    st.push(start.toString1());
    //south and east of start are edges of array
    start.setSouth(false);
    start.setEast(false);

    //while your position is not equal to point (0,0) [finish]
    while (st.peek() != "(0, 0)") {

        //getting the next coordinate to the North
        int nextY = start.getY() - 1;
        int nextX = start.getX();

        //if character to the North is an O it's open and the North flag is true
        if (hold.get(nextY) = 'O' && start.getNorth() == true) {
            //set flags and push coordinate
            start.setNorth(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop(); }

        //look at coordinate to the East
        nextX = start.getX() + 1;
        //if character to the East is a O and the East flag is true
        if (hold.get(nextX) = 'O' && start.getEast() == true) {
            //set flags and push coordinate
            start.setEast(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop(); }

        //look at coordinate to the South
        nextY = start.getY() + 1;
        //if character to the South is a O and the West flag is true
        if (hold.get(nextY) = 'O' && start.getSouth() == true) {
            //set flags and push coordinate
            start.setSouth(false);
            st.push(start.toString1());
        }
        //else pop from stack
        else { st.pop() }

        //keep looping until the top of the stack reads (0, 0)
    }

done = true;
}

//Print the results
System.out.println("---Path taken---");   
for (int i = 0; i< st.size(); i++) {
    System.out.println(st.pop);
    i++
}

除了任何语法错误，你们可以给我一些帮助吗？非常感谢 .

5 回答

13
我在这里提交了类似的答案Maze Solving Algorithm in C++ .

要有机会解决它，你应该：
- 创建 Solve() 例程并递归调用自身：
- 如果第1，第2，第3，......都是真的 Solve 已成功找到解决方案
- 如果1st，2nd，3rd，...包含false，则必须回溯并找到另一种方式
- 您需要构建一个缓冲区，以避免无限循环
- 当你做出动作时，它需要密切关注它
- 当我们走到死胡同时，我们需要消除不良行动
- 我们可以通过猜测来实现上述操作，如果错误则将其删除
这是解决方案的一些伪代码 .
```
boolean solve(int X, int Y)
{
    if (mazeSolved(X, Y))
    {
        return true;
    }

    // Test for (X + 1, Y)
    if (canMove(X + 1, Y))
    {
        placeDude(X + 1, Y);
        if (solve(X + 1, Y)) return true;
        eraseDude(X + 1, Y);
    }

    // Repeat Test for (X - 1, Y), (X, Y - 1) and (X, Y + 1)
    // ...

    // Otherwise force a back track.
    return false;
 }
```
回复于 2024-05-03T09:33:31+08:00
0
您可能应该module您的程序 - 我可以理解，您正在从文件中读取迷宫并尝试同时解决它 .

更好的方法是将程序分成两个不同的部分：
- 读取输入文件并创建包含所有数据的矩阵
- 解决给定矩阵的迷宫
这样做可以帮助您单独构建和测试每个部分，这可能会产生更好，更可靠的程序 .

解决迷宫可以通过简单的BFS来完成，这类似于你的算法最初建议的，这是一个DFS
回复于 2024-05-03T09:33:31+08:00
7
正如amit所说，你应该首先阅读整个迷宫并将其存储为二维数组 . 这使您可以看到整个迷宫，而无需逐行解决 .

由于您首先需要查找数组的大小，因此您应该将文本文件读入字符串列表 .
```
List<String> strs = new ArrayList<String>();

//Pseudocode, choose however you want to read the file
while(file_has_next_line) {
    strs.add(get_next_line);
}
```
List的大小为您提供行数，并假设它始终是一个网格，您可以使用split（） . length，（count spaces 1）或计算任何一个字符串上的符号来获取列数 .

存储 Map 数据的最简单方法是使用二维布尔数组 . 墙是真的，虚空是空的 .
```
boolean[][] wallMap = new boolean[rows][cols];

for(int i = 0; i < wallMap.length; i++) {

    //Separate each symbol in corresponding line
    String[] rowSymbols = strs.get(i).split(" ");

    for(int j = 0; j < wallMap[i].length; j++) {

        //Ternary operator can be used here, I'm just keeping it simple
        if(rowSymbols[j].equals("X")) {
             wallMap[i][j] = true;
        } else {
             wallMap[i][j] = false;
        }

    }

}
```
既然您已将 Map 数据存储在数组中，则可以更轻松地遍历 Map 并做出选择，您可以使用现成的算法（请参阅amit的答案）或制作您自己的算法 . 由于这是家庭作业，你应该尝试自己的想法 .

玩得开心 .
回复于 2024-05-03T09:33:31+08:00
0
您需要分两个阶段分离您的程序 . 第一个是初始化，您可以在其中阅读迷宫描述和玩家的初始位置 . 在此之后，您将拥有一个表示电路板的数据结构 . 第二个是实际游戏，应该有3个抽象：
- 玩家状态 . 在你的情况下，它非常简单，它在板上的实际位置 .
- 迷宫本身就是环境 . 它应该有功能告诉你你是否访问过一个给定的位置，标记你访问过的位置，目标在哪里，下一个可到达的单元格等等......
- 逻辑，即搜索算法 .
这些中的任何一个都应该能够在没有其他变化的情况下改变 . 例如，可能会要求您改进搜索算法，或者您有多个目标的问题 . 从当前问题切换到稍微修改的问题的容易程度是程序设计的真实度量 .
回复于 2024-05-03T09:33:31+08:00

我尝试使用DFS算法利用一些Java OOP概念来实现它 .

查看我的github repository上的完整解决方案

private boolean solveDfs() {
    Block block = stack.peekFirst();
    if (block == null) {
        // stack empty and not reached the finish yet; no solution
        return false;
    } else if (block.equals(maze.getEnd())) {
        // reached finish, exit the program
        return true;
    } else {
        Block next = maze.getNextAisle(block);
        // System.out.println("next:" + next);
        if (next == null) {
            // Dead end, chose alternate path
            Block discard = stack.pop();
            discard.setInPath(false);
            // System.out.println("Popped:" + discard);
        } else {
            // Traverse next block
            next.setVisited(true);
            next.setInPath(true);
            stack.push(next);
        }
    }
    return solveDfs();

}

回复于 2024-05-03T09:33:31+08:00

用Java创建迷宫求解算法

5 回答

相关问题