9 public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right
14 public Ghost(int x, int y, Map map) {
17 this.m_dx = this.m_dy = 0;
24 // 0:still, 1:up, 2:down, 3:left, 4:right
25 public void tryMove() {
26 //System.printString("step 1\n");
29 // find the shortest possible way to the chosen target
31 //System.printString("step 2\n");
34 private void setNextDirection() {
35 // current position of the ghost
36 int start = this.m_locY * this.m_map.m_nrofblocks + this.m_locX;
38 Vector cuts = new Vector();
45 int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1];
46 for(int i = 0; i < parents.length; i++) {
49 if(!BFS(start, parents, cuts)) {
50 this.m_target = tmptarget;
53 this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection;
55 //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n");
57 // Reversely go over the parents array to find the next node to reach
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("Index: " + index + "\n");
60 //System.printString("Target: " + this.m_target + "\n");
61 int steps = parents[parents.length - 1];
63 // already caught one pacman, stay still
64 this.m_dx = this.m_dy = 0;
65 this.m_map.m_ghostdirections[this.m_index] = this.m_direction = 0;
66 //System.printString("Stay still\n");
69 boolean found = false;
71 int parent = parents[index];
77 // System.printString("parent: " + parent + "\n");
79 //System.printString("Index: " + index + "\n");
81 // set the chase direction
82 int nx = index % this.m_map.m_nrofblocks;
83 int ny = index / this.m_map.m_nrofblocks;
84 this.m_dx = nx - this.m_locX;
85 this.m_dy = ny - this.m_locY;
89 } else if(this.m_dx < 0) {
92 } else if(this.m_dy > 0) {
95 } else if(this.m_dy < 0) {
100 this.m_direction = 0;
103 tmptarget = this.m_target;
106 tmpdirection = this.m_direction;
108 //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n");
112 // check if this choice follows some other ghosts' path
114 this.m_map.m_ghostdirections[this.m_index] = this.m_direction;
117 cuts.addElement(new Integer(index));
118 /*for( int h = 0; h < cuts.size(); h++) {
119 System.printString(cuts.elementAt(h) + ", ");
121 System.printString("\n");*/
127 // This methos do BFS from start node to end node
128 // If there is a path from start to end, return true; otherwise, return false
129 // Array parents records parent for a node in the BFS search,
130 // the last item of parents records the least steps to reach end node from start node
131 // Vector cuts specifies which nodes can not be the first one to access in this BFS
132 private boolean BFS(int start, int[] parents, Vector cuts) {
133 //System.printString("aaa\n");
135 Vector toaccess = new Vector();
136 toaccess.addElement(new Integer(start));
137 while(toaccess.size() > 0) {
138 //System.printString("bbb\n");
139 // pull out the first one to access
140 int access = ((Integer)toaccess.elementAt(0)).intValue();
141 toaccess.removeElementAt(0);
142 for(int i = 0; i < this.m_map.m_pacMenX.length; i++) {
143 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])) {
146 parents[parents.length - 1] = steps;
151 Vector neighbours = this.m_map.getNeighbours(access);
152 for(int i = 0; i < neighbours.size(); i++) {
153 int neighbour = ((Integer)neighbours.elementAt(i)).intValue();
154 if(parents[neighbour] == -1) {
156 boolean ignore = false;
157 if(access == start) {
158 // start node, check if the neighbour node is in cuts
160 while((!ignore) && (j < cuts.size())) {
161 int tmp = ((Integer)cuts.elementAt(j)).intValue();
162 if(tmp == neighbour) {
169 parents[neighbour] = access;
170 toaccess.addElement(new Integer(neighbour));
175 //System.printString("ccc\n");
176 parents[parents.length - 1] = -1;
180 // This method returns true if this ghost is traveling to the same
181 // destination with the same direction as another ghost.
182 private boolean isFollowing () {
183 boolean bFollowing = false;
186 // If the ghost is in the same location as another ghost
187 // and moving in the same direction, then they are on
188 // top of each other and should not follow.
189 for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
191 if (this.m_index != i) {
192 if (this.m_map.m_ghostsX[i] == this.m_locX &&
193 this.m_map.m_ghostsY[i] == this.m_locY &&
194 this.m_map.m_ghostdirections[i] == this.m_direction) {
200 // This will allow ghosts to often
201 // clump together for easier eating
202 dRandom = this.m_map.m_r.nextDouble();
204 //if (m_bInsaneAI && dRandom < .25)
210 // If ghost is moving to the same location and using the
211 // same direction, then it is following another ghost.
212 for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
214 if (this.m_index != i) {
215 if (this.m_map.m_targets[i] == this.m_target &&
216 this.m_map.m_ghostdirections[i] == this.m_direction) {
225 // This method will take the specified location and direction and determine
226 // for the given location if the thing moved in that direction, what the
227 // next possible turning location would be.
228 private boolean getDestination (int direction, int locX, int locY, int[] point) {
229 // If the request direction is blocked by a wall, then just return the current location
230 if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up
231 ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left
232 ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down
233 ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right
239 // Start off by advancing one in direction for specified location
240 if (direction == 1) {
243 } else if (direction == 2) {
246 } else if (direction == 3) {
249 } else if (direction == 4) {
254 // If we violate the grid boundary,
255 // then return false.
258 locY == this.m_map.m_nrofblocks ||
259 locX == this.m_map.m_nrofblocks) {
264 // Determine next turning location.
266 if (direction == 1 || direction == 2) {
268 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right
269 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left
270 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up
271 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down
276 if (direction == 1) {
277 // Check for Top Warp
280 point[1] = this.m_map.m_nrofblocks - 1;
286 // Check for Bottom Warp
287 if (locY == this.m_map.m_nrofblocks - 1) {
298 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up
299 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down
300 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right
301 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left
306 if (direction == 3) {
307 // Check for Left Warp
309 point[0] = this.m_map.m_nrofblocks - 1;
316 // Check for Right Warp
317 if (locX == this.m_map.m_nrofblocks - 1) {
331 public void doMove() {
332 if((this.m_dx == -1) && (this.m_locX == 0)) {
333 // go left and currently this.m_locX is 0
334 this.m_locX = this.m_map.m_nrofblocks - 1;
335 } else if((this.m_dx == 1) && (this.m_locX == this.m_map.m_nrofblocks - 1)) {
338 this.m_locX += this.m_dx;
341 if((this.m_dy == -1) && (this.m_locY == 0)) {
342 // go up and currently this.m_locY is 0
343 this.m_locY = this.m_map.m_nrofblocks - 1;
344 } else if((this.m_dy == 1) && (this.m_locY == this.m_map.m_nrofblocks - 1)) {
347 this.m_locY += this.m_dy;
351 //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n");