算法在二维地图中生成随机路径

Question

我需要在二维地图中生成一个简单的随机路径。输入参数是多个步骤。条件是每个瓦片在路径上只有两个相邻的瓦片，所以没有房间并且没有十字路口。

我在网上寻找一些解决方案，我没有找到像这样的东西。 Drunkard算法使得房间和其他一切都是迷宫生成算法。也许我不是通过适当的关键字搜索。

重要的是随机性，因为我需要每次都完全不同的路径。

编辑：将样本图像

样品路径：

主要特征是，每个瓦片具有仅2邻居。

改进后的版本将使用特定的目标图块作为路径的末端和步骤的最小和最大值，但现在并不那么重要。

谢谢你的任何想法。

Answer 1

1. 创建2D地图

   所以创建地图的大小的二维数组，并通过例如0

2. 添加N随机障碍

   例如清除地图中填满的圆圈

3. 使用A *找到最短路径

   ，你可以用我的... C++ A* example

如果你想更复杂的东西，那么你可以创建随机地形和使用A *找到最短路径（虽然上涨将花费更多，然后下降...）。为创建随机地形时，你可以使用：

• Diamond and Square Island generator

它可以使用也用于随机地图生成...

Answer 2

将此分解为子部分，您必须采取的唯一随机决定是在路径上的某个给定点处左/右/上/下而不形成交叉点，这可以使用让我们说的任意生成例如机器的时间戳，例如检查最后一位数字是偶数还是奇数，然后向左走偶数和奇数，向上取模4等等，这样每次都给你一条相当随机的路径。

尝试并在相对较快的速度上减慢计算时间跨越很多时间，以引入更多的随机性。

或者，在2D地图上做一个像遍历的DFS，并将每个唯一路径存储在一个哈希映射或集合中，并将一个唯一编号添加到该映射中作为关键，这是预处理部分，现在随机选取从一组所有可能的解决方案中选择唯一的密钥，将其从集合中删除，如果您需要另一个随机唯一路径，只需从其余可用路径中随机挑选一个。