int MAX_SPECIES = 4;
int CULTURE_SPACE = 50;
int MAX_CYCLES = 5000;

color colorTable[] = new color[MAX_SPECIES + 1];

int sx, sy;
float density = .1;
int[][][] world;
long cycle = 0;

// The two best cultures in a round
int firstPlace;
int secondPlace;

// Start states of each culture.  The 0 index is used as temporary storage
boolean[][][] geneticCode = new boolean[MAX_SPECIES + 1][CULTURE_SPACE][CULTURE_SPACE];

void setup()
{
  int x, y;
  size(250, 250, P2D);
//  frameRate(1);
  sx = width;
  sy = height;
  world = new int[sx][sy][2];
  colorTable[0] = #000000; 
  colorTable[1] = #FF0000; 
  colorTable[2] = #00FF00; 
  colorTable[3] = #0000FF; 
  colorTable[4] = #FFFFFF; 
 
  // Set up initial cultures
  for(int i = 0; i < CULTURE_SPACE * CULTURE_SPACE * density; i++)
  {
    x = (int)random(sx) % CULTURE_SPACE;
    y = (int)random(sy) % CULTURE_SPACE;
    world[x + CULTURE_SPACE][y + CULTURE_SPACE][1] = 1;
    geneticCode[1][x][y] = true;
 
    x = (int)random(sx) % CULTURE_SPACE;
    y = (int)random(sy) % CULTURE_SPACE;
    world[x + CULTURE_SPACE * 3][y + CULTURE_SPACE][1] = 2;
    geneticCode[2][x][y] = true;
   
    x = (int)random(sx) % CULTURE_SPACE;
    y = (int)random(sy) % CULTURE_SPACE;
    world[x + CULTURE_SPACE][y + CULTURE_SPACE * 3][1] = 3;
    geneticCode[3][x][y] = true;

    x = (int)random(sx) % CULTURE_SPACE;
    y = (int)random(sy) % CULTURE_SPACE;
    world[x + CULTURE_SPACE * 3][y + CULTURE_SPACE * 3][1] = 4;
    geneticCode[4][x][y] = true;
  }

}
 
void draw()
{
  background(0);
 
  // Drawing and update cycle
  for (int x = 0; x < sx; x=x+1) {
    for (int y = 0; y < sy; y=y+1) {
      for (int z = 1; z <= MAX_SPECIES; z ++)
      {
         if ((world[x][y][1] == z) || (world[x][y][1] == 0 && world[x][y][0] == z))
         {
           world[x][y][0] = z;
           set(x, y, colorTable[z]);
         } 
      }
    
      if (world[x][y][1] == -1) world[x][y][0] = 0;
      world[x][y][1] = 0;
    }
  }
 
  // Birth and death cycle
  for (int x = 0; x < sx; x=x+1) {
    for (int y = 0; y < sy; y=y+1) {
      for (int z = 0; z <= MAX_SPECIES; z++)
      {
         int count = neighbors(x, y, z);
         if (count == 3 && world[x][y][0] == 0)
         {
           world[x][y][1] = z;
         }
         if ((count < 2 || count > 3) && world[x][y][0] == z)
         {
            world[x][y][1] = -1;
         }
      }
    }
  }
 
  // Stop, find the winners, mutate, and start again
  if( cycle ++ > MAX_CYCLES )
  {
    int[] counts = new int[MAX_SPECIES];
    for (int x = 0; x < sx; x=x+1)
    {
      for (int y = 0; y < sy; y=y+1)
      {
        if( world[x][y][0] > 0 ) counts[world[x][y][0] - 1] ++;
      }
    }
   
    // Find first place
    firstPlace = 1;
    for(int i = 1; i < MAX_SPECIES; i ++)
    {
       if( counts[i] > counts[firstPlace-1] ) firstPlace = i + 1;
    }
   
    // Find first place
    if(firstPlace == 1) secondPlace = 2;
    else secondPlace = 1;
    for(int i = 1; i < MAX_SPECIES; i ++)
    {
       if( counts[i] > counts[secondPlace-1] && i != (firstPlace - 1)) secondPlace = i + 1;
    }
    cycle = 0;
   
    // Restart
    for (int x = 0; x < sx; x=x+1) {
      for (int y = 0; y < sy; y=y+1) {
        world[x][y][0] = 0;
        world[x][y][1] = 0;
      }
    }
   
    // Mutate
    int crossMutation = 0;
    for(int i = 1; i <= MAX_SPECIES; i ++)
    {
      if( i != firstPlace && i != secondPlace)
      {
         if( crossMutation == 0)
         {
            crossMutation = i;
            copyCode( firstPlace, crossMutation );
            for(int a = 0; a < CULTURE_SPACE/2; a ++)
               for(int b = 0; b < CULTURE_SPACE/2; b ++)
                  geneticCode[i][a][b] = geneticCode[secondPlace][a][b];
         } else {
            copyCode(firstPlace, i);
            // Change 5 values
            for(int k = 0; k < 5; k ++)
            {
              int x = (int)(random(sx)) % CULTURE_SPACE;
              int y = (int)(random(sy)) % CULTURE_SPACE;
              if(geneticCode[i][x][y]) geneticCode[i][x][y] = false;
              else geneticCode[i][x][y] = true;
            }
         }
      } 
    }
   
    // Swap around a few times so position isn't the deciding factor
    for(int i = 0; i < 3; i ++)
    {
       int randomSelect1 = (int)(random(MAX_SPECIES)) + 1;
       int randomSelect2 = (int)(random(MAX_SPECIES)) + 1;
       copyCode(randomSelect1, 0);
       copyCode(randomSelect2, randomSelect1);
       copyCode(0, randomSelect2);
       colorTable[0] = colorTable[randomSelect1];
       colorTable[randomSelect1] = colorTable[randomSelect2];
       colorTable[randomSelect2] = colorTable[0];
    }
   
    // Place in the genetic codes
    for( int x = 0; x < CULTURE_SPACE; x ++ )
    {
      for( int y = 0; y < CULTURE_SPACE; y ++)
      {
           if( geneticCode[1][x][y] ) world[x + CULTURE_SPACE][y + CULTURE_SPACE][1] = 1;
           if( geneticCode[2][x][y] ) world[x + CULTURE_SPACE * 3][y + CULTURE_SPACE][1] = 2;
           if( geneticCode[3][x][y] ) world[x + CULTURE_SPACE][y + CULTURE_SPACE * 3][1] = 3;
           if( geneticCode[4][x][y] ) world[x + CULTURE_SPACE * 3][y + CULTURE_SPACE * 3][1] = 4;
      }
    }
  }
}

// Copy one geneticCode to another
void copyCode( int source, int destination)
{
  for(int i = 0; i < CULTURE_SPACE; i++)
     for(int j = 0; j < CULTURE_SPACE; j++)
       geneticCode[destination][i][j] = geneticCode[source][i][j]; 
}
 
// Count the number of adjacent cells 'on'
int neighbors(int x, int y, int v)
{
  int ret = 0;
  if ( world[(x + 1) % sx][y][0] == v ) ret ++;
  if (world[x][(y + 1) % sy][0] == v) ret ++;
  if (world[(x + sx - 1) % sx][y][0] == v) ret ++;
  if (world[x][(y + sy - 1) % sy][0] == v) ret ++;
  if (world[(x + 1) % sx][(y + 1) % sy][0] == v) ret ++;
  if (world[(x + sx - 1) % sx][(y + 1) % sy][0] == v) ret ++;
  if (world[(x + sx - 1) % sx][(y + sy - 1) % sy][0] == v) ret ++;
  if (world[(x + 1) % sx][(y + sy - 1) % sy][0] == v) ret ++;
 
  return ret;
}