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

问题在于机器人和机器人需要拾取的物体在探路者中都是一个像素宽。实际上，它们要大得多。通常 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

当您关心所需的时间而不是路径的长度时，什么是好的路径查找算法。

如果您根本不关心路径而只想检查可达性，是否还有更快的算法。

（对于这类东西来说，洪水填充是一个很好的算法吗？）

我正在尝试实现 Pacman。它工作得很好，但到目前为止，幽灵没有使用任何寻路，而是随机决定每个路径交叉点要走哪条路径。所以你可以想象吃豆人赢得比赛并不难；）

所以我在 Pacman 中阅读了一些关于寻路算法的信息，在这里我找到了一个非常好的答案：Pathfinding Algorithm For Pacman

答案参考http://home.comcast.net/~jpittman2/pacman/pacmandossier.html#Chapter%204

这一切都很好，但是在我的 Pacman 实现中，有两个 Pacman 由两个不同的玩家玩。所以我想知道如何调整寻路算法，让鬼魂不总是追逐一个玩家。

关于如何修改算法以使幽灵对双方玩家或多或少平等公平的任何想法？

我遇到了探路者的问题（这是我的第一个，所以这是意料之中的）：它并不总是采用最短的方式。例如，如果我想向下走一格，路径将是：向左一格，向下一格，向右一格。

SquareListener 是一个简单的 MouseListener，它打印正方形的位置和路径。Map.x、Map.y 是地图大小。以起点调用getSquares2，绘制每6步远的方格，将每一个值为“11”的情况视为障碍物。

你能帮我找出我做错了什么吗？

这是结果的截图： http://img808.imageshack.us/img808/96/screen.gif 红色方块是可能的目标。只有当玩家点击一个方格时才会定义真正的方格（MouseListener 是 SquareListener，它应该知道要走的路径）。房屋是价值为“11”的箱子，即障碍物。

我在 Pacman 中找到了很多关于鬼魂 AI 的参考资料，但没有一个提到在 Pacman 吃掉一个鬼魂后，眼睛是如何回到中央鬼洞的。

在我的实现中，我实现了一个简单但糟糕的解决方案。我只是在每个角落硬编码应该采取哪个方向。

有没有更好/或最好的解决方案？也许是一个通用的，适用于不同的关卡设计？

假设我有这个 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上手动交叉发布的

我在哪里可以找到 C 中的 A* 实现？

我环顾四周，但似乎我的 google-fu 不够强大。我已经开始编写自己的实现，但后来我想起了 Stack Overflow，我想我应该先在这里问一下。编写一个真正的 A* 实现似乎有点复杂- 我很想只为二进制网格编写 Dijkstra 算法的实现，因为这就是我真正需要的，但我觉得我想在我的曲目。

问题

我想写一个简单的1D RTS 游戏，并且有以下寻路问题：一维线很多，到处都是传送器，可以用来在线之间穿行，也可以在当前线内穿行。传送器是在线路之间旅行的唯一途径。什么算法或伪代码可以用来确定线 li1 上的位置 po1 到 li2 上的 po2 之间的最短路径？我们有一组传送器 T（每个都有一个 po 和 li），它们以零成本相互连接。

为什么不是 A* 或 Dijkstra 算法

这是因为我认为这些在 1D 中将是过度杀伤力。

澄清

• 这听起来可能有点二维，但不是因为你只能在一条线上向左或向右移动。
• 前往传送器是有成本的，但从一个传送器传送到另一个是没有成本的。看到这个 ascii 艺术：

在这里，从 start s 到 target x 的最短路径是

• 去正确的传送器
• 向下传送一条线（仅在此图中；实际上飞机是无序的）
• 并直接到达目标（最终成本 = 5）

我有一条由多个点组成的路径 - 即 0,0 0,50 50,50 70,20

如果我只是在屏幕上画这条线，它看起来很刺眼，因为它在每个点的连接处都设置了一个锐角。

因此，我想知道贝塞尔曲线算法/方法会是什么样子，我可以称之为自动将锐角更改为“紧”曲线？

我不希望曲线太大或通常影响主路径的下降，只需软化连接即可。如果您看一下下面的内容，这里是我整理的一个快速示例。左边的线是我现在的线，中间的线是我想要的线。

右边的图像代表我认为我需要算法做的事情。本质上，我在距离连接 10% 的点处为构成连接的每个弧添加了一个附加点，然后我移除连接点并调整手柄，使它们位于点所在的位置（不在图中它们稍微分开，这只是为了让你可以看到）。这是我需要能够做到的。