PacMan AI character offers for optimal next direction

Question

Firstly, this is an AI for PacMan, not for ghosts .

I am writing Android wallpapers that play PacMan around your icons. Although it supports user suggestions via the screen, most games will play AI. I have done 99% of all the programs for the game, but the AI ​​for PacMan itself is still extremely weak. I am looking for help in developing a good AI to determine the next PacMan travel destination.

My initial plan was as follows:

• Initialize the counter counter for each direction with a zero value.
• Start at your current position and use BFS to move in the four possible starting directions, adding them to the queue.

• Put the element in the queue, make sure that it has not yet been "noticed", make sure that it is a valid position on the board, and add the value for the current cell based on:

  • There is a point: plus 10
  • Includes power: plus 50
  • Has a fruit: plus the cost of fruit (depending on level)
  • There's a ghost heading for PacMan: subtracting 200
  • Is there a ghost that walks away from PacMan: do nothing
  • There is a ghost moving perpendicular: subtract 50
  • Multiply the cell value at a time, based on the number of steps in the cell, the more steps from the initial direction, the closer the cell value reaches zero.

  and set three possible directions from the current cell.

• Once the line is empty, find the highest score for each of the four possible starting directions and select this.

It sounded good to me on paper, but ghosts surround PacMan very quickly, and it jerks back and forth in the same two or three cells until it reaches it. Setting the ghostly presence values ​​doesn't help either. My nearest BFS point can at least get to level 2 or 3 before the game ends.

I am looking for code, thoughts and / or links to resources for developing my own AI - preferably the first two. I would like to release this on the market this weekend, so I'm in a bit of a hurry. Any help is appreciated.

---

FYI, it was manually cross-hosted on GameDev.StackExchange

Answer 1

If PacMan is stuck in a position and starts to tremble back and forth, then this suggests that the various open moves for him have very similar estimates after you run your indicator. Then small changes in the position of the ghosts will lead to a better movement back and forth. You might want to add some hysteresis to stop this.

Setting: select a random move and write it with a score of 0.

For each step:

• Start the evaluation function for the available moves.
• If the highest score is x% greater than the record rate, overwrite the record rate and move it using this.
• Apply move.

This leads to the fact that PacMan will no longer choose the “best” move at every step, but does not seem to be a greedy local search. This will make PacMan more consistent and stop twitching.

Answer 2

Have a way to change the PacMan to the "path" mode. The plan is that you discover certain circumstances, compute a pre-drawn path for PacMan tracking, and then develop early exit conditions for that path. You can use this for several circumstances.

When PacMan is surrounded by ghosts in three of four directions at a certain distance, create an exit path that either leads PacMan away from the ghosts or to a power source. The exit situation would be when he eats energy or ceases to be surrounded.

When PacMan is energized, create a path to eat some nearby ghosts. The output situation will be when there are no ghosts on the path, recount the path. Or, if there are no ghosts nearby, completely exit the mode.

When less than half of the remaining points are left or there are no points nearby, enter the path to go eat some points, avoiding ghosts. Recount the way when the ghost appears nearby, or leave the whole if there are several ghosts nearby.

If there are no situations that require a path, then you can return to the previously set AI by default.

Answer 3

You can use Ant Column Optimization to find the shortest visible path that leads to many icons there or can get a lot of points.

Answer 4

I don’t know much about AI or specific algorithms, but here are some things you could try that could just shut you down for government work :)

For the problem with the ghosts surrounding him quickly, is the ghostly AI too powerful? I know that for every ghost in the classic Pacman there is a certain behavior, so if you did not turn it on, you might want to.

To eliminate backtracking, you can create a weight limit for recently traversed nodes, so it is less likely to return to previous paths. If this is not enough to hit him in one direction or another, then you can logarithmically increase the fine for attraction, so one path will become much more attractive than the other with very fast speed.

Due to the problem of ghost infection, you can move from a general target algorithm to an evasive algorithm when the ghosts reach the dangerous proximity of a node.

Answer 5

It may be useful for you to find out how bots “reason” (as explained in this excellent dossier ). For example, knowing the haunting / scattering pattern of ghosts will allow you to get points in "dangerous" places, etc.

I add this answer, knowing that this is not the best solution you were looking for (since you wanted to deliver next week ..), but maybe it will be useful for someone who reads this in the future. Sort a temporary capsule :)

Answer 6

You should check out this description of Antiobjects , which is a technique used by Pacman's ghosts to walk through the maze. In particular, please note:

Each of these anti-objects or agents has an identical and simple algorithm that it launches at every step of the game. Instead of making Ghosts smart enough to solve the “shortest path” problem around the maze, the concept is instead created by “Feeling Pac-Man”, each tile is responsible for saying how much Pac-Man smells on its tiles.

So, you are considering a similar odor-based method for controlling Pacman, perhaps where Pacman would prefer to cross a path with less odor; this will reduce the likelihood that he will cross the old land.