我需要在 8 个连接的网格（上/下左/右和对角线）中找到从 A 到 B 的路径。问题是，这个网格大部分 (25-60%) 是空的，但是可能必须通过某些具有高权重值的点（〜空瓷砖重量的 20 倍）。我已经用 RSR 和 JPS 研究过 A* 之类的东西，但这些似乎只适用于未加权的网格。现在我已经推出了一个 A* 实现，但它比我想要的要慢。我什至不需要一个完全最优的算法，只需要一个接近的算法。
问问题
606 次
2 回答
1
JPS was formulated and analyzed for uniform grids with obstacles. I think that if you treat any "unusual" tiles as you would treat obstacles, JPS will work (i.e. will let you go fast through uniform regions). JPS' author even speculated as much in the comments to his JPS blog post (and it seems fairly obvious):
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
However you seem to imply that your grid is not just non-uniform, but also has bonus tiles in addition to penalty tiles. You will need to deal with those as well (e.g. bias all grid weights up to avoid negative weights).
于 2013-01-13T10:29:52.110 回答
0
如果速度是一个问题，请考虑使用图形硬件（例如 CUDA 或 OpenCL）。 本文讨论了 3d 网格上的“brushfire”算法，用于为 2d 机器人找到具有旋转的路径。尽管您是二维的，但它几乎与您的问题完全相同。
于 2013-01-13T21:55:19.190 回答