AI：最快的算法发现，如果路径存在？ [英] AI: Fastest algorithm to find if path exists?

问题描述

我要寻找一个寻路算法用于一个AI控制，需要寻找从一个路径B.二维网格的实体它不一定是最短的路径，但它需要计算速度非常快。网格是静态的（不会改变）和一些网格单元被障碍物占据。

I am looking for a pathfinding algorithm to use for an AI controlling an entity in a 2D grid that needs to find a path from A to B. It does not have to be the shortest path but it needs to be calculated very fast. The grid is static (never changes) and some grid cells are occupied by obstacles.

我目前使用的是一个*，但它是我的目的，速度太慢，因为它总是试图计算出最快路径。当路径不存在，在这种情况下的A *将尝试探索过多的细胞发生的主要性能问题。

I'm currently using A* but it is too slow for my purposes because it always tries to calculate the fastest path. The main performance problem occurs when the path does not exist, in which case A* will try to explore too many cells.

是否有不同的算法，我可以使用，可以找到一条比A *更快，如果路径并不一定是最短路径？

Is there a different algorithm I could use that could find a path faster than A* if the path doesn't have to be the shortest path?

谢谢

管腔

推荐答案

假设你的网格是静态的，不会改变。建立电网后，一旦你可以计算出你图的连接部分。

Assuming your grid is static and doesn't change. You can calculate the connected components of your graph once after building the grid.

然后就可以轻松地检查源和目标顶点是在一个组件或没有。如果是，则执行A *，如果不是的话就不要，因为不能在部件之间的通路。

Then you can easily check if source and target vertex are within a component or not. If yes, then execute A*, if not then don't as there can't be a path between the components.

您可以使用BFS或DFS图的连接组件。

You can get the connected components of a graph using BFS or DFS.

这篇关于AI：最快的算法发现，如果路径存在？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！