javascript - 创建随机二维凹多边形景观 JavaScript

Question

我正在用 JavaScript ( http://www.isogenicengine.com/demos/1.1.0/lander/ ) 编写一个简单的月球着陆器克隆，而不是只有高低的基本景观，我想要一种算法来生成随机的洞穴状空间。给定一个使用 [0, 0, 1920, 1200] 的矩形区域，该算法应该能够生成如下图所示的内容。理想情况下，洞穴区域的任何“入口”都应具有固定宽度，以便着陆器可以进入“内部”。

我认为这可能是不可能的，我可以像上面那样绘制一堆图像并将像素数据转换为粗略的多边形数据，但随机生成关卡会更酷!

对于超硬核加分，能够指定有多少个类似洞穴的结构就更牛逼了。

算法的输出将是一个点数组，每个点都是一个包含 x 和 y 属性 {x: val, y: val} 的对象，当您在当前点和下一个点之间按顺序画线时，使得向上多边形。

如果有人有类似的 JavaScript 实现，那也会有很大帮助!

Answer 1

首先了解什么是气泡图，因为它在建筑中的使用。这是一个空间的拓扑图，气泡作为空间，线条代表 channel 。我没有找到任何一个很棒的网页可以快速推荐，但进行图像搜索会产生很多示例。

可以将气泡图视为以气泡为顶点的图形。在您的示例中，将“天空”(包括顶部边缘的 Blob )建模为顶点。洞穴是另一个顶点，入口是一条边。从这个 Angular 来看，您可以轻松生成任意多的洞穴式复杂性。

下一个技巧是将它变成几何图形。从本质上讲，您想要从图表的骨架中推出，并在玩家可以导航的地方留下空隙。同时，您要确保这些空隙不会伸出太远并变薄或消除壁。因此，您还需要对实体区域进行建模，这是通过 dual graph 完成的。 .对偶图位于原始图的“下方”，从某种意义上说，边缘交叉代表冲突，解决后有利于空而不是实。

总结: (1) 制作一个具有你想要的特征的拓扑图。 (2) 为图形创建几何图形，为每个顶点分配一个位置，为每条边分配一条路径。 (3) 构造对偶图，并赋值其几何。 (4) 通过向外生长来充实与每个图形相关的空间，解决有利于通过而不是阻塞的冲突。

您可能想说服自己，最终几何体的周长列表可以通过图的半边遍历生成，就像一只手扶着墙走迷宫一样。