如何在没有昂贵的跳跃模拟的情况下在2D平台游戏中生成航点地图？

Question

我正在开发一款游戏（使用Game Maker：Studio Professional v1.99.355），它需要具有用户可修改的关卡几何和基于平台物理的AI寻路。因此，我需要一种方法来动态地确定哪些平台可以从哪些平台到达，以便构建我可以提供给A *的节点图。

我目前的做法或多或少是这样的：

1. 对于每个平台，请考虑该级别中的每个其他平台。
2. 对于每个平台，如果它显然无法到达（例如，由于高于最大跳跃高度），请不要形成链接并转到下一个平台。
3. 如果链接看起来可能，请在起始平台上放置一个ai_character实例，并（在当前步骤事件中）模拟跳转尝试。

3.a对起始平台上的每个可能的起始位置重复此跳转尝试。

4. 如果此尝试成功，请记录实时复制所需的数据，然后转到下一个平台。
5. 如果没有，请不要形成链接。
6. 对所有平台重复。

这种方法或多或少有效，并产生一个链接结构，在可视化时如下所示：

linked platforms（超链接，因为没有代表。）

在这个例子中，右下角隐藏着大部分隐藏的粉红色幽灵试图到达黑白盒子。浅蓝色矩形只是突出显示识别平台的位置，实际平台是灰色框的行。链接线在原点处为绿色，在目标处为红色。

这种方法存在的巨大而明显的问题是，对于仅有17个平台的级别（如上所示），生成节点图需要一秒钟的时间。原因很明显，屏幕中心的黄色文字向我们展示了构建图表需要多长时间：超过24,000（！）个模拟帧，每个帧都对每个块进行附带冲突检查 - 我只是运行角色的步骤事件在一个循环中，所以它通常会做一切来处理一个框架中的平台运动，它现在做了24,000次。

这显然是不可接受的。如果它只在17个平台上严重缩放，那么对于我需要支持的数百个玩家来说，这将是一个笑话。哎呀，按照这个几何时间成本，它可能需要数年时间。

为了加快速度，我专注于另一个重要的调试编号，测试计数器：239。如果我只是尝试了每个可能的起始和目标平台组合，我需要运行17 * 16 = 272个测试。通过找出预测跳跃是否不可能的各种方法，我已经设法降低了高达33（12％！）的昂贵测试数量。然而，我添加到代码中的异常和特殊情况越多，我就越确信实际问题出现在跳转模拟代码中，这让我终于得到了我的问题：

如何完全可靠地确定角色是否可以从一个平台跳到另一个平台，最好不需要模拟整个跳跃？

我的具体平台物理：

跳跃是固定的高度，除非你达到天花板。

水平运动没有加速度或惯性。

允许水平空气控制。

进一步的信息：我发现this video，它描述了一个类似的问题，但没有提供一个很好的解决方案。这实际上是我发现的唯一资源。

Answer 1

您可以通过仅比较附近的平台来限制比较量。我可能只会检查平台之间的水平距离，如果它比可能的最长跳跃宽，那么不要费心检查这两者之间的链接。但是你可能已经这样做了，因为你检查了跳跃的最大高度。

我瞥了一眼视频，它给了我一个主意。而不是在所有平台上查找哪些跳转是不可能的，如果你做了相反的事情呢？尝试在所有平台上放置AI角色，并查看他们可以访问的其他平台。如果你的敌人无法在半空中改变方向，那肯定会更容易实现。哦，头脑风暴是找到一些东西的关键。

Answer 2

你可以试试几个想法：

1. 通过使用空间数据结构（如四叉树）限制需要进行的比较。这将允许您严格限制您甚至尝试检查的平台数量。这与您目前正在进行的操作大致相同，但更为通用。
2. 尝试提前预先计算一些跳跃轨迹。这不会捕获您拥有的所有用例 - 因为您允许完全水平控制 - 但可能允许您更快地捕获一些常见情况
3. 考虑某种可步行网格而不是链路生成方案。修改几何体时，计算水平的哪些部分是可步行的，哪些不是，具有一定的分辨率（类似于代理的尺寸可能是一个很好的起点）。您也可以使用高度过滤它们，这样，高于跳跃高度的网格图块，以及不能从较高位置掉落到它们上的网格图块，都标记为不可移动。然后，当你计算你的寻路时，作为寻路步骤的一部分你可以计算你何时开始跳跃，如果路径实际上是可执行的（'开始跳跃，我可以垂直移动不超过5个瓦片，并且在峰值之后）跳跃，我总是以一定的速度垂直坠落）。