--- /dev/null
+/**
+ ** A path finder implementation that uses the AStar heuristic based algorithm
+ ** to determine a path.
+ ** New changes for our purposes
+ **/
+public class AStarPathFinder {
+
+ /** The set of nodes that have been searched through */
+ private Vector closed;
+
+ /** The set of nodes that we do not yet consider fully searched */
+ private SortedList open;
+
+ /** The map being searched */
+ global GameMap[][] land;
+
+ /** The maximum depth of search we're willing to accept before giving up */
+ private int maxSearchDistance;
+
+ /** The complete set of nodes across the map */
+ private Node[][] nodes;
+
+ /** True if we allow diagonal movement */
+ private boolean allowDiagMovement;
+
+ /** Map size where we are searching */
+ private int rows, columns;
+
+ /**
+ ** Create a path finder with the default heuristic - closest to target.
+ **
+ ** @param land The map to be searched
+ ** @param maxSearchDistance The maximum depth we'll search before giving up
+ ** @param allowDiagMovement True if the search should try diagonal movement
+ **/
+ public AStarPathFinder(GameMap[][] land, int maxSearchDistance, boolean allowDiagMovement, int rows, int columns) {
+ this.land = land;
+ this.maxSearchDistance = maxSearchDistance;
+ this.allowDiagMovement = allowDiagMovement;
+ closed = new Vector();
+ open = new SortedList();
+
+ nodes = new Node[rows][columns];
+ for (int x=0;x<rows;x++) {
+ for (int y=0;y<columns;y++) {
+ nodes[x][y] = new Node(x,y);
+ }
+ }
+ this.rows = rows;
+ this.columns = columns;
+ }
+
+ /**
+ ** A description of an implementation that can find a path from one
+ ** location on a tile map to another based on information provided
+ ** by that tile map.
+ **
+ ** Find a path from the starting location to the target
+ ** location avoiding blockages and attempting to honour costs
+ ** provided by the land.
+ **
+ ** @return The path found from start to end, or null if no path can be found.
+ **/
+
+ public Path findPath(Player gamer) {
+ int tx = gamer.getGoalX();
+ int ty = gamer.getGoalY();
+ int sx = gamer.getX();
+ int sy = gamer.getY();
+
+ // easy first check, if the destination is blocked, we can't get there
+ if(land[tx][ty].hasTree() || land[tx][ty].hasRock()) {
+ return null;
+ }
+
+ // initial state for A*. The closed group is empty. Only the starting
+ // tile is in the open list
+ nodes[sx][sy].cost = 0;
+ nodes[sx][sy].depth = 0;
+ closed.clear();
+ open.clear();
+ open.add(nodes[sx][sy]);
+
+ nodes[tx][ty].parent = null;
+
+ // while we haven't exceeded our max search depth
+ int maxDepth = 0;
+ while ((maxDepth < maxSearchDistance) && (open.size() != 0)) {
+ // pull out the first node in our open list, this is determined to
+ // be the most likely to be the next step based on our heuristic
+
+ Node current = getFirstInOpen();
+
+ if (current == nodes[tx][ty]) {
+ break;
+ }
+
+ removeFromOpen(current);
+ addToClosed(current);
+
+ // search through all the neighbours of the current node evaluating
+ // them as next steps
+
+ for (int x=-1;x<2;x++) {
+ for (int y=-1;y<2;y++) {
+ // not a neighbour, its the current tile
+
+ if ((x == 0) && (y == 0)) {
+ continue;
+ }
+
+ // if we're not allowing diagonal movement then only
+ // one of x or y can be set
+
+ if (!allowDiagMovement) {
+ if ((x != 0) && (y != 0)) {
+ continue;
+ }
+ }
+
+ // determine the location of the neighbour and evaluate it
+
+ int xp = x + current.x;
+ int yp = y + current.y;
+
+ if (isValidLocation(sx,sy,xp,yp)) {
+ // the cost to get to this node is cost the current plus the movement
+ // cost to reach this node. Note that the heursitic value is only used
+ // in the sorted open list
+
+ int nextStepCost = current.cost + getMovementCost(current.x, current.y, xp, yp);
+ Node neighbour = nodes[xp][yp];
+
+ // if the new cost we've determined for this node is lower than
+ // it has been previously makes sure the node has
+ // determined that there might have been a better path to get to
+ // this node so it needs to be re-evaluated
+
+ if (nextStepCost < neighbour.cost) {
+ if (inOpenList(neighbour)) {
+ removeFromOpen(neighbour);
+ }
+ if (inClosedList(neighbour)) {
+ removeFromClosed(neighbour);
+ }
+ }
+
+ // if the node hasn't already been processed and discarded then
+ // reset it's cost to our current cost and add it as a next possible
+ // step (i.e. to the open list)
+ if (!inOpenList(neighbour) && !(inClosedList(neighbour))) {
+ neighbour.cost = nextStepCost;
+ neighbour.heuristic = getHeuristicCost(xp, yp, tx, ty);
+ maxDepth = Math.max(maxDepth, neighbour.setParent(current));
+ addToOpen(neighbour);
+ }
+ }
+ }
+ }
+ }
+
+ // since we'e've run out of search
+ // there was no path. Just return null
+ if (nodes[tx][ty].parent == null) {
+ return null;
+ }
+
+ // At this point we've definitely found a path so we can uses the parent
+ // references of the nodes to find out way from the target location back
+ // to the start recording the nodes on the way.
+
+ Path path = new Path();
+ Node target = nodes[tx][ty];
+ while (target != nodes[sx][sy]) {
+ path.prependStep(target.x, target.y);
+ target = target.parent;
+ }
+
+ // thats it, we have our path
+ return path;
+ }
+
+ /**
+ ** Check if a given location is valid for the supplied gamer
+ **
+ ** @param sx The starting x coordinate
+ ** @param sy The starting y coordinate
+ ** @param xp The x coordinate of the location to check
+ ** @param yp The y coordinate of the location to check
+ ** @return True if the location is valid for the given gamer
+ **/
+
+
+ public boolean isValidLocation(int sx, int sy, int xp, int yp) {
+ boolean invalid = (xp <= 0) || (yp <= 0) || (xp >= rows-1) || (yp >= columns-1);
+
+ if ((!invalid) && ((sx != xp) || (sy != yp))) {
+ if (land[xp][yp].hasTree() || land[xp][yp].hasRock()) {
+ invalid = true;
+ }
+ }
+ return !invalid;
+ }
+
+ /**
+ ** Get the first element from the open list. This is the next
+ ** one to be searched.
+ **
+ ** @return The first element in the open list
+ **/
+ protected Node getFirstInOpen() {
+ Node n = (Node) open.first();
+ return n;
+ }
+
+ /**
+ ** Remove a node from the open list
+ **
+ ** @param node The node to remove from the open list
+ **/
+ protected void removeFromOpen(Node node) {
+ open.remove(node);
+ }
+
+ /**
+ ** Add a node to the closed list
+ **
+ ** @param node The node to add to the closed list
+ **/
+ protected void addToClosed(Node node) {
+ closed.addElement(node);
+ }
+
+ /**
+ ** Remove a node from the closed list
+ **
+ ** @param node The node to remove from the closed list
+ **/
+ protected void removeFromClosed(Node node) {
+ closed.remove(node);
+ }
+
+ /**
+ ** Check if the node supplied is in the closed list
+ **
+ ** @param node The node to search for
+ ** @return True if the node specified is in the closed list
+ **/
+ protected boolean inClosedList(Node node) {
+ return closed.contains(node);
+ }
+
+ /**
+ ** Check if a node is in the open list
+ **
+ ** @param node The node to check for
+ ** @return True if the node given is in the open list
+ **/
+ protected boolean inOpenList(Node node) {
+ return open.contains(node);
+ }
+
+ /**
+ ** Add a node to the open list
+ **
+ ** @param node The node to be added to the open list
+ **/
+ protected void addToOpen(Node node) {
+ open.add(node);
+ }
+
+ /**
+ ** Get the cost to move through a given location
+ **
+ ** @param x The x coordinate of the tile whose cost is being determined
+ ** @param y The y coordiante of the tile whose cost is being determined
+ ** @param xp The x coordinate of the neighbor target location
+ ** @param yp The y coordinate of the neighbor target location
+ ** @return The cost of movement through the given tile
+ **/
+ public int getMovementCost(int x, int y, int xp, int yp) {
+ if (Math.abs(xp - x) == 1 && Math.abs(yp - y) == 1) {
+ return 14;
+ }
+ return 10;
+ }
+
+ /**
+ *
+ * Get the cost of moving through the given tile. This can be used to
+ ** make certain areas more desirable.
+ **
+ ** @param xp The x coordinate of the tile we're moving from
+ ** @param yp The y coordinate of the tile we're moving from
+ ** @param tx The x coordinate of the tile we're moving to
+ ** @param ty The y coordinate of the tile we're moving to
+ ** @return The relative cost of moving across the given tile
+ **/
+ public int getHeuristicCost(int xp, int yp, int tx, int ty) {
+ int heur = (Math.abs(tx - xp) + Math.abs(ty - yp)) * 10;
+ return heur;
+ }
+
+ /**
+ * Used only for debugging by printing the list element's
+ * x and y coordinates
+ **/
+
+ public void debugClosedList() {
+ for(int i=0; i<closed.size(); i++) {
+ Node n = (Node) closed.elementAt(i);
+ System.print("Element "+i+": n.getX()= "+n.getX()+" n.getY()= "+n.getY()+ "\n");
+ }
+ System.printString("\n");
+ }
+}
public class BarrierServer extends Thread {
int numthreads;
boolean done;
+ GameMap land;
public BarrierServer(int n) {
numthreads=n;
done=false;
}
+ /**
+ ** Update the age of all trees in a given map
+ ** @param land The map to be searched
+ ** @param rows The number of rows in the map
+ ** @param cols The number of columns in the map
+ **/
+ public void updateAge(GameMap[][] land, int maxage, int rows, int cols) {
+ for(int i = 0; i<rows; i++) {
+ for(int j = 0; j<cols; j++) {
+ if(land[i][j].tree != null) {
+ if(land[i][j].tree.getage() > maxage) {
+ land[i][j].tree = null;
+ } else {
+ land[i][j].tree.incrementFiveYrs();
+ }
+ }
+ }
+ }
+ }
+
public void run() {
int n;
ServerSocket ss=new ServerSocket(2000);
+/**
+ ** The main Map that is shared across machines
+ ** The description for the data we're pathfinding over. This provides the contract
+ ** between the data being searched (i.e. the in game map) and the path finding
+ ** generic tools
+ **/
+
public class GameMap {
private TreeType tree;
private RockType rock;
rock = r;
}
+ public void cutTree() {
+ tree = null;
+ }
+
public boolean isEmpty() {
if (tree == null && rock == null) {
return true;
}
return false;
}
+
+ /**
+ ** Only for Debugging by printing the map
+ ** Called after every round
+ **/
+ public void print() {
+ if (tree != null) {
+ System.print("T ");
+ return;
+ }
+ if (rock != null) {
+ System.print("o ");
+ return;
+ }
+ System.print(". ");
+ }
}
+/**
+ ** Saves the X and Y coordinates of a single tile in a Map
+ **/
+
public class Goal {
- private int LocX;
- private int LocY;
+ private int locX;
+ private int locY;
public Goal() {
- LocX = 0;
- LocY = 0;
+ locX = 0;
+ locY = 0;
}
public Goal(int x, int y) {
- LocX = x;
- LocY = y;
+ locX = x;
+ locY = y;
}
public void setXY(int x, int y) {
- LocX = x;
- LocY = y;
+ locX = x;
+ locY = y;
}
public int getX() {
- return LocX;
+ return locX;
}
public int getY() {
- return LocY;
+ return locY;
}
}
--- /dev/null
+/**
+ ** A single node in the search graph
+ ** Has same dimensions as the Map where we are searching
+ **/
+private class Node {
+ /** The x coordinate of the node */
+ private int x;
+ /** The y coordinate of the node */
+ private int y;
+ /** The path cost for this node */
+ private int cost;
+ /** The parent of this node, how we reached it in the search */
+ private Node parent;
+ /** The heuristic cost of this node */
+ private int heuristic;
+ /** The search depth of this node */
+ private int depth;
+
+ /**
+ **Create a new node
+ **
+ ** @param x The x coordinate of the node
+ ** @param y The y coordinate of the node
+ **/
+ public Node(int x, int y) {
+ this.x = x;
+ this.y = y;
+ }
+
+ /**
+ ** Set the parent of this node
+ **
+ ** @param parent The parent node which lead us to this node
+ ** @return The depth we have no reached in searching
+ **/
+ public int setParent(Node parent) {
+ depth = parent.depth + 1;
+ this.parent = parent;
+
+ return depth;
+ }
+
+ /**
+ ** compareTo(Object)
+ **/
+ public int compareTo(Object other) {
+ Node o = (Node) other;
+
+ int f = heuristic + cost;
+ int of = o.heuristic + o.cost;
+
+ if (f < of) {
+ return -1;
+ } else if (f > of) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+
+ /**
+ ** @return The cost of the heuristic
+ **/
+ public int getHeuristic() {
+ return heuristic;
+ }
+
+
+ /**
+ ** @return The actual cost of traversal
+ **/
+ public int getCost() {
+ return cost;
+ }
+
+ /**
+ ** Only for Debugging by printing contents of Node
+ **/
+ public void debugNode() {
+ System.println("x= "+ x + " y= "+ y + " cost= " + cost + " heuristic= "+ heuristic + " depth= " + depth);
+ }
+
+ public int getX() {
+ return x;
+ }
+
+ public int getY() {
+ return y;
+ }
+}
+
+/**
+ ** A simple sorted list
+ **
+ **/
+class SortedList {
+ /** The list of elements */
+ private Vector list;
+
+ public SortedList() {
+ list = new Vector();
+ }
+ /**
+ ** Retrieve the first element from the list
+ **
+ ** @return The first element from the list
+ **/
+ public Object first() {
+ Object o = list.elementAt(0);
+ return o;
+ }
+
+ /**
+ ** Empty the list
+ **/
+ public void clear() {
+ list.clear();
+ }
+
+ /**
+ **Add an element to the list - causes sorting
+ **
+ ** @param o The element to add
+ **/
+ public void add(Object o) {
+ list.addElement(o);
+ Node tmp = (Node) o;
+ int min = tmp.heuristic + tmp.cost;
+ int i;
+ int index = 0;
+ /* Move the Node with minimum cost to the first position */
+ for(i = 0; i < list.size(); i++) {
+ if(min > totalCost(list.elementAt(i))) {
+ min = totalCost(list.elementAt(i));
+ index = i;
+ }
+ }
+
+ if(index < 0 || index >=list.size()) {
+ System.printString("Illegal SortedList.add\n");
+ System.exit(-1);
+ return;
+ }
+
+ Object temp = list.elementAt(0);
+ list.setElementAt(list.elementAt(index),0);
+ list.setElementAt(temp, index);
+ }
+
+ /**
+ **@return fixed cost + heuristic cost
+ **/
+ public int totalCost(Object o) {
+ Node tmp = (Node) o;
+ int cost = tmp.getHeuristic() + tmp.getCost();
+ return cost;
+ }
+
+
+ /**
+ ** Remove an element from the list
+ **
+ ** @param o The element to remove
+ **/
+ public void remove(Object o) {
+ list.remove(o);
+ }
+
+ /**
+ ** Get the number of elements in the list
+ **
+ ** @return The number of element in the list
+ **/
+ public int size() {
+ return list.size();
+ }
+
+ /**
+ ** Check if an element is in the list
+ **
+ ** @param o The element to search for
+ ** @return True if the element is in the list
+ **/
+ public boolean contains(Object o) {
+ return list.contains(o);
+ }
+
+ /**
+ ** Only for Debugging by printing contents of openlist
+ **/
+ public void debugOpenList() {
+ for(int i=0; i<list.size(); i++) {
+ Node n = (Node) list.elementAt(i);
+ System.print("Element "+i+": n.getX()= "+n.getX()+" n.getY()= "+n.getY()+ "\n");
+ }
+ System.printString("\n");
+ }
+}
**/
public class Path {
/** The list of steps building up this path */
- private Vector steps = new Vector();
+ private Vector steps;
/**
- * * Create an empty path
- * */
+ ** Create an empty path
+ **/
public Path() {
-
+ steps = new Vector();
}
/**
** @return The step information, the position on the map.
**/
public Step getStep(int index) {
- return (Step) steps.get(index);
+ return (Step) steps.elementAt(index);
}
/**
** @param y The y coordinate of the new step
**/
public void appendStep(int x, int y) {
- steps.add(new Step(x,y));
+ steps.addElement(new Step(x,y));
}
/**
** @param y The y coordinate of the new step
**/
public void prependStep(int x, int y) {
- steps.add(0, new Step(x, y));
+ steps.insertElementAt(new Step(x, y), 0);
}
/**
return steps.contains(new Step(x,y));
}
+}
+
+/**
+ ** A single step within the path
+ **/
+class Step {
+ /** The x coordinate at the given step */
+ private int x;
+ /** The y coordinate at the given step */
+ private int y;
+
/**
- ** A single step within the path
+ ** Create a new step
**
- ** @author Kevin Glass
+ ** @param x The x coordinate of the new step
+ ** @param y The y coordinate of the new step
**/
- public class Step {
- /** The x coordinate at the given step */
- private int x;
- /** The y coordinate at the given step */
- private int y;
-
- /**
- ** Create a new step
- **
- ** @param x The x coordinate of the new step
- ** @param y The y coordinate of the new step
- **/
- public Step(int x, int y) {
- this.x = x;
- this.y = y;
- }
-
- /**
- ** Get the x coordinate of the new step
- **
- ** @return The x coodindate of the new step
- **/
- public int getX() {
- return x;
- }
+ public Step(int x, int y) {
+ this.x = x;
+ this.y = y;
+ }
- /**
- ** Get the y coordinate of the new step
- **
- ** @return The y coodindate of the new step
- **/
- public int getY() {
- return y;
- }
+ /**
+ ** Get the x coordinate of the new step
+ **
+ ** @return The x coodindate of the new step
+ **/
+ public int getX() {
+ return x;
+ }
- /**
- ** @see Object#hashCode()
- **/
- public int hashCode() {
- return x*y;
- }
+ /**
+ ** Get the y coordinate of the new step
+ **
+ ** @return The y coodindate of the new step
+ **/
+ public int getY() {
+ return y;
+ }
- /**
- ** @see Object#equals(Object)
- **/
- public boolean equals(Object other) {
- if (other instanceof Step) {
- Step o = (Step) other;
+ /**
+ ** Same as Object#hashCode()
+ **/
+ public int hashCode() {
+ return x*y;
+ }
- return (o.x == x) && (o.y == y);
+ /**
+ ** Same as Object#equals(Object)
+ **
+ **/
+ public boolean equals(Object other) {
+ if (other instanceof Step) {
+ Step o = (Step) other;
+ if((o.x == x) && (o.y == y)) {
+ return true;
}
-
- return false;
}
+ return false;
}
}
-
+/**
+ ** An object representing the entity in the game that
+ ** is going to moving along the path. This allows us to pass around entity/state
+ ** information to determine whether a particular tile is blocked, or how much
+ ** cost to apply on a particular tile.
+ **
+ ** a) Saves the current X and Y coordinates for a Player
+ ** b) Saves the destination goalX and goalY
+ ** c) Determines the boundary using high/low X and Y coordinates for
+ ** the current position
+ ** d) Keeps track of the STATE of the player
+ **/
public class Player {
private int type;
private int x;
private int id;
private int lowx, highx;
private int lowy, highy;
-
- public Player(int type) {
- this.type = type;
- x = -1;
- y = -1;
- id = -1;
- }
+ private int state;
+ private int goalx, goaly;
public Player(int type, int x, int y) {
this.type = type;
if (lowy <= 0)
lowy = 1;
if (highx >= rows)
- highx = rows-1;
+ highx = rows-2;
if (highy >= cols)
- highx = cols-1;
+ highy = cols-2;
+ }
+
+ public void reset(int row, int col, int bounds) {
+ int seed = x + y;
+ Random rand = new Random(seed);
+ x = (rand.nextInt(Math.abs(row - 2) + 1)) + 1;
+ y = (rand.nextInt(Math.abs(col - 2) + 1)) + 1;
+ goalx = -1;
+ goaly = -1;
+ setBoundary(bounds, row, col);
}
+ public void setBoundary(int bounds, int rows, int cols) {
+ lowx = x - bounds;
+ highx = x + bounds;
+ lowy = y - bounds;
+ highy = y + bounds;
+ // define new boundaries
+ if (lowx <= 0)
+ lowx = 1;
+ if (lowy <= 0)
+ lowy = 1;
+ if (highx >= rows-1)
+ highx = rows-2;
+ if (highy >= cols-1)
+ highy = cols-2;
+ return;
+ }
+
+ /**
+ ** @return if Player is lumberjack or a planter
+ **/
public int kind() {
return type;
}
+ /**
+ ** Sets the X and Y coordinate of the Player
+ **/
public void setPosition(int x, int y) {
this.x = x;
this.y = y;
- return;
+ }
+
+ public void setNewPosition(int x, int y, int row, int col, int bounds) {
+ setPosition(x, y);
+ setBoundary(bounds, row, col);
+ goalx = -1;
+ goaly = -1;
}
public int getX() {
return y;
}
- public int getId() {
- return id;
+ /** Sets state of the Player **/
+
+ public void setState(int state) {
+ this.state = state;
+ return;
}
-}
+ public int getState() {
+ return this.state;
+ }
+
+ /** Randomly finds a goal in a given boundary for player
+ ** @return 0 on success and -1 when you cannot find any new goal
+ **/
+ public int findGoal(GameMap[][] land) {
+ /* Try setting the goal for try count times
+ * if not possible , then select a completely new goal
+ */
+ int trycount = (highx - lowx) + (highy - lowy);
+ int i;
+ for (i = 0; i < trycount; i++) {
+ Random rand = new Random(i);
+ int row = (rand.nextInt(Math.abs(highx - lowx)) + 1) + lowx;
+ int col = (rand.nextInt(Math.abs(highy - lowy)) + 1) + lowy;
+ if (type == 1 && (land[row][col].hasTree() == false) && (land[row][col].hasRock() == false)) {
+ goalx = row;
+ goaly = col;
+ return 0;
+ }
+ if (type == 0 && (land[row][col].hasTree() == true) && (land[row][col].hasRock() == false)) {
+ goalx = row;
+ goaly = col;
+ return 0;
+ }
+ }
+ if (i == trycount) {
+ /* System.println("Timeout trying ... \n") Only for Debugging */
+ }
+ return -1;
+ }
+
+ public void setGoal(int x, int y) {
+ goalx = x;
+ goaly = y;
+ }
+
+ public int getGoalX() {
+ return goalx;
+ }
+
+ public int getGoalY() {
+ return goaly;
+ }
+
+ /**
+ ** Only for debugging
+ **/
+ public debugPlayer() {
+ System.println("State= "+ state+ " Curr X= "+ x + " Curr Y= " + y + " Goal X= "+ goalx + " Goal Y= "+ goaly + " Type = " + type + "\n");
+ }
+
+ /**
+ ** @return true if reached the goal else return false
+ **/
+ public boolean atDest() {
+ if (x == goalx && y == goaly) {
+ return true;
+ }
+ return false;
+ }
+}
-#define ROW 10 /* columns in the map */
-#define COLUMN 10 /* rows of in the map */
-#define ROUNDS 100 /* Number of moves by each player */
-#define PLAYERS 20 /* Number of Players when num Players != num of client machines */
-#define RATI0 0.5 /* Number of lumberjacks to number of planters */
-#define BLOCK 3 /* Area around the gamer to consider */
-#define TREE_ZONE 0.4 /* Max percentage of trees in a zone */
+#define ROW 7 /* columns in the map */
+#define COLUMN 7 /* rows of in the map */
+#define ROUNDS 20 /* Number of moves by each player */
+#define PLAYERS 20 /* Number of Players when num Players != num of client machines */
+#define RATI0 0.5 /* Number of lumberjacks to number of planters */
+#define BLOCK 3 /* Area around the gamer to consider */
+#define TREE_ZONE 0.4 /* Max percentage of trees in a zone */
+#define AGEUPDATETHRESHOLD 2 /* How frequently/how many rounds to increment age of tree */
+#define MAXAGE 100 /* Max age of a tree */
-#define LUMBERJACK 0
-#define PLANTER 1
+
+#define LUMBERJACK 0 /* If lumberjack */
+#define PLANTER 1 /* If a tree planter */
+
+#define INIT 0 /* Initial state */
+#define MOVING 1 /* When moving along the map */
public class RainForest extends Thread {
- GameMap land;
+ /**
+ * The grid where player is playing
+ **/
+ GameMap[][] land;
+
+ /**
+ * The gamer per thread: shared array where players do not see each other
+ **/
Player gamer;
- public RainForest(GameMap land, Player gamer) {
+ /**
+ ** The shared BarrierServer object updated when trees increment age
+ ** only updated by one thread running server
+ **/
+ BarrierServer barrserver;
+
+ /**
+ * The thread id involved
+ **/
+ int threadid;
+
+ /**
+ * The total number of threads
+ **/
+ int numThreads;
+
+
+ public RainForest() {
+
+ }
+
+ public RainForest(GameMap[][] land, Player gamer, BarrierServer barrserver, int threadid, int numThreads) {
this.land = land;
this.gamer = gamer;
+ this.threadid = threadid;
+ this.barrserver = barrserver;
+ this.numThreads = numThreads;
}
public void run() {
- // For N interations do one move and synchronise
- System.println("Start run\n");
+ //Do N rounds
+ //do one move per round and synchronise
Barrier barr;
- barr = new Barrier("128.196.136.162");
+ int id;
+ atomic {
+ id = threadid;
+ }
+ barr = new Barrier("128.195.136.162");
for(int i = 0; i<ROUNDS; i++) {
atomic {
doOneMove(land, gamer);
}
Barrier.enterBarrier(barr);
+ if((i%AGEUPDATETHRESHOLD) == 0 && id == 0) {
+ /* Update age of all trees in a Map */
+ atomic {
+ barrserver.updateAge(land, MAXAGE, ROW, COLUMN);
+ }
+ }
}
- System.println("End of run\n");
}
public static void main(String[] args) {
- int numThreads= 1;
+ // Parse args get number of threads
+ RainForest tmprf = new RainForest();
+ RainForest.parseCmdLine(args, tmprf);
+ int numThreads= tmprf.numThreads;
BarrierServer mybarr;
int[] mid = new int[8];
mid[6] = (128<<24)|(195<<16)|(136<<8)|168;//dc-7
mid[7] = (128<<24)|(195<<16)|(136<<8)|169;//dc-8
+
// Init land and place rocks in boundaries
GameMap[][] world;
atomic {
RockType r = global new RockType();
world[i][j].putRock(r);
}
- }
- if (i == 0 || i == ROW-1) {
- RockType r = global new RockType();
- world[i][j].putRock(r);
+ if (i == 0 || i == ROW-1) {
+ RockType r = global new RockType();
+ world[i][j].putRock(r);
+ }
}
}
}
mybarr.start(mid[0]);
// Create P players
- // Parse args get number of threads
// For each thread, init either a lumberjack/planter
Player[] players;
atomic {
players = global new Player[numThreads];
for (int i = 0; i < numThreads; i++) {
Random rand = new Random(i);
- int row = rand.nextInt(ROW-1);
- int col = rand.nextInt(COLUMN-1);
- int type = rand.nextInt(1);
+ /* Generate random numbers between 1 and row index/column index*/
+ int maxValue = ROW - 1;
+ int minValue = 1;
+ int row = (rand.nextInt(Math.abs(maxValue - minValue) + 1)) + minValue;
+ maxValue = COLUMN -1;
+ int col = (rand.nextInt(Math.abs(maxValue - minValue) + 1)) + minValue;
+ int type = rand.nextInt(2);
int person;
if (type == 0) {
person = LUMBERJACK;
}
}
- // Set up threads
+ /* Set up threads */
RainForest[] rf;
atomic {
rf = global new RainForest[numThreads];
for(int i=0; i<numThreads; i++) {
Random rand = new Random(i);
- int row = rand.nextInt(ROW-1);
- int col = rand.nextInt(COLUMN-1);
- rf[i] = global new RainForest(world[row][col], players[i]);
+ rf[i] = global new RainForest(world, players[i], mybarr, i, numThreads);
}
}
+ /* Barrier Server waits for messages */
boolean waitforthreaddone = true;
while(waitforthreaddone) {
atomic {
}
}
- RainForest tmp;
/* Start threads */
+ RainForest tmp;
for(int i = 0; i<numThreads; i++) {
atomic {
tmp = rf[i];
}
tmp.join();
}
-
System.printString("Finished\n");
-
}
- //TODO
- public void doOneMove(GameMap land, Player mover) {
+ public void doOneMove(GameMap[][] land, Player gamer) {
// 1. Get start(x, y) position of the player
+ int currx = gamer.getX();
+ int curry = gamer.getY();
+
+ // Only for Debugging
+ /* printLand(land, ROW, COLUMN); */
+
// 2. Get type of player (lumberjack or planter)
- // 3. Check if you have a goal(tx,ty)
- // a.If yes
- // check retvalue = run A* from my location to goal(tx,ty)
- // if retvalue = empty
- // pick new goal
- // go to 3
- // i.e wait here
- // go to next round
- // else {
- // if planter
- // check if you are at goal
- // if yes
- // can you plant tree there? i.e. 40% of block around is not full and there is no tree there
- // if yes
- // plant tree
- // reset start(x, y) to goal(tx, ty) position
- // set goal to empty
- // continue to next round
- // if no
- // reset start(x, y) to goal(tx, ty) position
- // set goal = pick new goal
- // go to 3
- // if no
- // move one step i.e. update player position
- // continue to next round
- // if lumberjack
- // check if you are at goal
- // if yes
- // can you cut tree(i.e. Tree present at that location)
- // if yes
- // cut tree
- // set start(x,y) to goal(tx, ty) position
- // set goal to empty
- // continue to next round
- // if no
- // reset start(x,y) to goal coordinates(tx,ty)
- // set goal = pick new goal
- // go to 3
- // if no
- // move one step i.e, update player position
- // continue to next round
- // }
- // b.If no
- // pick new goal
- // go to 3
+ int type = gamer.kind();
+
+ if (gamer.getState() == INIT) {
+
+ if (gamer.findGoal(land) < 0) {
+ gamer.reset(ROW, COLUMN, BLOCK);
+ return;
+ }
+ gamer.setState(MOVING);
+ /* gamer.debugPlayer(); Only for debugging */
+ }
+
+ if (gamer.getState() == MOVING) {
+ Goal nextmove = new Goal();
+
+ int maxSearchDistance = 10;
+ boolean allowDiagMovement = true;
+ AStarPathFinder apath = new AStarPathFinder(land, maxSearchDistance, allowDiagMovement, ROW, COLUMN);
+ Path newpath = apath.findPath(gamer);
+
+ /* Reset state if there in no path from src to destination */
+ if(newpath == null) {
+ gamer.reset(ROW, COLUMN, BLOCK);
+ gamer.setState(INIT);
+ return;
+ }
+
+ nextmove.setXY(newpath.getX(0), newpath.getY(0));
+ gamer.setPosition(nextmove.getX(), nextmove.getY());
+ currx = gamer.getX();
+ curry = gamer.getY();
+ if (gamer.atDest()) {
+ if (gamer.kind() == LUMBERJACK) {
+ //If tree present, cut
+ if (land[currx][curry].hasTree()) {
+ land[currx][curry].cutTree();
+ }
+ gamer.setNewPosition(currx, curry, ROW, COLUMN, BLOCK);
+ gamer.setState(INIT);
+ } else { // PLANTER
+ // If empty, plant tree
+ if (land[currx][curry].hasTree() == false) {
+ if(hasMoreTrees(land, currx, curry) == false) {
+ TreeType t = global new TreeType();
+ land[currx][curry].putTree(t);
+ }
+ }
+ gamer.setNewPosition(currx, curry, ROW, COLUMN, BLOCK);
+ gamer.setState(INIT);
+ }
+ }
+ // Not at destination - do nothing
+ /* Debug -> gamer.debugPlayer(); */
+ return;
+ }
}
- public int pickNewGoalX(Player mover) {
- //Randomly generate goal
- Random rand = new Random(mover.x);
- int row = rand.nextInt(ROW-1);
- //int col = rand.nextInt(COLUMN-1);
- return row;
+ /**
+ ** Only for Debugging
+ **/
+ public void printLand(GameMap[][] land, int row, int col) {
+ for (int i = 0; i < row; i++) {
+ for (int j = 0; j < col; j++) {
+ land[i][j].print();
+ }
+ System.println("");
+ }
+ }
+
+ /**
+ * Parse the command line options.
+ **/
+ public static void parseCmdLine(String args[], RainForest rf) {
+ int i = 0;
+ String arg;
+ while(i < args.length && args[i].startsWith("-")) {
+ arg = args[i++];
+ //check options
+ if(arg.equals("-N")) {
+ if(i < args.length) {
+ rf.numThreads = new Integer(args[i++]).intValue();
+ }
+ } else if(arg.equals("-h")) {
+ rf.usage();
+ }
+ }
+
+ if(rf.numThreads == 0)
+ rf.usage();
+ }
+
+ /**
+ * The usage routine which describes the program options.
+ **/
+ public void usage() {
+ System.println("usage: ./RainForestN.bin master -N <threads>\n");
+ System.printString(" -N the number of threads\n");
+ System.printString(" -h help with usage\n");
}
- public int pickNewGoalY(Player mover) {
- //Randomly generate goal
- Random rand = new Random(mover.y);
- int col = rand.nextInt(COLUMN-1);
- return col;
+ /**
+ ** Check the number of trees in a given area
+ ** @return true if area covered more than the zone for trees
+ **/
+ public boolean hasMoreTrees(GameMap[][] land, int x, int y) {
+ int lowx = x - BLOCK;
+ int highx = x + BLOCK;
+ int lowy = y - BLOCK;
+ int highy = y + BLOCK;
+ // define new boundaries
+ if (lowx <= 0)
+ lowx = 1;
+ if (lowy <= 0)
+ lowy = 1;
+ if (highx >= ROW-1)
+ highx = ROW-2;
+ if (highy >= COLUMN-1)
+ highy = COLUMN-2;
+ int treeCount = 0;
+ int areaCount = 0;
+ for(int i = lowx; i < highx; i++) {
+ for(int j = lowy; j < highy; j++) {
+ if(land[i][j].tree != null)
+ treeCount++;
+ areaCount++;
+ }
+ }
+ if(treeCount > (TREE_ZONE * areaCount)) {
+ return true;
+ }
+ return false;
}
}
+/**
+ ** Rock and its properties
+ **/
public class RockType {
- private char color;
public RockType() {
- color = (char)0;
- }
-
- public RockType(char color) {
- this.color = color;
- }
-
- public char getColor() {
- return color;
}
}
+/**
+ ** Tree and its properties
+ **/
public class TreeType {
private int age;
return age;
}
- public void incrementAge() {
+ public void incrementage() {
age++;
}
+
+ public void incrementTenYrs() {
+ age = age + 10;
+ }
+
+ public void incrementFiveYrs() {
+ age = age + 5;
+ }
}
#!/bin/sh
lines=$(grep -n "#" tmp1RainForest.java | cut -d: -f1 | sed '1q')
-sed '/#/d' tmp1RainForest.java > tmpRainForest.java
+sed '/^#/d' tmp1RainForest.java > tmpRainForest.java
GameMap.java \
RockType.java \
Barrier.java \
- Goal.java
+ Goal.java \
+ Path.java \
+ Node.java \
+ AStarPathFinder.java
-FLAGS1=-dsm -optimize -mainclass ${MAINCLASS}
+FLAGS1=-dsm -nooptimize -debug -mainclass ${MAINCLASS}
FLAGS2=-dsm -dsmcaching -optimize -mainclass ${MAINCLASS}
FLAGS3=-dsm -dsmcaching -prefetch -optimize -mainclass ${MAINCLASS} -trueprob 0.90
FLAGS4=-dsm -dsmcaching -rangeprefetch -optimize -mainclass ${MAINCLASS} -trueprob 0.90
cpp ${MAINCLASS}.java > tmp1${MAINCLASS}.java
./extractLines
../../../../buildscript ${FLAGS1} -o ${MAINCLASS}NPNC ${SRC}
+ ../../../../buildscript ${FLAGS3} -o ${MAINCLASS}N ${SRC}
clean:
rm -rf tmpbuilddirectory
projects / IRC.git / commitdiff