From 858b36126b2665dcf3341b4031f6257c80c837cb Mon Sep 17 00:00:00 2001 From: jzhou Date: Wed, 3 Sep 2008 03:47:37 +0000 Subject: [PATCH] changes --- Robust/src/Benchmarks/MMG/Java/Ghost.java | 84 +-- Robust/src/Benchmarks/MMG/Java/MMG.java | 4 +- Robust/src/Benchmarks/MMG/Java/Map.java | 2 +- Robust/src/Benchmarks/MMG/Nor/Ghost.java | 76 +- Robust/src/Benchmarks/MMG/Nor/MMG.java | 4 +- Robust/src/Benchmarks/MMG/Nor/Map.java | 2 +- Robust/src/Benchmarks/MMG/Tag/Ghost.java | 683 +++++++++--------- Robust/src/Benchmarks/MMG/Tag/MMG.java | 276 ++++---- Robust/src/Benchmarks/MMG/Tag/Map.java | 358 +++++----- Robust/src/Benchmarks/MMG/Tag/Pacman.java | 802 +++++++++++----------- 10 files changed, 1101 insertions(+), 1190 deletions(-) diff --git a/Robust/src/Benchmarks/MMG/Java/Ghost.java b/Robust/src/Benchmarks/MMG/Java/Ghost.java index 0d057a36..5ab35fd8 100755 --- a/Robust/src/Benchmarks/MMG/Java/Ghost.java +++ b/Robust/src/Benchmarks/MMG/Java/Ghost.java @@ -21,63 +21,19 @@ public class Ghost { // 0:still, 1:up, 2:down, 3:left, 4:right public void tryMove() { - // System.printString("step 1\n"); - int i = 0; - - // check the nearest pacman and set it as current target + //System.printString("step 1\n"); + // reset the target this.m_target = -1; - int deltaX = this.m_map.m_nrofblocks; - int deltaY = this.m_map.m_nrofblocks; - int distance = deltaX * deltaX + deltaY * deltaY; - for(i = 0; i < this.m_map.m_nrofpacs; i++) { - if(this.m_map.m_pacMenX[i] != -1) { - int dx = this.m_locX - this.m_map.m_pacMenX[i]; - int dy = this.m_locY - this.m_map.m_pacMenY[i]; - int dd = dx*dx+dy*dy; - if(distance > dd) { - this.m_target = i; - distance = dd; - deltaX = dx; - deltaY = dy; - } - } - } - // System.printString("target: " + this.m_target + "\n"); - - if(this.m_target == -1) { - // no more pacmen to chase, stay still - this.m_dx = 0; - this.m_dy = 0; - this.m_direction = this.m_map.m_ghostdirections[this.m_index] = 0; - return; - } - - // find the shortest way to the chosen target + // find the shortest possible way to the chosen target setNextDirection(); } private void setNextDirection() { // current position of the ghost Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; - - // get target's position - int targetx = this.m_map.m_pacMenX[this.m_target]; - int targety = this.m_map.m_pacMenY[this.m_target]; - int[] nextLocation = new int[2]; - nextLocation[0] = nextLocation[1] = -1; - // check the target pacman's possible destination - getDestination (this.m_map.m_directions[this.m_target], targetx, targety, nextLocation); - targetx = nextLocation[0]; - targety = nextLocation[1]; - // target's position - Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx]; - // reset the target as index of the end node - this.m_target = this.m_map.m_targets[this.m_index] = end.getIndex(); - - // breadth-first traverse the graph view of the maze - // check the shortest path for the start node to the end node boolean set = false; Vector cuts = new Vector(); + int tmptarget = 0; int tmpdx = 0; int tmpdy = 0; int tmpdirection = 0; @@ -87,7 +43,8 @@ public class Ghost { for(int i = 0; i < parents.length; i++) { parents[i] = -1; } - if(!BFS(start, end, parents, cuts)) { + if(!BFS(start, parents, cuts)) { + this.m_target = tmptarget; this.m_dx = tmpdx; this.m_dy = tmpdy; this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; @@ -96,7 +53,8 @@ public class Ghost { } else { // Reversely go over the parents array to find the next node to reach boolean found = false; - int index = end.getIndex(); + int index = this.m_map.m_pacMenY[this.m_target] * this.m_map.m_nrofblocks + this.m_map.m_pacMenX[this.m_target]; + //System.printString("Target: " + this.m_target + "\n"); while(!found) { int parent = parents[index]; if(parent == start.getIndex()) { @@ -128,6 +86,7 @@ public class Ghost { this.m_direction = 0; } if(first) { + tmptarget = this.m_target; tmpdx = this.m_dx; tmpdy = this.m_dy; tmpdirection = this.m_direction; @@ -152,20 +111,38 @@ public class Ghost { // This methos do BFS from start node to end node // If there is a path from start to end, return true; otherwise, return false - // Array parents records parent for a node in the BFS search + // Array parents records parent for a node in the BFS search, + // the last item of parents records the least steps to reach end node from start node // Vector cuts specifies which nodes can not be the first one to access in this BFS +<<<<<<< Ghost.java + private boolean BFS(Node start, int[] parents, Vector cuts) { + //System.printString("aaa\n"); + int steps = 0; +======= private boolean BFS(Node start, Node end, int[] parents, Vector cuts) { int steps = 0; +>>>>>>> 1.3 Vector toaccess = new Vector(); toaccess.addElement(start); while(toaccess.size() > 0) { + //System.printString("bbb\n"); // pull out the first one to access Node access = (Node)toaccess.elementAt(0); toaccess.removeElementAt(0); +<<<<<<< Ghost.java + for(int i = 0; i < this.m_map.m_pacMenX.length; i++) { + if((access.getXLoc() == this.m_map.m_pacMenX[i]) && (access.getYLoc() == this.m_map.m_pacMenY[i])) { + // hit one pacman + this.m_target = i; + parents[parents.length - 1] = steps; + return true; + } +======= if(access.getIndex() == end.getIndex()) { // hit the end node parents[parents.length - 1] = steps; return true; +>>>>>>> 1.3 } steps++; Vector neighbours = access.getNeighbours(); @@ -192,7 +169,12 @@ public class Ghost { } } } +<<<<<<< Ghost.java + //System.printString("ccc\n"); + parents[parents.length - 1] = -1; +======= parents[parents.length - 1] = -1; +>>>>>>> 1.3 return false; } diff --git a/Robust/src/Benchmarks/MMG/Java/MMG.java b/Robust/src/Benchmarks/MMG/Java/MMG.java index d4c89bb6..8ca79073 100755 --- a/Robust/src/Benchmarks/MMG/Java/MMG.java +++ b/Robust/src/Benchmarks/MMG/Java/MMG.java @@ -67,7 +67,7 @@ public class MMG { boolean death = map.check(map.m_pacmen[i]); /*if(death) { System.printString("Pacman " + map.m_pacmen[i].m_index + " caught!\n"); - }*/ + } */ } } map.m_nrofpacs -= map.m_deathcount; @@ -80,4 +80,4 @@ public class MMG { System.printString("Finish\n"); } -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/MMG/Java/Map.java b/Robust/src/Benchmarks/MMG/Java/Map.java index f87324d4..5cf20975 100755 --- a/Robust/src/Benchmarks/MMG/Java/Map.java +++ b/Robust/src/Benchmarks/MMG/Java/Map.java @@ -176,4 +176,4 @@ public class Map { public boolean isfinish() { return this.m_nrofpacs == 0; } -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/MMG/Nor/Ghost.java b/Robust/src/Benchmarks/MMG/Nor/Ghost.java index 228e6d8a..91f32614 100755 --- a/Robust/src/Benchmarks/MMG/Nor/Ghost.java +++ b/Robust/src/Benchmarks/MMG/Nor/Ghost.java @@ -24,62 +24,18 @@ public class Ghost { // 0:still, 1:up, 2:down, 3:left, 4:right public void tryMove() { //System.printString("step 1\n"); - int i = 0; - - // check the nearest pacman and set it as current target + // reset the target this.m_target = -1; - int deltaX = this.m_map.m_nrofblocks; - int deltaY = this.m_map.m_nrofblocks; - int distance = deltaX * deltaX + deltaY * deltaY; - for(i = 0; i < this.m_map.m_nrofpacs; i++) { - if(this.m_map.m_pacMenX[i] != -1) { - int dx = this.m_locX - this.m_map.m_pacMenX[i]; - int dy = this.m_locY - this.m_map.m_pacMenY[i]; - int dd = dx*dx+dy*dy; - if(distance > dd) { - this.m_target = i; - distance = dd; - deltaX = dx; - deltaY = dy; - } - } - } - // System.printString("target: " + this.m_target + "\n"); - - if(this.m_target == -1) { - // no more pacmen to chase, stay still - this.m_dx = 0; - this.m_dy = 0; - this.m_direction = this.m_map.m_ghostdirections[this.m_index] = 0; - return; - } - - // find the shortest way to the chosen target + // find the shortest possible way to the chosen target setNextDirection(); } private void setNextDirection() { // current position of the ghost Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; - - // get target's position - int targetx = this.m_map.m_pacMenX[this.m_target]; - int targety = this.m_map.m_pacMenY[this.m_target]; - int[] nextLocation = new int[2]; - nextLocation[0] = nextLocation[1] = -1; - // check the target pacman's possible destination - getDestination (this.m_map.m_directions[this.m_target], targetx, targety, nextLocation); - targetx = nextLocation[0]; - targety = nextLocation[1]; - // target's position - Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx]; - // reset the target as index of the end node - this.m_target = this.m_map.m_targets[this.m_index] = end.getIndex(); - - // breadth-first traverse the graph view of the maze - // check the shortest path for the start node to the end node boolean set = false; Vector cuts = new Vector(); + int tmptarget = 0; int tmpdx = 0; int tmpdy = 0; int tmpdirection = 0; @@ -89,7 +45,8 @@ public class Ghost { for(int i = 0; i < parents.length; i++) { parents[i] = -1; } - if(!BFS(start, end, parents, cuts)) { + if(!BFS(start, parents, cuts)) { + this.m_target = tmptarget; this.m_dx = tmpdx; this.m_dy = tmpdy; this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; @@ -98,7 +55,8 @@ public class Ghost { } else { // Reversely go over the parents array to find the next node to reach boolean found = false; - int index = end.getIndex(); + int index = this.m_map.m_pacMenY[this.m_target] * this.m_map.m_nrofblocks + this.m_map.m_pacMenX[this.m_target]; + //System.printString("Target: " + this.m_target + "\n"); while(!found) { int parent = parents[index]; if(parent == start.getIndex()) { @@ -130,6 +88,7 @@ public class Ghost { this.m_direction = 0; } if(first) { + tmptarget = this.m_target; tmpdx = this.m_dx; tmpdy = this.m_dy; tmpdirection = this.m_direction; @@ -154,20 +113,25 @@ public class Ghost { // This methos do BFS from start node to end node // If there is a path from start to end, return true; otherwise, return false - // Array parents records parent for a node in the BFS search + // Array parents records parent for a node in the BFS search, + // the last item of parents records the least steps to reach end node from start node // Vector cuts specifies which nodes can not be the first one to access in this BFS - private boolean BFS(Node start, Node end, int[] parents, Vector cuts) { + private boolean BFS(Node start, int[] parents, Vector cuts) { int steps = 0; Vector toaccess = new Vector(); toaccess.addElement(start); while(toaccess.size() > 0) { + //System.printString("bbb\n"); // pull out the first one to access Node access = (Node)toaccess.elementAt(0); toaccess.removeElementAt(0); - if(access.getIndex() == end.getIndex()) { - // hit the end node - parents[parents.length - 1] = steps; - return true; + for(int i = 0; i < this.m_map.m_pacMenX.length; i++) { + if((access.getXLoc() == this.m_map.m_pacMenX[i]) && (access.getYLoc() == this.m_map.m_pacMenY[i])) { + // hit one pacman + this.m_target = i; + parents[parents.length - 1] = steps; + return true; + } } steps++; Vector neighbours = access.getNeighbours(); @@ -356,4 +320,4 @@ public class Ghost { this.m_dy = 0; //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n"); } -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/MMG/Nor/MMG.java b/Robust/src/Benchmarks/MMG/Nor/MMG.java index 16cb4965..40392422 100755 --- a/Robust/src/Benchmarks/MMG/Nor/MMG.java +++ b/Robust/src/Benchmarks/MMG/Nor/MMG.java @@ -134,6 +134,6 @@ task next(Map map{next}) { } task finish(Map map{finish}) { - System.printString("Task Finish\n"); + System.printString("Task Finish\n"); taskexit(map{!finish}); -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/MMG/Nor/Map.java b/Robust/src/Benchmarks/MMG/Nor/Map.java index a75ec229..650f0a62 100755 --- a/Robust/src/Benchmarks/MMG/Nor/Map.java +++ b/Robust/src/Benchmarks/MMG/Nor/Map.java @@ -177,4 +177,4 @@ public class Map { public boolean isfinish() { return this.m_nrofpacs == 0; } -} \ No newline at end of file +} diff --git a/Robust/src/Benchmarks/MMG/Tag/Ghost.java b/Robust/src/Benchmarks/MMG/Tag/Ghost.java index b8d27981..d7126aed 100755 --- a/Robust/src/Benchmarks/MMG/Tag/Ghost.java +++ b/Robust/src/Benchmarks/MMG/Tag/Ghost.java @@ -1,360 +1,325 @@ -public class Ghost { - flag move; - flag update; - - public int m_locX; - public int m_locY; - public int m_index; - public int m_target; - public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right - int m_dx; - int m_dy; - Map m_map; - - public Ghost(int x, int y, Map map) { - this.m_locX = x; - this.m_locY = y; - this.m_dx = this.m_dy = 0; - this.m_index = -1; - this.m_target = -1; - this.m_direction = 0; - this.m_map = map; - } - - // 0:still, 1:up, 2:down, 3:left, 4:right - public void tryMove() { - //System.printString("step 1\n"); - int i = 0; - - // check the nearest pacman and set it as current target - this.m_target = -1; - int deltaX = this.m_map.m_nrofblocks; - int deltaY = this.m_map.m_nrofblocks; - int distance = deltaX * deltaX + deltaY * deltaY; - for(i = 0; i < this.m_map.m_nrofpacs; i++) { - if(this.m_map.m_pacMenX[i] != -1) { - int dx = this.m_locX - this.m_map.m_pacMenX[i]; - int dy = this.m_locY - this.m_map.m_pacMenY[i]; - int dd = dx*dx+dy*dy; - if(distance > dd) { - this.m_target = i; - distance = dd; - deltaX = dx; - deltaY = dy; - } - } - } - // System.printString("target: " + this.m_target + "\n"); - - if(this.m_target == -1) { - // no more pacmen to chase, stay still - this.m_dx = 0; - this.m_dy = 0; - this.m_direction = this.m_map.m_ghostdirections[this.m_index] = 0; - return; - } - - // find the shortest possible way to the chosen target - setNextDirection(); - } - - private void setNextDirection() { - // current position of the ghost - Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; - - // get target's position - int targetx = this.m_map.m_pacMenX[this.m_target]; - int targety = this.m_map.m_pacMenY[this.m_target]; - int[] nextLocation = new int[2]; - nextLocation[0] = nextLocation[1] = -1; - // check the target pacman's possible destination - getDestination (this.m_map.m_directions[this.m_target], targetx, targety, nextLocation); - targetx = nextLocation[0]; - targety = nextLocation[1]; - // target's position - Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx]; - // reset the target as index of the end node - this.m_target = this.m_map.m_targets[this.m_index] = end.getIndex(); - - // breadth-first traverse the graph view of the maze - // check the shortest path for the start node to the end node - boolean set = false; - Vector cuts = new Vector(); - int tmpdx = 0; - int tmpdy = 0; - int tmpdirection = 0; - boolean first = true; - while(!set) { - int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; - for(int i = 0; i < parents.length; i++) { - parents[i] = -1; - } - if(!BFS(start, end, parents, cuts)) { - this.m_dx = tmpdx; - this.m_dy = tmpdy; - this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; - set = true; - //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n"); - } else { - // Reversely go over the parents array to find the next node to reach - boolean found = false; - int index = end.getIndex(); - while(!found) { - int parent = parents[index]; - if(parent == start.getIndex()) { - found = true; - } else { - index = parent; - } - } - - // set the chase direction - int nx = this.m_map.m_mapNodes[index].getXLoc(); - int ny = this.m_map.m_mapNodes[index].getYLoc(); - this.m_dx = nx - this.m_locX; - this.m_dy = ny - this.m_locY; - if(this.m_dx > 0) { - // right - this.m_direction = 4; - } else if(this.m_dx < 0) { - // left - this.m_direction = 3; - } else if(this.m_dy > 0) { - // down - this.m_direction = 2; - } else if(this.m_dy < 0) { - // up - this.m_direction = 1; - } else { - // still - this.m_direction = 0; - } - if(first) { - tmpdx = this.m_dx; - tmpdy = this.m_dy; - tmpdirection = this.m_direction; - first = false; - //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n"); - } - - // check if this choice follows some other ghosts' path - if(!isFollowing()) { - this.m_map.m_ghostdirections[this.m_index] = this.m_direction; - set = true; - } else { - cuts.addElement(new Integer(index)); - /*for( int h = 0; h < cuts.size(); h++) { - System.printString(cuts.elementAt(h) + ", "); - } - System.printString("\n");*/ - } - } - } - } - - // This methos do BFS from start node to end node - // If there is a path from start to end, return true; otherwise, return false - // Array parents records parent for a node in the BFS search, -// the last item of parents records the least steps to reach end node from start node - // Vector cuts specifies which nodes can not be the first one to access in this BFS - private boolean BFS(Node start, Node end, int[] parents, Vector cuts) { - int steps = 0; - Vector toaccess = new Vector(); - toaccess.addElement(start); - while(toaccess.size() > 0) { - // pull out the first one to access - Node access = (Node)toaccess.elementAt(0); - toaccess.removeElementAt(0); - if(access.getIndex() == end.getIndex()) { - // hit the end node - parents[parents.length - 1] = steps; - return true; - } - steps++; - Vector neighbours = access.getNeighbours(); - for(int i = 0; i < neighbours.size(); i++) { - Node neighbour = (Node)neighbours.elementAt(i); - if(parents[neighbour.getIndex()] == -1) { - // not accessed - boolean ignore = false; - if(access.getIndex() == start.getIndex()) { - // start node, check if the neighbour node is in cuts - int j = 0; - while((!ignore) && (j < cuts.size())) { - int tmp = ((Integer)cuts.elementAt(j)).intValue(); - if(tmp == neighbour.getIndex()) { - ignore = true; - } - j++; - } - } - if(!ignore) { - parents[neighbour.getIndex()] = access.getIndex(); - toaccess.addElement(neighbour); - } - } - } - } - parents[parents.length - 1] = -1; - return false; - } - - // This method returns true if this ghost is traveling to the same - // destination with the same direction as another ghost. - private boolean isFollowing () { - boolean bFollowing = false; - double dRandom; - - // If the ghost is in the same location as another ghost - // and moving in the same direction, then they are on - // top of each other and should not follow. - for (int i = 0; i < this.m_map.m_ghostsX.length; i++) { - // Ignore myself - if (this.m_index != i) { - if (this.m_map.m_ghostsX[i] == this.m_locX && - this.m_map.m_ghostsY[i] == this.m_locY && - this.m_map.m_ghostdirections[i] == this.m_direction) { - return true; - } - } - } - - // This will allow ghosts to often - // clump together for easier eating - dRandom = this.m_map.m_r.nextDouble(); - if (dRandom < .90) { - //if (m_bInsaneAI && dRandom < .25) - // return false; - //else - return false; - } - - // If ghost is moving to the same location and using the - // same direction, then it is following another ghost. - for (int i = 0; i < this.m_map.m_ghostsX.length; i++) { - // Ignore myself - if (this.m_index != i) { - if (this.m_map.m_targets[i] == this.m_target && - this.m_map.m_ghostdirections[i] == this.m_direction) { - return true; - } - } - } - - return bFollowing; - } - - // This method will take the specified location and direction and determine - // for the given location if the thing moved in that direction, what the - // next possible turning location would be. - private boolean getDestination (int direction, int locX, int locY, int[] point) { - // If the request direction is blocked by a wall, then just return the current location - if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up - ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left - ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down - ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right - point[0] = locX; - point[1] = locY; - return false; - } - - // Start off by advancing one in direction for specified location - if (direction == 1) { - // up - locY--; - } else if (direction == 2) { - // down - locY++; - } else if (direction == 3) { - // left - locX--; - } else if (direction == 4) { - // right - locX++; - } - - // If we violate the grid boundary, - // then return false. - if (locY < 0 || - locX < 0 || - locY == this.m_map.m_nrofblocks || - locX == this.m_map.m_nrofblocks) { - return false; - } - - boolean set = false; - // Determine next turning location. - while (!set) { - if (direction == 1 || direction == 2) { - // up or down - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (direction == 1) { - // Check for Top Warp - if (locY == 0) { - point[0] = locX; - point[1] = this.m_map.m_nrofblocks - 1; - set = true; - } else { - locY--; - } - } else { - // Check for Bottom Warp - if (locY == this.m_map.m_nrofblocks - 1) { - point[0] = locX; - point[1] = 0; - set = true; - } else { - locY++; - } - } - } - } else { - // left or right - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (direction == 3) { - // Check for Left Warp - if (locX == 0) { - point[0] = this.m_map.m_nrofblocks - 1; - point[1] = locY; - set = true; - } else { - locX--; - } - } else { - // Check for Right Warp - if (locX == this.m_map.m_nrofblocks - 1) { - point[0] = 0; - point[1] = locY; - set = true; - } else { - locX++; - } - } - } - } - } - return true; - } - - public void doMove() { - this.m_locX += this.m_dx; - this.m_locY += this.m_dy; - this.m_dx = 0; - this.m_dy = 0; - //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n"); - } +public class Ghost { + flag move; + flag update; + + public int m_locX; + public int m_locY; + public int m_index; + public int m_target; + public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right + int m_dx; + int m_dy; + Map m_map; + + public Ghost(int x, int y, Map map) { + this.m_locX = x; + this.m_locY = y; + this.m_dx = this.m_dy = 0; + this.m_index = -1; + this.m_target = -1; + this.m_direction = 0; + this.m_map = map; + } + + // 0:still, 1:up, 2:down, 3:left, 4:right + public void tryMove() { + //System.printString("step 1\n"); + // reset the target + this.m_target = -1; + // find the shortest possible way to the chosen target + setNextDirection(); + } + + private void setNextDirection() { + // current position of the ghost + Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; + boolean set = false; + Vector cuts = new Vector(); + int tmptarget = 0; + int tmpdx = 0; + int tmpdy = 0; + int tmpdirection = 0; + boolean first = true; + while(!set) { + int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; + for(int i = 0; i < parents.length; i++) { + parents[i] = -1; + } + if(!BFS(start, parents, cuts)) { + this.m_target = tmptarget; + this.m_dx = tmpdx; + this.m_dy = tmpdy; + this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; + set = true; + //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n"); + } else { + // Reversely go over the parents array to find the next node to reach + boolean found = false; + int index = this.m_map.m_pacMenY[this.m_target] * this.m_map.m_nrofblocks + this.m_map.m_pacMenX[this.m_target]; + //System.printString("Target: " + this.m_target + "\n"); + while(!found) { + int parent = parents[index]; + if(parent == start.getIndex()) { + found = true; + } else { + index = parent; + } + } + + // set the chase direction + int nx = this.m_map.m_mapNodes[index].getXLoc(); + int ny = this.m_map.m_mapNodes[index].getYLoc(); + this.m_dx = nx - this.m_locX; + this.m_dy = ny - this.m_locY; + if(this.m_dx > 0) { + // right + this.m_direction = 4; + } else if(this.m_dx < 0) { + // left + this.m_direction = 3; + } else if(this.m_dy > 0) { + // down + this.m_direction = 2; + } else if(this.m_dy < 0) { + // up + this.m_direction = 1; + } else { + // still + this.m_direction = 0; + } + if(first) { + tmptarget = this.m_target; + tmpdx = this.m_dx; + tmpdy = this.m_dy; + tmpdirection = this.m_direction; + first = false; + //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n"); + } + + // check if this choice follows some other ghosts' path + if(!isFollowing()) { + this.m_map.m_ghostdirections[this.m_index] = this.m_direction; + set = true; + } else { + cuts.addElement(new Integer(index)); + /*for( int h = 0; h < cuts.size(); h++) { + System.printString(cuts.elementAt(h) + ", "); + } + System.printString("\n");*/ + } + } + } + } + + // This methos do BFS from start node to end node + // If there is a path from start to end, return true; otherwise, return false + // Array parents records parent for a node in the BFS search, + // the last item of parents records the least steps to reach end node from start node + // Vector cuts specifies which nodes can not be the first one to access in this BFS + private boolean BFS(Node start, int[] parents, Vector cuts) { + //System.printString("aaa\n"); + int steps = 0; + Vector toaccess = new Vector(); + toaccess.addElement(start); + while(toaccess.size() > 0) { + //System.printString("bbb\n"); + // pull out the first one to access + Node access = (Node)toaccess.elementAt(0); + toaccess.removeElementAt(0); + for(int i = 0; i < this.m_map.m_pacMenX.length; i++) { + if((access.getXLoc() == this.m_map.m_pacMenX[i]) && (access.getYLoc() == this.m_map.m_pacMenY[i])) { + // hit one pacman + this.m_target = i; + parents[parents.length - 1] = steps; + return true; + } + } + steps++; + Vector neighbours = access.getNeighbours(); + for(int i = 0; i < neighbours.size(); i++) { + Node neighbour = (Node)neighbours.elementAt(i); + if(parents[neighbour.getIndex()] == -1) { + // not accessed + boolean ignore = false; + if(access.getIndex() == start.getIndex()) { + // start node, check if the neighbour node is in cuts + int j = 0; + while((!ignore) && (j < cuts.size())) { + int tmp = ((Integer)cuts.elementAt(j)).intValue(); + if(tmp == neighbour.getIndex()) { + ignore = true; + } + j++; + } + } + if(!ignore) { + parents[neighbour.getIndex()] = access.getIndex(); + toaccess.addElement(neighbour); + } + } + } + } + //System.printString("ccc\n"); + parents[parents.length - 1] = -1; + return false; + } + + // This method returns true if this ghost is traveling to the same + // destination with the same direction as another ghost. + private boolean isFollowing () { + boolean bFollowing = false; + double dRandom; + + // If the ghost is in the same location as another ghost + // and moving in the same direction, then they are on + // top of each other and should not follow. + for (int i = 0; i < this.m_map.m_ghostsX.length; i++) { + // Ignore myself + if (this.m_index != i) { + if (this.m_map.m_ghostsX[i] == this.m_locX && + this.m_map.m_ghostsY[i] == this.m_locY && + this.m_map.m_ghostdirections[i] == this.m_direction) { + return true; + } + } + } + + // This will allow ghosts to often + // clump together for easier eating + dRandom = this.m_map.m_r.nextDouble(); + if (dRandom < .90) { + //if (m_bInsaneAI && dRandom < .25) + // return false; + //else + return false; + } + + // If ghost is moving to the same location and using the + // same direction, then it is following another ghost. + for (int i = 0; i < this.m_map.m_ghostsX.length; i++) { + // Ignore myself + if (this.m_index != i) { + if (this.m_map.m_targets[i] == this.m_target && + this.m_map.m_ghostdirections[i] == this.m_direction) { + return true; + } + } + } + + return bFollowing; + } + + // This method will take the specified location and direction and determine + // for the given location if the thing moved in that direction, what the + // next possible turning location would be. + private boolean getDestination (int direction, int locX, int locY, int[] point) { + // If the request direction is blocked by a wall, then just return the current location + if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up + ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left + ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down + ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right + point[0] = locX; + point[1] = locY; + return false; + } + + // Start off by advancing one in direction for specified location + if (direction == 1) { + // up + locY--; + } else if (direction == 2) { + // down + locY++; + } else if (direction == 3) { + // left + locX--; + } else if (direction == 4) { + // right + locX++; + } + + // If we violate the grid boundary, + // then return false. + if (locY < 0 || + locX < 0 || + locY == this.m_map.m_nrofblocks || + locX == this.m_map.m_nrofblocks) { + return false; + } + + boolean set = false; + // Determine next turning location. + while (!set) { + if (direction == 1 || direction == 2) { + // up or down + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (direction == 1) { + // Check for Top Warp + if (locY == 0) { + point[0] = locX; + point[1] = this.m_map.m_nrofblocks - 1; + set = true; + } else { + locY--; + } + } else { + // Check for Bottom Warp + if (locY == this.m_map.m_nrofblocks - 1) { + point[0] = locX; + point[1] = 0; + set = true; + } else { + locY++; + } + } + } + } else { + // left or right + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (direction == 3) { + // Check for Left Warp + if (locX == 0) { + point[0] = this.m_map.m_nrofblocks - 1; + point[1] = locY; + set = true; + } else { + locX--; + } + } else { + // Check for Right Warp + if (locX == this.m_map.m_nrofblocks - 1) { + point[0] = 0; + point[1] = locY; + set = true; + } else { + locX++; + } + } + } + } + } + return true; + } + + public void doMove() { + this.m_locX += this.m_dx; + this.m_locY += this.m_dy; + this.m_dx = 0; + this.m_dy = 0; + //System.printString("Ghost " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n"); + } } \ No newline at end of file diff --git a/Robust/src/Benchmarks/MMG/Tag/MMG.java b/Robust/src/Benchmarks/MMG/Tag/MMG.java index 7207bc60..72884abb 100755 --- a/Robust/src/Benchmarks/MMG/Tag/MMG.java +++ b/Robust/src/Benchmarks/MMG/Tag/MMG.java @@ -1,139 +1,139 @@ -task startup(StartupObject s{initialstate}) { - //System.printString("Task startup\n"); - - int nrofpacs = 4; - int nrofghosts = 8; - Map map = new Map(nrofpacs, nrofghosts){init}; - taskexit(s{!initialstate}); -} - -task initMap(Map map{init}) { - //System.printString("Task initMap\n"); - - map.init(); - - int i = 0; - // create ghosts - for(i = 0; i < map.m_nrofghosts; i++) { - Ghost ghost = new Ghost(7, 7, map){move}; - ghost.m_index = i; - map.placeGhost(ghost); - } - // create pacmen - int tx = 14; - int ty = 14; - for(i = 0; i < map.m_nrofpacs; i++) { - Pacman pacman = new Pacman(5, 7, map){move}; - pacman.setTarget(tx*(i/2), ty*(i%2)); - pacman.m_index = i; - map.placePacman(pacman); - map.m_desX[i] = tx*(i/2); - map.m_desY[i] = ty*(i%2); - } - - map.m_ghostcount = 0; - map.m_paccount = 0; - - taskexit(map{!init, updateGhost}); -} - -task moveGhost(Ghost g{move}) { - //System.printString("Task moveGhost\n"); - - g.tryMove(); - - taskexit(g{!move, update}); -} - -task movePacman(Pacman p{move}) { - //System.printString("Task movePacman\n"); - - p.tryMove(); - - taskexit(p{!move, update}); -} - -task updateGhost(Map map{updateGhost}, optional Ghost g{update}) { - //System.printString("Task updateGhost\n"); - - if(isavailable(g)) { - g.doMove(); - map.placeGhost(g); - } else { - map.m_ghostcount++; - } - - if(map.m_ghostcount == map.m_nrofghosts) { - //map.m_nrofghosts -= map.m_failghostcount; - map.m_ghostcount = 0; - map.m_failghostcount = 0; - /*for(int i = 0; i < map.m_ghostsX.length; i++) { - System.printString("(" + map.m_ghostsX[i] + "," + map.m_ghostsY[i] + ") "); - } - System.printString("\n");*/ - taskexit(map{updatePac, !updateGhost}, g{!update}); - } - taskexit(g{!update}); -} - -task updatePac(Map map{updatePac}, optional Pacman p{update}) { - //System.printString("Task updatePac\n"); - - if(isavailable(p)) { - p.doMove(); - map.placePacman(p); - //System.printString("Pacman " + p.m_index + ": (" + map.m_pacMenX[p.m_index] + "," + map.m_pacMenY[p.m_index] + ")\n"); - boolean death = map.check(p); - /*if(death) { - System.printString("Pacman " + p.m_index + " caught!\n"); - }*/ - } else { - map.m_deathcount++; - map.m_paccount++; - } - - boolean finish = map.m_paccount == map.m_nrofpacs; - - if(finish) { - map.m_nrofpacs -= map.m_deathcount; - //System.printString(map.m_nrofpacs + " pacmen left. \n"); - if(map.isfinish()) { - taskexit(map{finish, !updatePac}, p{!update, !move}); - } else { - taskexit(map{next, !updatePac}, p{!update, !move}); - } - } else { - taskexit(p{!move, !update}); - } -} - -task next(Map map{next}) { - //System.printString("Task next\n"); - - int i = 0; - for(i = 0; i < map.m_nrofghosts; i++) { - Ghost ghost = new Ghost(map.m_ghostsX[i], map.m_ghostsY[i], map){move}; - ghost.m_index = i; - ghost.m_direction = map.m_ghostdirections[i]; - } - for(i = 0; i < map.m_pacMenX.length; i++) { - if(map.m_pacMenX[i] != -1) { - // still in the map - //System.printString("new Pacman\n"); - Pacman pacman = new Pacman(map.m_pacMenX[i], map.m_pacMenY[i], map){move}; - pacman.setTarget(map.m_desX[i], map.m_desY[i]); - pacman.m_index = i; - pacman.m_direction = map.m_directions[i]; - } - } - - map.m_paccount = 0; - map.m_deathcount = 0; - - taskexit(map{!next, updateGhost}); -} - -task finish(Map map{finish}) { - System.printString("Task Finish\n"); - taskexit(map{!finish}); +task startup(StartupObject s{initialstate}) { + //System.printString("Task startup\n"); + + int nrofpacs = 4; + int nrofghosts = 8; + Map map = new Map(nrofpacs, nrofghosts){init}; + taskexit(s{!initialstate}); +} + +task initMap(Map map{init}) { + //System.printString("Task initMap\n"); + + map.init(); + + int i = 0; + // create ghosts + for(i = 0; i < map.m_nrofghosts; i++) { + Ghost ghost = new Ghost(7, 7, map){move}; + ghost.m_index = i; + map.placeGhost(ghost); + } + // create pacmen + int tx = 14; + int ty = 14; + for(i = 0; i < map.m_nrofpacs; i++) { + Pacman pacman = new Pacman(5, 7, map){move}; + pacman.setTarget(tx*(i/2), ty*(i%2)); + pacman.m_index = i; + map.placePacman(pacman); + map.m_desX[i] = tx*(i/2); + map.m_desY[i] = ty*(i%2); + } + + map.m_ghostcount = 0; + map.m_paccount = 0; + + taskexit(map{!init, updateGhost}); +} + +task moveGhost(Ghost g{move}) { + //System.printString("Task moveGhost\n"); + + g.tryMove(); + + taskexit(g{!move, update}); +} + +task movePacman(Pacman p{move}) { + //System.printString("Task movePacman\n"); + + p.tryMove(); + + taskexit(p{!move, update}); +} + +task updateGhost(Map map{updateGhost}, optional Ghost g{update}) { + //System.printString("Task updateGhost\n"); + + if(isavailable(g)) { + g.doMove(); + map.placeGhost(g); + } else { + map.m_ghostcount++; + } + + if(map.m_ghostcount == map.m_nrofghosts) { + //map.m_nrofghosts -= map.m_failghostcount; + map.m_ghostcount = 0; + map.m_failghostcount = 0; + /*for(int i = 0; i < map.m_ghostsX.length; i++) { + System.printString("(" + map.m_ghostsX[i] + "," + map.m_ghostsY[i] + ") "); + } + System.printString("\n");*/ + taskexit(map{updatePac, !updateGhost}, g{!update}); + } + taskexit(g{!update}); +} + +task updatePac(Map map{updatePac}, optional Pacman p{update}) { + //System.printString("Task updatePac\n"); + + if(isavailable(p)) { + p.doMove(); + map.placePacman(p); + //System.printString("Pacman " + p.m_index + ": (" + map.m_pacMenX[p.m_index] + "," + map.m_pacMenY[p.m_index] + ")\n"); + boolean death = map.check(p); + /*if(death) { + System.printString("Pacman " + p.m_index + " caught!\n"); + }*/ + } else { + map.m_deathcount++; + map.m_paccount++; + } + + boolean finish = map.m_paccount == map.m_nrofpacs; + + if(finish) { + map.m_nrofpacs -= map.m_deathcount; + //System.printString(map.m_nrofpacs + " pacmen left. \n"); + if(map.isfinish()) { + taskexit(map{finish, !updatePac}, p{!update, !move}); + } else { + taskexit(map{next, !updatePac}, p{!update, !move}); + } + } else { + taskexit(p{!move, !update}); + } +} + +task next(Map map{next}) { + //System.printString("Task next\n"); + + int i = 0; + for(i = 0; i < map.m_nrofghosts; i++) { + Ghost ghost = new Ghost(map.m_ghostsX[i], map.m_ghostsY[i], map){move}; + ghost.m_index = i; + ghost.m_direction = map.m_ghostdirections[i]; + } + for(i = 0; i < map.m_pacMenX.length; i++) { + if(map.m_pacMenX[i] != -1) { + // still in the map + //System.printString("new Pacman\n"); + Pacman pacman = new Pacman(map.m_pacMenX[i], map.m_pacMenY[i], map){move}; + pacman.setTarget(map.m_desX[i], map.m_desY[i]); + pacman.m_index = i; + pacman.m_direction = map.m_directions[i]; + } + } + + map.m_paccount = 0; + map.m_deathcount = 0; + + taskexit(map{!next, updateGhost}); +} + +task finish(Map map{finish}) { + System.printString("Task Finish\n"); + taskexit(map{!finish}); } \ No newline at end of file diff --git a/Robust/src/Benchmarks/MMG/Tag/Map.java b/Robust/src/Benchmarks/MMG/Tag/Map.java index eb0cef24..a75ec229 100755 --- a/Robust/src/Benchmarks/MMG/Tag/Map.java +++ b/Robust/src/Benchmarks/MMG/Tag/Map.java @@ -1,180 +1,180 @@ -public class Map { - flag init; - flag updateGhost; - flag updatePac; - flag next; - flag finish; - - // maze - private int m_nrofblocks; - public int[] m_map; - public Node[] m_mapNodes; - - // pacmen information - public int m_nrofpacs; - public int[] m_pacMenX; - public int[] m_pacMenY; - public int[] m_directions; - public int[] m_desX; - public int[] m_desY; - public int m_paccount; - public int m_deathcount; - - // ghosts information - public int m_nrofghosts; - public int[] m_ghostsX; - public int[] m_ghostsY; - public int[] m_ghostdirections; - public int[] m_targets; - public int m_ghostcount; - public int m_failghostcount; - - // helper member - public Random m_r; - - public Map(int nrofpacs, int nrofghosts) { - //System.printString("step 1\n"); - this.m_nrofblocks = 15; - this.m_map = new int[this.m_nrofblocks*this.m_nrofblocks]; - this.m_mapNodes = new Node[this.m_nrofblocks*this.m_nrofblocks]; - - this.m_nrofpacs = nrofpacs; - this.m_pacMenX = new int[this.m_nrofpacs]; - this.m_pacMenY = new int[this.m_nrofpacs]; - this.m_directions = new int[this.m_nrofpacs]; - this.m_desX = new int[this.m_nrofpacs]; - this.m_desY = new int[this.m_nrofpacs]; - this.m_paccount = 0; - this.m_deathcount = 0; - - this.m_nrofghosts = nrofghosts; - this.m_ghostsX = new int[this.m_nrofghosts]; - this.m_ghostsY = new int[this.m_nrofghosts]; - this.m_ghostdirections = new int[this.m_nrofghosts]; - this.m_targets = new int[this.m_nrofghosts]; - this.m_ghostcount = 0; - this.m_failghostcount = 0; - - this.m_r = new Random(); - - for(int i = 0; i < this.m_nrofblocks*this.m_nrofblocks; i++) { - this.m_map[i] = -1; - this.m_mapNodes[i] = new Node(i%this.m_nrofblocks, i/this.m_nrofblocks, i); - } - - //System.printString("step 2\n"); - for(int i = 0; i < this.m_nrofpacs; i++) { - this.m_pacMenX[i] = this.m_pacMenY[i] = -1; - this.m_desX[i] = this.m_desY[i] = -1; - } - //System.printString("step 3\n"); - for(int i = 0; i < this.m_nrofghosts; i++) { - this.m_ghostsX[i] = this.m_ghostsY[i] = -1; - this.m_targets[i] = -1; - } - //System.printString("step 4\n"); - } - - public void init() { - // initilize the maze - int i = 0; - this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6; - this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=15;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=5; - this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=6;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=3;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4; - this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=5; - this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=8;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=8;this.m_map[i++]=12;this.m_map[i++]=5; - this.m_map[i++]=9;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=8;this.m_map[i++]=2;this.m_map[i++]=12;this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=2;this.m_map[i++]=8;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=12; - this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=8;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=3; - this.m_map[i++]=4;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=1; - this.m_map[i++]=12;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=10;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=9; - this.m_map[i++]=3;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=0;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=0;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=6; - this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=2;this.m_map[i++]=2;this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=15;this.m_map[i++]=5;this.m_map[i++]=15;this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=2;this.m_map[i++]=2;this.m_map[i++]=6;this.m_map[i++]=5; - this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=8;this.m_map[i++]=8;this.m_map[i++]=4;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=1;this.m_map[i++]=8;this.m_map[i++]=8;this.m_map[i++]=12;this.m_map[i++]=5; - this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=2;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4; - this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=6;this.m_map[i++]=13;this.m_map[i++]=3;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=5; - this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=12; // 15*15 - - // initilize the graph of the maze - for(i = 0; i < this.m_nrofblocks*this.m_nrofblocks; i++) { - int tmp = this.m_map[i]; - Node tmpNode = this.m_mapNodes[i]; - int locX = tmpNode.getXLoc(); - int locY = tmpNode.getYLoc(); - if((int)(tmp & 1) == 0) { - // can go left - if(locX == 0) { - tmpNode.addNeighbour(this.m_mapNodes[locY * this.m_nrofblocks + this.m_nrofblocks - 1]); - } else { - tmpNode.addNeighbour(this.m_mapNodes[i - 1]); - } - } - if((int)(tmp & 2) == 0) { - // can go up - if(locY == 0) { - tmpNode.addNeighbour(this.m_mapNodes[(this.m_nrofblocks - 1) * this.m_nrofblocks + locX]); - } else { - tmpNode.addNeighbour(this.m_mapNodes[(locY - 1) * this.m_nrofblocks + locX]); - } - } - if((int)(tmp & 4) == 0) { - // can go right - if(locX == this.m_nrofblocks - 1) { - tmpNode.addNeighbour(this.m_mapNodes[locY * this.m_nrofblocks]); - } else { - tmpNode.addNeighbour(this.m_mapNodes[i + 1]); - } - } - if((int)(tmp & 8) == 0) { - // can go down - if(locY == this.m_nrofblocks - 1) { - tmpNode.addNeighbour(this.m_mapNodes[locX]); - } else { - tmpNode.addNeighbour(this.m_mapNodes[(locY + 1) * this.m_nrofblocks + locX]); - } - } - } - } - - public void placePacman(Pacman t) { - this.m_pacMenX[t.m_index] = t.m_locX; - this.m_pacMenY[t.m_index] = t.m_locY; - this.m_paccount++; - } - - public void placeGhost(Ghost t) { - this.m_ghostsX[t.m_index] = t.m_locX; - this.m_ghostsY[t.m_index] = t.m_locY; - this.m_ghostcount++; - } - - public boolean check(Pacman t) { - boolean death = false; - int i = 0; - while((!death) && (i < this.m_ghostsX.length)) { - if((t.m_locX == this.m_ghostsX[i]) && (t.m_locY == this.m_ghostsY[i])) { - death = true; - } - i++; - } - if((!death) && (t.m_locX == t.m_tx) && (t.m_locY == t.m_ty)) { - // reach the destination - //System.printString("Hit destination!\n"); - death = true; - } - if(death) { - // pacman caught by ghost - // set pacman as death - t.m_death = true; - // kick it out - //this.m_map[t.y * this.m_nrofblocks + t.x - 1] -= 16; - this.m_deathcount++; - this.m_pacMenX[t.m_index] = -1; - this.m_pacMenY[t.m_index] = -1; - } - return death; - } - - public boolean isfinish() { - return this.m_nrofpacs == 0; - } +public class Map { + flag init; + flag updateGhost; + flag updatePac; + flag next; + flag finish; + + // maze + private int m_nrofblocks; + public int[] m_map; + public Node[] m_mapNodes; + + // pacmen information + public int m_nrofpacs; + public int[] m_pacMenX; + public int[] m_pacMenY; + public int[] m_directions; + public int[] m_desX; + public int[] m_desY; + public int m_paccount; + public int m_deathcount; + + // ghosts information + public int m_nrofghosts; + public int[] m_ghostsX; + public int[] m_ghostsY; + public int[] m_ghostdirections; + public int[] m_targets; + public int m_ghostcount; + public int m_failghostcount; + + // helper member + public Random m_r; + + public Map(int nrofpacs, int nrofghosts) { + //System.printString("step 1\n"); + this.m_nrofblocks = 15; + this.m_map = new int[this.m_nrofblocks*this.m_nrofblocks]; + this.m_mapNodes = new Node[this.m_nrofblocks*this.m_nrofblocks]; + + this.m_nrofpacs = nrofpacs; + this.m_pacMenX = new int[this.m_nrofpacs]; + this.m_pacMenY = new int[this.m_nrofpacs]; + this.m_directions = new int[this.m_nrofpacs]; + this.m_desX = new int[this.m_nrofpacs]; + this.m_desY = new int[this.m_nrofpacs]; + this.m_paccount = 0; + this.m_deathcount = 0; + + this.m_nrofghosts = nrofghosts; + this.m_ghostsX = new int[this.m_nrofghosts]; + this.m_ghostsY = new int[this.m_nrofghosts]; + this.m_ghostdirections = new int[this.m_nrofghosts]; + this.m_targets = new int[this.m_nrofghosts]; + this.m_ghostcount = 0; + this.m_failghostcount = 0; + + this.m_r = new Random(); + + for(int i = 0; i < this.m_nrofblocks*this.m_nrofblocks; i++) { + this.m_map[i] = -1; + this.m_mapNodes[i] = new Node(i%this.m_nrofblocks, i/this.m_nrofblocks, i); + } + + //System.printString("step 2\n"); + for(int i = 0; i < this.m_nrofpacs; i++) { + this.m_pacMenX[i] = this.m_pacMenY[i] = -1; + this.m_desX[i] = this.m_desY[i] = -1; + } + //System.printString("step 3\n"); + for(int i = 0; i < this.m_nrofghosts; i++) { + this.m_ghostsX[i] = this.m_ghostsY[i] = -1; + this.m_targets[i] = -1; + } + //System.printString("step 4\n"); + } + + public void init() { + // initilize the maze + int i = 0; + this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6; + this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=15;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=5; + this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=6;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=3;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4; + this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=5; + this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=8;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=8;this.m_map[i++]=12;this.m_map[i++]=5; + this.m_map[i++]=9;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=8;this.m_map[i++]=2;this.m_map[i++]=12;this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=2;this.m_map[i++]=8;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=12; + this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=8;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=7;this.m_map[i++]=5;this.m_map[i++]=3; + this.m_map[i++]=4;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=5;this.m_map[i++]=1; + this.m_map[i++]=12;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=10;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=9; + this.m_map[i++]=3;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=0;this.m_map[i++]=10;this.m_map[i++]=2;this.m_map[i++]=10;this.m_map[i++]=0;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=6; + this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=2;this.m_map[i++]=2;this.m_map[i++]=6;this.m_map[i++]=5;this.m_map[i++]=15;this.m_map[i++]=5;this.m_map[i++]=15;this.m_map[i++]=5;this.m_map[i++]=3;this.m_map[i++]=2;this.m_map[i++]=2;this.m_map[i++]=6;this.m_map[i++]=5; + this.m_map[i++]=5;this.m_map[i++]=9;this.m_map[i++]=8;this.m_map[i++]=8;this.m_map[i++]=4;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=1;this.m_map[i++]=8;this.m_map[i++]=8;this.m_map[i++]=12;this.m_map[i++]=5; + this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=6;this.m_map[i++]=13;this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=2;this.m_map[i++]=14;this.m_map[i++]=5;this.m_map[i++]=13;this.m_map[i++]=3;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=4; + this.m_map[i++]=5;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=1;this.m_map[i++]=10;this.m_map[i++]=8;this.m_map[i++]=6;this.m_map[i++]=13;this.m_map[i++]=3;this.m_map[i++]=8;this.m_map[i++]=10;this.m_map[i++]=4;this.m_map[i++]=11;this.m_map[i++]=14;this.m_map[i++]=5; + this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=12;this.m_map[i++]=3;this.m_map[i++]=6;this.m_map[i++]=9;this.m_map[i++]=10;this.m_map[i++]=10;this.m_map[i++]=12; // 15*15 + + // initilize the graph of the maze + for(i = 0; i < this.m_nrofblocks*this.m_nrofblocks; i++) { + int tmp = this.m_map[i]; + Node tmpNode = this.m_mapNodes[i]; + int locX = tmpNode.getXLoc(); + int locY = tmpNode.getYLoc(); + if((int)(tmp & 1) == 0) { + // can go left + if(locX == 0) { + tmpNode.addNeighbour(this.m_mapNodes[locY * this.m_nrofblocks + this.m_nrofblocks - 1]); + } else { + tmpNode.addNeighbour(this.m_mapNodes[i - 1]); + } + } + if((int)(tmp & 2) == 0) { + // can go up + if(locY == 0) { + tmpNode.addNeighbour(this.m_mapNodes[(this.m_nrofblocks - 1) * this.m_nrofblocks + locX]); + } else { + tmpNode.addNeighbour(this.m_mapNodes[(locY - 1) * this.m_nrofblocks + locX]); + } + } + if((int)(tmp & 4) == 0) { + // can go right + if(locX == this.m_nrofblocks - 1) { + tmpNode.addNeighbour(this.m_mapNodes[locY * this.m_nrofblocks]); + } else { + tmpNode.addNeighbour(this.m_mapNodes[i + 1]); + } + } + if((int)(tmp & 8) == 0) { + // can go down + if(locY == this.m_nrofblocks - 1) { + tmpNode.addNeighbour(this.m_mapNodes[locX]); + } else { + tmpNode.addNeighbour(this.m_mapNodes[(locY + 1) * this.m_nrofblocks + locX]); + } + } + } + } + + public void placePacman(Pacman t) { + this.m_pacMenX[t.m_index] = t.m_locX; + this.m_pacMenY[t.m_index] = t.m_locY; + this.m_paccount++; + } + + public void placeGhost(Ghost t) { + this.m_ghostsX[t.m_index] = t.m_locX; + this.m_ghostsY[t.m_index] = t.m_locY; + this.m_ghostcount++; + } + + public boolean check(Pacman t) { + boolean death = false; + int i = 0; + while((!death) && (i < this.m_ghostsX.length)) { + if((t.m_locX == this.m_ghostsX[i]) && (t.m_locY == this.m_ghostsY[i])) { + death = true; + } + i++; + } + if((!death) && (t.m_locX == t.m_tx) && (t.m_locY == t.m_ty)) { + // reach the destination + //System.printString("Hit destination!\n"); + death = true; + } + if(death) { + // pacman caught by ghost + // set pacman as death + t.m_death = true; + // kick it out + //this.m_map[t.y * this.m_nrofblocks + t.x - 1] -= 16; + this.m_deathcount++; + this.m_pacMenX[t.m_index] = -1; + this.m_pacMenY[t.m_index] = -1; + } + return death; + } + + public boolean isfinish() { + return this.m_nrofpacs == 0; + } } \ No newline at end of file diff --git a/Robust/src/Benchmarks/MMG/Tag/Pacman.java b/Robust/src/Benchmarks/MMG/Tag/Pacman.java index e75900eb..651b90dc 100755 --- a/Robust/src/Benchmarks/MMG/Tag/Pacman.java +++ b/Robust/src/Benchmarks/MMG/Tag/Pacman.java @@ -1,402 +1,402 @@ -public class Pacman { - flag move; - flag update; - - public int m_locX; - public int m_locY; - public boolean m_death; - public int m_index; - public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right - int m_dx; - int m_dy; - public int m_tx; - public int m_ty; - Map m_map; - - public Pacman(int x, int y, Map map) { - this.m_locX = x; - this.m_locY = y; - this.m_dx = this.m_dy = 0; - this.m_death = false; - this.m_index = -1; - this.m_tx = this.m_ty = -1; - this.m_direction = 0; - this.m_map = map; - } - - public void setTarget(int x, int y) { - this.m_tx = x; - this.m_ty = y; - } - - public void tryMove() { - // decide dx & dy - - // find the shortest possible way to the chosen target - setNextDirection(); - } - - private void setNextDirection() { - // current position of the ghost - Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; - - // get target's position - int targetx = this.m_tx; - int targety = this.m_ty; - int[] nextLocation = new int[2]; - nextLocation[0] = nextLocation[1] = -1; - - // target's position - Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx]; - - // breadth-first traverse the graph view of the maze - // check the shortest path for the start node to the end node - boolean set = false; - Vector cuts = new Vector(); - int tmpdx = 0; - int tmpdy = 0; - int tmpdirection = 0; - boolean first = true; - while(!set) { - int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; - for(int i = 0; i < parents.length; i++) { - parents[i] = -1; - } - if(!BFS(start, end, parents, cuts)) { - this.m_dx = tmpdx; - this.m_dy = tmpdy; - this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; - set = true; - //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n"); - } else { - // Reversely go over the parents array to find the next node to reach - boolean found = false; - int index = end.getIndex(); - while(!found) { - int parent = parents[index]; - if(parent == start.getIndex()) { - found = true; - } else { - index = parent; - } - } - - // set the chase direction - int nx = this.m_map.m_mapNodes[index].getXLoc(); - int ny = this.m_map.m_mapNodes[index].getYLoc(); - this.m_dx = nx - this.m_locX; - this.m_dy = ny - this.m_locY; - if(this.m_dx > 0) { - // right - this.m_direction = 4; - } else if(this.m_dx < 0) { - // left - this.m_direction = 3; - } else if(this.m_dy > 0) { - // down - this.m_direction = 2; - } else if(this.m_dy < 0) { - // up - this.m_direction = 1; - } else { - // still - this.m_direction = 0; - } - if(first) { - tmpdx = this.m_dx; - tmpdy = this.m_dy; - tmpdirection = this.m_direction; - first = false; - //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n"); - } - - // check if this choice follows some other ghosts' path - if(canFlee()) { - this.m_map.m_directions[this.m_index] = this.m_direction; - set = true; - } else { - cuts.addElement(new Integer(index)); - /*for( int h = 0; h < cuts.size(); h++) { - System.printString(cuts.elementAt(h) + ", "); - } - System.printString("\n");*/ - } - } - } - } - - // This methos do BFS from start node to end node - // If there is a path from start to end, return true; otherwise, return false - // Array parents records parent for a node in the BFS search, - // the last item of parents records the least steps to reach end node from start node - // Vector cuts specifies which nodes can not be the first one to access in this BFS - private boolean BFS(Node start, Node end, int[] parents, Vector cuts) { - int steps = 0; - Vector toaccess = new Vector(); - toaccess.addElement(start); - while(toaccess.size() > 0) { - // pull out the first one to access - Node access = (Node)toaccess.elementAt(0); - toaccess.removeElementAt(0); - if(access.getIndex() == end.getIndex()) { - // hit the end node - parents[parents.length - 1] = steps; - return true; - } - steps++; - Vector neighbours = access.getNeighbours(); - for(int i = 0; i < neighbours.size(); i++) { - Node neighbour = (Node)neighbours.elementAt(i); - if(parents[neighbour.getIndex()] == -1) { - // not accessed - boolean ignore = false; - if(access.getIndex() == start.getIndex()) { - // start node, check if the neighbour node is in cuts - int j = 0; - while((!ignore) && (j < cuts.size())) { - int tmp = ((Integer)cuts.elementAt(j)).intValue(); - if(tmp == neighbour.getIndex()) { - ignore = true; - } - j++; - } - } - if(!ignore) { - parents[neighbour.getIndex()] = access.getIndex(); - toaccess.addElement(neighbour); - } - } - } - } - parents[parents.length - 1] = -1; - return false; - } - - // This method returns true if this pacmen can flee in this direction. - private boolean canFlee () { - int steps = 0; - int locX = this.m_locX; - int locY = this.m_locY; - int[] point = new int[2]; - point[0] = point[1] = -1; - - // Start off by advancing one in direction for specified location - if (this.m_direction == 1) { - // up - locY--; - } else if (this.m_direction == 2) { - // down - locY++; - } else if (this.m_direction == 3) { - // left - locX--; - } else if (this.m_direction == 4) { - // right - locX++; - } - steps++; - - boolean set = false; - // Determine next turning location. - while (!set) { - if (this.m_direction == 1 || this.m_direction == 2) { - // up or down - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (this.m_direction == 1) { - // Check for Top Warp - if (locY == 0) { - point[0] = locX; - point[1] = this.m_map.m_nrofblocks - 1; - set = true; - } else { - locY--; - steps++; - } - } else { - // Check for Bottom Warp - if (locY == this.m_map.m_nrofblocks - 1) { - point[0] = locX; - point[1] = 0; - set = true; - } else { - locY++; - steps++; - } - } - } - } else { - // left or right - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (this.m_direction == 3) { - // Check for Left Warp - if (locX == 0) { - point[0] = this.m_map.m_nrofblocks - 1; - point[1] = locY; - set = true; - } else { - locX--; - steps++; - } - } else { - // Check for Right Warp - if (locX == this.m_map.m_nrofblocks - 1) { - point[0] = 0; - point[1] = locY; - set = true; - } else { - locX++; - steps++; - } - } - } - } - } - - // check the least steps for the ghosts to reach point location - int chasesteps = -1; - Node end = this.m_map.m_mapNodes[point[1] * this.m_map.m_nrofblocks + point[0]]; - for(int i = 0; i < this.m_map.m_ghostsX.length; i++) { - Node start = this.m_map.m_mapNodes[this.m_map.m_ghostsY[i] * this.m_map.m_nrofblocks + this.m_map.m_ghostsX[i]]; - int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; - for(int j = 0; j < parents.length; j++) { - parents[j] = -1; - } - if(BFS(start, end, parents, new Vector())) { - if((chasesteps == -1) || - (chasesteps > parents[parents.length - 1])) { - chasesteps = parents[parents.length - 1]; - } - } - } - - return ((chasesteps == -1) || (steps < chasesteps)); - } - - // This method will take the specified location and direction and determine - // for the given location if the thing moved in that direction, what the - // next possible turning location would be. - private boolean getDestination (int direction, int locX, int locY, int[] point) { - // If the request direction is blocked by a wall, then just return the current location - if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up - ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left - ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down - ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right - point[0] = locX; - point[1] = locY; - return false; - } - - // Start off by advancing one in direction for specified location - if (direction == 1) { - // up - locY--; - } else if (direction == 2) { - // down - locY++; - } else if (direction == 3) { - // left - locX--; - } else if (direction == 4) { - // right - locX++; - } - - // If we violate the grid boundary, - // then return false. - if (locY < 0 || - locX < 0 || - locY == this.m_map.m_nrofblocks || - locX == this.m_map.m_nrofblocks) { - return false; - } - - boolean set = false; - // Determine next turning location. - while (!set) { - if (direction == 1 || direction == 2) { - // up or down - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (direction == 1) { - // Check for Top Warp - if (locY == 0) { - point[0] = locX; - point[1] = this.m_map.m_nrofblocks - 1; - set = true; - } else { - locY--; - } - } else { - // Check for Bottom Warp - if (locY == this.m_map.m_nrofblocks - 1) { - point[0] = locX; - point[1] = 0; - set = true; - } else { - locY++; - } - } - } - } else { - // left or right - if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right - ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left - point[0] = locX; - point[1] = locY; - set = true; - } else { - if (direction == 3) { - // Check for Left Warp - if (locX == 0) { - point[0] = this.m_map.m_nrofblocks - 1; - point[1] = locY; - set = true; - } else { - locX--; - } - } else { - // Check for Right Warp - if (locX == this.m_map.m_nrofblocks - 1) { - point[0] = 0; - point[1] = locY; - set = true; - } else { - locX++; - } - } - } - } - } - return true; - } - - public void doMove() { - this.m_locX += this.m_dx; - this.m_locY += this.m_dy; - this.m_dx = 0; - this.m_dy = 0; - //System.printString("Pacmen " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n"); - } +public class Pacman { + flag move; + flag update; + + public int m_locX; + public int m_locY; + public boolean m_death; + public int m_index; + public int m_direction; // 0:still, 1:up, 2:down, 3:left, 4:right + int m_dx; + int m_dy; + public int m_tx; + public int m_ty; + Map m_map; + + public Pacman(int x, int y, Map map) { + this.m_locX = x; + this.m_locY = y; + this.m_dx = this.m_dy = 0; + this.m_death = false; + this.m_index = -1; + this.m_tx = this.m_ty = -1; + this.m_direction = 0; + this.m_map = map; + } + + public void setTarget(int x, int y) { + this.m_tx = x; + this.m_ty = y; + } + + public void tryMove() { + // decide dx & dy + + // find the shortest possible way to the chosen target + setNextDirection(); + } + + private void setNextDirection() { + // current position of the ghost + Node start = this.m_map.m_mapNodes[this.m_locY * this.m_map.m_nrofblocks + this.m_locX]; + + // get target's position + int targetx = this.m_tx; + int targety = this.m_ty; + int[] nextLocation = new int[2]; + nextLocation[0] = nextLocation[1] = -1; + + // target's position + Node end = this.m_map.m_mapNodes[targety * this.m_map.m_nrofblocks + targetx]; + + // breadth-first traverse the graph view of the maze + // check the shortest path for the start node to the end node + boolean set = false; + Vector cuts = new Vector(); + int tmpdx = 0; + int tmpdy = 0; + int tmpdirection = 0; + boolean first = true; + while(!set) { + int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; + for(int i = 0; i < parents.length; i++) { + parents[i] = -1; + } + if(!BFS(start, end, parents, cuts)) { + this.m_dx = tmpdx; + this.m_dy = tmpdy; + this.m_map.m_ghostdirections[this.m_index] = this.m_direction = tmpdirection; + set = true; + //System.printString("Use first choice: (" + this.m_dx + ", " + this.m_dy + ")\n"); + } else { + // Reversely go over the parents array to find the next node to reach + boolean found = false; + int index = end.getIndex(); + while(!found) { + int parent = parents[index]; + if(parent == start.getIndex()) { + found = true; + } else { + index = parent; + } + } + + // set the chase direction + int nx = this.m_map.m_mapNodes[index].getXLoc(); + int ny = this.m_map.m_mapNodes[index].getYLoc(); + this.m_dx = nx - this.m_locX; + this.m_dy = ny - this.m_locY; + if(this.m_dx > 0) { + // right + this.m_direction = 4; + } else if(this.m_dx < 0) { + // left + this.m_direction = 3; + } else if(this.m_dy > 0) { + // down + this.m_direction = 2; + } else if(this.m_dy < 0) { + // up + this.m_direction = 1; + } else { + // still + this.m_direction = 0; + } + if(first) { + tmpdx = this.m_dx; + tmpdy = this.m_dy; + tmpdirection = this.m_direction; + first = false; + //System.printString("First choice: (" + tmpdx + ", " + tmpdy + ")\n"); + } + + // check if this choice follows some other ghosts' path + if(canFlee()) { + this.m_map.m_directions[this.m_index] = this.m_direction; + set = true; + } else { + cuts.addElement(new Integer(index)); + /*for( int h = 0; h < cuts.size(); h++) { + System.printString(cuts.elementAt(h) + ", "); + } + System.printString("\n");*/ + } + } + } + } + + // This methos do BFS from start node to end node + // If there is a path from start to end, return true; otherwise, return false + // Array parents records parent for a node in the BFS search, + // the last item of parents records the least steps to reach end node from start node + // Vector cuts specifies which nodes can not be the first one to access in this BFS + private boolean BFS(Node start, Node end, int[] parents, Vector cuts) { + int steps = 0; + Vector toaccess = new Vector(); + toaccess.addElement(start); + while(toaccess.size() > 0) { + // pull out the first one to access + Node access = (Node)toaccess.elementAt(0); + toaccess.removeElementAt(0); + if(access.getIndex() == end.getIndex()) { + // hit the end node + parents[parents.length - 1] = steps; + return true; + } + steps++; + Vector neighbours = access.getNeighbours(); + for(int i = 0; i < neighbours.size(); i++) { + Node neighbour = (Node)neighbours.elementAt(i); + if(parents[neighbour.getIndex()] == -1) { + // not accessed + boolean ignore = false; + if(access.getIndex() == start.getIndex()) { + // start node, check if the neighbour node is in cuts + int j = 0; + while((!ignore) && (j < cuts.size())) { + int tmp = ((Integer)cuts.elementAt(j)).intValue(); + if(tmp == neighbour.getIndex()) { + ignore = true; + } + j++; + } + } + if(!ignore) { + parents[neighbour.getIndex()] = access.getIndex(); + toaccess.addElement(neighbour); + } + } + } + } + parents[parents.length - 1] = -1; + return false; + } + + // This method returns true if this pacmen can flee in this direction. + private boolean canFlee () { + int steps = 0; + int locX = this.m_locX; + int locY = this.m_locY; + int[] point = new int[2]; + point[0] = point[1] = -1; + + // Start off by advancing one in direction for specified location + if (this.m_direction == 1) { + // up + locY--; + } else if (this.m_direction == 2) { + // down + locY++; + } else if (this.m_direction == 3) { + // left + locX--; + } else if (this.m_direction == 4) { + // right + locX++; + } + steps++; + + boolean set = false; + // Determine next turning location. + while (!set) { + if (this.m_direction == 1 || this.m_direction == 2) { + // up or down + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (this.m_direction == 1) { + // Check for Top Warp + if (locY == 0) { + point[0] = locX; + point[1] = this.m_map.m_nrofblocks - 1; + set = true; + } else { + locY--; + steps++; + } + } else { + // Check for Bottom Warp + if (locY == this.m_map.m_nrofblocks - 1) { + point[0] = locX; + point[1] = 0; + set = true; + } else { + locY++; + steps++; + } + } + } + } else { + // left or right + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (this.m_direction == 3) { + // Check for Left Warp + if (locX == 0) { + point[0] = this.m_map.m_nrofblocks - 1; + point[1] = locY; + set = true; + } else { + locX--; + steps++; + } + } else { + // Check for Right Warp + if (locX == this.m_map.m_nrofblocks - 1) { + point[0] = 0; + point[1] = locY; + set = true; + } else { + locX++; + steps++; + } + } + } + } + } + + // check the least steps for the ghosts to reach point location + int chasesteps = -1; + Node end = this.m_map.m_mapNodes[point[1] * this.m_map.m_nrofblocks + point[0]]; + for(int i = 0; i < this.m_map.m_ghostsX.length; i++) { + Node start = this.m_map.m_mapNodes[this.m_map.m_ghostsY[i] * this.m_map.m_nrofblocks + this.m_map.m_ghostsX[i]]; + int parents[] = new int[this.m_map.m_nrofblocks * this.m_map.m_nrofblocks + 1]; + for(int j = 0; j < parents.length; j++) { + parents[j] = -1; + } + if(BFS(start, end, parents, new Vector())) { + if((chasesteps == -1) || + (chasesteps > parents[parents.length - 1])) { + chasesteps = parents[parents.length - 1]; + } + } + } + + return ((chasesteps == -1) || (steps < chasesteps)); + } + + // This method will take the specified location and direction and determine + // for the given location if the thing moved in that direction, what the + // next possible turning location would be. + private boolean getDestination (int direction, int locX, int locY, int[] point) { + // If the request direction is blocked by a wall, then just return the current location + if (((direction == 1) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0)) || // up + ((direction == 3) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) || // left + ((direction == 2) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) || // down + ((direction == 4) && ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0))) { // right + point[0] = locX; + point[1] = locY; + return false; + } + + // Start off by advancing one in direction for specified location + if (direction == 1) { + // up + locY--; + } else if (direction == 2) { + // down + locY++; + } else if (direction == 3) { + // left + locX--; + } else if (direction == 4) { + // right + locX++; + } + + // If we violate the grid boundary, + // then return false. + if (locY < 0 || + locX < 0 || + locY == this.m_map.m_nrofblocks || + locX == this.m_map.m_nrofblocks) { + return false; + } + + boolean set = false; + // Determine next turning location. + while (!set) { + if (direction == 1 || direction == 2) { + // up or down + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) == 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) == 0) || // left + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) != 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) != 0)) { // down + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (direction == 1) { + // Check for Top Warp + if (locY == 0) { + point[0] = locX; + point[1] = this.m_map.m_nrofblocks - 1; + set = true; + } else { + locY--; + } + } else { + // Check for Bottom Warp + if (locY == this.m_map.m_nrofblocks - 1) { + point[0] = locX; + point[1] = 0; + set = true; + } else { + locY++; + } + } + } + } else { + // left or right + if (((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 2) == 0) || // up + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 8) == 0) || // down + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 4) != 0) || // right + ((int)(this.m_map.m_map[locX + locY * this.m_map.m_nrofblocks] & 1) != 0)) { // left + point[0] = locX; + point[1] = locY; + set = true; + } else { + if (direction == 3) { + // Check for Left Warp + if (locX == 0) { + point[0] = this.m_map.m_nrofblocks - 1; + point[1] = locY; + set = true; + } else { + locX--; + } + } else { + // Check for Right Warp + if (locX == this.m_map.m_nrofblocks - 1) { + point[0] = 0; + point[1] = locY; + set = true; + } else { + locX++; + } + } + } + } + } + return true; + } + + public void doMove() { + this.m_locX += this.m_dx; + this.m_locY += this.m_dy; + this.m_dx = 0; + this.m_dy = 0; + //System.printString("Pacmen " + this.m_index + ": (" + this.m_locX + ", " + this.m_locY + ")\n"); + } } \ No newline at end of file -- 2.34.1