生成具有定义好的最小和最大距离的随机点

Question

我需要算法的想法，用于生成在二维空间中具有定义的最小和最大可能点之间距离的点。

基本上，我想找到一种好的方法将一个点插入到充满点的二维空间中，使该点具有随机位置，但离最近点的距离大于MINIMUM_DISTANCE_NUM且小于MAXIMUM_DISTANCE_NUM。

我需要它用于游戏，所以它应该快速，并且不依赖于随机概率。

- deloki

---

需要添加更多信息吗？它们必须随机添加还是可以预先呈现，以便按升序添加它们是可能的？应该插入固定数量的点还是在这些约束条件下没有更多可能的位置时应该停止？ - Sebastiaan van den Broek

Answer 1

将点集存储在Kd树中。随机生成一个新点，然后查找它的最近邻，这些最近邻可以在Kd树中快速查找得到。如果该点被接受（即MIN_DIST < 最近邻 < MAX_DIST），则将其添加到树中。

需要注意的是，在点密度不太高的情况下，即MIN * N << L，其中N为点数，L为放置它们的盒子的维数，此方法效果最佳。如果不符合此条件，则大多数新点将被拒绝。但请考虑，在这种情况下，您正在将弹珠装入盒子中，而上面一定密度后排列方式可能就不能非常“随机”了。

- gcbenison

Answer 2

您可以使用一个二维点的常规网格（P0，P1，P2，P3，...，P（m*n），其中m是网格的宽度，n是高度）。

每个点都与以下两个内容相关联：1）一个布尔值，表示该网格点是否被使用，2）从此网格位置移位以避免过于规则。 （或者您可以将点+移位坐标放入您的网格中）

然后，当您需要一个新点时，只需选择一个尚未使用的随机网格点，将此点声明为“已使用”，并在游戏中使用点+移位。

这取决于您的二维空间的n，m，宽度/高度以及您将要使用的点的数量，这可能非常好。

- GameAlchemist

---

很高兴能够帮助。我想补充一下：1）你可以通过将所有网格点按随机顺序一个接一个地放入另一个数组中（使用标志以避免重复放置同一点），从而预先计算随机点，这样当你需要一个点时，只需取n+1个点即可。（更快）2）你可能会将此标记为答案 :-)。 - GameAlchemist

Answer 3

一个很好的选择是使用泊松盘采样。该算法高效(O(n))，"生成的点紧密排列，但彼此之间距离不会比指定的最小距离更近，从而产生更自然的模式"。

https://www.jasondavies.com/poisson-disc/

- antonagestam

Answer 4

你说的是多少个点？如果你对点的数量有一个上限，你可以生成（预计算）一个点的数组并将它们存储在数组中。将该数组存储在文件中。

在地图加载之前，你可以完成所有艰难的计算处理（这样你就可以使用任何随机点生成算法），然后以一种快速的方式获取你的点。

这样，你可以生成大量不同的地图，然后随机选择其中一个地图来生成你的点。

只有在有一个上限并且你可以在游戏加载之前预先计算出这些点时，这种方法才有效。

- joe_coolish