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