创建一个随机的二维凹多边形景观JavaScript

Question

我正在使用JavaScript编写一个简单的月球着陆器克隆版（http://www.isogenicengine.com/demos/1.1.0/lander/）。与其使用只有高低之分的基本景观，我想要一个算法来生成类似洞穴的随机空间。给定一个矩形区域[0, 0, 1920, 1200]，该算法应该能够生成如下图所示的东西。理想情况下，任何进入洞穴区域的“入口”都应该有一个固定的宽度，以便着陆器可以“进入”其中。

我已经考虑到这可能不可能实现，我可以像上面那个一样画出一堆图像，并将像素数据转换为粗略的多边形数据，但是随机生成的关卡会更酷！对于超级困难的奖励点，能够指定有多少个类似洞穴的结构将会更加棒。算法的输出将是一个点数组，每个点都是一个包含x和y属性的对象{x:val，y:val}，当您依次在当前点和下一个点之间绘制线条时，就会组成多边形。如果有人有类似东西的JavaScript实现，那也会帮很大忙！

- Rob Evans

---

看看这些，它们可能会有所帮助：http://accidentalnoise.sourceforge.net/minecraftworlds.html http://gamedev.stackexchange.com/questions/20588/how-can-i-generate-worms-style-terrain http://gamedev.stackexchange.com/questions/15912/terrain-generation-for-tile-based-2d-platformer - mfreitas

Answer 1

从学习什么是气泡图开始，因为它在建筑中被使用。它是空间的拓扑图，用气泡表示空间，用线表示通道。我没有找到一个可以快速推荐的优秀网页，但是进行图片搜索会得到很多示例。

可以将气泡图看作带有气泡作为顶点的图形。在您的例子中，将“天空”，包括顶部边缘的区域，建模为一个顶点。洞穴是另一个顶点，入口是一条边。从这个角度来看，很容易生成想要的洞穴复杂度。

下一个技巧是将其转化为几何图形。基本上，您希望从图形的骨架向外推出，并制造出玩家可以导航的空洞。同时，您还希望确保这些空洞不会推得太远并稀薄或消除墙壁。因此，您还需要对实体区域进行建模，这是通过对偶图完成的。对偶图“位于”原始图形下方，因为边界交叉代表冲突，这种冲突以空洞取代实体而得到解决。

总结：(1) 制作包含所需特征的拓扑图。(2) 为图形创建几何形状，为每个顶点分配位置和每个边分配路径。(3) 构建一个对偶图，并分配其几何形状。(4) 通过向外扩展来完善与每个图形相关联的空间，以通行为优先而不是阻塞来解决冲突。

您可能希望自己确信最终几何形状的周长列表可以通过对图进行半边遍历生成，就像在迷宫中走路时手上靠着一堵墙。

- eh9

Answer 2

如果您感兴趣，可以使用Marching Squares将2D标量值场（可能是从Perlin或Simplex Noise获取的）转换为一组边缘线。当然，最终看起来像什么取决于您如何获得2D标量值场（如何操作Perlin或Simplex Noise）。

这个是我能找到的最好的详细介绍网站。（它的文档不如其3D孪生兄弟Marching Cubes那么全面）

实际上，Wiki页面上的介绍也很好。

- Miles