algorithm - 查找路径是一个大部分为空的加权网格

Question

我需要在 8 连接的网格(上/下左/右和对角线)中找到从 A 到 B 的路径。问题是，这个网格大部分 (25-60%) 是空的，但是有一些具有高权重值(~20 倍空方 block 重量)的点可能必须通过。我已经看过像 A* 和 RSR 和 JPS 这样的东西，但那些似乎只适用于未加权的网格。现在我推出了一个 A* 实现，但它比我想要的要慢。我什至不需要完全最优的算法，只需要接近的算法。

Answer 1

JPS对具有障碍物的均匀网格进行了制定和分析。我认为，如果您像对待障碍物一样对待任何“不寻常”的瓷砖，JPS 就会起作用(即会让您快速穿过统一区域)。 JPS 的作者甚至在对他的 JPS blog post 的评论中推测了很多。 (而且看起来相当明显):

simply treat any neighbour which is of a different terrain type to the current node, as forced. This will allow you to quickly search across a uniform-cost region, stop to expand a node when crossing into a different region, and continue jumping on the other side

然而，您似乎暗示您的网格不仅不均匀，而且除了惩罚牌之外还有奖励牌。您还需要处理这些问题(例如，将所有网格权重偏置以避免负权重)。