4

所以我的任务是创建一个具有队列、集合、位置对象和单元对象的迷宫求解器，最终形成一个迷宫对象。

快速浏览一下完成后我的所有代码基本上会做什么：

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() 方法。我想我最大的问题是我做错了什么？我已经在这几天了，只是无法弄清楚。任何帮助表示赞赏。我的代码如下：

My 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");
    }

}

编辑：我的问题是 Maze 对象而不是其他类，所以我基本上是在清理。

4

1 回答 1

3

你的基本算法有缺陷。您只需将单元格添加到路径中，但如果它们变成死胡同，请不要删除它们。

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

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 算法）。

更新：通过查看您的代码：

很难在心理上调试这么多行代码，而且 SO 不能代替花大量时间使用您选择的调试器，观察程序的实际状态与预期状态，等等。不要期望太多，SO 更适合于代码量有限的具体问题（“我希望这段代码能做到这一点，但它没有，为什么”）。

无论如何，这让我觉得很奇怪：

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

我敢打赌这是不正确的。当然，可能还隐藏了其他问题，如果您尝试自己调试它以找到无法按预期工作的片段（然后，如果需要，请在 SO 中寻求帮助），会更好（并为您提供更多经验）。

于 2013-04-04T09:30:17.050 回答