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

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

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]

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

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

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

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:

WWWWWWWWWWW321P1234WW432WW345WW5434W45WWWWWWWWWWW 

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 ghostsint 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]