Jump to content
  • Advertisement

Archived

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

Beren77

Not quite Pac-Man AI

This topic is 5533 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!