From 1611e54bd80799778e2ab163f593070109902820 Mon Sep 17 00:00:00 2001 From: adash Date: Tue, 3 Mar 2009 10:05:41 +0000 Subject: [PATCH] Stable working version of the benchmark with AStar* algo --- .../RainForest/dsm/AStarPathFinder.java | 316 ++++++++++++++++++ .../Distributed/RainForest/dsm/Barrier.java | 21 ++ .../Distributed/RainForest/dsm/GameMap.java | 27 ++ .../Distributed/RainForest/dsm/Goal.java | 24 +- .../Distributed/RainForest/dsm/Node.java | 198 +++++++++++ .../Distributed/RainForest/dsm/Path.java | 115 ++++--- .../Distributed/RainForest/dsm/Player.java | 138 +++++++- .../RainForest/dsm/RainForest.java | 304 ++++++++++++----- .../Distributed/RainForest/dsm/RockType.java | 13 +- .../Distributed/RainForest/dsm/TreeType.java | 13 +- .../Distributed/RainForest/dsm/extractLines | 2 +- .../Distributed/RainForest/dsm/makefile | 8 +- 12 files changed, 995 insertions(+), 184 deletions(-) create mode 100644 Robust/src/Benchmarks/Distributed/RainForest/dsm/AStarPathFinder.java create mode 100644 Robust/src/Benchmarks/Distributed/RainForest/dsm/Node.java diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/AStarPathFinder.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/AStarPathFinder.java new file mode 100644 index 00000000..55f511d9 --- /dev/null +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/AStarPathFinder.java @@ -0,0 +1,316 @@ +/** + ** 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-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 maxage) { + land[i][j].tree = null; + } else { + land[i][j].tree.incrementFiveYrs(); + } + } + } + } + } + public void run() { int n; ServerSocket ss=new ServerSocket(2000); diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/GameMap.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/GameMap.java index 5e35b654..0168e0ef 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/GameMap.java +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/GameMap.java @@ -1,3 +1,10 @@ +/** + ** 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; @@ -29,10 +36,30 @@ public class GameMap { 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(". "); + } } diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/Goal.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/Goal.java index 0f44184d..7e03ac95 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/Goal.java +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/Goal.java @@ -1,27 +1,31 @@ +/** + ** 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; } } diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/Node.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/Node.java new file mode 100644 index 00000000..7c10bcdb --- /dev/null +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/Node.java @@ -0,0 +1,198 @@ +/** + ** 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= 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() { @@ -58,9 +104,75 @@ public class Player { 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; + } +} diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/RainForest.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/RainForest.java index 73b04b12..f5b0e1f6 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/RainForest.java +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/RainForest.java @@ -1,39 +1,88 @@ -#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 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 \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; } } diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/RockType.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/RockType.java index 315677b9..75989c13 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/RockType.java +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/RockType.java @@ -1,15 +1,8 @@ +/** + ** 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; } } diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/TreeType.java b/Robust/src/Benchmarks/Distributed/RainForest/dsm/TreeType.java index a4718cca..c13b981f 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/TreeType.java +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/TreeType.java @@ -1,3 +1,6 @@ +/** + ** Tree and its properties + **/ public class TreeType { private int age; @@ -9,7 +12,15 @@ public class TreeType { return age; } - public void incrementAge() { + public void incrementage() { age++; } + + public void incrementTenYrs() { + age = age + 10; + } + + public void incrementFiveYrs() { + age = age + 5; + } } diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/extractLines b/Robust/src/Benchmarks/Distributed/RainForest/dsm/extractLines index 0415dca7..aff1b586 100755 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/extractLines +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/extractLines @@ -1,3 +1,3 @@ #!/bin/sh lines=$(grep -n "#" tmp1RainForest.java | cut -d: -f1 | sed '1q') -sed '/#/d' tmp1RainForest.java > tmpRainForest.java +sed '/^#/d' tmp1RainForest.java > tmpRainForest.java diff --git a/Robust/src/Benchmarks/Distributed/RainForest/dsm/makefile b/Robust/src/Benchmarks/Distributed/RainForest/dsm/makefile index 5c823954..6b6c6995 100644 --- a/Robust/src/Benchmarks/Distributed/RainForest/dsm/makefile +++ b/Robust/src/Benchmarks/Distributed/RainForest/dsm/makefile @@ -5,9 +5,12 @@ SRC=tmp${MAINCLASS}.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 @@ -16,6 +19,7 @@ default: cpp ${MAINCLASS}.java > tmp1${MAINCLASS}.java ./extractLines ../../../../buildscript ${FLAGS1} -o ${MAINCLASS}NPNC ${SRC} + ../../../../buildscript ${FLAGS3} -o ${MAINCLASS}N ${SRC} clean: rm -rf tmpbuilddirectory -- 2.34.1