[Commit]
RRbot RicochetRecursive.java,NONE,1.1 Node.java,1.1.1.1,1.2
Ricochet.java,1.3,1.4
Adam Ingram-Goble
commit at keithp.com
Tue Jun 10 00:03:21 PDT 2003
- Previous message: [Commit]
fontconfig/debian compat,NONE,1.1 rules,1.3,1.4 control,1.2,1.3
changelog,1.4,1.5 rocks,1.2,NONE
- Next message: [Commit] RRbot RicochetRecursive.java,1.1,1.2
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Committed by: adamaig
Update of /local/src/CVS/RRbot
In directory home.keithp.com:/tmp/cvs-serv19254
Modified Files:
Node.java Ricochet.java
Added Files:
RicochetRecursive.java
Log Message:
--- NEW FILE: RicochetRecursive.java ---
/* RicochetRecursive.java
**
** Christian Platt, Adam Ingram-Goble
** CS543
**
**
** uses:
**
*/
import java.io.*;
import java.net.*;
import java.lang.*;
import java.util.*;
public class RicochetRecursive {
public static Robot [] robots;
public static Board board;
public static Node newNode;
public static int goalRotation;
public static int goalRow;
public static int goalCol;
// IDA*
public static int c;
public static int cprime;
public static int INFINITY = 100000;
public static Stack nodeStack;
//transposition table
public static TranspositionTable stopT;
// All Pairs Shortest Path
public static int [][] costMatrix;
public static int [][] distMatrix;
public static int goalMatrixPos;
//node count
public static long totalNodes = 0;
public static long prunedNodes = 0;
public static long removedNodes = 0;
public static void main ( String args[] ) {
board = new Board();
robots = new Robot[4];
nodeStack = new Stack ( );
stopT = new TranspositionTable( 4, 16, 16 );
int numArgs = args.length;
if ( args.length != 0 ) {
//parseArgs ( args );
readInBoard();
} else {
getData();
}
//readInBoard();
//System.out.println( board.toString() );
//System.exit(1);
calcAllPairsShortestPath();
Node n = new Node( 0, 0, "" );
//store the robots original postions in this first node
for ( int i=0; i < 4; i++ ) {
n.placeRobot( i, robots[i].rpos(), robots[i].cpos() );
}
System.out.println( board.toString() );
// set goal base's matrix position
goalMatrixPos = (goalRow * 16) + goalCol;
n = new Node( 0, 0, "" );
//store the robots original postions in this first node
for ( int i=0; i < 4; i++ ) {
n.placeRobot( i, robots[i].rposOrig, robots[i].cposOrig );
}
for( int idx = 1; idx < 12; ++idx ) {
if( 0 != IDAstar( 0, idx, n ) ) {
break;
}
System.out.println( "Nodes searched = " + totalNodes
+ "\tstopT size = " + stopT.size()
+ "\tprunedNodes = " + prunedNodes
+ "\tremovedNodes = " + removedNodes );
prunedNodes = removedNodes = 0;
stopT.clear();
}
System.out.println( "Nodes searched = " + totalNodes
+ "\tstopT size = " + stopT.size()
+ "\tprunedNodes = " + prunedNodes
+ "\tremovedNodes = " + removedNodes );
}
// main search function
public static int IDAstar ( int curDepth, int maxDepth, Node curNode ) {
totalNodes++;
if( curDepth == maxDepth ) {
return 0;
}
curDepth++;
int g = curDepth + 1;
int h = 0;
//generate all possible moves
for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
//store current robot location
int oldRow = robots[i].rpos();
int oldCol = robots[i].cpos();
// attempt to make the move
if ( board.makeMove( robots[i], j ) != 1 ) {
continue;
}
//add move to move string
String newMoves = new String( curNode.moves );
newMoves += i + "" + j;
// convert grid coordinates to matrix coordinates
int robMatrixPos = (int) (robots[0].rpos() * 16) + robots[0].cpos();
//check to see if it is a solution
if ( robMatrixPos == goalMatrixPos ) {
solutionFound( newMoves );
}
//calculate h for new node
h = (int) (1.5 * distMatrix[robMatrixPos][goalMatrixPos]);
//create a new node
newNode = new Node( g, h, newMoves );
// store robot's positions in the new node
for ( int k=0; k < 4; k++ ) {
newNode.placeRobot( k, robots[k].rpos(), robots[k].cpos() );
}
int rc = 0;
/*
if( 0 != ( rc = IDAstar( curDepth, maxDepth, newNode ) ) ) {
return rc;
}
*/
Long zkey = stopT.getKey( robots );
Node old = (Node) stopT.get( zkey );
boolean prune =
old != null &&
old.equals( newNode ) &&
old.g <= g;
if ( prune ) {
prunedNodes++;
board.takeBackMove ( robots[i], oldRow, oldCol, robots[i].rpos()
, robots[i].cpos() );
continue;
}
if ( old != null ) {
removedNodes++;
stopT.remove(zkey);
} else {
IDAstar( curDepth, maxDepth, newNode );
stopT.put( zkey, newNode );
}
// undo the move
board.takeBackMove ( robots[i], oldRow, oldCol, robots[i].rpos()
, robots[i].cpos() );
}
}
return 0;
}
public static void solutionFound( String newMoves ) {
System.out.println( "SOLUTION" );
String testString = "";
for (int c=0; c < newMoves.length(); c++ ) {
if ( (c % 2) == 0 && c != 0 ) {
System.out.print( " " );
testString += " ";
}
System.out.print( newMoves.charAt(c) );
testString += newMoves.charAt( c );
}
System.out.println();
System.out.println( "in " + newMoves.length() / 2 + " moves" );
System.out.println( "Nodes searched = " + totalNodes
+ "\tstopT size = " + stopT.size()
+ "\tprunedNodes = " + prunedNodes
+ "\tremovedNodes = " + removedNodes );
System.out.println( solToRRstr( newMoves ));
/*
String[] chckArgs = { "game2.gm", testString };
SolutionChecker.main( chckArgs );
*/
System.exit(1);
}
public static void calcAllPairsShortestPath ( ) {
costMatrix = new int [256][256];
distMatrix = new int [256][256];
for (int i=0; i < 256; ++i) {
for (int j=0; j < 256; ++j ) {
// convert vertice to grid coordinates
int row1 = i / 16;
int col1 = i % 16;
int row2 = j / 16;
int col2 = j % 16;
costMatrix[i][j] = board.calcEdge ( row1, col1, row2, col2 );
}
}
// Use Floyd's algorithm to calc all the shortest paths
for ( int i = 0; i < 256; ++i ) {
for ( int j = 0; j < 256; ++j ) {
distMatrix[i][j] = costMatrix[i][j];
}
distMatrix[i][i] = 0;
}
for ( int k = 0; k < 256; ++k ) {
for ( int i = 0; i < 256; ++i ) {
for ( int j = 0; j < 256; ++j ) {
if ( (distMatrix[i][k] + distMatrix[k][j]) < distMatrix[i][j] ) {
distMatrix[i][j] = distMatrix[i][k] + distMatrix[k][j];
}
}
}
}
return;
}
// This method is sent a string of mmoves in our representation and converts
// it to a string in the rrserver's format.
public static String solToRRstr ( String moves ) {
String RRsolution = "";
for ( int i=0; i < moves.length(); i++ ) {
// use this line to have robot colors output (only works if we read in
// a board from the rrserver
//RRsolution += robots[Integer.parseInt(moves.substring( i, i+1))].color;
// use this line to output the robot numbers instead (for our
// representation)
RRsolution += moves.charAt(i);
RRsolution += " ";
i++;
switch ( moves.charAt(i) ) {
case '0': RRsolution += "north";
break;
case '1': RRsolution += "east";
break;
case '2': RRsolution += "south";
break;
case '3': RRsolution += "west";
break;
}
RRsolution += " ";
}
return RRsolution;
}
// this method is only used for reading in a board from the rrserver and
// converting it to our internal representation
public static void readInBoard ( ) {
try {
InputStreamReader is = new InputStreamReader( System.in );
BufferedReader br = new BufferedReader( is );
String lineStr;
int robotNum = 1;
int rowPos = 0;
while ( (lineStr = br.readLine()) != null ) {
System.out.println( lineStr );
for ( int colPos =0; colPos < lineStr.length(); colPos++ ) {
switch ( lineStr.charAt(colPos) ) {
case '|':
//add blocker
board.addRowBlock( rowPos/3, colPos/3 );
break;
case 'y':
case 'g':
case 'r':
case 'b':
if ( lineStr.charAt(colPos) == lineStr.charAt(++colPos) ){
robots[robotNum] = new Robot ( rowPos/3, colPos/3
, lineStr.charAt(colPos));
board.placeRobot( (rowPos/3), (colPos/3), robotNum++);
}
break;
case '=':
//add blocker
board.addColBlock( rowPos/3, colPos/3 );
colPos++;
break;
case 'Y':
case 'G':
case 'R':
case 'B':
case 'W':
if ( lineStr.charAt(colPos) == lineStr.charAt(colPos+1) ){
robots[0] = new Robot ( rowPos/3, colPos/3
, lineStr.charAt(colPos));
board.placeRobot( (rowPos/3), (colPos/3), 0);
} else if ( lineStr.charAt(colPos+1) == 'S' ||
lineStr.charAt(colPos+1) == 'T' ||
lineStr.charAt(colPos+1) == 'C' ||
lineStr.charAt(colPos+1) == 'O' ||
lineStr.charAt(colPos+1) == 'W' ) {
board.placeGoal ( rowPos/3, colPos/3 );
goalRow = rowPos/3;
goalCol = colPos/3;
}
++colPos;
break;
}
}
++rowPos;
}
} catch ( IOException ioe ) {
System.out.println( "Input Error" + ioe );
}
return;
}
// Read in all the data from an external file and store it in
// the appropriate objects
public static void getData ( ) {
try {
InputStreamReader is = new InputStreamReader( System.in );
BufferedReader br = new BufferedReader( is );
StringTokenizer st;
String lineStr;
int row, col, rot;
int numCommentLines = 0;
int robotNum = 0;
int sideBlockers = 0;
boolean goalPlaced = false;
while ( (lineStr = br.readLine()) != null ) {
if ( lineStr.charAt( 0 ) != '#' ) {
st = new StringTokenizer( lineStr );
row = Integer.parseInt( st.nextToken() );
col = Integer.parseInt( st.nextToken() );
if ( numCommentLines >= 4 ) {
robots[robotNum] = new Robot ( row, col );
board.placeRobot( row, col, robotNum++ );
} else if ( numCommentLines >= 3 ) {
board.addBlocker( row, col, 0 );
} else if ( numCommentLines >= 2 ) {
rot = Integer.parseInt( st.nextToken() );
board.addBlocker( row, col, rot );
if ( goalPlaced == false ) {
board.placeGoal ( row, col );
goalPlaced = true;
goalRotation = rot;
goalRow = row;
goalCol = col;
}
}
} else {
numCommentLines++;
}
}
} catch ( IOException ioe ) {
System.out.println( "Input Error" + ioe );
}
return;
}
// Parses the optional command line arguments
public static void parseArgs ( String args[] ) {
int numArgs = args.length;
boolean err = false;
if ( err ) {
System.out.println( "Invalid usage." );
System.exit(1);
}
return;
}
}
Index: Node.java
===================================================================
RCS file: /local/src/CVS/RRbot/Node.java,v
retrieving revision 1.1.1.1
retrieving revision 1.2
diff -u -d -r1.1.1.1 -r1.2
--- Node.java 9 Jun 2003 02:43:58 -0000 1.1.1.1
+++ Node.java 10 Jun 2003 06:03:19 -0000 1.2
@@ -58,5 +58,15 @@
//System.out.println( robotLocations[num].row + " " + robotLocations[num].col );
}
-
+ public boolean equals( Node n ) {
+ for( int idx = 0; idx < 4; ++idx ) {
+ if( ! ( this.robotLocations[ idx ].row
+ == n.robotLocations[ idx ].row
+ && this.robotLocations[ idx ].col
+ == n.robotLocations[ idx ].col ) ) {
+ return false;
+ }
+ }
+ return true;
+ }
}
Index: Ricochet.java
===================================================================
RCS file: /local/src/CVS/RRbot/Ricochet.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -d -r1.3 -r1.4
--- Ricochet.java 9 Jun 2003 07:45:31 -0000 1.3
+++ Ricochet.java 10 Jun 2003 06:03:19 -0000 1.4
@@ -14,8 +14,6 @@
import java.lang.*;
import java.util.*;
-
-
public class Ricochet {
public static Robot [] robots;
public static Board board;
@@ -39,6 +37,8 @@
public static int goalMatrixPos;
+ public static int totalNodes = 0;
+
public static void main ( String args[] ) {
board = new Board();
robots = new Robot[4];
@@ -78,8 +78,6 @@
// set goal base's matrix position
goalMatrixPos = (goalRow * 16) + goalCol;
- //System.out.println( goalMatrixPos );
- //System.exit(1);
while (true) {
@@ -98,7 +96,6 @@
}
-
// main search function
public static int IDAstar ( ) {
String currMoves;
@@ -111,12 +108,10 @@
System.out.println( "Couldn't find a solution" );
System.exit(1);
}
-
c = cprime;
return 0;
}
- //System.out.println( nodeStack.size() );
Node n = (Node) nodeStack.pop();
currMoves = n.moves;
@@ -135,10 +130,15 @@
robots[r].move( n.robotLocations[r].row, n.robotLocations[r].col );
}
+ Long szkey = stopT.getKey( robots );
+ stopT.put( szkey, n );
+
//generate all possible moves
for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
-
+
+ totalNodes++;
+ System.out.println( "node = " + totalNodes );
/*
// Don't do a move that is just an inverse of the previous move
if ( currMoves.length() > 1 ) {
@@ -180,7 +180,6 @@
if ( robMatrixPos == goalMatrixPos ) {
System.out.println( "SOLUTION" );
String testString = "";
- //System.out.println( newMoves );
for (int c=0; c < newMoves.length(); c++ ) {
if ( (c % 2) == 0 && c != 0 ) {
System.out.print( " " );
@@ -201,44 +200,29 @@
//calculate h for new node
h = (int) (1.5 * distMatrix[robMatrixPos][goalMatrixPos]);
- //h = distMatrix[robMatrixPos][goalMatrixPos];
- //System.out.println( h + " " );
+ //create a new node
+ newNode = new Node( g, h, newMoves );
+ // store robot's positions in the new node
+ for ( int k=0; k < 4; k++ ) {
+ newNode.placeRobot( k, robots[k].rpos(), robots[k].cpos() );
+ }
Long zkey = stopT.getKey( robots );
- if( stopT.containsKey( zkey ) ) {
- Node old = (Node) stopT.get( zkey );
- //if( ! ( old.g > g
- //&& ( old.g + old.h > g + h ) ) ) {
- //System.out.println( old.g + " " + old.h );
- //System.out.println( newNode.g + " " + newNode.h );
- if ( old.g + old.h >= g + h ) {
-
- //create a new node
- newNode = new Node( g, h, newMoves );
- // store robot's positions in the new node
- for ( int k=0; k < 4; k++ ) {
- newNode.placeRobot( k, robots[k].rpos(), robots[k].cpos() );
- }
-
- stopT.put( zkey, newNode );
- } else {
- --g;
- board.takeBackMove ( robots[i], oldRow, oldCol, robots[i].rpos()
- , robots[i].cpos() );
- continue;
- }
-
- } else {
- //create a new node
- newNode = new Node( g, h, newMoves );
- // store robot's positions in the new node
- for ( int k=0; k < 4; k++ ) {
- newNode.placeRobot( k, robots[k].rpos(), robots[k].cpos() );
- }
- stopT.put( zkey, newNode );
+ Node old = (Node) stopT.get( zkey );
+ boolean prune =
+ old != null &&
+ old.equals( newNode ) &&
+ old.g <= g;
+ if ( prune ) {
+ --g;
+ board.takeBackMove ( robots[i], oldRow, oldCol, robots[i].rpos()
+ , robots[i].cpos() );
+ continue;
}
-
+ if ( old != null )
+ stopT.remove(zkey);
+
if ( (g + h) <= c ) {
nodeStack.push ( newNode );
} else if ( cprime > (g + h) ) {
@@ -270,16 +254,11 @@
// convert vertice to grid coordinates
int row1 = i / 16;
- //System.out.print( row1 + " " );
int col1 = i % 16;
- //System.out.print( col1 + " " );
int row2 = j / 16;
- //System.out.print( row2 + " " );
int col2 = j % 16;
- //System.out.print( col2 + " - " );
costMatrix[i][j] = board.calcEdge ( row1, col1, row2, col2 );
- //System.out.println( i + " " + j + " " + costMatrix[i][j] );
}
}
@@ -299,7 +278,6 @@
}
}
}
-
return;
}
@@ -336,7 +314,6 @@
return RRsolution;
}
-
// this method is only used for reading in a board from the rrserver and
// converting it to our internal representation
public static void readInBoard ( ) {
@@ -368,7 +345,6 @@
}
break;
-
case '=':
//add blocker
board.addColBlock( rowPos/3, colPos/3 );
@@ -396,24 +372,16 @@
}
++colPos;
break;
-
}
-
}
-
++rowPos;
}
-
-
} catch ( IOException ioe ) {
System.out.println( "Input Error" + ioe );
}
-
return;
-
}
-
// Read in all the data from an external file and store it in
// the appropriate objects
public static void getData ( ) {
@@ -437,12 +405,8 @@
if ( numCommentLines >= 4 ) {
robots[robotNum] = new Robot ( row, col );
board.placeRobot( row, col, robotNum++ );
-
} else if ( numCommentLines >= 3 ) {
-
board.addBlocker( row, col, 0 );
-
-
} else if ( numCommentLines >= 2 ) {
rot = Integer.parseInt( st.nextToken() );
@@ -468,7 +432,6 @@
return;
}
-
// Parses the optional command line arguments
public static void parseArgs ( String args[] ) {
- Previous message: [Commit]
fontconfig/debian compat,NONE,1.1 rules,1.3,1.4 control,1.2,1.3
changelog,1.4,1.5 rocks,1.2,NONE
- Next message: [Commit] RRbot RicochetRecursive.java,1.1,1.2
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the Commit
mailing list