吃豆人角色 AI 建议最佳下一步方向
首先，这是吃豆人的人工智能，而不是幽灵。
我正在编写一个 Android 动态壁纸，它可以在您的图标周围播放 PacMan。虽然它支持用户通过屏幕触摸提出建议，但游戏的大部分内容将由人工智能来玩。我已经完成了 99% 的游戏编程，但吃豆人本身的 AI 仍然非常弱。我正在寻求帮助来开发一个好的人工智能来确定吃豆人的下一个旅行方向。
我最初的计划是这样的：
- 为每个方向初始化一个分数计数器，其值为零。
- 从当前位置开始，使用 BFS 沿着四个可能的初始方向向外遍历，将它们添加到队列中。
从队列中弹出一个元素，确保它尚未被“看到”，确保它是有效的棋盘位置，并将当前单元格的分数添加到相应的初始方向，基于：
- 有一个点：加 10
- 拥有能力：加 50
- 有水果：加上水果价值（因级别而异）
- 有幽灵向 PacMan 移动：减去 200
- 有幽灵离开吃豆人：什么都不做
- 有幽灵垂直移动：减去 50
- 将单元格的值乘以基于到单元格的步数的百分比，距初始方向的步数越多，单元格的值越接近零。
并将当前单元格的三个可能方向排入队列。
- 一旦队列为空，找到四个可能的初始方向中每一个的最高分并选择它。
从纸面上看，这对我来说听起来不错，但幽灵以极快的速度包围了吃豆人，他在同样的两三个牢房中来回抽搐，直到有一个到达他身边。调整鬼影存在的值也没有帮助。我最近的点BFS至少可以在游戏结束前达到2级或3级。
我正在寻找用于开发合适的人工智能的代码、想法和/或资源链接——最好是前两者。我想在本周末的某个时候在市场上发布这个，所以我有点着急。非常感谢任何帮助。
仅供参考，这是在 GameDev 上手动交叉发布的。 StackExchange
Firstly, this is AI for PacMan and not the ghosts.
I am writing an Android live wallpaper which plays PacMan around your icons. While it supports user suggestions via screen touches, the majority of the game will be played by an AI. I am 99% done with all of the programming for the game but the AI for PacMan himself is still extremely weak. I'm looking for help in developing a good AI for determining PacMan's next direction of travel.
My initial plan was this:
- Initialize a score counter for each direction with a value of zero.
- Start at the current position and use a BFS to traverse outward in the four possible initial directions by adding them to the queue.
Pop an element off of the queue, ensure it hasn't been already "seen", ensure it is a valid board position, and add to the corresponding initial directions score a value for the current cell based on:
- Has a dot: plus 10
- Has a power up: plus 50
- Has a fruit: plus fruit value (varies by level)
- Has a ghost travelling toward PacMan: subtract 200
- Has a ghost travelling away from PacMan: do nothing
- Has a ghost travelling perpendicular: subtract 50
- Multiply the cell's value times a pecentage based on the number of steps to the cell, the more steps from the initial direction, the closer the value of the cell gets to zero.
and enqueue the three possible directions from the current cell.
- Once the queue is empty, find the highest score for each of the four possible initial directions and choose that.
It sounded good to me on paper but the ghosts surround PacMan extremely rapidly and he twitches back and forth in the same two or three cells until one reaches him. Adjusting the values for the ghost presence doesn't help either. My nearest dot BFS can at least get to level 2 or 3 before the game ends.
I'm looking for code, thoughts, and/or links to resources for developing a proper AI--preferably the former two. I'd like to release this on the Market sometime this weekend so I'm in a bit of a hurry. Any help is greatly appreciated.
FYI, this was manually cross-posted on GameDev.StackExchange
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
如果吃豆人卡在某个位置并开始来回抽动，则表明在您运行指标后，他可以采取的不同动作具有非常相似的分数。那么鬼魂位置的微小变化就会导致最佳走法来回翻转。您可能需要考虑添加一些滞后来阻止这种情况发生。
设置：选择一个随机移动并记录为 0 分。
对于每一步：
这会导致吃豆人不再在每一步中选择“最佳”动作，但无论如何，贪婪的本地搜索似乎都不是最佳的。这将使吃豆人更加一致并停止抽搐。
If PacMan gets stuck in a position and starts to twitch back and forth then it suggests that the different moves open to him have very similar scores after you run your metric. Then small changes in position by the ghosts will cause the best move to flip back and forth. You might want to consider adding some hysteresis to stop this happening.
Setup: Choose a random move and record it with score 0.
For each step:
This has the effect that PacMan will no longer pick the "best" move on each step, but it doesn't seem like a greedy local search would be optimal anyway. It will make PacMan more consistent and stop the twitches.
有办法将 PacMan 更改为“路径跟踪”模式。该计划是您检测某些情况，计算吃豆人要遵循的预先绘制的路径，然后计算出该路径的早期退出条件。您可以在多种情况下使用它。
当吃豆人在一定距离内被四个方向中的三个方向的幽灵包围时，创建一条出口路径，引导吃豆人远离幽灵或通向能量提升。退出的情况是当他吃掉力量或者不再被包围时。
当吃豆人吃掉能量时，创建一条路径来吃掉附近的一些幽灵。退出的情况是当路径上没有鬼魂时，重新计算路径。或者如果附近没有鬼魂，则完全退出该模式。
当只剩下不到一半的点，或者附近没有点时，进入一条路径去吃一些点，避开幽灵。当鬼魂靠近时重新计算路径，或者如果附近有多个鬼魂则完全退出路径。
当不存在需要路径的情况时，您可以恢复到之前编程的默认 AI。
Have a way to change PacMan into a "path following" mode. The plan is that you detect certain circumstances, calculate a pre-drawn path for PacMan to follow, and then work out early exit conditions for that path. You can use this for several circumstances.
When PacMan is surrounded by ghosts in three of the four directions within a certain distance, then create an exit path that either leads PacMan away from the ghosts or towards a power up. The exit situation would be when he eats the power up or ceases to be surrounded.
When PacMan eats a power up, create a path to eat some nearby ghosts. The exit situation would be when there are no ghosts on the path, recalculate the path. Or if there are no ghosts nearby, exit the mode entirely.
When there are less than half the dots left, or no dots nearby, enter a path to go eat some dots, steering clear of the ghosts. Recalculate the path when a ghost comes nearby, or exit it entirely if several ghosts are nearby.
When there are no situations which warrant a path, then you can revert back to the default AI you programmed before.
您可以使用蚁群优化技术来找到最短可见路径导致很多图标可以吃或者可以获得很多分数。
You can use Ant Colony Optimisation techniques to find shortest visible path that leads to many icons to eat or can get many score.
我对人工智能或特定算法了解不多，但这里有一些你可以尝试的事情，可能会让你足够接近政府工作:)
对于幽灵很快包围他的问题，也许幽灵人工智能太强大了？我知道经典吃豆人中的每个鬼魂据说都有特定的行为，所以如果您还没有将其纳入其中，您可能需要这样做。
为了消除回溯，您可以为最近遍历的节点创建权重惩罚，这样他就不太愿意返回到以前的路径。如果这还不足以将他踢向一个方向或另一个方向，那么您可以对数增加吸引力惩罚，因此一条路径将以非常快的速度变得比另一条路径更具吸引力。
对于他被鬼魂抓住的问题，一旦鬼魂到达危险的节点附近，你也许可以从基于目标的通用算法更改为规避算法。
I don't know a lot about AI or specific algorithms, but here are some things you could try that might just get you close enough for government work :)
For the problem with ghosts surrounding him quickly, maybe the ghost AI is too powerful? I know that there's supposedly specific behaviors for each ghost in classical Pacman, so if you haven't incorporated that, you may want to.
To eliminate backtracking, you could create an weight penalty for recently traversed nodes, so he's less inclined to go back to previous paths. If that's not enough to kick him in one direction or another, then you can logarithmically increase the attraction penalty, so one path will become significantly more attractive than the other at a very quick rate.
For the problem of him getting caught by ghosts, you might be able to change from a general goal-based algorithm to an evasive algorithm once the ghosts have reached a dangerous node proximity.
您可能会受益于了解机器人如何“推理”（如这篇优秀的 档案）。例如，了解幽灵的追逐/分散模式将使您能够在“危险”位置获得点，等等。
我添加这个答案时知道这不是您正在寻找的最佳解决方案（因为您想在下周交付..），但也许对将来阅读此内容的人有用。有点像时间胶囊:)
You might benefit of knowing how the bots "reason" (as explained in this excellent dossier). For example, knowing the chase/scatter pattern of the ghosts will allow you to get the dots in "dangerous" locations, and so on.
I am adding this answer knowing that it's not the best solution you were looking for (since you wanted to deliver next week..) but maybe will be of use to somebody reading this in the future. Sortof a time capsule :)
您应该查看 Antiobjects 的描述，这是吃豆人幽灵用来遍历的技术迷宫。特别要注意：
因此，您考虑使用类似的基于气味的技术来控制吃豆人，也许吃豆人更喜欢穿过气味较少的路径；这会减少他重蹈覆辙的机会。
You should check out this description of Antiobjects, which is the technique used by the Pacman ghosts to traverse the maze. In particular, note:
So you consider a similar scent-based technique to control Pacman, perhaps where Pacman preferred traversing a path with a smaller amount of scent; this would reduce the chance of him going over old ground.