Fra*_*las 9 algorithm artificial-intelligence pathfinder a-star path-finding
我正在寻找一种寻路算法,用于AI控制2D网格中的实体,需要找到从A到B的路径.它不一定是最短路径,但需要非常快速地计算.网格是静态的(永远不会改变),一些网格单元被障碍物占用.
我目前正在使用A*,但它对我的目的来说太慢了,因为它总是试图计算最快的路径.当路径不存在时会出现主要的性能问题,在这种情况下,A*将尝试探索太多的单元.
如果路径不必是最短路径,我可以使用不同的算法找到比A*更快的路径吗？
谢谢,
鲁米
假设您的网格是静态的并且不会更改.构建网格后,您可以计算一次图形的连接组件.
然后,您可以轻松检查源和目标顶点是否在组件内.如果是,则执行A*,否则执行A*,因为组件之间不存在路径.
您可以使用BFS或DFS获取图形的连接组件.