   Not quite Pac-Man AI
  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?)WWWWWWWW_____WW__G__WW_____WWWW_WWW__W_WNow, 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 ;  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? ;  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];  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. ;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.