Dar, C++ (gcc) - rextester

Dar

//g++  7.4.0

const int GW = 10; //grid width
const int GL = 10; //grid length
const int GENES = 16; //number of genes per robot
const int GENELEN=5; //length of each gene
const int GN = 0; //empty grid cell
const int GB = 9; //battery grid cell
const int GDC = 5; //used in gene to match any cell
const int GWA = 1; //wall grid cell (out-of-bounds assumed wall)
//array of view codes that can go in gene
const int VC[4]={GN,GB,GWA,GDC};
const int NVC=4;
//directions and the random direction
const int UP=1;
const int LEFT=2;
const int RIGHT=3;
const int DOWN=4;
const int RANDDIR=5;
const int NDC =5; //number of direction codes including the code for random direction
const int MOVECODES[5]={UP,LEFT,RIGHT,DOWN,RANDDIR};
const int NR=200; //number of robots in each generation
const double PERCBAT = 0.4; //proportion of batteries in grid
const int GENERATIONS = 5000;
const double MUTRATE=0.08;
const int INITEN=5; //initial energy of a robot

#include <iostream>
class Grid { 
  int g[GW][GL]; //g[x][y] is cell at (x,y)
//to place k batteries in empty cells, place 1 battery in an empty cell, then recursively place k-1 batteries
void randbat(int k){
  int x,y;
  if (k==0) return;
  //generate random (x,y) pairs until (x,y) is empty, then place a battery there
  do {
    x=rand()%GW; 
    y=rand()%GL;
  } while(g[x][y] != GN);
  g[x][y]=GB;
  randbat(k-1);
}
public:
  //random Grid with a percentage of cells occupied with batteries
Grid(double perc) {
  for (int y=0; y<GL; y++) 
    for (int x=0; x<GW;x++)
       g[x][y]=0;
  int k=(GW*GL)*perc;
  randbat(k);
}
//get code of cell at (x,y) so out-of-bounds is a wall
int getcode(int x, int y) {
  if ((x>=GW)||(x<0)||(y>=GL)||(y<0)) return GWA;
  else return g[x][y];
}
//get codes of cells north, west, east, and south of 
//(x,y) and pack into pre-allocated array of 4 ints
void getnwes(int x, int y, int* into) {
  into[0]=getcode(x,y-1);
  into[1]=getcode(x-1,y);
  into[2]=getcode(x+1,y);
  into[3]=getcode(x,y+1);
}
//for debugging, print the grid
void print() {
  for (int y=0;y<GL;y++) {
    for (int x=0;x<GW;x++) {
      std::cout<<g[x][y];
    }
    std::cout<<std::endl;
  }
}
//creature munches at cell (x,y)
//deplete battery there accordingly if any
//return energy munched
  int munch(int x, int y) {
     if (g[x][y]==GB) {g[x][y]=GN; return 1;}
     else return 0;
  }
  //is cell (x,y) not a grid wall?
  int cango(int x, int y) {
    return (getcode(x,y)!=GWA);
  }

//for debugging, print codes for sensor at (x,y)
void printcodes(int x, int y) {
  int a[4];
  getnwes(x,y,a);
  for(int i=0;i<4;i++)
    std::cout<<a[i];
  }
//end class
};

//robot
class Rb {
  int genes[GENES][GENELEN];
  int energy;
  int x,y;
  int movesmade;
  void randplace() {
    x=rand()%GW;
    y=rand()%GL;
  }
 void randgene(int* g) {
   //first 4 codes are one of nothing,wall,battery,or don't care
   for (int i=0;i<4;i++) {
     g[i]=VC[rand()%NVC];
   }
   //5th code is a (non-zero) direction code
   g[4]=MOVECODES[rand()%NDC];
}
public:
//construct a robot with a random set of genes ready to run
Rb() {
      for (int g=0;g<GENES;g++) {
         randgene(genes[g]);
      }
      randplace();
      movesmade=0;
      energy=INITEN;
}
//returns 0 if view does not match gene
//else returns the code at the end of the gene
int activategene(int*view,int*gene){
   for (int i=0;i<4;i++) {
      if (view[i]!=gene[i]&&gene[i]!=GDC) return 0;
   }
   return gene[GENELEN-1];
}
//return the last code from the first of this robot's 
//genes that matches view
//if no gene matches, return last gene's last code
int lookup(int* view) {
    int move;
    for (int i=0;i<GENELEN;i++) {
       move=activategene(view, genes[i]);
       if (move!=0) return move;
    }
    //if there are gene activations assume the last gene is activated
    return genes[GENES-1][GENELEN-1];
}
//gets the robot ready to run the grid again
void reset() {
    randplace();
    movesmade=0;
    energy=INITEN;
 }
//runs the robot to energy depletion
void go(Grid*gr) {
  if (energy<0) return;
  int view[4]; 
  int move;
  int x2, y2;
  gr->getnwes(x,y,view);
  move=lookup(view);
  //if move represents a random move then 
  //the move becomes a random move
  if (move==RANDDIR) {
     int ds[4]={UP,LEFT,RIGHT,DOWN};
     move=ds[rand()%4];
  }
  y2=y;x2=x;
  switch(move) {
     case(UP): y2--;break;
     case(LEFT): x2--; break;
     case(RIGHT): x2++; break;
     case(DOWN): y2++; break;
  }
  //if can go then go
  if (gr->cango(x2,y2)) {x=x2;y=y2;}
  //and always increment moves made
  movesmade++;
  //return energy
  energy+=gr->munch(x,y);
  energy--;
  go(gr);
}
void mutate(int z) {
  int code=rand()%GENELEN;
  const int* source=VC; //array to copy from
  int l=NVC;           //length of array to copy from
  if (code==GENELEN-1) {
    source=MOVECODES;
    l=NDC;
  }
  genes[z][code]=source[rand()%l];
}
 
void printgenes() {
  for (int g=0; g<GENES;g++) {
    for (int i=0; i<GENELEN; i++) {
      std::cout<<genes[g][i]<<" ";
    }
    std::cout<<std::endl;
  }
}
void printstats() {
  std::cout<<"x: "<<x<<" y: "<<y<<" E: "<<energy+1<<" Score: "<<movesmade<<std::endl;
}
int harvest() {
  return movesmade-INITEN;
}
Rb mate(Rb pa) {
  Rb baby;
  int i=0;
  Rb *source=this;
  for (i=0;i<GENES;i++) {
    if(i>=GENES/2) source=&pa;
    for(int i2=0;i2<GENELEN;i2++) {
       baby.genes[i][i2]=source->genes[i][i2];
    }
  }
  return baby;
}
//end class
};

class Breeder {
  Rb rs[NR]; //the 200 robots
  double avg[GENERATIONS];
Grid newgrid() {
  Grid g(PERCBAT);
  return g;
}
void runrs() {
  for (int gennum=0; gennum<GENERATIONS; gennum++) {
  double tot=0.0;
  for (int i=0; i<NR; i++) {
     Grid g=newgrid();
     rs[i].reset();
     rs[i].go(&g);
     tot+=rs[i].harvest();
  }
  avg[gennum]=tot/(double)NR;
  sort();
  breed();
  } 
}
void sort() {
  Rb temp;
  for (int i=0;i<NR-1;i++) {
    for (int i2=i+1;i2<NR;i2++) {
       if (rs[i].harvest()<rs[i2].harvest()) {
         temp=rs[i];
         rs[i]=rs[i2];
         rs[i2]=temp;
      }
    }
  }
}
void breed() {
  //do the gene combining perfectly
  for(int i=0;i<NR/2;i=i+2) {
    rs[i+NR/2]=rs[i].mate(rs[i+1]);
    rs[i+NR/2+1]=rs[i+1].mate(rs[i]);
  }
  //make some mutants
  int m[(int)(NR*MUTRATE*GENES)]; //array of individual gene numbers in the population
  for (int i=0; i<NR*MUTRATE*GENES;i++) {
    int in;
    do {
       in=0;
       m[i]=rand()%(NR*GENES);
       for(int i2=0;i2<i;i2++) if (m[i2]==m[i]) in=1;
     } while (in);
     rs[i/GENES].mutate(i%GENES);
   }
}
public:
Breeder() {
  runrs();
}
void print() {
  for (int i=0;i<GENERATIONS;i++) {
    std::cout<<"Generation "<<1+i<<" average "<<avg[i]<<std::endl;
  }
}
void printwinner() {
  rs[0].printgenes();
  std::cout<<rs[0].harvest()<<std::endl;
}
};

int main()
{
    srand(time(NULL));
    Breeder b;
    b.print();
    std::cout<<"Bonus feature - genes of top robot"<<std::endl;
    b.printwinner();
}


run \| edit \| history \| help	0