javascript - 在游戏地图上创建非均匀空间

Question

我需要有关创建游戏地图的建议。我需要在地图上创建 1400 个空间。我想象每个空间将是 10 种不同尺寸中的一种——例如，它们将是 10 个“size-10”，40 个“size-9”等，最小的有几百个-sizes（这是数据驱动的）。中心也会有一个中性空间（可能比其他所有空间都大一点）。我想将这些区域随机放置在游戏空间上，但它们之间不应有重叠，也不应有空间。总空间是否为矩形并不重要。我真的很喜欢这种努力，虽然它非常不符合我的要求，但它让我研究了 voronoi tesselations 并找到了一个javascript 实现我有点理解，但是我看到的所有示例都使用随机点作为原点，并且我正在寻找如上所述的更自定义的结果，所以这可能不是要走的路。--- 无论如何，我愿意接受任何建议。请注意，我是一名设计师而不是一名编码员，但我正在编写自己的原型，所以任何建议都值得赞赏。

Answer 1

如果我理解正确，您想要实现的是所谓的路径定向细分树或四叉树。该算法的特点是将一个矩形二维空间递归地划分为四个更小的部分，称为象限或四边形。这些区域可以是正方形或矩形，或者可以具有任意形状。

如果您需要一个真实的示例来研究代码，您可以将这个实验在 Actionscript 中创建作为起点，但这也可以很好地翻译成 Javascript：http ://wonderfl.net/c/fLVs

另一种可能性是手动选择控制点的Delaunay 三角剖分，因为如果理解正确，您不想随机分散这些点。也许这个链接会有所帮助： http: //neoformix.com/2012/DelaunayImages2.html

我希望这些有帮助！

Answer 2

如果我理解正确，这似乎类似于背包问题。但是，您不是在优化，而是在寻找一个单一的解决方案。这实际上是一个很难尝试和解决的问题，无论是在时间复杂度方面，还是在让一些合理的事情（即在合理的时间内完成）工作方面。这是一篇关于它的有趣帖子（尽管他处理优化问题）——只需一点工作，你就可以提供一个足够好的算法。