我正在使用 A-star 算法，其中有一个 2D 网格和一些障碍物。现在，我只有垂直和水平障碍物，但它们可能会密集变化。
现在，A-star 工作得很好（即在大多数情况下找到最短路径），但如果我尝试从左上角到达右下角，那么有时我会看到路径不是最短的，即有一些路径笨拙。
该路径似乎偏离了最短的路径。
现在这是我正在用我的算法做的事情。我从源开始，向外移动，同时计算邻居的值，对于距源的距离+距目的地的距离，我不断选择最小的单元格，并不断重复，直到我遇到的单元格是目的地，此时我停下来。
我的问题是，为什么A-star不能保证给我最短路径。或者是吗？我做错了什么？
A-star 保证根据您的度量函数（不一定是“鸟儿飞翔”）提供最短路径，前提是您的启发式是“可接受的”，这意味着它永远不会高估剩余距离。
检查此链接：http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
为了帮助确定您的实施错误，我们需要有关您的指标和启发式的详细信息。
更新：
OP 的度量函数对于正交移动为 10，对于对角移动为 14。
OP的启发式仅考虑正交移动，因此是“不可接受的”；它通过忽略更便宜的对角线移动来高估。
过于保守的启发式方法的唯一成本是在找到最小路径之前访问额外的节点；过于激进的启发式方法的成本是可能返回的非最佳路径。 OP 应使用启发式：
7 * (deltaX + deltaY)
这稍微低估了直接对角路径的可能性，因此也应该是高性能的。
更新＃2：
为了真正发挥性能，这接近最佳状态，同时仍然非常快：
7 * 最小值(deltaX,deltaY) + 10 * ( 最大值(deltaX,deltaY) - 分钟（deltaX，deltaY））
更新＃3：
上面的7源自14/2，其中14是度量中的对角线成本。
只有你的启发式改变；该指标是“业务规则”并驱动其他所有规则。如果您对 A-star 六角形网格感兴趣，请查看我的项目：http://hexgridutilities.codeplex.com/
更新#4（关于性能）：
我对 A-star 的印象是它在 O(N^2) 性能区域和几乎 O(N) 性能区域之间徘徊。但这非常依赖于网格或图表、障碍物的放置以及起点和终点，因此很难一概而论。对于已知特定形状或风格的网格和图表，有多种更有效的算法，但它们通常也变得更复杂； 坦斯塔夫.
我确信你做错了什么（也许是一些实现缺陷，你的 A* 想法听起来是正确的）。 A* 保证给出最短路径，可以用数学证明。
查看此wiki页面将为您提供解决问题的所有信息。
不
A* 是最快的寻路算法之一，但它不一定给出最短路径。如果您正在寻找随时间推移的正确性，那么最好使用 dijkstra 算法。