所以，我有一个简单的寻路算法，可以预先计算到几个目标 endpoints 的最短路径，每个目标 endpoints 的权重不同 . 这有点等同于一个 endpoints 在其与每个 endpoints 之间具有节点，尽管其边缘具有不同的权重 . 它使用的算法是一个简单的扩展算法，在1d中看这个（|表示墙， - 表示空间）：
-
5 - - - 3 | - - - 2 - - - - 2 -
5 4 - - 3 | - - - 2 - - - - 2 : Handled distance 5 nodes -
5 4 3 - 3 | - - - 2 - - - - 2 : Handled distance 4 nodes -
5 4 3 2 3 | - - - 2 - - - - 2 : Handled distance 3 nodes -
5 4 3 2 3 | - - 1 2 1 - - 1 2 : Handled distance 2 nodes -
Done. Any remaining rooms are unreachable.
所以，让我们假设我有一个像这样的预先计算的寻路解决方案，其中只有5是目标：
- - - - | 5 4 3 2 1 -
如果我把墙改成房间 . 重新计算很简单 . 只需重新处理所有距离节点（但忽略已存在的节点） . 但是，如果4成为墙，我无法找到一种有效的方法来处理该怎么做 . 显然结果如下：
- - - - | 5 | - - - -
但是，在二维解决方案中，我不确定如何有效地处理4.很容易存储4依赖于5因此需要重新计算，但我如何安全地确定其新的依赖关系和值？我宁愿避免重新计算整个数组 .
一个优于零的解决方案（大致）仅重新计算曼哈顿距离为5的阵列元素，并维护源信息 . 这基本上意味着将算法重新应用到选定区域但是我可以做得更好吗？
1 回答
嗯 . 我提出的一个解决方案是：保留每个节点可以最快到达的节点列表 . 如果节点成为墙，请检查可从哪个节点访问，并获取相应的列表 . 然后使用标准算法重新检查所有这些节点 . 到达新距离较小的节点时，请将其标记为需要重新测试 .
获取未标记的标记节点的所有邻居，并在其上重新应用算法，忽略此技术命中的任何标记节点 . 如果重新应用的算法增加了标记节点的值，请使用新值 .