C# 中的 A* 算法实现
4.84/5 (71投票s)
2006年8月24日
16分钟阅读
312330
14408
优化的 A* 算法实现加上前端。
引言
不久前，我需要做一个项目来确定矩阵中的最短路径。我心想，“路径查找再好不过了。”关于路径查找，有大量的链接和解释，但我没有找到一个用 C# 编写且能满足我需求的版本。因此，我决定实现 C# 的 A* 算法。这段代码对我来说非常有用，我相信它对许多其他人也会有用。我不会过多解释算法的实现，因为只要在 Google 上输入“pathfinding algorithm A*”就能找到大量文档，其中你可以找到所有细节。
关于应用程序
A* 是一个通用算法，没有完美的参数可以设置。算法有很多可以设置的地方，因此确定适合你项目的最佳参数的方法是测试不同的组合。另外，通常一个好的 A* 实现不会使用标准的 ArrayList 或 List 来存储开放节点。如果使用标准 List，算法将花费大量时间在该列表中搜索节点。应该使用优先级队列。我从 BenDi 的优先级队列实现中借用了代码。我对其进行了一些小改动，并且还将其实现改为使用泛型而不是 ArrayList，这使其运行更快。该项目有两个主要原因非常有用。
- 我遵循了 A* 的实现，并尝试实现它以获得良好的性能，因此算法本身可以轻松地在任何项目中重用。
- 前端提供了充分的机会来试验许多变量，在那里你可以真正观察和学习它的工作原理，改变启发式函数、公式或选项来分析什么可能是你的项目的最佳设置。
源代码中执行所有工作的调用如下
public List<PathFinderNode> FindPath(Point start, Point end, byte[,] grid);
此方法以起始点、终点和网格作为参数。它将以节点列表（包含坐标）的形式返回路径。我在单独的线程中进行了此调用，这使得在 PathFinder 工作时能够保持应用程序的控制权。
算法设置
速度
这是渲染速度；降低速度可以详细检查算法如何实时打开和关闭节点。
对角线
此复选框会告知算法是否允许将对角线作为有效路径进行处理。如果未选中此复选框，算法将只处理 4 个方向而不是 8 个。
加重对角线
如果选中此复选框，对角线的成本将更高；这将使算法避免使用对角线。
惩罚转向
如果选中此复选框，每次算法改变方向时都会产生一定的成本。最终结果是，如果找到路径，它将相对平滑，没有太多方向变化，看起来更自然。缺点是它将花费更多时间，因为它必须搜索额外的节点。
重新打开已关闭的节点
如果选中此项，算法在成本低于先前值时允许重新打开已关闭的节点。如果允许重新打开节点，它将产生更好、更平滑的路径，但会花费更多时间。
启发式函数
这是一个常数，它会影响从当前位置到目标点的估计距离。启发式函数用于创建到达目标状态需要多长时间的估计。估计越好，找到的路径越短。
公式
这是用于计算启发式函数的方程式。不同的公式会产生不同的结果：有些更快，有些更慢，结果也可能不同。使用的公式很大程度上取决于 A* 算法的用途。
使用平局分割器
有时，当 A* 寻找路径时，它会发现许多成本和目的地相同的可能选择。平局分割器设置告诉算法，当它有多个选择时，它应该继续进行。随着它的进行，变化的成本可以用于第二个公式来确定要遵循的“最佳猜测”。通常，这个公式是当前位置到目标的启发式函数增加，乘以一个常数因子。
Heuristic = Heuristic + Abs(CurrentX * GoalY - GoalX * CurrentY) * 0.001
搜索限制
这是在返回“未找到路径”消息之前要搜索的最大已关闭节点数。这是一个有用的参数，因为有时网格可能太大，我们只在目标靠近当前位置时才需要知道路径。如果该过程不能花费太多时间计算路径，它也很有用。
网格大小
此参数仅影响前端。它可以改变网格大小，减小网格大小有机会创建更大的测试，但渲染会花费更长时间。
快速路径查找器
当未选中时，使用的实现是书中通常出现的算法。当选中时，它将使用我自己的 PathFinder 实现。它需要更多的内存，但速度大约是 300 到 1500 倍，具体取决于地图的复杂性。有关更多详细信息，请参阅下面的 PathFinder 优化部分。
显示进度
这允许实时观察算法的运行情况。如果选中此框，完成时间将是计算时间加上渲染时间。
完成时间
这是算法计算路径所花费的时间。要了解真实值，请取消选中“显示进度”。
路径查找器优化
在实现了原始算法后，我因为解决路径所花费的时间而感到沮丧。特别是对于更大的网格和没有解决方案的路径。基本上，我注意到开放列表和关闭列表正在扼杀算法。第一次优化是将开放列表替换为排序列表，将关闭列表替换为哈希表。这提高了计算时间，但仍然不如我所愿。
大问题是，当网格很大（1000x1000）时，列表中开放和关闭节点的数量非常多。搜索这些列表花费了很长时间，无论我使用什么方法。起初，我想使用类来保存节点信息，但这会导致垃圾回收在节点内存分配和已处置节点的内存释放之间变得疯狂。我没有使用类，而是决定使用结构并在代码中重用它们。我从中获得了一些改进，但仍然无法与 StarCraft 在实时处理八百个单位的水平相提并论。
我目前的应用程序类似于 Visio 应用程序，我需要在对象之间找到一条路径。对象不会移动，所以我不需要超快的算法，但我需要能在不到一秒内响应的东西。我需要找到一种方法以 O(1) 或接近 O(1) 的时间复杂度从开放列表中获取节点。我认为唯一的办法是不使用开放列表。这时我想到了使用计算网格。这个计算网格将存储节点。因此，如果我知道 (X, Y) 位置，我就可以立即以 O(1) 的时间复杂度访问节点。
因此，我可以摆脱关闭列表；我可以直接在计算网格中标记一个已关闭的节点。另外，由于每个节点都有指向父节点的链接，所以我根本不需要关闭列表。但是，我无法摆脱开放列表，因为我仍然需要获取总成本（F）最低的节点，而第二个网格对此没有帮助。这次，我继续使用开放列表（优先级队列），但只是为了推送和获取成本最低的节点。优先级队列在这方面非常出色，根本没有线性访问。
唯一缺点是内存消耗巨大，需要维护第二个网格。这是因为每个单元格都存储一个节点，而每个节点长 32 字节。基本上，对于一个地图（1000x1000），我需要 32MB 的 RAM。因为我现在通过坐标 (X, Y) 访问第二个网格，所以节点中不再需要这些值。这减少了 1,000,000 个节点乘以 8 字节。因此我节省了 8MB 的内存。每个节点都有一个指向父节点的链接，这些是 int（32 位），因为网格永远不会太大。然后我用 ushort（16 位）替换了它们，这让我每个节点节省了 2 字节。这又节省了我 2MB。我还意识到启发式函数（H）是为每个节点即时计算的，并且不再用于算法。因此，我也将其从节点结构中删除了。启发式函数是一个 int（4 字节），所以我又节省了 4MB。我还有至少 13 字节的节点，但由于内存对齐，它们在运行时占用了 16 字节。我必须设置结构以使用每个字节的内存对齐。
[StructLayout(LayoutKind.Sequential, Pack=1)]
最后，我为每个节点得到了 13 字节。因此，在运行示例时，您会看到 FastPathFinder 运行需要额外 13MB 的内存。
- 如果网格是 1024x1024，计算网格将占用 13MB
- 如果网格是 512x512，计算网格将占用 3.2MB
- 如果网格是 256x256，计算网格将占用 832KB
我不得不承认，由于 A* 调试的复杂性，我花了相当多的时间才使其正常工作。不过，当它工作时，我感到很满意。我简直不敢相信，对于简单的网格，我得到了至少 300 倍的速度提升，对于复杂的网格，更是超过 1500 倍的速度提升。尽管如此，我仍然在从优先级队列插入和移除节点，这意味着内存工作和垃圾回收。因此，我想出了一个办法来保持节点在优先级队列中：我没有推送和弹出节点，而是推送和弹出节点在计算网格中的地址。这让我节省了内存并运行得更快。我存储坐标的方式是将 (X, Y) 坐标转换为线性坐标。
Location = Y * grid width + X;
那里出现的问题是我必须在线性坐标和地图坐标之间来回转换。所以我把我的计算网格从一个固定的地图数组
PathFinderNode[,]
改为线性数组
PathFinderNode[]
这使代码清晰得多，因为不再需要在地图和线性坐标之间进行转换。我还对网格的大小进行了限制。这个限制是地图的宽度和高度必须是 2 的幂。这样做可以进行移位和逻辑运算，这比算术运算符快得多。以前是
LinearLocation = LocationY * Width + LocationX;
…
LocationY = LinearLocation / Width;
LocationX = LinearLocation – LocationY;
现在变成了
LinearLocation = (LocationY << Log(Width, 2)) | LocationX;
…
LocationX = LinearLocation & Width;
LocationY = LinearLocation >> Log(Width, 2);
完成所有这些之后，当标准的 PathFinder 算法在 131 秒内解决了地图 HardToGet.astar 的路径，优化的 PathFinder 在 100 毫秒内得到了相同的结果。这是一个 1300 倍的改进。另一个优化是，如果当前的开放节点已经在开放列表中，并且当前节点的总成本低于列表中存储的成本，那么旧节点将被移除或替换。相反，我决定将旧的开放节点留在开放列表中，只添加新的节点。旧节点将具有更高的成本，因此稍后将被处理。但是，当处理时，该节点将已经被关闭，因此将被忽略。这比去开放列表并移除旧开放节点要快得多。
另一个优化源于这样一个事实：在路径查找调用之间，我必须清除计算网格。计算网格存储 PathFinderNode 类型的对象，每个对象都有一个 Status 字段。此字段指示节点是打开、关闭还是都不是。零化网格通常需要大约 30 毫秒（对于 1024x1024 网格），并且必须在路径查找调用之间完成。为了优化它，我没有零化网格，而是更改了节点状态的值。然后，在调用之间，它将状态值增加 2。因此，在第一次路径查找搜索中，我们有
- 1 = 打开
- 2 = 关闭
- X = 未搜索
在第二次路径查找搜索中，我们有
- 3 = 打开
- 4 = 关闭
- X = 未搜索
等等……
这样，在路径查找调用之间，它就不需要清除计算网格。它只需要为打开和关闭的节点使用不同的值；任何其他值意味着未搜索。
在优化之旅中，我基本上消除了几乎所有的内存分配和顺序搜索，转为固定分配和最小搜索。这类似于将机器中的所有移动部件替换为固定部件。尽管如此，仍有更多的优化可以进行，我可能会继续进行这些优化。如果您对优化或可以改进的地方有任何反馈，请随时发表评论，我将尽快回复。
工具栏
工具栏允许我们加载、创建新场景和保存测试场景。它还允许在网格中插入具有不同成本的节点（障碍物）。默认情况下，网格中的所有节点成本都为“1”，但可以更改为其他成本。“X”在工具栏中表示成本“0”，代表不可通行节点。“开始”和“结束”按钮允许我们在运行算法之前在网格中放置开始和结束位置。节点的成本不限于工具栏中定义的成本。鼠标按钮也可以更改节点的当前成本。在移动鼠标并按下
左键按钮 --> 当前节点设置为工具栏中活动成本按钮指定的成本。
右键按钮 --> 当前节点成本通过工具栏中活动成本按钮指定的成本增加。
左右键按钮 --> 当前节点成本通过工具栏中活动按钮指定的成本递减。
前端
当我实现 A* 算法时，我花了很长时间才找到我的实际项目所需的最佳参数。因此，我决定创建一个独立于实际应用程序的前端来帮助我找到这些值。前端唯一的目的是测试和调试，所以前端目前设计不佳。有很多可以改进和提高性能的地方，但本文的目标是学习 A* 算法的实现，而不是 GDI 优化。因此，我没有花太多时间在这上面。
不久前，我看到一个实现 A* 的很棒的应用程序，但我记不起名字了。它是用 Delphi 制作的，但没有源代码。我从那里汲取了主要想法来创建这个前端。我不想制作那个应用程序的克隆；相反，我觉得它看起来非常有趣，并且创建类似的东西会很好。有一个不同的命名空间，其中只包含算法和辅助类，“Algorithms”命名空间。
另外，研究节点的实时渲染不是持久的。基本上，节点直接绘制在窗口的 HDC（设备上下文）上。因此，如果窗口的一部分失效，它将不会再次重绘。如果你将另一个窗口移到前端上，当前路径将消失。这可以通过使用第二个网格并保留每个节点的 [状态](https://codeproject.org.cn/csharp/pathfinding_algorithm_a_star/status.gif) 来解决，但同样，当我制作前端时，它只是为了调试算法并查看设置如何影响路径搜索。
你可能会注意到，将速度设置为最大值（最小值）看起来性能仍然不佳。这不是因为算法；而是因为算法进行了大量的回调（事件）到前端以允许渲染。PathFinder.cs 中的第一行是一个 #define
#define DEBUGON
如果定义了此符号，那么算法将评估是否定义了调试事件。如果定义了，算法将在每一步进行回调（事件）。当应用程序在实际项目中使用时，强烈建议您从 PathFinder.cs 中删除该符号。删除该符号将极大地提高算法的性能。如果未定义该符号，则算法不会进行任何回调，并且在找到路径或未找到路径后将立即返回。
结论
这个应用程序和代码可以帮助从初学者到高级开发者一步一步地探索 A* 算法。欢迎提出任何评论或建议。
历史
- 2007 年 5 月 24 日 - 文章已编辑并发布到 CodeProject.com 主文章库
- 2006 年 9 月 29 日 - 作者首次更新
- 2006 年 8 月 24 日 - 发布原始版本