c# - 具有定义路径大小的随机路径生成算法

Question

我正在尝试在矩阵内生成一条路径，该路径在所选路径内具有定义的元素数。

我可以毫无问题地从 A 点创建到 B 点:

step(int[] s, int[] e) //start - end
{
   int d = delta(s, e);
   if (d > 1)
   {
      //spread around
      List<int[]> pts = new List<int[]>();
      pts.Add(new int[2] { s[0] -1, s[1]    }); //left
      pts.Add(new int[2] { s[0] +1, s[1]    }); //right
      pts.Add(new int[2] { s[0]   , s[1] +1 }); //top
      pts.Add(new int[2] { s[0]   , s[1] -1 }); //bot

      //remove out of bounds points
      List<int[]> goodPoints = new List<int[]>();
      foreach (var p in pts)
      {
         if (checkValidBoundries(p))
         {
            goodPoints.Add(p);
         }
      }

      //calculate lowest deltas
      int lowestDelta = int.MaxValue;
      int[] bestFit = new int[2];
      foreach (var p in goodPoints)
      {
         int localDelta = delta(p, e);
         if (localDelta == lowestDelta) //local shuffle
         {
            if (await coinFlip())
            {
               bestFit = p;
            }
         }
         else if (localDelta < lowestDelta)
         {
            lowestDelta = localDelta;
            bestFit = p;
         }
      }

      matrix.setValue(bestFit[0], bestFit[1]);
      step(bestFit, e);
   }
}

这段代码会递归迭代，直到路径结束。 这是我获得最短路径的方式。

所以我的问题是:如何在路径中定义多个元素？

例如:从 A 到 B 这个算法给了我 6 个元素，无论路径如何，它总是使用点之间的最小增量。但是，如果我希望这条路径有 7、8 个元素长呢？

我尝试一次从路径中选择一个元素并将其锁定，以便下次运行时它不会将其视为有效，但它一直出错。

新路径可以是随机的没问题我只是想控制“最佳路径”内的元素数量。

有什么帮助吗？提前致谢

Answer 1

看来你想在一个没有障碍物的格子中找到两点A和B之间最近的路径。运动必须在四个主要方向之一。然后，您想要延长这条路径，使其具有一定的长度。

首先，如果没有障碍物，你不需要探查所有方向。例如，如果 B 在 A 的东边 4 步和北边的两步，只需从 {E, E, E, E, N, N} 中随机选择步数(或打乱数组)直到到达。

A 和 B 之间的最短距离 d* 是曼哈顿距离:

d* = |A.x - B.x| + |A.y - B.y|

如果您将网格想象成棋盘的颜色，则 A 和 B 之间的距离为偶数，如果它们具有相同的颜色，否则为奇数。这不仅适用于最短距离，还适用于 A 和 B 之间任何有效路径的距离。因此，您只能获得 d* + 2·k 的距离。

您可以通过在理想路径中添加小的“弯路”来获得更长的路径:

        · · · · · · · ·            · · · · · · · ·            · · · · · · · ·
        · · · · · · B ·            · · · · · · B ·            · · · · · · B ·
        · · · · ┌───┘ ·            · u · · ┌───┘ ·            · · · · ┌───┘ ·
        · · · · │ · · ·            · ╒═╕ · └─╖ · ·            · · · ╔═╡ · · ·
        · ┌─────┘ · · ·            · │ └─────╜ v ·            · ┌───╜ ╧ w · ·
        · A · · · · · ·            · A · · · · · ·            · A · · · · · ·
        · · · · · · · ·            · · · · · · · ·            · · · · · · · ·

“凹痕”u 和 v 中的每一个都会向您的路径添加两个部分。当你制作凹痕时，注意不要在已经有一段路径的地方留下凹痕:凹痕 w 有一段路径向后折叠，所以有一个死胡同。您可以移除死胡同，但路径的长度将与以前相同。

如何实现所有这些留给读者作为练习。 :)