Pacman Ghost AI

Question

I'm currently making a pacman game in java. I have a question about the ghosts though.

I understand that the ghosts do not all have the same style of attack. I first want to work on the basics of getting the ghost to go after the pacman and not worry about there differences yet.

My question to you smart people out there is what would be the best way to make the ghosts chase the pacman but sometimes randomly divert paths. I'm currently using a 21 by 21 2D array for telling where walls are and such so I was thinking make it more try and head for the current grid location of pacman. (for example go to 10,14) Of course while avoiding going through walls like pacman. I'm wondering how I could make it do this and also have the ghosts sometimes stop and go another direction or something so that it's not always a constant chase and pacman has a chance to get away. Maybe some of you have programmed a pacman game or just know a good way for this. Any help would be greatly appreciated.

(Please note I'm currently in a Grade 11 Computer Science course and halfway through the first semester ever of learned java.)

Solution 1

If you just want the ghosts not all to behave the same, each time they encounter an intersection, make their decision a random mix of some reasonable chasing default (such as continuing the way with the shortest distance to Pacman — Use Dijkstra's algorithm on all successors to pick the best one) and a random choice.

Solution 2

I found very helpful this article: Understanding Pac-Man Ghost Behavior, as it explains just what you need.

Solution 3

Here's a possibility: for all steps that the ghost can take, compute whether that step will bring it closer to Pacman. That can be done with the Manhattan distance, which in a 2d grid is just the x distance + the y distance. Then randomly pick a step, with higher probability assigned to those steps that will actually take it closer.

If you have an array steps with the first n_closing_in steps representing the steps that will take the ghost closer to Pacman, then you can assign those a total probability of 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's left in total_probability over the steps that will take the ghost farther away 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 isn't too complicated and the probability of closing in is >.5, the ghosts will appear to chase after Pacman, but in a haphazard way.

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

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

Solution 4

For my college level AI course, I did some work with an older version of the Pacman Ghost AI framework. It looks like the current version can be found here http://www.pacman-vs-ghosts.net/software (Now DEAD). In this you would develop your own Ghost agents to try and capture an agent or user controlled Pacman.

This was very useful in playing around with different AI techniques.

More to your question, the levels in that framework are actually built out of a graph and not a 2d array. You might take a look at the code to see how they do it.

The original link is dead and so far haven't been able to find an official mirror. However, the below will probably be of help:

Understanding Pac Man Ghost Behavior Ms Pac Man Vs Ghost AI (GitHub) PacMan_v6.2 (GitHub)

View more solutions

Comments

[ComputerLocus]

Yes I know each ghost has it's own behavior but we are not at all expected in the course I'm in to program a game of such complexity. I just want to first add a basic chase system not this advanced of methods yet.

[ComputerLocus]

Will take a look at it but do consider my skill level.

[ComputerLocus]

Well you kinda lost me there. I never have learnt about Steps before.

[ComputerLocus]

So your saying make them pick a random turn from the intersection yet make it more probably that they will go in the direction pacman is going?

[Fred Foo]

@Fogest: I was thinking along the lines of enum Step { LEFT, RIGHT, UP, DOWN }.

[Pascal Cuoq]

@Fogest Exactly. The values that prevent the ghosts from clumping together but keep the game interesting would have to be determined by experiments (depending on the shape of the maze), but I would guess 50% random choice — 50% shortest path would give acceptable results.

[ComputerLocus]

Okay I like the idea and most likely will use something along the lines of this or @larsmans answer.

[Fred Foo]

@Fogest: I mean you should represent the possible steps in some way. I've assumed you have a type Step for that, which might be an enum or a class. It doesn't really matter, as long as you have some way to represent the information that a step can be left, right, up or down. You could even use an int for this purpose.

[ComputerLocus]

You see I don't know what a step is or a class or enum. Never learnt about that yet.

[Fred Foo]

@Fogest: pick up any book on Java in your local library and look up classes. They're pretty fundamental. (And I bet you'll have to learn about them pretty soon anyway.)

[ComputerLocus]

I will consider it. It would be nice if my schools library has one as well.

[user3575425]

I think the website pacman-vs-ghosts.net/software is inactive. Is there anywhere else I can find the framework?

[user3575425]

jumpnett. Do you have a newer link?