santafeants.java

aco algorithm for santafe trail

				System.out.print ( "  " + a.if_not_food_ahead[j] );
			}
			fitness = a.food*100/89;
			System.out.println( "    Food:  " + a.food + "   Fitness:   " + fitness + " %  " );
		}
	}
	
	
	
	//sort out the smart ants from the dumb ants order smart starting at 0 and dumb ones at end of array
	public void sort()
	{
		ArrayList<Ant> sorted = new ArrayList<Ant>();
		
		//prime loop
		sorted.add( ants[0] );
		
		for ( int i=1; i<max_ants; i++){
			
			int added = 0;
			int end = sorted.size()-1;

			for ( int j=0; j<end; j++){

				if ( ants[i].food >= sorted.get(j).food ) { 
					sorted.add( j, ants[i]); 
					added = 1;
					end = 0;
				}
			}
			if ( added == 0 ) { sorted.add ( ants[i] );   }
		}
				
		int total = 0;										
		for ( int i=0; i<max_ants; i++){
			ants[i] = sorted.get(i);
			total += ants[i].food;
		}
		
		current_average_score = total/max_ants;
																						
	}
	


		
	
	
	
	// ***************************** graphics stuff  *******************************************************************************
    public void update(Graphics g) { paint(g); } 
    
    //repaint the scene
    public synchronized void paint(Graphics g) 
    { 
		//draw background
		g.setColor( Color.black ); 
		g.fillRect( 0, 0, dim, dim ); 
	
		// Colors
		Color background = new Color ( 0, 0, 0 );
		Color food = new Color ( 0, 100, 0 );
		Color ant = new Color ( 0, 0, 180 );
			
		// draw the food
		g.setColor ( food );
		
		for ( int i=0; i<32; i++){
			for ( int j=0; j<32; j++ ){
				if ( SantaFeTrail[i][j] == 1 ){
					g.fillRect ( (i*20)+15, (j*20)+30, 18, 18 );
				}
			}
		}
			
		
		// draw ants
		g.setColor( ant );
		for ( int i=0; i<number_ants_to_view; i++){				// show top few ants
			Ant a = (Ant)ants[i];
			g.fillOval ( (a.x*20)+15, (a.y*20)+30, 10, 10 );
		}


		notifyAll(); 
    } 
    
    
    // gui stuff
    public void windowOpened( WindowEvent ev ) {} 
    public void windowActivated( WindowEvent ev ) {} 
    public void windowIconified( WindowEvent ev ) {} 
    public void windowDeiconified( WindowEvent ev ) {} 
    public void windowDeactivated( WindowEvent ev ) {} 
    public void windowClosed( WindowEvent ev ) {} 
    
    
    public void windowClosing(WindowEvent ev) 
    { 
		animThread = null; 
		setVisible(false); 
		dispose(); 
		System.exit(0); 
    } 

    
} 


// *******************  Ant class ************************************************************
// ***************************************************************************************************
// 12 step program, one move per cycle in order 0 = move forward; 1 = right, 2 = left
// x, y are current position
// d is the direction we are facing 0 = N, 1 = E, 2 = S, 3 = W
class Ant
{
	int program_length = 12;
	int food = 0;
	int steps = 0;
	int if_food_ahead[] = new int[program_length];
	int if_not_food_ahead[] = new int[program_length];
	int x = 0, y = 0, d = 1;		
	int santa_fe[][] = new int[32][32];
	Random random;

	
	// new ant
	Ant( int sft[][], Random r )
	{
		random = r;
		
		// lay out the food trail
		for ( int i=0; i<32; i++){
			for ( int j=0; j<32; j++){
				santa_fe[i][j] = sft[i][j];
			}
		}
		
		// create a if-food and if-not-food program to follow 
		//  we can turn left, turn right, or move
		//  0 = m; 1 = r; 2 = l;
		
		for ( int i=0; i<program_length; i++){
			 if_food_ahead[i] = random.nextInt()%3;
			 if ( if_food_ahead[i] < 0 ) { if_food_ahead[i] *= -1; }
		}
		for ( int i=0; i<program_length; i++){
			if_not_food_ahead[i] = random.nextInt()%3;
			if ( if_not_food_ahead[i] < 0 ) { if_not_food_ahead[i] *= -1; }
		}
		
		// pick a starting direction to face
		d = 1;
	}
	
		
		
	//  one move along our dna state machine
	void move ( int day )
	{
		int c = day % program_length;
		int m = 0;
		int see_food = 0;
			
		//check for food in square in front of us
		if ( d == 0 ){ if ( y > 0 ){ if ( santa_fe[x][y-1] == 1) { see_food = 1; } } }
		else if ( d == 1 ) { if ( x < 31 ) { if ( santa_fe[x+1][y] == 1) { see_food = 1; } } }
		else if ( d == 2 ) { if ( y < 31 ) { if ( santa_fe[x][y+1] == 1) { see_food = 1;  } } }
		else if ( d == 3 ) { if ( x > 0 ) { if ( santa_fe[x-1][y] == 1) { see_food = 1; } } }
		
		
		// if food in front of us follow if_food_ahead program
		if ( see_food == 1 ){
			if ( if_food_ahead[c] == 0 ){		// move forward one and fetch the food
				if ( d == 0 ){ 
					
					if ( y > 0 ){ y--;}
					santa_fe[x][y] = 0;
					food++; 
				
				}else if ( d == 1 ){
					
					if ( x < 31 ){ x++; }
					santa_fe[x][y] = 0;
					food++;
					
				}else if ( d == 2 ){

					if ( y < 31 ){ y++; }
					santa_fe[x][y] = 0;
					food++;
					 
				}else if ( d == 3 ) {
					if ( x > 0 ){ x--; }
					santa_fe[x][y] = 0;
					food++;
				}	
			}else if ( if_food_ahead[c] == 1 ){	//  turn right

				if ( d == 0 ){ d = 1; }
				else if ( d == 1 ) { d = 2; }
				else if ( d == 2 ) { d = 3; }
				else if ( d == 3 ) { d = 0; }
				
			}else{  // must be 2 so turn left
				if ( d == 0 ){ d = 3; }
				else if ( d == 1 ) { d = 2; }
				else if ( d == 2 ) { d = 1; }
				else if ( d == 3 ) { d = 0; }
			}
			
			see_food = 0;
			
		}else{  // else follow if_not_food_ahead
			if ( if_not_food_ahead[c] == 0 ){		// move forward one and fetch the food
				if ( d == 0 ){ 
					if ( y > 0 ){ y--;}
				
				}else if ( d == 1 ){
					
					if ( x < 31 ){ x++; }
					
				}else if ( d == 2 ){

					if ( y < 31 ){ y++; }
					 
				}else if ( d == 3 ) {
					if ( x > 0 ){ x--; }
									}	
			}else if ( if_not_food_ahead[c] == 1 ){	//  turn right

				if ( d == 0 ){ d = 1; }
				else if ( d == 1 ) { d = 2; }
				else if ( d == 2 ) { d = 3; }
				else if ( d == 3 ) { d = 0; }
				
			}else{  // must be 2 so turn left
				if ( d == 0 ){ d = 3; }
				else if ( d == 1 ) { d = 2; }
				else if ( d == 2 ) { d = 1; }
				else if ( d == 3 ) { d = 0; }
			}
	
			if ( santa_fe[x][y] == 1 ){
				santa_fe[x][y] = 0;
				food++;
			}
			see_food = 0;
		} //end else if not food ahead
	}
	
	
	
	// randomly adjust some bit of dna in each of our two state machines
	Ant adjust_dna ( Ant a, Random random )
	{
		//randomize dna
		//for ( int i=0; i<4; i++){
			a.if_food_ahead[random.nextInt( program_length )] = random.nextInt()%3;
			a.if_not_food_ahead[random.nextInt( program_length )] = random.nextInt()%3;
		//}
		
		for ( int i=0; i<program_length; i++){
			if( a.if_food_ahead[i] < 0 ){ a.if_food_ahead[i] *= -1; }
			if( a.if_not_food_ahead[i] < 0 ) { a.if_not_food_ahead[i] *= -1; }
		}
		
		return a;
	}
	
	
	
	// mate two ants and return the baby/
	// one dna from mom, one from dad and randomize one bit in each
	Ant mate ( Ant a, Ant b, int sft[][], Random random )
	{
		Ant baby = new Ant( sft, random );
		
		// lay out a fresh food trail
		for ( int i=0; i<32; i++){
			for ( int j=0; j<32; j++){
				baby.santa_fe[i][j] = sft[i][j];
			}
		}
		
		//swap dna one piece from mom and one from dad
		if( random.nextInt()%2 == 0 ){
			for ( int i=0; i<program_length; i++){
				baby.if_food_ahead[i] = a.if_food_ahead[i];
				baby.if_not_food_ahead[i] = b.if_not_food_ahead[i];
			}
		}else{
			for ( int i=0; i<program_length; i++){
				baby.if_food_ahead[i] = b.if_food_ahead[i];
				baby.if_not_food_ahead[i] = a.if_not_food_ahead[i];
			}
		}
		
		
		
		baby.adjust_dna ( baby, random );							//randomize dna
		
		return baby;												// hand baby off to the stork to deliver
	}
	
	
}