tcl - 如何使用 struct::graph(::op) 找到两个节点之间的最短路径？

Question

我有一个带有障碍物的网格，需要在两个节点之间找到最有吸引力的多边形。该操作很可能是一个瓶颈，所以我希望尽早打包一个性能合理的实现，并且仍然有一个可移植的解决方案（即，还没有 C）。我很想在游戏后期做一个 OpenCL 解决方案，但必须先到达那里。

我已经使用struct::graph了许多问题，并认为我可以再使用一次。阅读有关图形和操作的文档，似乎问题已经解决，但它使我无法实际使用 API。

问题是通过设计简化的。有一个有限的矩形网格（顶部 30x30），其中每个单元格都是图中的一个节点。只要沿途没有障碍物（通常是已经存在的多边形的末端），每个节点都与网格中的其他节点具有轴对齐的边缘。较长边的边成本较低，使得许多转弯（楼梯）对路径查找算法的吸引力降低。（还有其他影响边缘成本的启发式方法。）

假设我已经填写struct::graph了上面的内容，我如何找到从节点 A 到任何一组节点 B的最短路径（如果连接到超图则很多）？

---

到目前为止的进展：许多操作 API 似乎返回到图中所有节点的最短路径，这不是我想要的，尽管我可以使用它直到找到更好的方法。假设我可以在 cmd 中修改图形，walk我可以进行一些更简单的即时修剪，但文档并未表明这是一种可能性。

如果事实证明 struct::graph 本质上（太）慢，我很乐意将其修补成形状。只需要知道我将首先使用什么...

标签： tclpath-finding