public class Ghost {\r
- public int x;\r
- public int y;\r
- public int index;\r
- public int target;\r
- public int direction; // 0:still, 1:up, 2:down, 3:left, 4:right\r
- int dx;\r
- int dy;\r
- int destinationX;\r
- int destinationY;\r
- Map map;\r
\r
- public Ghost(int x, int y, Map map) {\r
- this.x = x;\r
- this.y = y;\r
- this.dx = this.dy = 0;\r
- this.index = -1;\r
- this.target = -1;\r
- this.direction = 0;\r
- this.destinationX = -1;\r
- this.destinationY = -1;\r
- this.map = map;\r
- }\r
+ public int m_locX;\r
+ public int m_locY;\r
+ public int m_index;\r
+ public int m_target;\r
+ public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right\r
+ int m_dx;\r
+ int m_dy;\r
+ Map m_map;\r
\r
- public void setTarget(int pacman) {\r
- this.target = pacman;\r
+ public Ghost(int x, int y, Map map) {\r
+ this.m_locX = x;\r
+ this.m_locY = y;\r
+ this.m_dx = this.m_dy = 0;\r
+ this.m_index = -1;\r
+ this.m_target = -1;\r
+ this.m_direction = 0;\r
+ this.m_map = map;\r
}\r
\r
// 0:still, 1:up, 2:down, 3:left, 4:right\r
public void tryMove() {\r
- //System.printString("step 1\n");\r
- //System.printString("target: " + this.target + "\n");\r
- \r
- // Don't let the ghost go back the way it came.\r
- int prevDirection = 0;\r
+ // System.printString("step 1\n");\r
+ int i = 0;\r
\r
- // If there is a destination, then check if the destination has been reached.\r
- if (destinationX >= 0 && destinationY >= 0) {\r
- // Check if the destination has been reached, if so, then\r
- // get new destination.\r
- if (destinationX == x && destinationY == y) {\r
- destinationX = -1;\r
- destinationY = -1;\r
- prevDirection = direction;\r
- } else {\r
- // Otherwise, we haven't reached the destionation so\r
- // continue in same direction.\r
- return;\r
+ // check the nearest pacman and set it as current target\r
+ this.m_target = -1;\r
+ int deltaX = this.m_map.m_nrofblocks;\r
+ int deltaY = this.m_map.m_nrofblocks;\r
+ int distance = deltaX * deltaX + deltaY * deltaY;\r
+ for(i = 0; i < this.m_map.m_nrofpacs; i++) {\r
+ if(this.m_map.m_pacMenX[i] != -1) {\r
+ int dx = this.m_locX - this.m_map.m_pacMenX[i];\r
+ int dy = this.m_locY - this.m_map.m_pacMenY[i];\r
+ int dd = dx*dx+dy*dy;\r
+ if(distance > dd) {\r
+ this.m_target = i;\r
+ distance = dd;\r
+ deltaX = dx;\r
+ deltaY = dy;\r
+ }\r
}\r
}\r
- setNextDirection (prevDirection);\r
+ // System.printString("target: " + this.m_target + "\n");\r
+ \r
+ if(this.m_target == -1) {\r
+ // no more pacmen to chase, stay still\r
+ this.m_dx = 0;\r
+ this.m_dy = 0;\r
+ this.m_direction = this.m_map.m_ghostdirections[this.m_index] = 0;\r
+ return;\r
+ }\r
+ \r
+ // find the shortest way to the chosen target\r
+ setNextDirection();\r
}\r
\r
- private void setNextDirection(int prevDirection) {\r
+ private void setNextDirection() {\r
+ // current position of the ghost\r
+ Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX];\r
+ \r
// get target's position\r
- int targetx = this.map.pacMenX[this.target];\r
- //System.printString("aaa\n");\r
- int targety = this.map.pacMenY[this.target];\r
+ int targetx = this.m_map.m_pacMenX[this.m_target];\r
+ int targety = this.m_map.m_pacMenY[this.m_target];\r
int[] nextLocation = new int[2];\r
nextLocation[0] = nextLocation[1] = -1;\r
- \r
- //System.printString("bbb\n");\r
- if(targetx == -1) {\r
- //System.printString("a\n");\r
- // already kicked off, choose another target\r
- int i = 0;\r
- boolean found = false;\r
- while((!found) && (i < map.pacMenX.length)) {\r
- if(this.map.pacMenX[i] != -1) {\r
- this.target = i;\r
- targetx = this.map.pacMenX[i];\r
- targety = this.map.pacMenY[i];\r
- this.map.targets[i] = this.target;\r
- found = true;\r
- }\r
- i++;\r
- }\r
- //System.printString("b\n");\r
- if(i == this.map.pacMenX.length) {\r
- //System.printString("c\n");\r
- // no more pacmen to chase\r
- this.dx = 0;\r
- this.dy = 0;\r
- this.direction = 0;\r
- return;\r
- }\r
- //System.printString("d\n");\r
- }\r
- getDestination (this.map.pacmen[this.target].direction, targetx, targety, nextLocation);\r
+ // check the target pacman's possible destination\r
+ getDestination (this.m_map.m_directions[this.m_target], targetx, targety, nextLocation);\r
targetx = nextLocation[0];\r
targety = nextLocation[1];\r
+ // target's position\r
+ Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx];\r
+ // reset the target as index of the end node\r
+ this.m_target = this.m_map.m_targets[this.m_index] = end.getIndex();\r
\r
- //System.printString("step 2\n");\r
- // check the distance\r
- int deltax = this.x - targetx; // <0: move right; >0: move left\r
- int deltay = this.y - targety; // <0: move down; >0: move up\r
- // decide the priority of four moving directions\r
- int[] bestDirection = new int[4];\r
- //System.printString("dx: " + deltax + "; dy: " + deltay + "\n");\r
- if((Math.abs(deltax) > Math.abs(deltay)) && (deltay != 0)) {\r
- // go first along y\r
- if(deltay > 0) {\r
- bestDirection[0] = 1;\r
- bestDirection[3] = 2;\r
- if(deltax > 0) {\r
- bestDirection[1] = 3;\r
- bestDirection[2] = 4;\r
- } else {\r
- bestDirection[1] = 4;\r
- bestDirection[2] = 3;\r
- }\r
+ // breadth-first traverse the graph view of the maze\r
+ // check the shortest path for the start node to the end node\r
+ boolean set = false;\r
+ Vector cuts = new Vector();\r
+ int tmpdx = 0;\r
+ int tmpdy = 0;\r
+ int tmpdirection = 0;\r
+ boolean first = true;\r
+ while(!set) {\r
+ int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks];\r
+ for(int i = 0; i < parents.length; i++) {\r
+ parents[i] = -1;\r
+ }\r
+ if(!BFS(start, end, parents, cuts)) {\r
+ this.m_dx = tmpdx;\r
+ this.m_dy = tmpdy;\r
+ this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection;\r
+ set = true;\r
+ //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n");\r
} else {\r
- bestDirection[0] = 2;\r
- bestDirection[3] = 1;\r
- if(deltax > 0) {\r
- bestDirection[1] = 3;\r
- bestDirection[2] = 4;\r
- } else {\r
- bestDirection[1] = 4;\r
- bestDirection[2] = 3;\r
+ // Reversely go over the parents array to find the next node to reach\r
+ boolean found = false;\r
+ int index = end.getIndex();\r
+ while(!found) {\r
+ int parent = parents[index];\r
+ if(parent == start.getIndex()) {\r
+ found = true;\r
+ } else {\r
+ index = parent;\r
+ }\r
}\r
- }\r
- } else {\r
- if(deltax > 0) {\r
- bestDirection[0] = 3;\r
- bestDirection[3] = 4;\r
- if(deltay > 0) {\r
- bestDirection[1] = 1;\r
- bestDirection[2] = 2;\r
+\r
+ // set the chase direction\r
+ int nx = this.m_map.m_mapNodes[index].getXLoc();\r
+ int ny = this.m_map.m_mapNodes[index].getYLoc();\r
+ this.m_dx = nx - this.m_locX;\r
+ this.m_dy = ny - this.m_locY;\r
+ if(this.m_dx > 0) {\r
+ // right\r
+ this.m_direction = 4;\r
+ } else if(this.m_dx < 0) {\r
+ // left\r
+ this.m_direction = 3;\r
+ } else if(this.m_dy > 0) {\r
+ // down\r
+ this.m_direction = 2;\r
+ } else if(this.m_dy < 0) {\r
+ // up\r
+ this.m_direction = 1;\r
} else {\r
- bestDirection[1] = 2;\r
- bestDirection[2] = 1;\r
+ // still\r
+ this.m_direction = 0;\r
}\r
- } else {\r
- bestDirection[0] = 4;\r
- bestDirection[3] = 3;\r
- if(deltay > 0) {\r
- bestDirection[1] = 1;\r
- bestDirection[2] = 2;\r
+ if(first) {\r
+ tmpdx = this.m_dx;\r
+ tmpdy = this.m_dy;\r
+ tmpdirection = this.m_direction;\r
+ first = false;\r
+ //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n");\r
+ }\r
+\r
+ // check if this choice follows some other ghosts' path\r
+ if(!isFollowing()) {\r
+ this.m_map.m_ghostdirections[this.m_index] = this.m_direction;\r
+ set = true;\r
} else {\r
- bestDirection[1] = 2;\r
- bestDirection[2] = 1;\r
+ cuts.addElement(new Integer(index));\r
+ /*for( int h = 0; h < cuts.size(); h++) {\r
+ System.printString(cuts.elementAt(h) + ", ");\r
+ }\r
+ System.printString("\n");*/\r
}\r
}\r
}\r
- /*for(int i = 0; i < 4; i++) {\r
- System.printString(bestDirection[i] + ",");\r
- }\r
- System.printString("\n");*/\r
- \r
- // There's a 50% chance that the ghost will try the sub-optimal direction first.\r
- // This will keep the ghosts from following each other and to trap Pacman.\r
- if (this.map.r.nextDouble() < .50) { \r
- int temp = bestDirection[0];\r
- bestDirection[0] = bestDirection[1];\r
- bestDirection[1] = temp;\r
- }\r
- \r
- //System.printString("step 3\n");\r
- // try to move one by one\r
- int i = 0;\r
- boolean set = false;\r
- this.dx = 0;\r
- this.dy = 0;\r
- while((!set) && (i < 4)) {\r
- if(bestDirection[i] == 1) {\r
- // try to move up\r
- if((prevDirection != 2) && ((int)(this.map.map[y * this.map.nrofblocks + x] & 2) == 0)) {\r
- //System.printString("a\n");\r
- if (getDestination (1, this.x, this.y, nextLocation)) {\r
- this.dx = 0;\r
- this.dy = -1;\r
- set = true;\r
+ }\r
+ \r
+ // This methos do BFS from start node to end node\r
+ // If there is a path from start to end, return true; otherwise, return false\r
+ // Array parents records parent for a node in the BFS search\r
+ // Vector cuts specifies which nodes can not be the first one to access in this BFS\r
+ private boolean BFS(Node start, Node end, int[] parents, Vector cuts) {\r
+ Vector toaccess = new Vector();\r
+ toaccess.addElement(start);\r
+ while(toaccess.size() > 0) {\r
+ // pull out the first one to access\r
+ Node access = (Node)toaccess.elementAt(0);\r
+ toaccess.removeElementAt(0);\r
+ if(access.getIndex() == end.getIndex()) {\r
+ // hit the end node\r
+ return true;\r
+ }\r
+ Vector neighbours = access.getNeighbours();\r
+ for(int i = 0; i < neighbours.size(); i++) {\r
+ Node neighbour = (Node)neighbours.elementAt(i);\r
+ if(parents[neighbour.getIndex()] == -1) {\r
+ // not accessed\r
+ boolean ignore = false;\r
+ if(access.getIndex() == start.getIndex()) {\r
+ // start node, check if the neighbour node is in cuts\r
+ int j = 0;\r
+ while((!ignore) && (j < cuts.size())) {\r
+ int tmp = ((Integer)cuts.elementAt(j)).intValue();\r
+ if(tmp == neighbour.getIndex()) {\r
+ ignore = true;\r
+ }\r
+ j++;\r
+ }\r
}\r
- }\r
- } else if (bestDirection[i] == 2) {\r
- // try to move down\r
- if((prevDirection != 1) && ((int)(this.map.map[y * this.map.nrofblocks + x] & 8) == 0)) {\r
- //System.printString("b\n");\r
- if (getDestination (2, this.x, this.y, nextLocation)) {\r
- this.dx = 0;\r
- this.dy = 1;\r
- set = true;\r
+ if(!ignore) {\r
+ parents[neighbour.getIndex()] = access.getIndex();\r
+ toaccess.addElement(neighbour);\r
}\r
}\r
- } else if (bestDirection[i] == 3) {\r
- // try to move left\r
- if((prevDirection != 4) && ((int)(this.map.map[y * this.map.nrofblocks + x] & 1) == 0)) {\r
- //System.printString("c\n");\r
- if (getDestination (3, this.x, this.y, nextLocation)) {\r
- this.dx = -1;\r
- this.dy = 0;\r
- set = true;\r
- }\r
+ }\r
+ }\r
+ return false;\r
+ }\r
+ \r
+ // This method returns true if this ghost is traveling to the same\r
+ // destination with the same direction as another ghost.\r
+ private boolean isFollowing () {\r
+ boolean bFollowing = false;\r
+ double dRandom;\r
+\r
+ // If the ghost is in the same location as another ghost\r
+ // and moving in the same direction, then they are on\r
+ // top of each other and should not follow.\r
+ for (int i = 0; i < this.m_map.m_ghostsX.length; i++) {\r
+ // Ignore myself\r
+ if (this.m_index != i) {\r
+ if (this.m_map.m_ghostsX[i] == this.m_locX &&\r
+ this.m_map.m_ghostsY[i] == this.m_locY &&\r
+ this.m_map.m_ghostdirections[i] == this.m_direction) {\r
+ return true;\r
}\r
- } else if (bestDirection[i] == 4) {\r
- // try to move right\r
- if((prevDirection != 3) && ((int)(this.map.map[y * this.map.nrofblocks + x] & 4) == 0)) {\r
- //System.printString("d\n");\r
- if (getDestination (4, this.x, this.y, nextLocation)) {\r
- this.dx = 1;\r
- this.dy = 0;\r
- set = true;\r
- }\r
+ }\r
+ }\r
+\r
+ // This will allow ghosts to often\r
+ // clump together for easier eating\r
+ dRandom = this.m_map.m_r.nextDouble();\r
+ if (dRandom < .90) { \r
+ //if (m_bInsaneAI && dRandom < .25)\r
+ // return false;\r
+ //else\r
+ return false;\r
+ }\r
+\r
+ // If ghost is moving to the same location and using the\r
+ // same direction, then it is following another ghost. \r
+ for (int i = 0; i < this.m_map.m_ghostsX.length; i++) { \r
+ // Ignore myself \r
+ if (this.m_index != i) {\r
+ if (this.m_map.m_targets[i] == this.m_target &&\r
+ this.m_map.m_ghostdirections[i] == this.m_direction) {\r
+ return true;\r
}\r
}\r
- i++;\r
}\r
- //System.printString("step 4\n");\r
+\r
+ return bFollowing;\r
}\r
\r
// This method will take the specified location and direction and determine\r
// for the given location if the thing moved in that direction, what the\r
// next possible turning location would be.\r
- boolean getDestination (int direction, int locX, int locY, int[] point) {\r
+ private boolean getDestination (int direction, int locX, int locY, int[] point) {\r
// If the request direction is blocked by a wall, then just return the current location\r
- if ((direction == 1 && (this.map.map[locX + locY * this.map.nrofblocks] & 2) != 0) || // up\r
- (direction == 3 && (this.map.map[locX + locY * this.map.nrofblocks] & 1) != 0) || // left\r
- (direction == 2 && (this.map.map[locX + locY * this.map.nrofblocks] & 8) != 0) || // down\r
- (direction == 4 && (this.map.map[locX + locY * this.map.nrofblocks] & 4) != 0)) { // right \r
+ if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up\r
+ ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left\r
+ ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down\r
+ ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right \r
point[0] = locX;\r
point[1] = locY;\r
return false;\r
// then return false.\r
if (locY < 0 ||\r
locX < 0 ||\r
- locY == this.map.nrofblocks ||\r
- locX == this.map.nrofblocks) {\r
+ locY == this.m_map.m_nrofblocks ||\r
+ locX == this.m_map.m_nrofblocks) {\r
return false;\r
}\r
\r
boolean set = false;\r
- // Determine next turning location..\r
+ // Determine next turning location.\r
while (!set) {\r
if (direction == 1 || direction == 2) { \r
// up or down\r
- if ((this.map.map[locX + locY * this.map.nrofblocks] & 4) == 0 || // right\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 1) == 0 || // left\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 2) != 0 || // up\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 8) != 0) { // down\r
+ if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down\r
point[0] = locX;\r
point[1] = locY;\r
set = true;\r
// Check for Top Warp\r
if (locY == 0) {\r
point[0] = locX;\r
- point[1] = this.map.nrofblocks - 1;\r
+ point[1] = this.m_map.m_nrofblocks - 1;\r
set = true;\r
} else {\r
locY--;\r
}\r
} else {\r
// Check for Bottom Warp\r
- if (locY == this.map.nrofblocks - 1) {\r
+ if (locY == this.m_map.m_nrofblocks - 1) {\r
point[0] = locX;\r
point[1] = 0;\r
set = true;\r
}\r
} else {\r
// left or right\r
- if ((this.map.map[locX + locY * this.map.nrofblocks] & 2) == 0 || // up\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 8) == 0 || // down\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 4) != 0 || // right\r
- (this.map.map[locX + locY * this.map.nrofblocks] & 1) != 0) { // left \r
+ if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right\r
+ ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left \r
point[0] = locX;\r
point[1] = locY;\r
set = true;\r
if (direction == 3) {\r
// Check for Left Warp\r
if (locX == 0) {\r
- point[0] = this.map.nrofblocks - 1;\r
+ point[0] = this.m_map.m_nrofblocks - 1;\r
point[1] = locY;\r
set = true;\r
} else {\r
}\r
} else {\r
// Check for Right Warp\r
- if (locX == this.map.nrofblocks - 1) {\r
+ if (locX == this.m_map.m_nrofblocks - 1) {\r
point[0] = 0;\r
point[1] = locY;\r
set = true;\r
}\r
\r
public void doMove() {\r
- this.x += this.dx;\r
- this.y += this.dy;\r
- //this.dx = 0;\r
- //this.dy = 0;\r
+ this.m_locX += this.m_dx;\r
+ this.m_locY += this.m_dy;\r
+ this.m_dx = 0;\r
+ this.m_dy = 0;\r
+ //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n");\r
}\r
}
\ No newline at end of file
projects / IRC.git / blobdiff