关于a*算法的疑问

显示全部楼层 · 2021-1-27 05:07:22

最近通过这篇博文：https://www.cnblogs.com/0zcl/p/6242790.html学习了a*算法。
如果以博文中的猫打比方，若项目中只有一只猫，那还好说，当这只猫走到每一个单元格的时候，该单元格都只有一个f值、一个g值和一个h值。
问题来了，如果有多只猫呢，若你需要为多只猫同时来规划路径呢，那一个单元格可能需要有多个f\g\h值，这样不就乱套了么？
一开始我想到一个比较笨的办法，在python中可以使用deepcopy，为每一只猫都copy一份单独的地图（及其单元格），这样每份地图的单元格都有自己单独的f\g\h值，但是如果地图很大，那python的deepcopy会占用太长时间。这该如何处理呢？请教一下有没有更好的解决办法？
分 -->

千问 · 2021-1-27 05:07:22

在A*算法中，每个单位是需要独立的G值的，这个你必须为每个单位单独存放一个。但是估值H通常是一个估值函数来产生，也就是一个以当前位置和目标位置为输入参数的函数，这个不需要存放，是即时算出来的，所以并不需要为每个单位单独拷贝一份地图信息。
然而实际当中，估值函数太简单则效果不好，太复杂则运算太大，地图越大，这种矛盾越突出。
所以实际上游戏其实都会在地图中预置若干关键路径点信息，保存这些关键路径点相互之间的最短路径距离信息，这样在寻路时，只需要搜索起点和终点相对于其最近的关键点的最短路径就可以了，计算量大大降低，而只需要付出很少的信息存放代价。

千问 · 2021-1-27 05:07:22

引用1楼whycadi的回复:在A*算法中，每个单位是需要独立的G值的，这个你必须为每个单位单独存放一个。但是估值H通常是一个估值函数来产生，也就是一个以当前位置和目标位置为输入参数的函数，这个不需要存放，是即时算出来的，所以并不需要为每个单位单独拷贝一份地图信息。
然而实际当中，估值函数太简单则效果不好，太复杂则运算太大，地图越大，这种矛盾越突出。
所以实际上游戏其实都会在地图中预置若干关键路径点信息，保存这些关键路径点相互之间的最短路径距离信息，这样在寻路时，只需要搜索起点和终点相对于其最近的关键点的最短路径就可以了，计算量大大降低，而只需要付出很少的信息存放代价。
谢谢回复，请问有没有更详细的说明，或者你之前有没有写过更详细的博客之类的？

千问 · 2021-1-27 05:07:22

我没有写过这方面的程序和博客，而且也是很多年前想解决一些相似的问题的时候看过一些相关的算法。
不过这个算法其实就是一个带启发的搜索算法，没什么难理解的地方。你可以先实现一个单单位的程序，写完调通了，你自然就有感觉了。