创建随机2D凹面多边形景观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

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

气泡图可以被视为以气泡为顶点的图。在您的示例中，将“天空”（包括顶部边缘的斑点）建模为顶点。洞穴是另一个顶点，入口是一条边。有了这个视角，就可以轻松地生成您想要的尽可能多的洞穴式复杂性。

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

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

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