我怎样才能生成(相对)线性的地牢path?

我们正在开发一个动作侧卷轴的概念。 我们需要的是一种生成(相对)直线地图的方法。 通过这个我的意思是像…

在这里输入图像描述

很清楚地看到,这张地图只是一条简单的路线,即使有些偏差。 有了这个,我们也要实施一些迷路,比如捷径,秘密通道。 所以,也许是从第三圈到第四圈,你会有主要的path和一个充满了更强大的敌人的秘密通道,但更快,更高的奖励。

我们在这里陷入了僵局。 我们正在探索几个scheme,但还没有真正取得进展。 我们可以使用什么方法来生成这种path我们不受编程语言的束缚,迄今为止我们已经用Java,C#和C ++进行了实验。 同样,我们没有任何当前的具体游戏引擎的依赖。

要求

  1. 你需要从A到B的多条path
  2. 你想在网格空间工作,大概这是你的侧面卷轴的平铺空间。
  3. 你不希望path交叉,否则会破坏游戏进程。
  4. 你想要path看起来有机的。

Voronoi图

Voronoi图是空间填充,平面图:

在这里输入图像描述

关于他们的一个好处是如何使用它们来创建有机的path。 如果从中心到中心绘制一条直线,则会得到一个不可预知的结果(读取:非直线)。

如何创建Voronoi图以用于基于图块的系统

创建一个合理大小的地图,比如说128×128。 在地图中生成n随机网格坐标(x,y),并使用唯一的ID /颜色填充每个坐标。 为该颜色创建一个列表,并将该起始单元格添加到该列表中; 为每种颜色做这个。

现在,您将这些独特的色点漂浮在空白处,但是您需要在它们周围创建完整的颜色岛,最终效果如下:

在这里输入图像描述

要做到这一点,我们需要看看哪个颜色拥有地图中的每个单元格(单元格=上图中的像素)。 我们遍历地图中的每个单元格,检查n起始色点中哪一个最接近它(通过pythagoras)。 该单元格进入与该唯一的ID /颜色相关的列表…以下称为 AKA Voronoi单元(在上图中,具有相同颜色的像素组)。

你现在应该有一个量化的Voronoi图。 下一步是分析每个岛屿与其他岛屿的邻接关系。 设置一个简单的节点和边缘结构,以便可以存储graphics(节点只是id,该id的列表和边的空列表; edge只是开始和结束节点)。 对于每个独特的岛屿,创建一个节点,并添加边缘,将其链接到每个相邻的岛屿。

一旦你有完整的图表(图),你可以find有趣的部分 – 使用graphicsfind岛链,并通过使链中的每个岛上的所有细胞具有相同的ID,你正在雕刻出你的path。 假设一个拥有ID为503的单元格的岛屿坐在ID为657的岛屿旁边。你可以用一个657 IDreplace所有的503单元格,从而创建一个更大的相邻657岛屿。

例如 – 红色是path1,蓝色是path2,品红色是:

在这里输入图像描述

您可以使用任何现有的graphicsalgorithm(包括A *)从头到尾生成path。 得到一个曲折的道路是一个并不总是使用目标岛的最佳步骤的情况。

最后,如果你想要更窄的path,或者为了获得更好的分辨率而使用更多的岛屿的更大的地图,缩小岛屿是微不足道的。

可选的最后一步,用于寻路

要么你可以使用与底层单元格/拼贴块一起构建的高级graphics来运行A *,或者可以在底层单元格/拼贴块上爬山以获得更好的运动效果:

在目标岛的中心(或任何)坐标处,可以放置影响单元。 这种影响可以像在协作扩散中那样抽出“气味”。 这种气味会一路蔓延回到开始的岛屿,越来越弱。 现在对于一个实体来说,我们只是从一个较低的香味细胞爬到一个更高香味的细胞,每一次都会使您更接近目标 – 就像一只狗一样运作。 每条path大致是线性的,这可以避免在运行时使用A *。 或者你也可以用海岛图来做同样的事情,但是这种方式有点复杂,因为你可能想要在tile级别上导航你的实体。 所以第一种方式可能会更好。 无论哪种方式将允许您以低处理成本导航到目标。