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