javascript - 寻路：如何为寻路算法创建路径数据？

Question

我意识到这与编程问题并不严格相关，但由于 SO 是编程相关问题的最佳资源，我决定尝试一下。:)

我有一个项目，我需要在建筑物内使用 javascript 进行 3D 寻路。Dijkstra 算法可能是最好的情况，因为它可以很好地处理不规则形状。

然而，问题是这样的：Dijkstra 需要节点结构才能工作。但是如何创建这些数据？显然需要从基础数据进行某种转换，但是如何创建基础数据呢？浏览蓝图，为每个可能的路径节点获取 x 和 y 值，手动计算距离似乎有点过分......而且容易脏话......

我什至在考虑为此使用 Google Scetchup。为每个可能的路径画线，但问题是从中获取路径数据。：/

我不能成为第一个遇到这个问题的人......有什么想法吗？有没有现成的工具来创建路径数据？

Answer 1

找不到任何现成的工具，所以我最终在 Google SketchUp 中将路径数据创建为线条，将它们导出 Collada 文件并为 Collada XML 数据编写我自己的转换器。

Answer 2

这一切都可以在代码中通过构建 3d 网格并移除与 3d 对象相交的立方体来完成。

然后，我将分层多个 3d 网格（每次大小加倍），以提供更一般的可达性概念（由较小的网格构成），然后凭借寻路算法，您将始终从 AB 中自动找到最有效的路径使用最大的单元格引导路径（因此计算步骤最少）。注意：使较大的 3d 网格具有稍低的权重，以便其路径受到青睐。

这可以用于许多应用程序。例如，如果您只能在地面上行走，则只需在无法到达的区域移除块。