我需要在8个连接的网格中找到从A到B的路径（上/下左/右和对角线） . 问题是，这个网格是空的（25-60％）是空的，但是某些地点的加权值很高（约为空瓦重量的20倍）可能需要通过 . 我已经用RSR和JPS查看了A *之类的东西，但这些似乎只适用于未加权的网格 . 现在我已经推出了A *实现，但它比我想要的慢 . 我甚至不需要一个完全优化的算法，只需要接近的东西 .
JPS制定并分析了带有障碍物的均匀网格 . 我认为，如果你对待任何"unusual"瓷砖就像对待障碍物一样，JPS会起作用（即让你快速穿过均匀的区域） . JPS的作者甚至在他的评论中推测了他的JPS blog post（看起来相当明显）：
简单地将任何与当前节点不同的地形类型的邻居视为强制 . 这将允许您快速搜索统一成本区域，停止在跨越到不同区域时扩展节点，并继续在另一侧跳跃
但是你似乎暗示你的网格不仅仅是不均匀的，而且除了惩罚牌之外还有额外的牌 . 您还需要处理这些问题（例如，将所有网格权重偏向上以避免负权重） .
如果需要考虑速度，请考虑使用图形硬件（例如CUDA或OpenCL） . This paper讨论了3d网格上的"brushfire"算法，以找到具有旋转的2d机器人的路径 . 它在2d重新开始 .
2 回答
JPS制定并分析了带有障碍物的均匀网格 . 我认为，如果你对待任何"unusual"瓷砖就像对待障碍物一样，JPS会起作用（即让你快速穿过均匀的区域） . JPS的作者甚至在他的评论中推测了他的JPS blog post（看起来相当明显）：
但是你似乎暗示你的网格不仅仅是不均匀的，而且除了惩罚牌之外还有额外的牌 . 您还需要处理这些问题（例如，将所有网格权重偏向上以避免负权重） .
如果需要考虑速度，请考虑使用图形硬件（例如CUDA或OpenCL） . This paper讨论了3d网格上的"brushfire"算法，以找到具有旋转的2d机器人的路径 . 它在2d重新开始 .