8

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.)

rid
  • 61,078
  • 31
  • 152
  • 193
ComputerLocus
  • 3,448
  • 10
  • 47
  • 96

5 Answers5

6

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.

Pascal Cuoq
  • 79,187
  • 7
  • 161
  • 281
  • 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? – ComputerLocus Nov 15 '11 at 19:06
  • 1
    @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. – Pascal Cuoq Nov 15 '11 at 19:09
  • Okay I like the idea and most likely will use something along the lines of this or @larsmans answer. – ComputerLocus Nov 15 '11 at 19:15
4

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

Óscar López
  • 232,561
  • 37
  • 312
  • 386
  • 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 Nov 15 '11 at 18:36
4

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.)

Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • Well you kinda lost me there. I never have learnt about Steps before. – ComputerLocus Nov 15 '11 at 19:05
  • @Fogest: I was thinking along the lines of `enum Step { LEFT, RIGHT, UP, DOWN }`. – Fred Foo Nov 15 '11 at 19:06
  • @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. – Fred Foo Nov 15 '11 at 19:22
  • You see I don't know what a step is or a class or enum. Never learnt about that yet. – ComputerLocus Nov 15 '11 at 19:28
  • @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.) – Fred Foo Nov 15 '11 at 19:36
  • I will consider it. It would be nice if my schools library has one as well. – ComputerLocus Nov 15 '11 at 23:20
1

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)

Casey
  • 12,070
  • 18
  • 71
  • 107
0

Easiest implementations of such an AI would be to use a naive graph search algorithm. BFS would be a simple one which would work. However, you'd want to implement a heuristic to better optimize runtime of course, so a simple Manhattan distance from ghost agent to Pac-man would suffice.

Summary: BFS with Manhattan distance heuristic.

If you want to get fancier, and make your ghosts even more efficient at hunting, you can implement a game state heuristic (based on distance from ghost to Pac-man, and how many dots Pac-man has eaten so far, for eg) to use for when the ghost has to chose which next move to take. You can use pruning techniques to shorten runtime in this case.

ylun.ca
  • 2,504
  • 7
  • 26
  • 47