寻找两个对象之间最短路径的算法

Question

我有一个平面图，上面有很多代表展位的 d3.js 多边形对象。我想知道在两个不与其他对象重叠的对象之间找到路径的最佳方法是什么。这里的用例是我们有摊位，想向用户展示如何步行才能最有效地从 a 点到达 b 点。我们可以假设路径必须只包含 90 或 45 度转弯。

我们试过使用 Dijkstra，但它的规模似乎离我们远了。

我们系统的示例快照:

我们的限制是这需要在浏览器中运行。如果它与 d3.js 配合良好，那就太好了。

Answer 1

由于布局是一个矩阵(或嵌套矩阵)，这不是 Dijkstra 问题，它比那更简单。该问题的技术名称是“曼哈顿路由”。我不会给出代码算法，而是在下图中向您展示最佳路线(蓝线)的示例。从这里应该很明显算法是什么: 请注意，这里有一个细微的差别，那就是你总是希望最大限度地增加慢跑的次数，因为即使整体形状是一个矩阵，在每个角落，人实际上都会沿对角线行走(想象一个人沿对角线穿过四路交叉口)。因此，简单地向北然后向西是错误的，因为您只能拐弯一个角，但在显示的路线上您可以拐弯 5 个弯角。