Archived

This topic is now archived and is closed to further replies.

Beren77

Not quite Pac-Man AI

Recommended Posts

Hi, I am making a kind of a Pac-Man game and I am wondering how to write the AI for the ghosts. --- Wait: Before you flame me: There are some differences to the original Pac-Man: First: The walls ( == blocks) in the level are not static. The player (and only the player) has the ability to move them (i.e. push them) or even destroy them. Thus, the ghosts (whose aim is of course to catch the player) have to somehow react on those changes. Second, situations can happen (and will happen), where a ghost is in not in close contact with a wall but has many fields in his neighbourhood that are indeed free. So, the question is: Do you know good "heuristics" or algorithms on how to tweak the AI of the ghosts so that they are not too dumb to follow the player and yet dumb enough not to frustrate him? Thanks for your help, Beren

Share this post


Link to post
Share on other sites
Hi Beren,

If I remember correctly the original ghost pac-man worked thus;

As the player moved through the world he would leave an invisible trail behind him, the trail would fade over time.

When a ghost encountered a trial above a certain value it would then follow it for X duration. The threshhold for following a trail and the duration for following could be tuned to increase/decrease difficulty.

Now obviously if your going to be moving the walls around then this wouldn''t work so well, however it doesn''t mean that you can''t use it too a certain degree at least until it encounters a blocked wall at which point you could navigate around it while continually watching for a line of sight to the player.

The level you want to take this too depends on how clever you want the ghosts to be. At least with up to 4 ghosts continually scanning for a route it wouldn''t be overkill on the processor.

Michael

Share this post


Link to post
Share on other sites
Hmmm... Interesting idea... I think I can implement that. But what about the ghosts that do not find a trail? How do they move? Especially, if they are not surrounded by walls, I cannot think of anything special (I admit: Though I am a computer scientist, AI has never been one of my strong subjects). Imagine this situation: "W" is a wall "G" is a ghost and "_" is a space (can I somehow switch to non-proportional fonts here?)


WWWWWWW
W_____W
W__G__W
W_____W
WWW_WWW
__W_W

Now, I'd like the ghost to "explore" the "room" it is currently in and then leave it after a while... Greedy random algorithms just don't do the trick.

Any ideas?

Thanks,
Beren

[edited by - Beren77 on July 28, 2003 10:53:20 AM]

[edited by - Beren77 on July 28, 2003 10:54:15 AM]

[edited by - Beren77 on July 28, 2003 10:54:39 AM]

[edited by - Beren77 on July 28, 2003 10:54:56 AM]

Share this post


Link to post
Share on other sites
Beren,

Have you considered using a similar trail leaving for the ghosts?

By this I mean the ghost also leave an invisible trail behind them which fades over time (probably a much longer timer period than the players trail) You scan the tiles around the ghost and find the tiles least travelled and select one randomly.

That way the ghost would explore all parts of your example room, of course it''s possible for a ghost to box himself into a corner in which case it then has to just simply make a choice (random) which will move him out of the corner and give him tiles least travelled again.

Michael

Share this post


Link to post
Share on other sites
Hi MichaelCarr,

thanks for the ideas. I have implemented a basic version (a step-by-step "game", where you control a square block and try to escape four other square blocks...) and it works quite nicely. I will probably have to tweak the random values, since sometimes the ghosts are still just a little too smart, but making them less intelligent seems to be easier than making them smarter.

Again, thanks for your help,
Beren

Share this post


Link to post
Share on other sites
Hm. I have done a Pacman clone and my ghosts were just moving by a simple move-in-direction-where-player-is-and-dont-care-for-walls. That way is pretty dumb, but it is a fast way of implementing an npc-"ai" and it worked surprisingly well, at least it gets really tough sometimes

Share this post


Link to post
Share on other sites
Hey there,

I was overlooking this posting, and an old problem I had crept back up... I always had this idea that a "mouse" looking for cheese, would leave and "invisible trail" or "scent" that would slowly fade as tim ewent, but that it could follow all the hall intersections or middles of rooms randomly whenever it had more than one option with the same value, then after every move check the values of all the spaces it had just been, then keep moving accordingly... It is of course my theory that this isnt such a bad way of a really stupid thing to search out unknown terrority (or contstantly changing territory... kinda) that it could find its target (the cheese).

However, I cannot even really determine how to make the walls, and then assing values to "spaces"... maybe I just need to use someone else program and then fool with my own ai...

Anyway, dont thin kthat woulda helped anything, maybe I can check your program out after your done?

Share this post


Link to post
Share on other sites
Hi Brackus,

here is some preliminary code that shows how I am going to represent my maze. It is still rough and you would have to put in your own graphic's system, but once you've done that, you will be able to play around with the AI.

What I currently do to model the AI is as follows:
Originating from the current player position, I build an AIMap that has the same size as my field. Each index of the AIMap represents the number of fields it takes to reach the player.
Example:


WWWWWWWWWW
W321P1234W
W432WW345W
W5434W45WW
WWWWWWWWW


Where W is a wall, P is the player and the numbers indicate the "cost" (or trail) of each field. Now you can move your ghost to a field with a smaller number than it is currently on and voilà.

Applied to your problem, the player would be the "cheese" and the ghosts would be the mouse (or mice?!) - taken the program below as a basis, you would have to implement your AI; the degeneration of the trail of cheese could be done by implementing a maximum value in the recursive function CalculateAIMap. (Add an "if (value > some_border) return;"). This border should (over time) get smaller and smaller and there you go...

Have fun with it,
Beren


// A Pointer to my graphics interface... Use your system here.

GRAPHICS *Graphic;
bool End = false;

// This is the maze for Pac-Man. 1 denotes a wall, 0 a free space

// and 2 another kind of wall. Note that I have not positioned

// starting points for ghosts or pac-man itself (which would

// be sensible).

char Field[256] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1,
1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,
1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1,
1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1,
1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1,
1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 2, 0, 1,
1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1,
1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,
1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1,
1, 0, 2, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1,
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

// This is the AIMap that is generated automatically to calculate

// the next move of the ghosts

int AIMap[256];

long FAR PASCAL WindowProc(HWND hwnd, UINT message, WPARAM wparam, LPARAM lparam)
{
char filename[50];
static int counter = 0;

switch (message) {
case WM_KEYDOWN: switch (wparam) {
case VK_ESCAPE: End = true;
break;
}
}

return DefWindowProc(hwnd, message, wparam, lparam);
}

void DrawField() {
int x, y;
// Define some colors to draw simple graphics.

int a[3] = {0, Graphic -> Rgb2Int(0, 0, 255), // black, blue, red

Graphic -> Rgb2Int(255, 0, 0)};
int b[3] = {0, Graphic -> Rgb2Int(100, 100, 255), // black, light blue,

Graphic -> Rgb2Int(255, 100, 100)}; // light red

int c[3] = {0, Graphic -> Rgb2Int(50, 50, 255), // black, dark blue,

Graphic -> Rgb2Int(255, 50, 50)}; // dark red


// My maze is 16x16 fields in size (you will have guessed already...)

for (x = 0; x < 16; x++) {
for (y = 0; y < 16; y++) {
// Here you would paint your maze by blitting blocks of "real"

// graphic. I simply draw a rectangle with a 3d effect:

Graphic -> Rec_3d(x * 36 + 100, // x1

y * 36 + 5, // y1

x * 36 + 135, // x2

y * 36 + 40, // y2

a[Field[y * 16 + x]], // outer frame color

b[Field[y * 16 + x]], // inner frame color

c[Field[y * 16 + x]], // rectangle color

3); // width of the frame

// Note that the color of the rectangle depends on the

// type of the field.

}
}
}

// Clears the AIMap (i.e. initializes each field with -1). There are faster

// ways to do this, yes...

void ClearAIMap() {
for (int x = 0; x < 256; x++) {
AIMap[x] = -1;
}
}

// The AI calculation function. Starting at the player, all fields are given

// the number of fields it takes to reach the player. This is done recursively.

void CalculateAIMap(int x, int y, int value) {
int offset = (y << 4) + x;
AIMap[offset] = value;
if (Field[offset + 1] == 0 &&
(AIMap[offset + 1] == -1 || AIMap[offset + 1] > (value + 1))) {
CalculateAIMap(x + 1, y, value + 1);
}
if (Field[offset - 1] == 0 &&
(AIMap[offset - 1] == -1 || AIMap[offset - 1] > (value + 1))) {
CalculateAIMap(x - 1, y, value + 1);
}
if (Field[offset + 16] == 0 &&
(AIMap[offset + 16] == -1 || AIMap[offset + 16] > (value + 1))) {
CalculateAIMap(x, y + 1, value + 1);
}
if (Field[offset - 16] == 0 &&
(AIMap[offset - 16] == -1 || AIMap[offset - 16] > (value + 1))) {
CalculateAIMap(x, y - 1, value + 1);
}
}

void GameLoop() {
while (!End) {
ClearAIMap();
CalculateAIMap(playerPositionX, playerPositionY, 0);

// Sort the distances of the ghosts (the nearest ghost moves first)

// This is just crap: Implement a better way of sorting the ghosts!

int vals[4] = {-1, -1, -1, -1};
for (int t = 0; t < 4; t++) {
// vals[t] == current distance of ghost t to the player or -1

// if the ghost cannot reach the player at all.

vals[t] = AIMap[ghost[t].yposition * 16 + ghost[t].xposition];
}

for (int i = 0; i < 4; i++) {
int min = 99999;
int current = -1;

// Now really: Find the ghost closest to the player:

for (int u = 0; u < 4; u++) {
if (vals[u] < min && vals[u] != -1) {
current = u;
min = vals[u];
}
}

if (current == -1) {
// No more ghosts can reach the player, so move them randomly.

continue;
}
vals[current] = 99999;
u = current;

min = 99999;
int dir = -1;
int value = AIMap[posy[u] * 16 + posx[u] - 1]; // LEFT

if (value != -1 && value < min) {
min = value;
dir = 0;
}
value = AIMap[posy[u] * 16 + posx[u] + 1]; // RIGHT

if (value != -1 && value < min) {
min = value;
dir = 1;
}
value = AIMap[(posy[u] - 1) * 16 + posx[u]]; // UP

if (value != -1 && value < min) {
min = value;
dir = 2;
}
value = AIMap[(posy[u] + 1) * 16 + posx[u]]; // DOWN

if (value != -1 && value < min) {
min = value;
dir = 3;
}
switch (dir) {
case 0: posx[u]--; break;
case 1: posx[u]++; break;
case 2: posy[u]--; break;
case 3: posy[u]++; break;
}
// Now draw the ghost (not done here!)


// For the remaining ghosts, block this ghost's position. Thereby

// escape routes of the player are cut off by other ghosts.

Field[posy[u] * 16 + posx[u]] = -1;
ClearAIMap();
CalculateAIMap(posx[4], posy[4], 0);
}
// Clear the ghosts' positions agaian

for (int u = 0; u < 4; u++) {
Field[posy[u] * 16 + posx[u]] = 0;
}
// Draw the player and let him move...

}
}

// WinMain-Function follows (Window initialization...)



[edited by - Beren77 on July 31, 2003 5:17:03 AM]

Share this post


Link to post
Share on other sites
The obvious answer, of which I am suprised that no-one has mentioned, is A*. Every time a ghost reaches the centre of a ''tile'' or ''square'', run A* for it, save the next destenation square with the ghost, and have the ghost move to it. I have used AI similar to this to have a platoon of soldiers follow a leader around a tilemap. But this might make your mosters a little too smart and subtract from the game.

Share this post


Link to post
Share on other sites
quote:
Original post by jack_1313
The obvious answer, of which I am suprised that no-one has mentioned, is A*. Every time a ghost reaches the centre of a ''tile'' or ''square'', run A* for it, save the next destenation square with the ghost, and have the ghost move to it. I have used AI similar to this to have a platoon of soldiers follow a leader around a tilemap. But this might make your mosters a little too smart and subtract from the game.


One of the original posters was correct. The original pacman laid a trail down behind the player that the ghosts followed, (with slightly different rules for duration etc.)

A* doesn''t work as well for "pursuit" AI. A* may find the shortest path to the player, but doesn''t guarantee that you''ll end up behind the player chasing him. You could get to the target location without getting in the path of the player at all and find the player is traveling away from you. The point of the original game was that the ghosts "chased" you.

Share this post


Link to post
Share on other sites
Hey, thanks for the nice reply Beren...

You orginally asked for help, and now in the same posting your assisting me

Anyway, I dont have a "graphics system"

Originally I made a stupid thing in turing by drawing a square, then drawing a bunch of rectangles or squares over it... Then i had a blue circle (mouse) go after a yellow arc... I only ever got to the point where the "mouse" wouldnt go out side of the main square, but other than that it owuld just move randomly arund and thru walls until like 400 moves later it "might" run into the cheese...

I kinda came up with a good way to do this one day while I was sitting at work (im a telemarketer) anyway, I am outta programming for over a year now... and now Im am gonna learn c++ right now again, but I think the code you posted is still a little over my head(but I will give it a clear lookover) will it run by itself???

Anyway, just some of my abstract rambling(oh yeah, I meant like this:

*******************
* * * * * *CC*
* * * * * *
* * * *
* **** * * 1****
* **** 1*2 *
* **** * 1* 223 *
*SS111111112111*2 *
*******************

See, my main theory is that let the cpu randomly decide a way to go, and eac htime it gets more than one chance, let it decide again, however, you gotta check the "value" of each square, the above map shows a "mouse" trying to get to the CC without knowing where it is... It randomly starts out going east... keeps going past the first intersection, then makes a wrong turn, but when it goes to go back, the previous value is 1.. however, in that event, it just goes to the place it has been the least, so it escapes, and keeps going east(cause to go west would be going over all those ones, which are higher than the "0" or whatever value for the unchecked spaces... it then meets a wall, has to go up, then gets a chance to go up or right, it chooses right, then goes up, then goes down, and it keeps going one direction or the other til eventually the spaces it has passed grows larger(or as large as) the values of the spaces it must go back over, so then it just keeps going...

That is a whole lot of writing for nothing, and maybe my idea is stupid, but I just thought when I was younger that something not knowing where to go, can just choose randomly, and yet, if it can keep conscious of where its been before slightly, then eventually, it owuld cover a whole map until it got to its destination, while not the fastest way, its not as stupid looking as always turning left/right, and the cpu doesnt really "cheat" it just can sense how many times its been in that spot before, and then always goes to the place its been the least( or randomly if one or more of the same value are open)

Well, thats just my crazy rambling thoughts... Iwould love to see this idea implemented someday, but well have to see...

Share this post


Link to post
Share on other sites
Hi Brackus,

don't want the spoil the fun for you, but I was just a little frustrated about some other code of mine (don't ask...), so I settled down to write a (graphically _very_ simple) console program to visualize your mouse/cheese problem.
I tried to implement your idea, so I have an AIMap representing the number of times the mouse has passed over a field. The mouse then moves by checking where the neighboring field with the lowest number is. There are cases where the mouse could choose between two or more fields, because they have the same value. You could apply a random choice here. For the sake of simplicity, I omitted it and simply went for a strict ordering. So the mouse tries to go up, down, left, right (in that order).
(in other words, if all four neighboring fields have the same value, the mouse will always go up).

One problem is still unsolved, though: If the mouse hits a dead-end, it takes a step back and could then be in a position where the route back to the dead-end could have the same value as the way further out. So the dead-end could be entered twice (so occuring in the sample program below).

Feel free to ask any questions about the code, play with it, change it, do whatever you like with it --- and have fun.

Hope this code is easier to understand.
Beren


#include <stdio.h>
#include <conio.h>

#define MAZE_SIZE_X 10
#define MAZE_SIZE_Y 10

// Stores the maze information

char Maze[MAZE_SIZE_X * MAZE_SIZE_Y] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 0, 1, 0, 1, 0, 1, 0, 0, 1,
1, 0, 0, 0, 0, 0, 1, 0, 1, 1,
1, 1, 1, 0, 1, 1, 1, 0, 0, 1,
1, 0, 1, 0, 0, 0, 0, 0, 1, 1,
1, 0, 0, 0, 1, 0, 1, 0, 0, 1,
1, 1, 0, 1, 0, 0, 0, 1, 0, 1,
1, 0, 0, 1, 0, 1, 0, 0, 1, 1,
1, 0, 1, 0, 0, 0, 1, 0, 0, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1};

char AIMap[MAZE_SIZE_X * MAZE_SIZE_Y];

// This functions outputs the Maze and the AIMap on the console.

void drawMazeAndMap() {
for (int y = 0; y < MAZE_SIZE_Y; y++) {
for (int x = 0; x < MAZE_SIZE_X; x++) {
switch (Maze[y * MAZE_SIZE_X + x]) {
case 0: printf(" "); break; // Free space

case 1: printf("*"); break; // Wall

case 2: printf("M"); break; // Mouse

case 3: printf("C"); break; // Cheese

}
}
printf(" ");
// Now draw one line of the AI Map:

for (int x2 = 0; x2 < MAZE_SIZE_X; x2++) {
printf("%d", AIMap[y * MAZE_SIZE_X + x2]);
}
printf("\n");
}
printf("\n\n");
}

// Simply initializes the AIMap with 0 values.

void clearAIMap() {
for (int i = 0; i < (MAZE_SIZE_Y * MAZE_SIZE_X); i++) {
AIMap[i] = 0;
}
}

// The main "mouse-loop".

// Hit any key to let the mouse move one more step and observe

// how the maze and the AIMap change.

// Hit ESC to abort or wait until the mouse found the cheese.

void mainLoop() {
bool end = false;
char key;

// (Starting) positions of cheese and mouse:

// (Upper left corner is (0,0), lower right corner is

// (MAZE_SIZE_X - 1, MAZE_SIZE_Y - 1)

int cheese_x = 1, cheese_y = 1;
int mouse_x = 1, mouse_y = 8;

// Place the cheese (3 == cheese)

Maze[cheese_y * MAZE_SIZE_X + cheese_x] = 3;
// Place the mouse (2 == mouse)

Maze[mouse_y * MAZE_SIZE_X + mouse_x] = 2;
// The mouse has been on its initial field once, so set the

// AIMap value of its current position to 1

AIMap[mouse_y * MAZE_SIZE_X + mouse_x]++;

// Show the maze

drawMazeAndMap();

while (!end) {
key = getch();
if (key == 27) {
end = true;
}
// Move the mouse:

// First, determine which fields the mouse can walk to (empty fields):

int left = -1, right = -1, up = -1, down = -1;
if (Maze[(mouse_y - 1) * MAZE_SIZE_X + mouse_x] != 1) {
up = AIMap[(mouse_y - 1) * MAZE_SIZE_X + mouse_x];
}
if (Maze[(mouse_y + 1) * MAZE_SIZE_X + mouse_x] != 1) {
down = AIMap[(mouse_y + 1) * MAZE_SIZE_X + mouse_x];
}
if (Maze[mouse_y * MAZE_SIZE_X + mouse_x - 1] != 1) {
left = AIMap[mouse_y * MAZE_SIZE_X + mouse_x - 1];
}
if (Maze[mouse_y * MAZE_SIZE_X + mouse_x + 1] != 1) {
right = AIMap[mouse_y * MAZE_SIZE_X + mouse_x + 1];
}
// Now select the best field (the one with the smallest number > -1):

// If there are two fields with the same value, the mouse will prefer

// the field checked first (i.e. it will go up, down, left, right).

// So, the mouse will only go right, if there are no other chances at

// all. One problem here is, that thus, one dead-end is always hit

// twice.

int min = 99999, dir = -1;
if (up < min && up != -1) {
min = up;
dir = 0;
}
if (down < min && down != -1) {
min = down;
dir = 1;
}
if (left < min && left != -1) {
min = left;
dir = 2;
}
if (right < min && right != -1) {
min = right;
dir = 3;
}
// Remove the mouse from its old position

Maze[mouse_y * MAZE_SIZE_X + mouse_x] = 0;

// Calculate the new mouse coordinates:

switch (dir) {
case 0: mouse_y--; break;
case 1: mouse_y++; break;
case 2: mouse_x--; break;
case 3: mouse_x++; break;
}
// Now check if the target field contains the cheese...

if (Maze[mouse_y * MAZE_SIZE_X + mouse_x] == 3) {
printf("And the mouse is happily munching its cheese *hjam*...\n");
// Comment the next line out, if you want to know, if all fields

// of the maze are reached... (and they are :-))

end = true;
}
// Move the mouse:

Maze[mouse_y * MAZE_SIZE_X + mouse_x] = 2;
// And increase the "waycounter" of the mouse:

AIMap[mouse_y * MAZE_SIZE_X + mouse_x]++;

// Show the progress...

drawMazeAndMap();
}
}

void main() {
clearAIMap();
drawMazeAndMap();
mainLoop();
}


[edited by - Beren77 on July 31, 2003 5:34:27 PM]

Share this post


Link to post
Share on other sites
Yeah, its way easier in person, but basically, that is what i tried to show in my last posting!!!

Once the mouse hits a dead end, then backs up, likely, the way forward/backward (or right/left) has the same value (most likely a 1) that I guess is where the randomness would be stupid, so maybe if a thing was implemented so that in the event that situation occured, that it would go to the space it hadnt been to in the longest amount of time... Anyway, like I said, even if randomly it went down the dead end again, it would still add the numbers up, until eventuallythe "mouse" would have to get back down the dead end, and with the numbers to go back way higher than the numbers out, it would work...

This sound kinda like gibberish even to me, but its cool you find this a bit interesting...

Dustin

Share this post


Link to post
Share on other sites
Hi,

one solution to that problem would be to assign a "how-long-has-it-been-since-the-mouse-was-here" value to each field. Actually, all you have to do is to increase the value of the AIMap field that the mouse moves to by any value > 1 (say 50 for example). Then, all AI fields that the mouse is currently not on and have a value > 0 are reduced by 1 et voilà: instead of having two fields with the same value, one leading into a dead-end, you would have two fields with different values, the lower one leading away from the dead end.

Beren

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I''m not exactly sure (never checked myself) but one time the AI in Pac Man was described to me like this:

The ghosts follow a "set" routine for a few seconds then...

1. The Red ghost always picks the shortest path to you.
2. 2 Ghosts pick the best path to get to the spot left/right of you.
3. A fourth ghost tries to get to a spot below you.

Every now and then, the ghosts are forced to flip back on themselves.

Again, this is what I was told one time, but never looked at the source to confirm.

Share this post


Link to post
Share on other sites