Robust/src/Benchmarks/MMG/Tag/Ghost.java

   1 public class Ghost {
   2     flag move;
   3     flag update;
   4
   5     public int m_locX;
   6     public int m_locY;
   7     public int m_index;
   8     public int m_target;
   9     public int m_direction;  // 0:still, 1:up, 2:down, 3:left, 4:right
  10     int m_dx;
  11     int m_dy;
  12     Map m_map;
  13
  14     public Ghost(int x, int y, Map map) {
  15         this.m_locX = x;
  16         this.m_locY = y;
  17         this.m_dx = this.m_dy = 0;
  18         this.m_index = -1;
  19         this.m_target = -1;
  20         this.m_direction = 0;
  21         this.m_map = map;
  22     }
  23
  24     // 0:still, 1:up, 2:down, 3:left, 4:right
  25     public void tryMove() {
  26         //System.printString("step 1\n");
  27         // reset the target
  28         this.m_target = -1;
  29         // find the shortest possible way to the chosen target
  30         setNextDirection();
  31     }
  32
  33     private void setNextDirection() {
  34         // current position of the ghost
  35         int start = this.m_locY * this.m_map.m_nrofblocks + this.m_locX;
  36         boolean set = false;
  37         Vector cuts = new Vector();
  38         int tmptarget = 0;
  39         int tmpdx = 0;
  40         int tmpdy = 0;
  41         int tmpdirection = 0;
  42         boolean first = true;
  43         while(!set) {
  44             int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1];
  45             for(int i = 0; i < parents.length; i++) {
  46                 parents[i] = -1;
  47             }
  48             if(!BFS(start, parents, cuts)) {
  49                 this.m_target = tmptarget;
  50                 this.m_dx = tmpdx;
  51                 this.m_dy = tmpdy;
  52                 this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection;
  53                 set = true;
  54                 //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n");
  55             } else {
  56                 // Reversely go over the parents array to find the next node to reach
  57                 boolean found = false;
  58                 int index = this.m_map.m_pacMenY[this.m_target] * this.m_map.m_nrofblocks + this.m_map.m_pacMenX[this.m_target];
  59                 //System.printString("Target: " + this.m_target + "\n");
  60                 while(!found) {
  61                     int parent = parents[index];
  62                     if(parent == start) {
  63                         found = true;
  64                     } else {
  65                         index = parent;
  66                     }
  67                 }
  68
  69                 // set the chase direction
  70                 int nx = index % this.m_map.m_nrofblocks;
  71                 int ny = index / this.m_map.m_nrofblocks;
  72                 this.m_dx = nx - this.m_locX;
  73                 this.m_dy = ny - this.m_locY;
  74                 if(this.m_dx > 0) {
  75                     // right
  76                     this.m_direction = 4;
  77                 } else if(this.m_dx < 0) {
  78                     // left
  79                     this.m_direction = 3;
  80                 } else if(this.m_dy > 0) {
  81                     // down
  82                     this.m_direction = 2;
  83                 } else if(this.m_dy < 0) {
  84                     // up
  85                     this.m_direction = 1;
  86                 } else {
  87                     // still
  88                     this.m_direction = 0;
  89                 }
  90                 if(first) {
  91                     tmptarget = this.m_target;
  92                     tmpdx = this.m_dx;
  93                     tmpdy = this.m_dy;
  94                     tmpdirection = this.m_direction;
  95                     first = false;
  96                     //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n");
  97                 }
  98
  99                 // check if this choice follows some other ghosts' path
 100                 if(!isFollowing()) {
 101                     this.m_map.m_ghostdirections[this.m_index] = this.m_direction;
 102                     set = true;
 103                 } else {
 104                     cuts.addElement(new Integer(index));
 105                     /*for( int h = 0; h < cuts.size(); h++) {
 106                         System.printString(cuts.elementAt(h) + ", ");
 107                     }
 108                     System.printString("\n");*/
 109                 }
 110             }
 111         }
 112     }
 113
 114     // This methos do BFS from start node to end node
 115     // If there is a path from start to end, return true; otherwise, return false
 116     // Array parents records parent for a node in the BFS search,
 117     // the last item of parents records the least steps to reach end node from start node
 118     // Vector cuts specifies which nodes can not be the first one to access in this BFS
 119     private boolean BFS(int start, int[] parents, Vector cuts) {
 120         //System.printString("aaa\n");
 121         int steps = 0;
 122         Vector toaccess = new Vector();
 123         toaccess.addElement(new Integer(start));
 124         while(toaccess.size() > 0) {
 125             //System.printString("bbb\n");
 126             // pull out the first one to access
 127             int access = ((Integer)toaccess.elementAt(0)).intValue();
 128             toaccess.removeElementAt(0);
 129             for(int i = 0; i < this.m_map.m_pacMenX.length; i++) {
 130                 if(((access%this.m_map.m_nrofblocks) == this.m_map.m_pacMenX[i]) && ((access/this.m_map.m_nrofblocks) == this.m_map.m_pacMenY[i])) {
 131                     // hit one pacman
 132                     this.m_target = i;
 133                     parents[parents.length - 1] = steps;
 134                     return true;
 135                 }
 136             }
 137             steps++;
 138             Vector neighbours = this.m_map.getNeighbours(access);
 139             for(int i = 0; i < neighbours.size(); i++) {
 140                 int neighbour = ((Integer)neighbours.elementAt(i)).intValue();
 141                 if(parents[neighbour] == -1) {
 142                     // not accessed
 143                     boolean ignore = false;
 144                     if(access == start) {
 145                         // start node, check if the neighbour node is in cuts
 146                         int j = 0;
 147                         while((!ignore) && (j < cuts.size())) {
 148                             int tmp = ((Integer)cuts.elementAt(j)).intValue();
 149                             if(tmp == neighbour) {
 150                                 ignore = true;
 151                             }
 152                             j++;
 153                         }
 154                     }
 155                     if(!ignore) {
 156                         parents[neighbour] = access;
 157                         toaccess.addElement(new Integer(neighbour));
 158                     }
 159                 }
 160             }
 161         }
 162         //System.printString("ccc\n");
 163         parents[parents.length - 1] = -1;
 164         return false;
 165     }
 166
 167     // This method returns true if this ghost is traveling to the same
 168     // destination with the same direction as another ghost.
 169     private boolean isFollowing () {
 170         boolean bFollowing = false;
 171         double  dRandom;
 172
 173         // If the ghost is in the same location as another ghost
 174         // and moving in the same direction, then they are on
 175         // top of each other and should not follow.
 176         for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
 177             // Ignore myself
 178             if (this.m_index != i) {
 179                 if (this.m_map.m_ghostsX[i] == this.m_locX &&
 180                         this.m_map.m_ghostsY[i] == this.m_locY &&
 181                         this.m_map.m_ghostdirections[i] == this.m_direction) {
 182                     return true;
 183                 }
 184             }
 185         }
 186
 187         // This will allow ghosts to often
 188         // clump together for easier eating
 189         dRandom = this.m_map.m_r.nextDouble();
 190         if (dRandom < .90) {
 191             //if (m_bInsaneAI && dRandom < .25)
 192             //   return false;
 193             //else
 194             return false;
 195         }
 196
 197         // If ghost is moving to the same location and using the
 198         // same direction, then it is following another ghost.
 199         for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
 200             // Ignore myself
 201             if (this.m_index != i) {
 202                 if (this.m_map.m_targets[i] == this.m_target &&
 203                         this.m_map.m_ghostdirections[i] == this.m_direction) {
 204                     return true;
 205                 }
 206             }
 207         }
 208
 209         return bFollowing;
 210     }
 211
 212     // This method will take the specified location and direction and determine
 213     // for the given location if the thing moved in that direction, what the
 214     // next possible turning location would be.
 215     private boolean getDestination (int direction, int locX, int locY, int[] point) {
 216        // If the request direction is blocked by a wall, then just return the current location
 217        if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up
 218            ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) ||  // left
 219            ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down
 220            ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right
 221           point[0] = locX;
 222           point[1] = locY;
 223           return false;
 224        }
 225
 226        // Start off by advancing one in direction for specified location
 227        if (direction == 1) {
 228            // up
 229            locY--;
 230        } else if (direction == 2) {
 231            // down
 232            locY++;
 233        } else if (direction == 3) {
 234            // left
 235            locX--;
 236        } else if (direction == 4) {
 237            // right
 238            locX++;
 239        }
 240
 241        // If we violate the grid boundary,
 242        // then return false.
 243        if (locY < 0 ||
 244            locX < 0 ||
 245            locY == this.m_map.m_nrofblocks ||
 246            locX == this.m_map.m_nrofblocks) {
 247            return false;
 248        }
 249
 250        boolean set = false;
 251        // Determine next turning location.
 252        while (!set) {
 253           if (direction == 1 || direction == 2) {
 254               // up or down
 255               if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right
 256                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left
 257                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up
 258                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0))  { // down
 259                   point[0] = locX;
 260                   point[1] = locY;
 261                   set = true;
 262                } else {
 263                    if (direction == 1) {
 264                        // Check for Top Warp
 265                        if (locY == 0) {
 266                            point[0] = locX;
 267                            point[1] = this.m_map.m_nrofblocks - 1;
 268                            set = true;
 269                        } else {
 270                            locY--;
 271                        }
 272                    } else {
 273                        // Check for Bottom Warp
 274                        if (locY == this.m_map.m_nrofblocks - 1) {
 275                            point[0] = locX;
 276                            point[1] = 0;
 277                            set = true;
 278                        } else {
 279                            locY++;
 280                        }
 281                    }
 282                }
 283           } else {
 284               // left or right
 285               if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up
 286                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down
 287                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right
 288                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left
 289                   point[0] = locX;
 290                   point[1] = locY;
 291                   set = true;
 292               } else {
 293                   if (direction == 3) {
 294                       // Check for Left Warp
 295                       if (locX == 0) {
 296                           point[0] = this.m_map.m_nrofblocks - 1;
 297                           point[1] = locY;
 298                           set = true;
 299                       } else {
 300                           locX--;
 301                       }
 302                   } else {
 303                       // Check for Right Warp
 304                       if (locX == this.m_map.m_nrofblocks - 1) {
 305                           point[0] = 0;
 306                           point[1] = locY;
 307                           set = true;
 308                       } else {
 309                           locX++;
 310                       }
 311                   }
 312               }
 313           }
 314        }
 315        return true;
 316     }
 317
 318     public void doMove() {
 319         this.m_locX += this.m_dx;
 320         this.m_locY += this.m_dy;
 321         this.m_dx = 0;
 322         this.m_dy = 0;
 323         //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n");
 324     }
 325 }