Projects‎ > ‎Pacman‎ > ‎

AI for Ghosts in Pacman

 Note: I wrote this but haven't actually tested out this algorithm in pacman. All I know is that it compiles, but in theory it should work. This may seem obvious, but to speed things up you should only execute this algorithm when a ghost hits a wall and has more than one direction to travel. To use this algorithm, you should have your map set up as a grid, i.e. be able to identify each position with a horizontal value and a vertical value, such as (7,10) for a space 7 units horizontal to the right, and 10 units up the vertical. Also, I used a class called point to define a position in terms of x and y. It's quite simple, even for a beginner programmer,  so I probably don't need to annotate it:`    public class point {``    ``        private int xVal;``        private int yVal;``    ``        public point(int xint,int yint){``            xVal=xint;``            yVal=yint;``        }``    ``        public int x(){``            return xVal;``        }``        public int y(){``            return yVal;``        }``    ``    }`The algorithm is in a class called ghostAI in a function called control(). There are 4 parameters in control():`    control( current x position of the ghost, current y position of the`` ghost,             current x position of pacman, current y position of pacman);`where x is the horizontal value, and y is the vertical value. All values should be integers.We'll be creating that later, first we need to create a few functions so the algorithm knows which spaces are along the path of the ghosts, and which are within walls or restricted by the boundaries. If you already have an array that defines which points (or spaces) are along the paths for the ghost, you can skip on to creating the control() function. Now for the code:First, import the Math class: ```import java.lang.Math.*;```In the algorithm, a few variables we needed to define at the start are:an array to store points where a ghost is allowed to go (e.g. it can't go where a wall is, or outside the map)define the size of the map, with the highest horizontal value (highest x value), lowest horizontal value (lowest x value), highest vertical value (highest y value), and lowest vertical value.Also, define an integer named lowestSquare, which will be used later to hold the referrence to the direction closest to pacman that the ghost should turn.    ```     public class ghostAI {``````        ``````         int lowestSquare;````  ``// location of the square closest to pacman````        ``````         point[] ghostAllowed = new point;````   ````//for my map, 691 is the total number of spaces there were. Yours will probably be different``````                ``````                 public static final int xmax = 375; //highest horizontal value (on the x axis)``````                 public static final int ymax = 375; //highest vertical value (on the y axis)``````                 public static final int xmin = 5; //lowest x value``````                 public static final int ymin = 5; //highest x value``` ```            //your values will probably be different, so you’d want to change these to suit your map``````        ```So once you've done all that, we create the functions that check points for whether or not they're out of bounds (i.e. create a function that defines the boundaries of the paths). It's pretty simple to understand. To use it, just put the x value of a point as the first argument and y value of the same point as the second, then it spits back out whether it's within the boarder of the map. `    boolean checkBound( int xval, int yval ){````        // Border boundraries  ``````        //if true, it's in the boundaries                                          ``````        ``````         if (xval > xmax) {``````                ``````                 return false;``````         }``````         if (xval < xmin) {``````                 return false;``````                ``````         }``````         if (yval < ymin) {``````                 return false;``````                ``````         }``````         if (yval > ymax) {``````                 return false;``````                ``````         }else {``````                 return true;``````         }``````        ``````      }````  `Now for the more time consuming part (don't worry, it's not hard at all. Just reptitive and long....at least for me), creating a function that checks if the point is within a wall or not. It's pretty much the same as the function before, except with a heck of alot more if statements. It works exactly the same as before (with the same parameters and return values), just create an if statement to see if a point is on the path (i.e. if there's a wall from point (3,9) to (3, 7) to (6,7) to (6,9), if the x value is between 4 and 3 (inclusive), check if the y value's between 7 and 9 (inclusive). If it is, then the point is in a wall. ).  Here's mine: (I didn't copy the whole function, as it would take too much space and besides, you'd have to be pretty damn bored to read the whole thing...)`    public boolean checkPlace( int xval, int yval ){````        // if true, it's not hitting anything  ``````        if ((yval==375) & (xval>=105) & (xval<=250)) {``````                ``````                 return true;``````         }``````         if ((yval==375) & (xval>=310)) {``````                ``````                 return true;``````         }``````         if ((xval==250) & (yval>=245)) {``````                ``````                 return true;``````         }``````         if ((yval==330) & (xval>=250) & (xval<=310)) {``````                ``````                 return true;``````         }``````         if ((xval==310) & (yval>=110)) {``````                ``````                 return true;``````         }``````         if ((yval==245) & (xval>=250) & (xval<=310)) {``````                ``````                 return true;``````         }```                `}`Of course, if you want, you could combine the boundraries checking function with the wall checking function. So we've got all the parts we need, we can start writing the actual algorithm!Now we create a function called control. We'll make it string because in the end it will be returning "left", "right", "up" or "down". You can replace these with different data types if you want. So in control(), we'll be accepting 4 arguments. xint, the current x value of the position of the ghost, yint, the current y integer of the ghost, pacmanx, the current x value of the position of pacman and pacmany, the y value of pacman.```         public String control(int xint,int yint, int pacmanx, int pacmany){````        }`In control(), we'll define a few variables:`    int k = 0 ;`` //identifies the points in the openspace [].````     point[] openspace = new point;````  ````//keeps track of possible moves a ghost can go after each move (4 spaces, as it can either go up, down,````  ``left or right)````                ````    int pointCounter = 0; `` ````//keeps track of how far away each possible move is from pacman, so the ghost moves to the closest one.``````                   ```Now we use those function we created before, to fill up an array of points where a ghost can go. Loop through all the points within the map and if you find one thats not within a wall or out of bounds, then put it in ghostAllowed[]. : ```    //this loop just creates a list of places the ghost is allowed to go, i.e all       the points that are within the walls are excluded             ``````         for(int j=0;j<375;j++){``````             int dotx=5*j;```  `    ``        ``dotx+=5;````             for(int i=0;i<375;i++){``````                 int doty=5*i;``````                 doty+=5;``````                 if((checkBound(dotx,doty)) & (checkPlace(dotx,doty))){````  ``//if the                         ghost is allowed to go to that space…````                     pointCounter++;``````            ``````                     ghostAllowed[pointCounter]=new point(xint,yint);``````                              }``````             }``````         }```You might have noticed I multiplied all the points tested by 5, and added 5 to every points tested. That's because my axis started at point (5,5), and each step is 5 units. i.e. The ghosts move 5 units every turn. So for example, when j=0, and i=2, it's testing the point.     Next, we'll use this array to see which direction the ghost can turn. To speed things up, instead of individually checking each point and seeing if it exists in ghostAllowed[], scanning a total of 4 times, instead, we'll scan it once, and whenever we hit a point thats left, right, above or below the ghost, we'll add it to the openspace array as a possibility for the ghost to move there.   ```    for(int j=0;j<375;j++){ //loop through ghostAllowed for all the legitimate                         moves for the ghost…``````              ``` ```      if ((ghostAllowed[j].x() == xint+5)&&(ghostAllowed[j].y() == yint)){ //…and             when the point of a possible move is found, check if that possible                 move is also legitamate.``````            k++; //k keeps track of what position in the array the next point                 should be put into. It’s incremented here because we’re adding                 another point, so it needs to be one position above the last.``````            openspace[k] = new point(xint+5,yint); // The point is legitimate, so                 add it in openspace so it can be tested later if it’s the closest                 point to pacman.``````               ``````        }````        //Do the same for all the other directions````         if ((ghostAllowed[j].x() == xint-5)&&(ghostAllowed[j].y() == yint)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````                     ``````         }``````         if ((ghostAllowed[j].x() == xint)&&(ghostAllowed[j].y() == yint+5)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````               ``````         }``````         if ((ghostAllowed[j].x() == xint)&&(ghostAllowed[j].y() == yint-5)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````               ``````         }``````       }```    `k=0;``// reset k back to zero because we'll use it again````         ``` Now that we know which points are possible for the ghost to move to, we have to test each point out in relation to where pacman is, to see which one is the closest. We need to create a variable to hold the closest distance found from each square around the ghost to pacman. We'll define outside the loop as we don't want to keep redifeining it everytime a new point is tested, as this will reset the value for it and there's no way of testing for which square has the lowest value for the distance against eachother. That's why we define it outside the loop and give it a high value, so the first square tested will overwrite it:`           ````           int lowestValue=1000; //just set this as a high enough number so the                         first calculation will be lower.````          ````           ``````            for(int j=0;j<5;j++){   //this should go through all points in the                         open space array``````               //Now to calculates the distance from each possible move of the                     ghost from pacman``````                 int currentVal = 10*(Math.abs(openspace[k].x()-pacmanx) +                         Math.abs(openspace[k].y()-pacmany));``````                  if (currentValopenspace[lowestSquare].y()){ ``````                 return "down";``````               }``````               if(yintopenspace[lowestSquare].y()){``````                 return "left";``````               }``` ```               return "something went wrong";   //this shouldn’t be returned…``````            ``` And there's the end of the control() function. So overall, here's the whole code: ```import java.lang.Math.*;`````` public class ghostAI {``````        ``````         int lowestSquare;````  ``// location of the square closest to pacman````        ``````         point[] ghostAllowed = new point;````   ````//for my map, 691 is the total number of spaces there were. Yours will probably be different``````                ``````                 public static final int xmax = 375; //highest horizontal value (on the x axis)``````                 public static final int ymax = 375; //highest vertical value (on the y axis)``````                 public static final int xmin = 5; //lowest x value``````                 public static final int ymin = 5; //highest x value``` ```//yours will probably be different, so you’d want to change these to suit your map``````                ``````                ``````         public String control(int xint,int yint, int pacmanx, int pacmany){``````                 int k = 0 ;``````                 point[] openspace = new point;````  ````//keeps track of possible moves a ghost can go after each move (4 spaces, as it can either go up, down,````  ``left or right)````                ``````                         int pointCounter = 0; ```` ````//keeps track of how far away each possible move is from pacman, so the ghost moves to the closest one.``````                   ``` ```//this array just creates a list of places the ghost is allowed to go, i.e all the points that are the walls are excluded             ``````              for(int j=0;j<375;j++){``````                 int dotx=5*j;``````                 dotx+=5;``````                 for(int i=0;i<375;i++){``````                         int doty=5*i;``````                         doty+=5;``````                         if((checkBound(dotx,doty)) & (checkPlace(dotx,doty))){````  ``//if the ghost is allowed to go to that space…````                                    pointCounter++;                     ``````                                   ``````                                    ghostAllowed[pointCounter]=new point(xint,yint);``````                                   ``````                                ``````                         }``````                 }``````           }``````          ``````            for(int j=0;j<375;j++){ //scan the array for all the legitimate moves for the ghost…`````` //xint ```` ````and yint is the position the ghost is currently in              ``` ```  if ((ghostAllowed[j].x() == xint+5)&&(ghostAllowed[j].y() == yint)){ //…and when the point of a possible move is found, check if that possible move is also legitamate.``````                         k++; //k keeps track of what position in the array the next point should be put into. It’s incremented here because we’re adding another point, so it needs to be one position above the last.``````                         openspace[k] = new point(xint+5,yint); // The point is legitimate, so add it in openspace so it can be tested later if it’s the closest point to pacman.                       ``````                         ``````               }``````               if ((ghostAllowed[j].x() == xint-5)&&(ghostAllowed[j].y() == yint)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````                         ``````               }``````           if ((ghostAllowed[j].x() == xint)&&(ghostAllowed[j].y() == yint+5)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````                ``````           }``````           if ((ghostAllowed[j].x() == xint)&&(ghostAllowed[j].y() == yint-5)){``````                         k++;``````                         openspace[k] = new point(xint,yint);``````                ``````           }``````           }``````            k=0;``````           //In my pacman map, the positions (points) are incremented by 5. So, for example, when it tests for say y-5, it’s testing the point one down the vertical axis from the current position of the ghost.``` ```            //now to work out which square out of all of them are best to use…``````           int lowestValue=1000; //just set this as a high enough number so the first calculation will be lower, You can also set it to 999999 if you want to be extra sure…``````           ``````           ``````            for(int j=0;j<5;j++){   //this should go through all points in the open space array``````           //this calculates the distance from each possible move of the ghost from pacman``````                 int currentVal = 10*(Math.abs(openspace[k].x()-pacmanx) + Math.abs(openspace[k].y()-pacmany));``````                         if (currentValopenspace[lowestSquare].y()){ ``````                 return "down";``````               }``````               if(yintopenspace[lowestSquare].y()){``````                 return "left";``````               }``` ```        return "something went wrong";   //this shouldn’t be returned…``````            ``` ```                 }``````     boolean checkBound( int xval, int yval ){``````    // Border boundraries  ``````    //if true, it's in the boundraries                                          ``````        ``````         if (xval > xmax) {``````                ``````                 return false;``````         }``````         if (xval < xmin) {``````                 return false;``````                ``````         }``````         if (yval < ymin) {``````                 return false;``````                ``````         }``````         if (yval > ymax) {``````                 return false;``````                ``````         }else {``````                 return true;``````         }``````        ``````    }``````   ``` ```//for this function, I just put the points in that define where the walls are so it can return whether or not a point is in the wall (i.e. a ghost can’t move there), or not (so a ghost can move there)``````     public boolean checkPlace( int xval, int yval ){``````    // if true, it's not hitting anything                                           ``````        ``````         if ((xval==5) & (yval>=5) & (yval<=375)) {``````                ``````                 return true;``````         }``````         if ((yval==375) & (xval>=5) & (xval<=55)) {``````                ``````                 return true;``````         }``````         if ((yval==375) & (xval>=105) & (xval<=250)) {``````                ``````                 return true;``````         }``````         if ((yval==375) & (xval>=310)) {``````                ``````                 return true;``````         }``````         if ((xval==250) & (yval>=245)) {``````                ``````                 return true;``````         }``````         if ((yval==330) & (xval>=250) & (xval<=310)) {``````                ``````                 return true;``````         }``````         if ((xval==310) & (yval>=110)) {``````                ``````                 return true;``````         }``````         if ((yval==245) & (xval>=250) & (xval<=310)) {``````                ``````                 return true;``````         }``````         if ((xval==105) & (yval>=310)) {``````                ``````                 return true;``````         }``````         if ((yval==170) & (xval>=5) & (xval<=135)) {``````                ``````                 return true;``````         }``````         if ((xval==55) & (yval>=170)) {``````                ``````                 return true;``````         }``````         if ((yval==310) & (xval>=55) & (xval<=190)) {``````                ``````                 return true;``````         }``````         if ((xval==190) & (yval>=245) & (yval<=310)) {``````                ``````                 return true;``````         }``````         if ((yval==245) & (xval>=135) & (xval<=190)) {``````                ``````                 return true;``````         }``````         if ((xval==375) & (yval>=5) & (yval<=375)) {``````                ``````                 return true;``````         }``````         if ((yval==160) & (xval>=310)) {``````                ``````                 return true;``````         }``````         if ((yval==110) & (xval>=135) & (xval<=310)) {``````                ``````                 return true;``````         }``````         if ((yval==245) & (xval>=135) & (xval<=190)) {``````                ``````                 return true;``````         }``````         if ((xval==135) & (yval>=110) & (yval<=245)) {``````                ``````                 return true;``````         }``````         if ((xval==85) & (yval>=115) & (yval<=170)) {``````                ``````                 return true;``````         }``````         if ((yval==115) & (xval>=45) & (xval<=80)) {``````                ``````                 return true;``````         }``````         if ((xval==45) & (yval>=55) & (yval<=115)) {``````                ``````                 return true;``````         }``````         if ((yval==55) & (xval>=45) & (xval<=310)) {``````                ``````                 return true;``````         }``````         if ((xval==185) & (yval>=55) & (yval<=110)) {``````                ``````                 return true;``````         }``````         if ((xval==310) & (yval>=5) & (yval<=55)) {``````                ``````                 return true;``````         }``````         if ((xval==150) & (yval>=5) & (yval<=55)) {``````                ``````                 return true;``````         }``````         if ((yval==5) & (xval>=5) & (xval<=375)) {``````                ``````                 return true;``````         }``````   ``````         else {``````                 return false;``````         }``````        ``` ```          ``````       ``````           }`````` }```