Robust/src/Benchmarks/MMG/Nor/Pacman.java

   1 public class Pacman {
   2     flag move;
   3     flag update;
   4
   5     public int m_locX;
   6     public int m_locY;
   7     public boolean m_death;
   8     public int m_index;
   9     public int m_direction;  // 0:still, 1:up, 2:down, 3:left, 4:right
  10     int m_dx;
  11     int m_dy;
  12     public int m_tx;
  13     public int m_ty;
  14     Map m_map;
  15
  16     public Pacman(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_death = false;
  21         this.m_index = -1;
  22         this.m_tx = this.m_ty = -1;
  23         this.m_direction = 0;
  24         this.m_map = map;
  25     }
  26
  27     public void setTarget(int x, int y) {
  28         this.m_tx = x;
  29         this.m_ty = y;
  30     }
  31
  32     public void tryMove() {
  33         // decide dx & dy
  34
  35         // find the shortest possible way to the chosen target
  36         setNextDirection();
  37     }
  38
  39     private void setNextDirection() {
  40         // current position of the ghost
  41         int start = this.m_locY * this.m_map.m_nrofblocks + this.m_locX;
  42
  43         // get target's position
  44         int targetx = this.m_tx;
  45         int targety = this.m_ty;
  46         int[] nextLocation = new int[2];
  47         nextLocation[0] = nextLocation[1] = -1;
  48
  49         // target's position
  50         int end = targety * this.m_map.m_nrofblocks + targetx;
  51
  52         // breadth-first traverse the graph view of the maze
  53         // check the shortest path for the start node to the end node
  54         boolean set = false;
  55         Vector cuts = new Vector();
  56         int tmpdx = 0;
  57         int tmpdy = 0;
  58         int tmpdirection = 0;
  59         boolean first = true;
  60         while(!set) {
  61             int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1];
  62             for(int i = 0; i < parents.length; i++) {
  63                 parents[i] = -1;
  64             }
  65             if(!BFS(start, end, parents, cuts)) {
  66                 this.m_dx = tmpdx;
  67                 this.m_dy = tmpdy;
  68                 this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection;
  69                 set = true;
  70                 //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n");
  71             } else {
  72                 // Reversely go over the parents array to find the next node to reach
  73                 boolean found = false;
  74                 int index = end;
  75                 while(!found) {
  76                     int parent = parents[index];
  77                     if(parent == start) {
  78                         found = true;
  79                     } else {
  80                         index = parent;
  81                     }
  82                 }
  83
  84                 // set the chase direction
  85                 int nx = index % this.m_map.m_nrofblocks;
  86                 int ny = index / this.m_map.m_nrofblocks;
  87                 this.m_dx = nx - this.m_locX;
  88                 this.m_dy = ny - this.m_locY;
  89                 if(this.m_dx > 0) {
  90                     // right
  91                     this.m_direction = 4;
  92                 } else if(this.m_dx < 0) {
  93                     // left
  94                     this.m_direction = 3;
  95                 } else if(this.m_dy > 0) {
  96                     // down
  97                     this.m_direction = 2;
  98                 } else if(this.m_dy < 0) {
  99                     // up
 100                     this.m_direction = 1;
 101                 } else {
 102                     // still
 103                     this.m_direction = 0;
 104                 }
 105                 if(first) {
 106                     tmpdx = this.m_dx;
 107                     tmpdy = this.m_dy;
 108                     tmpdirection = this.m_direction;
 109                     first = false;
 110                     //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n");
 111                 }
 112
 113                 // check if this choice follows some other ghosts' path
 114                 if(canFlee()) {
 115                     this.m_map.m_directions[this.m_index] = this.m_direction;
 116                     set = true;
 117                 } else {
 118                     cuts.addElement(new Integer(index));
 119                     /*for( int h = 0; h < cuts.size(); h++) {
 120                         System.printString(cuts.elementAt(h) + ", ");
 121                     }
 122                     System.printString("\n");*/
 123                 }
 124             }
 125         }
 126     }
 127
 128     // This methos do BFS from start node to end node
 129     // If there is a path from start to end, return true; otherwise, return false
 130     // Array parents records parent for a node in the BFS search,
 131     // the last item of parents records the least steps to reach end node from start node
 132     // Vector cuts specifies which nodes can not be the first one to access in this BFS
 133     private boolean BFS(int start, int end, int[] parents, Vector cuts) {
 134         int steps = 0;
 135         Vector toaccess = new Vector();
 136         toaccess.addElement(new Integer(start));
 137         while(toaccess.size() > 0) {
 138             // pull out the first one to access
 139             int access = ((Integer)toaccess.elementAt(0)).intValue();
 140             toaccess.removeElementAt(0);
 141             if(access == end) {
 142                 // hit the end node
 143                 parents[parents.length - 1] = steps;
 144                 return true;
 145             }
 146             steps++;
 147             Vector neighbours = this.m_map.getNeighbours(access);
 148             for(int i = 0; i < neighbours.size(); i++) {
 149                 int neighbour = ((Integer)neighbours.elementAt(i)).intValue();
 150                 if(parents[neighbour] == -1) {
 151                     // not accessed
 152                     boolean ignore = false;
 153                     if(access == start) {
 154                         // start node, check if the neighbour node is in cuts
 155                         int j = 0;
 156                         while((!ignore) && (j < cuts.size())) {
 157                             int tmp = ((Integer)cuts.elementAt(j)).intValue();
 158                             if(tmp == neighbour) {
 159                                 ignore = true;
 160                             }
 161                             j++;
 162                         }
 163                     }
 164                     if(!ignore) {
 165                         parents[neighbour] = access;
 166                         toaccess.addElement(new Integer(neighbour));
 167                     }
 168                 }
 169             }
 170         }
 171         parents[parents.length - 1] = -1;
 172         return false;
 173     }
 174
 175     // This method returns true if this pacmen can flee in this direction.
 176     private boolean canFlee () {
 177         int steps = 0;
 178         int locX = this.m_locX;
 179         int locY = this.m_locY;
 180         int[] point = new int[2];
 181         point[0] = point[1] = -1;
 182
 183         // Start off by advancing one in direction for specified location
 184         if (this.m_direction == 1) {
 185             // up
 186             locY--;
 187         } else if (this.m_direction == 2) {
 188             // down
 189             locY++;
 190         } else if (this.m_direction == 3) {
 191             // left
 192             locX--;
 193         } else if (this.m_direction == 4) {
 194             // right
 195             locX++;
 196         }
 197         steps++;
 198
 199         boolean set = false;
 200         // Determine next turning location.
 201         while (!set) {
 202             if (this.m_direction == 1 || this.m_direction == 2) {
 203                 // up or down
 204                 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right
 205                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left
 206                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up
 207                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0))  { // down
 208                     point[0] = locX;
 209                     point[1] = locY;
 210                     set = true;
 211                 } else {
 212                     if (this.m_direction == 1) {
 213                         // Check for Top Warp
 214                         if (locY == 0) {
 215                             point[0] = locX;
 216                             point[1] = this.m_map.m_nrofblocks - 1;
 217                             set = true;
 218                         } else {
 219                             locY--;
 220                             steps++;
 221                         }
 222                     } else {
 223                         // Check for Bottom Warp
 224                         if (locY == this.m_map.m_nrofblocks - 1) {
 225                             point[0] = locX;
 226                             point[1] = 0;
 227                             set = true;
 228                         } else {
 229                             locY++;
 230                             steps++;
 231                         }
 232                     }
 233                 }
 234             } else {
 235                 // left or right
 236                 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up
 237                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down
 238                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right
 239                         ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left
 240                     point[0] = locX;
 241                     point[1] = locY;
 242                     set = true;
 243                 } else {
 244                     if (this.m_direction == 3) {
 245                         // Check for Left Warp
 246                         if (locX == 0) {
 247                             point[0] = this.m_map.m_nrofblocks - 1;
 248                             point[1] = locY;
 249                             set = true;
 250                         } else {
 251                             locX--;
 252                             steps++;
 253                         }
 254                     } else {
 255                         // Check for Right Warp
 256                         if (locX == this.m_map.m_nrofblocks - 1) {
 257                             point[0] = 0;
 258                             point[1] = locY;
 259                             set = true;
 260                         } else {
 261                             locX++;
 262                             steps++;
 263                         }
 264                     }
 265                 }
 266             }
 267         }
 268
 269         // check the least steps for the ghosts to reach point location
 270         int chasesteps = -1;
 271         int end = point[1] * this.m_map.m_nrofblocks + point[0];
 272         for(int i = 0; i < this.m_map.m_ghostsX.length; i++) {
 273             int start = this.m_map.m_ghostsY[i] * this.m_map.m_nrofblocks + this.m_map.m_ghostsX[i];
 274             int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1];
 275             for(int j = 0; j < parents.length; j++) {
 276                 parents[j] = -1;
 277             }
 278             if(BFS(start, end, parents, new Vector())) {
 279                 if((chasesteps == -1) ||
 280                         (chasesteps > parents[parents.length - 1])) {
 281                     chasesteps = parents[parents.length - 1];
 282                 }
 283             }
 284         }
 285
 286         return ((chasesteps == -1) || (steps < chasesteps));
 287     }
 288
 289     // This method will take the specified location and direction and determine
 290     // for the given location if the thing moved in that direction, what the
 291     // next possible turning location would be.
 292     private boolean getDestination (int direction, int locX, int locY, int[] point) {
 293        // If the request direction is blocked by a wall, then just return the current location
 294        if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up
 295            ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) ||  // left
 296            ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down
 297            ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right
 298           point[0] = locX;
 299           point[1] = locY;
 300           return false;
 301        }
 302
 303        // Start off by advancing one in direction for specified location
 304        if (direction == 1) {
 305            // up
 306            locY--;
 307        } else if (direction == 2) {
 308            // down
 309            locY++;
 310        } else if (direction == 3) {
 311            // left
 312            locX--;
 313        } else if (direction == 4) {
 314            // right
 315            locX++;
 316        }
 317
 318        // If we violate the grid boundary,
 319        // then return false.
 320        if (locY < 0 ||
 321            locX < 0 ||
 322            locY == this.m_map.m_nrofblocks ||
 323            locX == this.m_map.m_nrofblocks) {
 324            return false;
 325        }
 326
 327        boolean set = false;
 328        // Determine next turning location.
 329        while (!set) {
 330           if (direction == 1 || direction == 2) {
 331               // up or down
 332               if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right
 333                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left
 334                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up
 335                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0))  { // down
 336                   point[0] = locX;
 337                   point[1] = locY;
 338                   set = true;
 339                } else {
 340                    if (direction == 1) {
 341                        // Check for Top Warp
 342                        if (locY == 0) {
 343                            point[0] = locX;
 344                            point[1] = this.m_map.m_nrofblocks - 1;
 345                            set = true;
 346                        } else {
 347                            locY--;
 348                        }
 349                    } else {
 350                        // Check for Bottom Warp
 351                        if (locY == this.m_map.m_nrofblocks - 1) {
 352                            point[0] = locX;
 353                            point[1] = 0;
 354                            set = true;
 355                        } else {
 356                            locY++;
 357                        }
 358                    }
 359                }
 360           } else {
 361               // left or right
 362               if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up
 363                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down
 364                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right
 365                       ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left
 366                   point[0] = locX;
 367                   point[1] = locY;
 368                   set = true;
 369               } else {
 370                   if (direction == 3) {
 371                       // Check for Left Warp
 372                       if (locX == 0) {
 373                           point[0] = this.m_map.m_nrofblocks - 1;
 374                           point[1] = locY;
 375                           set = true;
 376                       } else {
 377                           locX--;
 378                       }
 379                   } else {
 380                       // Check for Right Warp
 381                       if (locX == this.m_map.m_nrofblocks - 1) {
 382                           point[0] = 0;
 383                           point[1] = locY;
 384                           set = true;
 385                       } else {
 386                           locX++;
 387                       }
 388                   }
 389               }
 390           }
 391        }
 392        return true;
 393     }
 394
 395     public void doMove() {
 396         this.m_locX += this.m_dx;
 397         this.m_locY += this.m_dy;
 398         this.m_dx = 0;
 399         this.m_dy = 0;
 400         //System.printString("Pacmen " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n");
 401     }
 402 }