对于经典的水壶搜索问题，即使是三个以上的水壶，A*搜索算法可以使用哪些可接受的函数？

编辑：

我知道http://www.dave-reed.com/csc550.S02/HW/HW4.html，但该功能显然不一致。

我想问一下是否有任何方法可以生成从节点 A 到节点 B 的最短路径，而无需在 QuickGraph 中使用 A-star 生成到所有其他节点的最短路径（当节点 B 在检查集中时停止）。

我想将 QuickGraph 插入游戏中，因此从环境施加的时间限制来看，不允许生成所有路径。

欢迎任何其他在 C# 中解决我的问题的建议

在此先感谢， Xtapodi

或类似语言的版本。一种适用于所有类型的地图，而不仅仅是 2d。

这是我的节点网格：

我正在使用 A* 寻路算法在其上移动一个对象。它通常可以正常工作，但有时会出现错误：

• 从 3 移动到 1 时，它正确地通过 2。但是，当从 1 移动到 3 时，它通过 4。
• 在 3 和 5 之间移动时，它会在任一方向上通过 4，而不是通过 6 的较短路径

有什么问题？这是我的代码（AS3）：

NodeGridNode::distanceTo()

我正在与一个机器人进行一个项目，该机器人必须找到通往物体的路，并在前往它必须拾取的物体时避开一些障碍物。

问题在于机器人和机器人需要拾取的物体在探路者中都是一个像素宽。实际上，它们要大得多。通常 A* 探路者选择将路线放置在障碍物的边缘，有时会使其与障碍物发生碰撞，我们不希望这样做。

我尝试在障碍物上添加更多不可步行的场地，但效果并不总是很好。它仍然与障碍物发生碰撞，还增加了太多不允许它行走的点，导致它没有可以运行的路径。

你对如何解决这个问题有什么建议吗？

编辑：

所以我按照贾斯汀 L 的建议做了，在障碍物周围增加了很多成本，导致以下结果： 没有路径的网格 http://sogaard.us/uploades/1_grid_no_path.png

在这里你可以看到障碍物周围的成本，最初中间的两个障碍物应该看起来就像角落里的那些，但是在运行我们的探路者之后，成本似乎被覆盖了：

带有路径的网格 http://sogaard.us/uploades/1_map_grid.png

图片显示图片上的东西 http://sogaard.us/uploades/2_complete_map.png

上图显示了图片上发现的东西。

找到的路径 http://sogaard.us/uploades/3_path.png

这是我们之前遇到的问题也是遇到障碍的路径。

之前的网格与 http://sogaard.us/uploades/4_mg_path.png 上的路径

还有一张带有路径的成本图的图片。

所以我觉得奇怪的是为什么 A* 探路者会压倒这些非常高的现场成本。

是否会在使用当前字段评估打开列表中的节点以查看当前字段路径是否比打开列表中的路径短时？

这是我用于探路者的代码：

Pathfinder.cs： http: //pastebin.org/343774

Field.cs 和 Grid.cs：http ://pastebin.org/343775

I have the ability to calculate the best route between a start and end point using A*. Right now, I am including waypoints between my start and end points by applying A* to the pairs in all permutations of my points.

Example:

I want to get from point 1 to point 4. Additionally, I want to pass through points 2 and 3.

I calculate the permutations of (1, 2, 3, 4):

Then, for each permutation, I calculate the A* route from the first to the second, then append it to the route from the second to the third, then the third to the fourth.

When I have this calculated for each permutation, I sort the routes by distance and return the shortest.

Obviously, this works but involves a lot of calculation and totally collapses when I have 6 waypoints (permutations of 8 items is 40320 :-))

Is there a better way to do this?

假设我有这个 2D Array map

我有 HashSet 充满了定义被阻止的瓷砖的整数。什么是一种好方法，以便当我从我的玩家站立的位置单击地图的一部分时进行良好的寻路？A*（使用节点/等）？你有什么建议？

谢谢。

首先，这是吃豆人的人工智能，而不是幽灵。

我正在编写一个围绕你的图标播放 PacMan 的 Android 动态壁纸。虽然它通过屏幕触摸支持用户建议，但大部分游戏将由 AI 玩。我已经完成了 99% 的游戏编程，但 PacMan 本人的 AI 仍然非常薄弱。我正在寻求帮助来开发一个好的人工智能来确定 PacMan 的下一个旅行方向。

我最初的计划是这样的：

1. 用零值初始化每个方向的分数计数器。
2. 从当前位置开始，使用 BFS 通过将四个可能的初始方向添加到队列中向外遍历。

3. 从队列中弹出一个元素，确保它还没有被“看到”，确保它是一个有效的棋盘位置，并在相应的初始方向上添加一个基于当前单元格的值：

   1. 有一个点：加10
   2. 拥有力量：加50
   3. 有果实：加果实值（因等级而异）
   4. 有一个幽灵向吃豆人移动：减去 200
   5. 有鬼离开吃豆人：什么都不做
   6. 有鬼垂直行进：减去 50
   7. 将单元格的值乘以基于到单元格的步数的百分比，从初始方向开始的步数越多，单元格的值越接近零。

   并将当前单元格中的三个可能方向排入队列。

4. 一旦队列为空，为四个可能的初始方向中的每一个找到最高分数并选择它。

这在纸上听起来不错，但 PacMan 周围的幽灵非常迅速，他在相同的两三个牢房中来回抽搐，直到一个到达他身边。调整幽灵存在的值也无济于事。我最近的点BFS至少可以在游戏结束前达到2级或3级。

我正在寻找用于开发适当 AI 的代码、想法和/或资源链接——最好是前两者。我想在这个周末的某个时候在市场上发布这个，所以我有点着急。任何帮助是极大的赞赏。

仅供参考，这是在GameDev.StackExchange上手动交叉发布的

我正在尝试为 iPhone 创建一个 Pacman AI，而不是 Ghost AI，而是 Pacman 本人。我正在使用 A* 进行寻路，并且我有一个非常简单的应用程序正在运行，它计算游戏板上 2 个瓷砖之间的最短路径，避开墙壁。

所以运行 1 个函数来计算 2 个点之间的路径很容易。一旦函数到达goalNode，我可以通过每个tile 'parentNode' 属性向后遍历路径并创建所需的动画。但在实际游戏中，状态是不断变化的，因此路径和动画也必须如此。我是游戏编程的新手，所以我不确定实现这一点的最佳方法。

我应该创建一个在后台运行的 NSOperation 并在给定当前游戏状态的情况下不断计算goalNode 和最佳路径吗？该线程还必须在某些时候通知主线程并为其提供信息。问题是什么？

我应该在什么时候通知主线程？

我应该用什么数据通知主线程？

......或者我在一起了吗？

非常感谢任何指导。

我已经实现了一个A* 搜索算法来查找两个状态之间的最短路径。算法使用哈希映射来存储访问状态的最佳已知距离。以及一个用于存储重建最短路径所需的子父关系的哈希图。

这是代码。该算法的实现是通用的（状态只需要是“可散列的”和“可比较的”），但在这种特殊情况下，状态是整数对（向量），[x y]它们代表给定高度图中的一个单元格（跳转到相邻单元格的成本取决于关于高度的差异）。

问题是是否可以提高性能以及如何提高性能？也许通过使用 1.2 或未来版本的某些功能，通过更改算法实现的逻辑（例如使用不同的方式存储路径）或在这种特殊情况下更改状态表示？

此地图的Java 实现会立即运行，而 Clojure 实现大约需要 40 秒。当然，这有一些自然而明显的原因：动态类型、持久数据结构、对原始类型进行不必要的（取消）装箱......

使用瞬变并没有太大的区别。