Pacman Ghost AI

Question

I am currently making a pacman game in java. However, I have a question about ghosts.

I understand that not all ghosts have the same attack style. First, I want to work on how to make the ghost go after the pacman and not worry about the differences.

My question for you, smart people, is what would be the best way to get ghosts to chase a pacman, but sometimes randomly distract ways. I am currently using a 21 by 21 2D array to tell me where the walls are, and so I thought it was trying more and heading to the current location of the pacman grid. (e.g. go to 10.14). Of course, avoiding going through walls like pacman. I wonder how I can do this, and sometimes ghosts stop and go in another direction or something like that, so he doesn’t always have a constant pursuit, and the pacman has a chance to leave. Perhaps some of you have programmed the pacman game or just know how to do it. Any help would be greatly appreciated.

(Please note that I am in the 11th grade Computer Science course and halfway to the first semester ever recognized by java.)

Answer 1

If you just want the ghosts to not all behave the same, every time they encounter an intersection, decide on a random combination of some reasonable pursuit by default (for example, continuing the path with the shortest distance to Pacman - Use the Dijkstra algorithm for all successors to choose the best) and random selection.

Answer 2

I really liked this article: Understanding Pac-Man Ghost Behavior as It Explains What You Need.

Answer 3

There is an opportunity: for all the steps that a ghost can take, calculate whether this step will bring Pacman closer. This can be done using the Manhattan distance , which in the 2nd grid is equal to the distance x + y . Then arbitrarily choose a step with a higher probability assigned to those steps that will actually bring it closer.

If you have an array of steps with the first steps n_closing_in representing the steps that will bring the ghost closer to Pacman, you can assign them the overall probability prob_closing_in with

 double total_probility = 1.; for (int i=0; i<n_closing_in; i++) { step_prob[i] = prob_closing_in / n_closing_in; total_probability -= prob_closing_in / n_closing_in; } 

Then similarly distribute what remains of total_probability into steps that distract the ghost further from Pacman.

 Step random_step(Step[] possible_steps, double[] step_prob) { double r = Math.random(); int i; for (i=0; i<possible_steps.length(); i++) { if (r < step_prob[i]) break; r -= step_prob[i]; } return possible_steps[i]; } 

If the maze is not too complicated, and the probability of closure in it is >.5 , ghosts will haunt after Pacman, but randomly.

Raising prob_closing_in to 1. will make the game more difficult.

(All of the above code is untested and may contain errors. I'm not very good at Java.)

Answer 4

For my college-level AI course, I worked a little with the old version of Pacman Ghost AI. It seems that the current version can be found here http://www.pacman-vs-ghosts.net/software (now DEAD) . In this case, you developed your own Ghost agents to try to capture the agent or user-controlled Pacman.

This was very useful when playing with various AI methods.

In addition to your question, the levels in this structure are actually constructed from a graph, not a 2d array. You can take a look at the code to see how they do it.

The original link is dead and still could not find the official mirror. However, below is likely to be useful:

Understanding the ghost behavior of Pac Man Ms Pac Man Vs Ghost AI (GitHub) PacMan_v6.2 (GitHub)

Answer 5

The simplest implementations of such an AI would be to use a naive graph search algorithm. BFS will be simple, which will work. However, you want to implement heuristics so that, of course, it is better to optimize the execution time, so a simple Manhattan distance from the ghost agent to the Pac-man is enough.

Summary: BFS with Manhattan distance heuristics.

If you want to become more attractive and make your ghosts even more effective when hunting, you can implement a game state heuristic (based on the distance from the ghost to the Pac-man and how many points Pac-man have eaten so far, for example, for use when the ghost should choose which next step to take, you can use cropping methods to shorten the execution time in this case.