Hi there guys, i have made a 2D pacman game in DirectX 9 and all i need to finish it is some AI for my ghosts, the maze is made by just using an array. As i am new to AI could some one tell mw which method is best and how to implement it?

As i remember
The AI from the original PAC Man was something like this:

One ghost would fallow you
One would go up and down and in the center
And one ghost would just have a random pattern

Don't know if this is quite the same.

Well you said your map is an array.

Matrix I ques (2d array).

You could use some graphs algo there fro computing the shortest path or something :d

Maybe even Lee's algorithm.

What do you want your AI to do?

You should probably implement multiple behaviors for your ghosts, one where they wander randomly around the level, another where they flee from the pacman, one where they try to attack the pacman and one where they try to reach their "base" in the center.

For this you need a state machine that tells the ghost in which state it is (which behavior to follow) and some logic to change the state. Then you need to implement each of the behaviors. Wandering around is simple, whenever you reach an intersection, randomly pick a direction and go that way until the next intersection or until you run into a wall. Fleeing and attacking the pacman is not that hard either, you just move in the direction of the pacman. You maybe need to implement some kind of "vision" for the ghosts, so that they don't just run for the pacman. The return-to-base-behavior is the most complex, for that you need some kind of path finding to find the shortest path. You should find the path once and then follow that path, don't find the path on every update.

The pathfinding algorithm depends a lot on the data structures you use in the levels. There's a lot of resources available on different pathfinding methods, one of the most popular is the A* (A star) pathfinding.

You can implement more (or less) different behaviors what I've described here. A state machine + behavior type AI is a very common way of doing simple AI's.

-Riku

@clauchiorean: almost :-)

there were 4 ghosts in the original pacman.
quite easy but effective ai.

1. the chaser:
a ghost that always follows you.
i think thats quite easy to do. just calc the shortest route to the players actual position and follow that route.

2. the runner
a ghost that goes anywhere just randomly.
at each crossing, just select the direction randomly.

3. the protector:
a ghost that protects the doors, where you can walk outside the game area and come in at the other side.
you could do this by a 6-point model. at each "door", place 3 points: one a bit up, one a bit down, and one in front of the door. now your ghost randomly selects one of that 6 points and goes there. when reaching that point, select the next one to travel to.

4. the interceptor:
a ghost that seems to know where you want to go to, and tries to cross your way.
the hardest one to implement. you could do something like the following:
record the players position, 3 times. with these 3 positions (i call them a,b and c), build 3 vectors (a->b, b->c, a->c). now add these vectors and divide the resulting vector by 3. this is where the player seems to go to. if the point is outside the game field, reflect it on the field wall. when calculating your way to that point, try not to cross the chaser's way, but to go the other way round (in the middle, there is the "ghost house" where the ghosts spawn).


just test a bit, so that the ghost ai is not too strong.
you could also make the interceptor protect the remaining cookies or something.

Actually, the Interceptor was nothing more than a ghost that would head toward the closest intersection in the direction the player was moving.

Quote: Original post by Anonymous Poster

4. the interceptor:
a ghost that seems to know where you want to go to, and tries to cross your way.
the hardest one to implement. you could do something like the following:
record the players position, 3 times. with these 3 positions (i call them a,b and c), build 3 vectors (a->b, b->c, a->c). now add these vectors and divide the resulting vector by 3. this is where the player seems to go to.

That doesn't quite seem to make sense.

Example 1: Say the user is going in a straight line. The three positions are (0,0),(0,1),(0,2). If you add the three vectors ab, bc, ac, you get a vector from (0,0) to (0,4). Divide it by three, you get a vector from (0,0) to (0,1.3). So you'd calculate the user to be heading for a point he's already passed.


Example 2: Say the user turns a corner. The positions are (0,0),(0,1),(1,1). Add them together, divide by three, you're again predicting that the user is going to backtrack, this time at an angle into a wall.

I might not have understood what you were saying, though.

I think the idea of just heading towards the next intersection makes the most sense (finding the shortest path between the ghost and whichever intersection Pacman will hit if he keeps going in the same direction). If Pacman has just emerged from an intersection, and hasn't turned left or right yet, you could use the second-to-last direction he was traveling in as a guess.

Quote: Original post by Anonymous Poster
1. the chaser:
a ghost that always follows you.
i think thats quite easy to do. just calc the shortest route to the players actual position and follow that route.

I don't think the red ghost was that intelligent. I believe it just chose to go downwards in an intersection if pacman's position was below it, and likewise for all directions.

or for a really interesting ai, have all the ghosts line up across the middle, and then just advance towards the player, closing off every escape route . . .

kinda like a net . . .

though i dont think anyone would want to play that hehe

Cheers guys for telling me how all the ghosts behave but now i need to implement it. the 1st thing that i want to do is to make a graph data structure connecting the nodes together and I want the end product to look like this: -


i have created all the nodes like: -

But where do i go from here to create a graph?

[Edited by - Prog101 on September 6, 2006 4:55:32 AM]

Your last reply is a total cross-post. Bad kitty!