7

我被分配了用 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 类,它具有用于在所有基本方向上行驶的 set/get 方法,这些方法将返回布尔值,如下所示:

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

除了任何语法错误,你们能给我一些帮助吗?非常感谢。

4

5 回答 5

13

在此处输入图像描述

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

为了有机会解决它,您应该:

  • 创建一个Solve()例程并递归调用自身:
    • if 1st, 2nd, 3rd, ... are trueSolve已成功找到解决方案
    • 如果 1st, 2nd, 3rd, ... 包含一个错误,它必须回溯并找到另一种方式
  • 你需要建立一个你去过的地方的缓冲区以避免无限循环
    • 当你采取行动时,它需要密切关注它
    • 当我们遇到死胡同时,我们需要消除不良举动
    • 我们可以通过猜测并在错误时将其删除来实现上述

这是解决方案的一些伪代码。

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;
 }
于 2012-02-16T23:03:02.303 回答
7

您可能应该模块化您的程序-据我所知,您正在从文件中读取迷宫并尝试同时解决它。

更好的方法是将程序分成两个不同的部分:

  1. 读取输入文件并创建一个包含所有数据的矩阵
  2. 从给定的矩阵中解出迷宫

这样做将帮助您分别构建和测试每个部分,这可能会产生更好、更可靠的程序。

解决迷宫可以通过一个简单的BFS来完成,这类似于您最初建议的算法,即DFS 。

于 2012-02-16T20:33:26.113 回答
1

正如阿米特所说,您应该首先阅读整个迷宫并将其存储为二维数组。这使您无需逐行解决即可查看整个迷宫。

由于您首先需要找到数组的大小,因此您应该将文本文件读入字符串列表。

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 个空格 + 1) 或计算任何一个字符串上的符号来获取列数.

存储地图数据的最简单方法是使用 2D 布尔数组。真为墙,假为空。

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

    }

}

既然您将地图数据存储在数组中,那么遍历地图并做出选择就容易多了,您可以使用现成的算法(请参阅 amit 的答案)或自己制作。由于这是家庭作业,您应该尝试自己思考。

玩得开心。

于 2012-02-16T21:37:49.607 回答
0

您需要将程序分为两个阶段。第一个是初始化,在这里您可以阅读迷宫描述和玩家的初始位置。在此之后,您有一个数据结构来表示板。第二个是实际游戏,应该有 3 个抽象:

  • 玩家状态。在您的情况下,它非常简单,它在板上的实际位置。
  • 迷宫本身,也就是环境。它应该具有告诉您是否访问过给定位置、标记您访问过的位置、目标在哪里、下一个可到达的单元格等功能的功能......
  • 逻辑,即搜索算法。

这些中的任何一个都应该能够改变,而其他的没有太大变化。例如,您可能会被要求改进您的搜索算法,或者您有多个目标的问题。从当前问题切换到稍微修改的问题的难易程度是程序设计的真正衡量标准。

于 2012-02-16T21:49:59.183 回答
0

我尝试使用 DFS 算法利用一些 Java OOP 概念来实现这一点。

在我的github 存储库中查看完整的解决方案

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();

}

于 2017-06-06T16:14:22.153 回答