问题标签 [a-star]

根据我对 A* 启发式和 Bresenham 算法如何工作的了解，这可能是不可能的，因为只有当前状态和目标状态被传递给启发式函数。但也许有人对这个问题有一个聪明的解决方案。

我正在使用 A* 来规划网格上的路径，并且我想要一个启发式方法，当当前状态和目标之间或下一次绕过障碍物之间有空闲空间时，它会导致最佳路径遵循 Bresenham 的线。

这里有一些图片来说明这个问题。

曼哈顿距离：

如果世界上的运动就像一个网格上的跳棋，这将是非常好的，但我最终会将 A* 路径转换为连续平面上的运动，所以这确实很好用。

欧几里得距离：

更好，但仍然不完美。注意最后的直线。对角线可以很容易地保持对角线，这就是我想要的。

我想要的是：

布雷森汉姆线被绘制到下一个转弯或目标。

我在这里找到了一个很好的资源，http ://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html，它触及了我正在寻找的东西，但似乎只适用于从开始到目标绘制 Bresenham 线。我想要的是布雷森汉姆线也被吸引到下一个绕过障碍物的转弯处。

有什么想法可以解决这个问题吗？

为了更好地理解 C 并尝试提高我为 iOS 构建的应用程序的性能，我决定在 C 中实现路径查找。

代码可在此处获得

在代码中，我创建并使用了以下结构：

• 节点：这是图的一个顶点，它有坐标和一些与 A* 相关的其他数据
• NodeGraph：节点的集合
• NodeHeap：用于打开列表（优先队列）的堆

NodeGraph 负责管理节点内存；需要访问该节点的所有其他内容都使用指向 NodeGraph 中特定节点的指针。例如，NodeHeap 只是 Node 指针的集合，例如：

在游戏中，我打算对多个路径查找调用使用相同的图形结构。据我了解，重用相同结构而不是释放它并为新结构分配内存会带来一些性能提升。

这是我应该在 C 中做这样的事情的方式吗？是否有任何我没有利用的 C 构造，或者我完全缺少的其他任何东西？

我正在重新制作一个旧的魔兽争霸 3 自定义游戏，我曾经在 iPhone 上玩过该游戏。基本上，您有一定的时间从一定数量的块中构建迷宫，并且爬行者运行迷宫所需的时间越长，您获得的积分就越多。

我正在使用 cocos2d 进行这一切，现在我正在使用 a* 寻路算法。我正在使用Justin Heyes-Jones 的实现并正在处理节点类。

但是，有几件事让我感到困惑。该类如下所示：

我只是不确定 GetCost 是什么意思。在这个示例迷宫中，X 是墙壁，_ 是可步行区域，从 (3, 1) 到 (3, 2) 的成本是否为 0？那么从 (3, 1) 到 (4, 1) 的成本是多少，因为这是不可能的？

然后我想我可以通过使用距离公式来实现 GoalDistanceEstimate，对吗？

我想对以下 A* 搜索示例进行澄清：

用红色椭圆突出显示的部分是我不明白的区域；似乎{S,B} f=2+6=8已从Expand S（以上）中获取/移动/复制并用于Expand A. 似乎也{S,A,X} f=(1+4)+5=10已从Expand A.Expand B

有人可以解释为什么会这样吗？我能够很好地阅读图表并且在解释它时没有任何问题 - 这只是我不知道为什么上述路径/路线在其他地方重复的事实。

谢谢你。

对于学校的作业，我必须为 Rush Hour 游戏做一个求解器。如果你不熟悉 Rush Hour。请查看此链接：http ://www.puzzles.com/products/rushhour.htm

对于这个求解器，我必须使用 A* 搜索算法，我在网上看了一点，我想我很理解算法是如何工作的。只是我真的不知道如何在求解器中实现它。 . 也不应该如何为汽车建立电网.. 有人可以给我一些提示/帮助吗？不是一个完整的解决方案..

Hey, I'm AI Student and gonna try my homework that is implementation of A* algorithm in order to traversal a graph. i use c++ codes and what i made for now is below code which is only a Graph class + insertedge and vertices functions. but now i'm confused of how to define cost function (f= h(n) + g(n)) ...

also any code refrence or explain of how A* works for graphs would help me . what i found in google was about pathfinding via a* and it has nothing with traversal graph.

首先，对于那些不知道的人 - 随时算法是一种算法，它可以输入它可以运行的时间量，它应该在那个时候给出最好的解决方案。

加权 A* 与 A* 相同，但 f 函数有一个差异：

（其中 g 是到 node 的路径成本，h 是直到达到目标的路径结束的启发式）

我的任何时候算法运行加权 A*，权重从 1 到 0.5，直到达到时间限制。

我的问题是，在大多数情况下，它需要很长时间才能找到解决方案，如果给定 10 秒之类的时间，它通常不会找到解决方案，而其他算法（如任何时间梁）在 0.0001 秒内找到一个解决方案。

有什么想法该怎么做？

遵循使用这个问题作为新问题基础的明显传统，我也有一个问题，我希望尽可能优雅地解决：

我已经实现了一个六边形地图：

（想在这里插入图片..但由于是新的，我不允许...请参阅上面的链接）

但现在我想知道如何（优雅地）为这种类型的地图使用这些类型的坐标实现 A*。我有在典型的平方网格（我认为是笛卡尔网格？）上使用 A* 的经验，我在那里处理它的方式似乎与这个坐标系不兼容。

通常我会生成一个二维字节数组。数组的索引将对应于网格坐标，并且所述索引处的值将给出该节点的“权重”。（0 是不可通行的，较高的数字“权重”比较低的数字更多）。

例子： sbyte[,] pathGrid = new sbyte[5, 5] { {0,0,1,0,0}, {9,5,1,3,0}, {9,5,1,3,0}, {9,5,1,3,0}, {0,0,1,0,0} };

在 0 无法通过的情况下，1 将很容易遍历，并且更大的数字将“花费”更多遍历。（对不起格式化..我是一个堆栈溢出newb：P）这个数组将根据我的地图的组成生成，然后输入我的寻路算法，该算法又会吐出一个节点列表（路径）如果没有找到路径，则返回 null。

然而，使用这种类型的网格，这是不可能的（至少乍一看），因为负坐标（显然在数组中不起作用）以及网格不遵循与 ' 相同的规则这一事实典型的'网格。

我认为有一些方法可以使用我的 A* 方法来解决这个问题，但它们都相当草率（转换网格坐标和使用空节点），我想知道是否有人想到了一种优雅地做到这一点的方法。

感谢您在任何情况下阅读:)（顺便说一句，我在 C#/.net 中这样做是为了它的价值）

我很难让 H 和 G 正常工作。发生的事情是，当我运行程序时，它有时会找到最佳路径，有时会避开到达该位置的路。

以下是正在发生的事情的一些屏幕截图：

找路好

错误的路径查找

这是我目前对 F、H 和 G 的设置：

谢谢！

我在维基百科的文章中实现了这个伪的 A* 搜索算法：

我被困在要求我检索 openSet 中具有最低 f 值的节点的行上。openSet 什么时候被填满？什么？它应该在第一次运行时开始吗？

我也不明白重建路径伪：

应该如何实现伪指令？