-2

我知道这并不完美，而且我知道它还没有完成。棋盘是一个 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;
}
4

1 回答 1

0

这是一个寻路问题。正如 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>();

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

于 2013-10-31T05:47:17.177 回答