迷宫递归和最短路径

Question

我知道这并不完美，我知道它还没有完成。该板是一个 19 x 19 的数组，其中 1 代表空正方形。现在，它将直接向下，然后向西走。如果它的左侧有一堵墙，那么它将有一个堆栈溢出。原因是当它试图"爬"墙时，它最终会一遍又一遍地倒下并坠毁。但是，即使我解决了这个问题，它也不会找到最短的路径。我找到的解决方案是绘制路径，而不是计算它有多少个正方形。

private static int turnsforshortestmove(Vector2 location, int[,] board, int endrow)
{
    if (location.Y == endrow)
    {
        return 0;
    }
    if (board[(int)location.X, (int)location.Y - 1] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X, location.Y - 2), board, endrow);
    }
    else if (board[(int)location.X - 1, (int)location.Y] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X - 2, location.Y), board, endrow);
    }
    else if (board[(int)location.X, (int)location.Y + 1] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X, location.Y + 2), board, endrow);
    }
    else if (board[(int)location.X + 1, (int)location.Y ] == 1)
    {
        return 1 + turnsforshortestmove(new Vector2(location.X + 2, location.Y), board, endrow);
    }
    return 0;
}

Answer 1

这是一个寻路问题。 正如SJuan76已经建议的那样，Dijkstra的算法是这类问题的最佳起点。

给定一个开放/阻塞正方形的网格式地图，其中只允许正交移动（向上、向下、向左和向右），并且每次移动的成本相同，查找从一个网格单元到另一个网格单元的路径涉及相当简单但耗时的迭代可能的移动。

基本原则是创建一个可能的移动列表，并处理每个移动以寻找最短路径。 在每个步骤中，您检查从当前位置可能移动，检查目标位置是否已移动到先前的位置，并将尚未检查的位置（或可以比上一个检查更快地移动到的位置）添加到要处理的列表。 继续处理列表，直到找到目标位置。

你如何 做到这一点是有趣的部分。

您需要

开始做一些事情：

• 一种从网格中的任意点查找可能移动的方法。
• 一种跟踪您已经访问过的位置以及从哪个位置访问过它们的方法。
• 一种快速确定下一步检查最佳位置的方法。

假设你正在使用一个简单的方形网格，你只执行正交移动（向上、向下、向左、向右），并且所有移动的成本都相同，你可以忽略一些在你的方案中没有用的概念。 所以。。。

1. 创建两个集合：一个用于存储要process的位置列表，另一个用于存储visited位置的列表。

2. 将您的起点添加到process列表中。

3. 虽然process列表不为空

   1. 从process列表中获取下一个位置
   2. 如果当前位置是目标，则返回构成路径的先前位置的列表。
   3. 查找从该位置出发的可用移动，不包括visited列表中的任何移动
   4. 将所有未访问的可能移动推送到process列表中

最终，会发生

以下两件事之一：要么你用完尚未检查的可能动作，要么找到你的目标点。

这是一个类似于我上次进行路径查找时使用的结构：

public struct SearchNode
{
    public Vector2 position;
    public SearchNode prior;
    public int TotalCost;
}

visited列表可以使用字典来完成：

var visited = new Dictionary<Vector2, SearchNode>();

process列表可以使用一堆集合类型来完成。 最简单的形式是：

var process = new Queue<Vector2>();

希望我已经给了你一些开始的东西。