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
33 private void setNextDirection() {
34 // current position of the ghost
35 Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX];
37 Vector cuts = new Vector();
44 int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1];
45 for(int i = 0; i < parents.length; i++) {
48 if(!BFS(start, parents, cuts)) {
49 this.m_target = tmptarget;
52 this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection;
54 //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n");
56 // Reversely go over the parents array to find the next node to reach
57 boolean found = false;
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("Target: " + this.m_target + "\n");
61 int parent = parents[index];
62 if(parent == start.getIndex()) {
69 // set the chase direction
70 int nx = this.m_map.m_mapNodes[index].getXLoc();
71 int ny = this.m_map.m_mapNodes[index].getYLoc();
72 this.m_dx = nx - this.m_locX;
73 this.m_dy = ny - this.m_locY;
77 } else if(this.m_dx < 0) {
80 } else if(this.m_dy > 0) {
83 } else if(this.m_dy < 0) {
91 tmptarget = this.m_target;
94 tmpdirection = this.m_direction;
96 //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n");
99 // check if this choice follows some other ghosts' path
101 this.m_map.m_ghostdirections[this.m_index] = this.m_direction;
104 cuts.addElement(new Integer(index));
105 /*for( int h = 0; h < cuts.size(); h++) {
106 System.printString(cuts.elementAt(h) + ", ");
108 System.printString("\n");*/
114 // This methos do BFS from start node to end node
115 // If there is a path from start to end, return true; otherwise, return false
116 // Array parents records parent for a node in the BFS search,
117 // the last item of parents records the least steps to reach end node from start node
118 // Vector cuts specifies which nodes can not be the first one to access in this BFS
119 private boolean BFS(Node start, int[] parents, Vector cuts) {
121 Vector toaccess = new Vector();
122 toaccess.addElement(start);
123 while(toaccess.size() > 0) {
124 //System.printString("bbb\n");
125 // pull out the first one to access
126 Node access = (Node)toaccess.elementAt(0);
127 toaccess.removeElementAt(0);
128 for(int i = 0; i < this.m_map.m_pacMenX.length; i++) {
129 if((access.getXLoc() == this.m_map.m_pacMenX[i]) && (access.getYLoc() == this.m_map.m_pacMenY[i])) {
132 parents[parents.length - 1] = steps;
137 Vector neighbours = access.getNeighbours();
138 for(int i = 0; i < neighbours.size(); i++) {
139 Node neighbour = (Node)neighbours.elementAt(i);
140 if(parents[neighbour.getIndex()] == -1) {
142 boolean ignore = false;
143 if(access.getIndex() == start.getIndex()) {
144 // start node, check if the neighbour node is in cuts
146 while((!ignore) && (j < cuts.size())) {
147 int tmp = ((Integer)cuts.elementAt(j)).intValue();
148 if(tmp == neighbour.getIndex()) {
155 parents[neighbour.getIndex()] = access.getIndex();
156 toaccess.addElement(neighbour);
161 parents[parents.length - 1] = -1;
165 // This method returns true if this ghost is traveling to the same
166 // destination with the same direction as another ghost.
167 private boolean isFollowing () {
168 boolean bFollowing = false;
171 // If the ghost is in the same location as another ghost
172 // and moving in the same direction, then they are on
173 // top of each other and should not follow.
174 for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
176 if (this.m_index != i) {
177 if (this.m_map.m_ghostsX[i] == this.m_locX &&
178 this.m_map.m_ghostsY[i] == this.m_locY &&
179 this.m_map.m_ghostdirections[i] == this.m_direction) {
185 // This will allow ghosts to often
186 // clump together for easier eating
187 dRandom = this.m_map.m_r.nextDouble();
189 //if (m_bInsaneAI && dRandom < .25)
195 // If ghost is moving to the same location and using the
196 // same direction, then it is following another ghost.
197 for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {
199 if (this.m_index != i) {
200 if (this.m_map.m_targets[i] == this.m_target &&
201 this.m_map.m_ghostdirections[i] == this.m_direction) {
210 // This method will take the specified location and direction and determine
211 // for the given location if the thing moved in that direction, what the
212 // next possible turning location would be.
213 private boolean getDestination (int direction, int locX, int locY, int[] point) {
214 // If the request direction is blocked by a wall, then just return the current location
215 if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up
216 ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left
217 ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down
218 ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right
224 // Start off by advancing one in direction for specified location
225 if (direction == 1) {
228 } else if (direction == 2) {
231 } else if (direction == 3) {
234 } else if (direction == 4) {
239 // If we violate the grid boundary,
240 // then return false.
243 locY == this.m_map.m_nrofblocks ||
244 locX == this.m_map.m_nrofblocks) {
249 // Determine next turning location.
251 if (direction == 1 || direction == 2) {
253 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right
254 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left
255 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up
256 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down
261 if (direction == 1) {
262 // Check for Top Warp
265 point[1] = this.m_map.m_nrofblocks - 1;
271 // Check for Bottom Warp
272 if (locY == this.m_map.m_nrofblocks - 1) {
283 if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up
284 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down
285 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right
286 ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left
291 if (direction == 3) {
292 // Check for Left Warp
294 point[0] = this.m_map.m_nrofblocks - 1;
301 // Check for Right Warp
302 if (locX == this.m_map.m_nrofblocks - 1) {
316 public void doMove() {
317 this.m_locX += this.m_dx;
318 this.m_locY += this.m_dy;
321 //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n");