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

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