// Genetic Ant Algorithm // Carl E. Bredlau // from Koza, _Genetic Programming_, MIT Press // programmed modeled after sga. Thanks to the author. // 1-30-01 Added setCanvas(Canvas c) since Pegasus complained // The board for the ant package geneticAnt; import java.awt.*; public class Board implements Cloneable { private Canvas board_canvas = null; // for graphic display int size; // size of board in pixels int grid; // size of one square in pixels // What's on a square: public static final int EMPTY = 0; public static final int FOOD = 1; // Food is here public static final int WALKED = 2; // Ant walked here public static final int EATEN = 4; // Ant walked here and eaten public static final int PCT = 100; // For random selection public static final int PLACE = 75; // 75% give food public static final int DIR = 25; // change direction 25% public static final int FLIP = 50; // flip public static final int NORTH = 0; public static final int EAST = 1; public static final int SOUTH = 2; public static final int WEST = 3; // Moves: public static final int MOVE = Chromosome.MOVE; // move foward public static final int LEFT = Chromosome.LEFT; // turn left public static final int RIGHT = Chromosome.RIGHT; // move right public static final int NOP = Chromosome.NOP; // does nothing // Constants for food being seen: public static boolean IS_FOOD = true; int[][] square; // the board int [] pos = {0,0}; // (x,y) position of ant on the board boolean placed = false; // for display int dir = SOUTH; // which way the ant is facing public Board(int board_size) { // Put food in a path along the board IntRandom r = new IntRandom(PCT); // to generate food boolean prev = false; // previous has food? square = new int[board_size][board_size]; for (int i = 0; i < board_size; i++) // i heads SOUTH for (int j = 0; j < board_size; j++) square[i][j] = EMPTY; int i = 1, j = board_size / 2; int which = SOUTH; // start going south while (i < board_size) { if (!prev ||( r.nextInt() < PLACE)) { // if prev empty, place food square[i][j] = FOOD; prev = true; } else prev = false; switch (which) { // move down a square case SOUTH : i++; break; case EAST : j++; if (j >= board_size) { // off the edge? j--; i++; which = SOUTH; } break; case WEST : j--; if (j < 0) { // off the edge? j++; i++; which = SOUTH; } } // switch if (r.nextInt() < DIR) // change direction? switch (which) { case SOUTH : if (r.nextInt() < FLIP) which = EAST; else which = WEST; break; case EAST : case WEST : which = SOUTH; } } // while } public Board(int board_size, Canvas canvas) { this(board_size); board_canvas = canvas; size = board_canvas.getSize().height; grid = size/square.length; } private int[] nextSquare() { // what the next square should be, but must worry about // walking off the edge of the board. If you do, stay where you are int x = pos[0], y = pos[1]; switch (dir) { case NORTH : if (x > 0) x--; break; case SOUTH : x++; if (x == square.length) x--; break; case EAST : y++; if (y == square.length) y--; break; case WEST : if (y > 0) y--; break; } int[] w = {x,y}; return w; } public boolean isFood() { int[] food_pos = nextSquare(); // If walk off stay where you are. // There is no food. int x = food_pos[0], y = food_pos[1]; return square[x][y] == Board.FOOD; } public void place() { // put ant on the board int[] pos = { 0, square.length / 2}; this.pos = pos; dir = Board.SOUTH; square[pos[0]][pos[1]] = WALKED; } public int moveAnt(int ant_move) { Graphics g; int oldpos[] = new int[2]; // for display oldpos[0] = pos[0]; oldpos[1] = pos[1]; int olddir = dir; int food = EMPTY; // initialize return value // Move ant. Return FOOD if there was some switch(ant_move) { case MOVE: pos = nextSquare(); break; case LEFT: if (dir == NORTH) dir = WEST; else dir--; break; case RIGHT: if (dir == WEST) dir = NORTH; else dir++; break; case NOP: break; } int x = pos[0], y = pos[1]; switch (square[x][y]) { case EMPTY: square[x][y] = WALKED; // if (board_canvas != null) { // Graphics Xor // g = board_canvas.getGraphics(); // g.setColor(Color.cyan); // g.fillOval(grid*y,grid*x,grid/2,grid/2); // } break; case FOOD: square[x][y] = EATEN; food = FOOD; // if (board_canvas != null) { // Graphics Xor // g = board_canvas.getGraphics(); // g.setColor(Color.blue); // g.fillRect(grid*y,grid*x,grid,grid); // g.setColor(Color.yellow); // g.fillOval(grid*y,grid*x,grid*2/3,grid*2/3); // } // fall through... case WALKED: case EATEN: break; } if (board_canvas != null) { // do we show it? int oldx = oldpos[0], oldy = oldpos[1]; // System.out.println("Trying to show the canvas"); if((oldx != x) || (oldy != y) || (olddir != dir)) { g = board_canvas.getGraphics(); /* For using Xor mode g.setXORMode(Color.white); if (placed) g.drawPolygon(Arrow.create(oldpos,grid,olddir)); // g.fillPolygon(Arrow.create(oldpos,grid,olddir)); g.drawPolygon(Arrow.create(pos,grid,dir)); g.fillPolygon(Arrow.create(pos,grid,dir)); try { Thread.sleep(1000);} catch (InterruptedException e) {} ; g.setPaintMode(); */ if (placed) { // redraw the square g.setColor(Color.blue); g.fillRect(grid*oldy,grid*oldx,grid,grid); switch (square[oldx][oldy]) { case WALKED : g.setColor(Color.cyan); g.fillOval(grid*oldy,grid*oldx,grid/2,grid/2); break; case EATEN : g.setColor(Color.yellow); g.fillOval(grid*oldy,grid*oldx,grid*2/3,grid*2/3); } } // try { Thread.sleep(525);} catch (InterruptedException e) {} ; g.setColor(Color.blue); g.fillRect(grid*y,grid*x,grid,grid); g.setColor(Color.white); g.fillPolygon(Arrow.create(pos,grid,dir)); placed = true; try { Thread.sleep(25);} catch (InterruptedException e) {} ; g.dispose(); } } return food; } public Object clone() { //try public insteand of protected... // The only thing we need to worry about is the board. Board b; try { b = (Board) super.clone(); /* I'm getting access errors ... b.square = (int[][]) square.clone(); // this only clones a list of pointers, so... for (int i = 0; i < b.square.length; i++) b.square[i] = (int []) this.square[i].clone(); */ int b_size = this.square.length; b.square = new int[b_size][b_size]; for (int i = 0; i < b_size; i++) for (int j = 0; j < b_size; j++) b.square[i][j] = this.square[i][j]; } catch (CloneNotSupportedException e) { // cannot happen so throw new InternalError(e.toString()); } return b; } public static String dirToDisplay(int dir) { String str = null; switch(dir) { case NORTH: str = "North"; break; case EAST : str = "East "; break; case SOUTH: str = "South"; break; case WEST : str = "West "; break; } return str; } public void show() { if (board_canvas == null) { // command line System.out.println("Ant is at (" + pos[0] + "," + pos[1] + ") Ant is facing " + dirToDisplay(dir)); for (int i = 0; i < square.length; i++) { for (int j = 0; j < square.length; j++) { switch(square[i][j]) { case(EMPTY ) : System.out.print(" "); break; case(FOOD ) : System.out.print("* "); break; case(WALKED) : System.out.print("# "); break; case(EATEN ) : System.out.print("+ "); break; } } System.out.println(); } } else { // graphics display board_canvas.repaint(); // clean out -- repaint calls update which // cleans out the screen. But we have to wait. try { Thread.sleep(100);} catch (InterruptedException e) {} ; Graphics g = board_canvas.getGraphics(); for (int i = 0; i < square.length; i++) { for (int j = 0; j < square.length; j++) { switch(square[i][j]) { case(EMPTY ) : break; case(FOOD ) : g.setColor(Color.white); // the board had i going down and j across g.fillOval(grid*j,grid*i,grid-2,grid-2); break; case(WALKED) : g.setColor(Color.cyan); g.fillOval(grid*j,grid*i,grid/2,grid/2); break; case(EATEN ) : g.setColor(Color.yellow); g.fillOval(grid*j,grid*i,grid*2/3,grid*2/3); break; } } } g.dispose(); } } public void setCanvas(Canvas c) {board_canvas = c;}; // Somehow the browser on Pegasus complains about accessing the // board. So I made it private and added this method public static void main(String args[]) { Board b1 = new Board(10); Board b2 = (Board) b1.clone(); // test to see if cloned... b1.square[0][0] = EATEN; b2.square[0][1] = WALKED; System.out.println("1 2 3 4 5 6 7 8 9 10"); b1.show(); System.out.println("**********"); b2.show(); } }