当前位置: 首页 > 知识库问答 >
问题:

Java迷宫解算器——我从来没有这么困过

越景天
2023-03-14

因此,我的任务是创建一个带有队列、集合、位置对象和Cell对象的迷宫求解器,最终形成一个迷宫对象

要快速了解我的所有代码在完成后都会做些什么:

7
10
   _ _ _ _ _ _ _ _ _
|_ _ _  |  _ _   _  |
|  _ _| | |  _  |   |
| |   | |_| | | |_| |
|_ _|_ _   _| |_  | |
|  _    | |  _ _| |_|
| |_ _|  _|   |_    |
|_ _ _ _|_ _|_ _ _| |

对此:

 @ _ _ _ _ _ _ _ _ _
|@ @ @ @|  _ _   _  |
|  _ _|@| |@ @ @|   |
| |   |@|_|@| |@|_| |
|_ _|_ @ @ @| |@ @| |
|  _    | |  _ _|@|_|
| |_ _|  _|   |_ @ @|
|_ _ _ _|_ _|_ _ _|@|
                   @

到目前为止,我所做的一切都很好,但是当我在我的Maze对象中实际编码findPath()方法时,我的代码会生成一个无效的路径。当我接收一个文件来读取迷宫时,我将该迷宫转换为多维字符数组,然后我将该字符数组转换为多维单元格数组,并使用布尔值映射每个单元格的边界北、南、东、西。

现在,我想知道如何在迷宫中导航,我在迷宫的findPath()方法中尝试过,但实际上失败了。

 @  @  @  @  .  .  .  .  .  . 
 .  .  .  @  .  .  .  .  .  . 
 .  @  @  @  .  .  .  .  .  . 
 .  @  @  @  @  .  .  .  .  . 
 .  .  @  @  @  .  .  .  .  . 
 .  @  @  @  @  .  .  .  .  . 
 .  .  .  .  .  .  .  .  .  . 

首先,为了说明我应该实现的目标,让我来看看我的需求文档:

The algorithm operates according to the following pseudo-code:

* Visit the starting Location.
* Add this Location to the set.
* Enqueue the Location in the queue.

while (ArrayQueue<E> != empty( )) 
{
    Dequeue a Location(next) from the queue

        For each neighbor of Location(next) which has
         not yet been placed in the set, repeat:
                * Visit the neighbor of Location(next).
                * Add the neighbor of Location(next) to the Set.
                * Enqueue the neighbor of Location(next)in the Queue.
 }

我几乎可以肯定我在一定程度上正确地使用了他的算法,但我无法找出我做错了什么来获得我遇到的路径。我最头疼的是我在下面包含的Maze对象的findPath()方法。我想我最大的问题是我做错了什么?我已经研究这个好几天了,只是无法弄清楚。感谢任何帮助。我的代码如下:

我迷宫的寻径法

public void findPath()
{
    Location startLocation = new Location(0, 0);
    theMaze[startLocation.getRow()][startLocation.getColumn()].setVisited(true);

    Location endLocation = new Location(6, 9);

    Location cursor;

    locationQueue.enqueue(startLocation);
    locationSet.enter(startLocation);

    while(!locationQueue.isEmpty())
    {
        cursor = locationQueue.dequeue();

        if(cursor == endLocation)
            break;

        for(int i = 0; i < 4; i++)
        {
            Location temp = cursor.getLoc(i);

            if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
            {
                cursor = cursor.getLoc(i);
                theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);

                if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
                {
                    cursor = startLocation;
                    continue;
                }

                locationSet.enter(cursor);
                locationQueue.enqueue(cursor);                          
            }               
        }           
    }

    for(int i = 0; i < locationSet.size(); i++)
    {
        System.out.println("Row " + locationSet.get(i).getRow() + " Column " + locationSet.get(i).getColumn());
        theMaze[locationSet.get(i).getRow()][locationSet.get(i).getColumn()].setPath();
    }

    for(int i = 0; i < theMaze.length; i++)
    {
        for(int j = 0; j < theMaze[i].length; j++)
        {
            System.out.print(theMaze[i][j].toString());
        }
        System.out.print("\n");
    }

}

编辑:我的问题是迷宫对象,而不是其他类,所以我基本上是在清理。

共有1个答案

孟成文
2023-03-14

你的基本算法有缺陷。您只向路径中添加单元格,但如果结果是死胡同,则不会删除它们。

这种问题最适合递归算法。

function findExit(gameMap, listOfVisitedCells, currentCell, solution)
    listOfVisitedCells.add(currentCell);
    for each gameMap.NeighbourOf(currentCell)
        if neighbour not in listOfVisitedCells
             solution.add(neighbour)
             if (gameMap.isExit(neighbour)) {
               return true;
             }
             if (findExit(gameMap, listOfVisitedCells, currentCell, solution)) {
               return true;
             }
             solution.remove(neighbour);
        }
    }
    // No neighbours of the current cell got to find the exit.
    return false;
 }

当然,这将首先探索地图深度,因此如果有多条路径有效,就不能保证找到最短的路径(使用Djikstra的算法)。

更新:从审查您的代码:

在头脑中调试这么多行代码是很困难的,因此不能代替花大量时间使用您选择的调试器,观察程序的实际状态和预期状态,等等。不要期望太多,所以它更适合于具体问题(“我希望这段代码可以做到这一点,但它没有,为什么”),代码量有限。

无论如何,这让我觉得很奇怪:

        Location temp = cursor.getLoc(i);

        if(theMaze[cursor.getRow()][cursor.getColumn()].validDirection(i) && (!locationSet.isElement(temp)) && !(theMaze[temp.getRow()][temp.getColumn()].isVisited()))
        {
            cursor = cursor.getLoc(i);       <-- Why are you overwritting the current
                                             <-- location when you have still not checked
                                             <-- all the posible directions?
            theMaze[cursor.getRow()][cursor.getColumn()].setVisited(true);

            if(theMaze[cursor.getColumn()][cursor.getColumn()].getPathAmount() < 2)
            {
                cursor = startLocation;
                continue;
            }

            locationSet.enter(cursor);
            locationQueue.enqueue(cursor);                          
        }               

我敢打赌这是不对的。当然,可能还有另一个隐藏的问题,如果您尝试自己调试它,以找到无法按预期工作的片段(然后,如果需要,请在这方面寻求帮助),这会更好(并为您提供更多经验)。

 类似资料:
  • 我在一门课上学习序言。我有一个练习,我需要读取一个文件,从中生成一个迷宫,获得从源到目标的路径,然后将其写入一个文件。 我读了文件,对我拥有的每个单元格断言,对连接的每两个单元格断言。 ,,,都是整数坐标,所以我知道起点和终点。 我的工作原理是,如果当前节点连接到目标,完成并返回。否则,找到当前节点所连接的节点,并用新节点调用递归

  • 所以我们有一个迷宫,有墙(W ),开放路径(O ),起点点(S)和终点点(F)。 我试图编写一个算法,采取迷宫文件,然后把它变成一个二维数组的点,使网格。 一旦我有了网格,我想从迷宫中的“S”字符开始,并尝试找到是否有可能穿过“O”到达“f”。(返回布尔值true/false) 我知道这个迷宫是可以解决的,那么为什么我得到了“假”??一定有一个复杂的问题,因为我得到的只是简单的布尔假,而不是“对不

  • 问题内容: 为了编写一个解决C程序的蛮力迷宫,我首先编写了这个Java程序来测试一个想法。我对C还是很陌生,打算在Java中正确处理后将其转换。结果,我试图远离arraylist,fancy库等,以便更轻松地转换为C。该程序需要生成最短步骤的单个宽度路径来解决迷宫问题。我认为我的问题可能在于将通过每个递归传递的路径存储数组碎片化。感谢您的关注。-乔 代码中解释了数字符号 问题答案: 这本来不是要作

  • 问题内容: 我正在尝试使用递归编写一个迷宫求解器,似乎它尝试每个方向一次,然后停止,我不知道为什么。如果您发现问题,请告诉我。钥匙0是一个开放空间1是墙壁2是路径的一部分3是迷宫的末端 问题答案: 在过去五个小时中,您已经问过有关此迷宫递归难题的四个问题,这证明它有多复杂。这整个概念的1/0迷宫电网已吸引了我,我想出了一个类,使它成为一个 整体 变得简单许多。如果需要进行递归,那么它将对您没有用,

  • 我在用递归解迷宫。我的矩阵是这样的 这是更大矩阵的原型。我的求解递归方法如下所示 你们可以注意到,这里我返回一个布尔值,如果我找到一条路径,它应该会给我一个真值。但它总是给我错误的答案。我不确定我在递归方法中犯的逻辑错误。方法如下 endX=3;endY=10;

  • 我正在尝试寻找到EndPotion的路径。这是一个递归函数。请帮助,我要自杀了。 这是给定的地图 我想递归地使用GetPath来到达上面地图中的EndPotion。参数是当前位置、结束位置和地图。对于这个例子,起始位置是(0,0)和结束,EndPotionis是(0,3),右上角。0代表墙壁,1代表路径。 我需要返回一个包含有效点的arraylist到结束位置。虽然我的数组大小始终为0,并且基本大