所以,我有一个简单的寻路算法,它预先计算到几个目标端点的最短路径,每个目标端点都有不同的权重。这在某种程度上等同于在一个端点和每个端点之间有一个节点,尽管那里的边具有不同的权重。它使用的算法是一种简单的传播算法,在 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 的曼哈顿距离为 5 的数组元素,并维护源信息。这基本上意味着将算法重新应用于选定区域但是我可以做得更好吗?