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

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步而在A的北边两步，则只需从{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的路径本身折回去，因此有死角。您可以删除死角，但是路径的长度将与以前相同。

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