filename="listc.txt"

#include <stdio.h>
#include <malloc.h>
#include <math.h>

#include <Xm/Xm.h>
#include <Xm/MainW.h>
#include <Xm/RowColumn.h>
#include <Xm/Frame.h>
#include <Xm/PushB.h>
#include <Xm/CascadeB.h>
#include <Xm/DrawingA.h>
#include <Xm/Label.h>
#include <Xm/Form.h>

#define PI 3.141592654

#define MAX_NEURAL 40
#define FITNESS_STEPS 400
#define POPULATION 500
#define WORLDSIZE 50
#define GENERATIONS 20000

typedef enum { SUM_THRESHOLD, FSENSOR, TSENSOR, TURN} functions; typedef enum { NONE, FOOD, VISITED } spotstates;

Display *theDisplay;
int screen;
Window theRoot, theWindow;
GC gc;
Colormap theCmap;
Pixmap bitmap;
XColor black, white, brown;
XtAppContext app_context;
XmString text;
Widget topLevel, mainWindow, menuBar, frame, sketchpad; Widget fileButton, fileMenu, run, quit;

struct neuralnode {
functions function;
double weights[3];
int inpointers[3], numinputs;
int constants[3], numconstants;
int connected, computed, used;
double outputvalue;
};

struct animal {
int living;
double fitness, oldfitness, direction, x, y, turn;
};

struct neuralnode brains[POPULATION+1][MAX_NEURAL+1];
struct neuralnode parent1b[MAX_NEURAL+1], parent2b[MAX_NEURAL+1]; struct animal animals[POPULATION+1];
struct animal parent1a, parent2a;
char world[WORLDSIZE+1][WORLDSIZE+1];


void RestoreWin(w, client, call)
Widget w;
XtPointer client, call;
{
XCopyArea(theDisplay, bitmap, XtWindow(sketchpad),
DefaultGCOfScreen(XtScreen(sketchpad)), 0, 0, 810, 860, 0, 0);
}


/* Set up the food patches */

void init_world(void)
{
int i, j, k;
double xaxis, yaxis, x, y, xp, yp;

for (i=0; i<=WORLDSIZE; i++)
for (j=0; j<=WORLDSIZE; j++)
world[i][j]=NONE;

for (k=0; k<3; k++) {
xaxis=rand()/65536.+0.1;
yaxis=rand()/65536.+0.1;
xp=rand()/16384.-1.;
yp=rand()/16384.-1.;

for (i=0; i<=WORLDSIZE; i++) {
for (j=0; j<=WORLDSIZE; j++) {
x=((double)i/WORLDSIZE-0.5)*2.;
y=((double)j/WORLDSIZE-0.5)*2.;
if ((x-xp)*(x-xp)*xaxis+(y-yp)*(y-yp)*yaxis<.06)
world[i][j]=FOOD;
}
}
}
}


/* Recursively compute the output of a node based upon its inputs */

void compute_node(int animal, int node) {
int i;
double inputs[3], constants[3], outval=0.;

if (brains[animal][node].computed) return; brains[animal][node].computed=1;
for (i=0; i<brains[animal][node].numinputs; i++) {
if (brains[animal][node].inpointers[i]>-1) {
compute_node(animal, brains[animal][node].inpointers[i]); inputs[i]=brains[animal][node].weights[i]*
brains[animal][brains[animal][node].inpointers[i]].outputvalue;
} else inputs[i]=brains[animal][node].weights[i];
}
for (i=0; i<brains[animal][node].numconstants; i++) {
constants[i]=brains[animal][node].constants[i];
}
switch(brains[animal][node].function) {
case SUM_THRESHOLD: outval=inputs[0]+inputs[1]+inputs[2];
outval=(1./(1.+exp(-fabs(constants[0])*outval))); break;
case FSENSOR: { double angle=(animals[animal].direction+inputs[0])*PI+PI/2.;
double x, y; int xp, yp, i;
outval=1.;
for (i=1; i<3; i++) {
x=animals[animal].x+i*cos(angle)/WORLDSIZE; y=animals[animal].y+i*sin(angle)/WORLDSIZE; if (x<0.) x=0.; if (x>0.99999) x=0.99999; if (y<0.) y=0.; if (y>0.99999) y=0.99999; xp=(int)(x*WORLDSIZE); yp=(int)(y*WORLDSIZE); if (world[xp][yp]==FOOD) break;
outval*=0.25;
}
}; break;
case TSENSOR: { double angle=(animals[animal].direction+inputs[0])*PI+PI/2.;
double x, y; int xp, yp, i;
outval=1.;
for (i=1; i<3; i++) {
x=animals[animal].x+cos(angle)/WORLDSIZE; y=animals[animal].y+sin(angle)/WORLDSIZE; if (x<0.) x=0.; if (x>0.99999) x=0.99999; if (y<0.) y=0.; if (y>0.99999) y=0.99999;
xp=(int)(x*WORLDSIZE); yp=(int)(y*WORLDSIZE); if (world[xp][yp]==VISITED) break;
outval*=0.25;
}
}; break;
case TURN: outval=inputs[0]-inputs[1];
if (outval<-1.) outval=-1.;
if (outval>1.) outval=1.;
animals[animal].turn=outval;
break;
}
brains[animal][node].outputvalue=outval*(0.95+rand()/327680.);
}


/* Evaluate an animal in a newly generated world */

double fitness(int which, int graph) {
int i, j, xp, yp;
double xpd, ypd, xold, yold;
double score=0., angle, box=800./WORLDSIZE; char str[100];

init_world();

animals[which].direction=0.;
animals[which].x=0.5; xold=0.5*800.; animals[which].y=0.; yold=0.;
animals[which].turn=0.;

if (graph) {
XSetForeground(theDisplay, gc, white.pixel); XFillRectangle(theDisplay, bitmap, gc, 0, 0, 850, 850); for (i=0; i<WORLDSIZE; i++) {
for (j=0; j<WORLDSIZE; j++) {
if (world[i][j]==FOOD) XSetForeground(theDisplay, gc, brown.pixel);
else XSetForeground(theDisplay, gc, white.pixel);
XFillRectangle(theDisplay, bitmap, gc, box*j, box*i, box, box);
}
}

XSetForeground(theDisplay, gc, black.pixel); XSetLineAttributes(theDisplay, gc, 8, LineSolid, CapRound,
JoinMiter);
}

for (i=0; i<FITNESS_STEPS; i++) {
for (j=0; j<MAX_NEURAL; j++) {
brains[which][j].computed=0;
}

/* THINK */
compute_node(which, 0);

/* MOVE */
animals[which].direction+=animals[which].turn/2.;
if (animals[which].direction<-1.) animals[which].direction+=2.; if (animals[which].direction>1.) animals[which].direction-=2.; angle=animals[which].direction*PI+PI/2.; animals[which].x+=cos(angle)/WORLDSIZE; animals[which].y+=sin(angle)/WORLDSIZE;
if (animals[which].x<0.) animals[which].x=0.;
if (animals[which].x>.99999) animals[which].x=.99999; if (animals[which].y<0.) animals[which].y=0.;
if (animals[which].y>.99999) animals[which].y=.99999;

/* EAT */
xpd=animals[which].x*800.; xp=(int)(animals[which].x*WORLDSIZE); ypd=animals[which].y*800.; yp=(int)(animals[which].y*WORLDSIZE); if (world[xp][yp]==FOOD) score++;
if (world[xp][yp]==VISITED) score-=0.; world[xp][yp]=VISITED;
if (graph) {
XDrawLine(theDisplay, bitmap, gc, yold, xold, ypd, xpd);
}
xold=xpd; yold=ypd;
}

if (graph) {
XSetLineAttributes(theDisplay, gc, 0, LineSolid, CapRound,
JoinMiter);
for (i=0; i<POPULATION; i++) {
XDrawLine(theDisplay, bitmap, gc, i*800./POPULATION, 850,
i*800./POPULATION, 850-animals[i].fitness/10.);
printf("%f\n", animals[i].fitness);
}
printf("Score: %f\n",score);
RestoreWin(NULL,NULL,NULL);
}
return score;
}


void mutate_parameters(struct neuralnode which[], int num) {
int pos, input, constant, i, j;

for (i=0; i<num; i++) {
do {
pos=(int)(MAX_NEURAL*(double)rand()/32768.);
} while (which[pos].used==0);
input=(int)(which[pos].numinputs*rand()/32768.); for (j=0; j<3; j++)
which[pos].weights[input]+=
which[pos].weights[input]*(rand()/262144.-0.0625);
if (rand()<100)
which[pos].weights[input]=rand()/16384.-1.;
if (rand()<100)
which[pos].weights[input]=-which[pos].weights[input];

constant=(int)(which[pos].numconstants*rand()/32768.); for (j=0; j<5; j++)
which[pos].constants[constant]+=
which[pos].constants[constant]*(rand()/262144.-0.0625);
if (rand()<100)
which[pos].constants[constant]=rand()/16384.-1.;
if (rand()<100)
which[pos].constants[constant]=-which[pos].constants[constant];

}
}


void add_random_node(struct neuralnode which[]) {
functions type;
int pos=1, numinputs, numconstants;

while (which[pos].used) {
pos++; if (pos==MAX_NEURAL) return;
}

which[pos].used=1;
which[pos].weights[0]=rand()/16384.-1.; which[pos].weights[1]=rand()/16384.-1.; which[pos].weights[2]=rand()/16384.-1.; which[pos].constants[0]=rand()/16384.-1.; which[pos].constants[1]=rand()/16384.-1.; which[pos].constants[2]=rand()/16384.-1.; which[pos].inpointers[0]=-1.;
which[pos].inpointers[1]=-1.;
which[pos].inpointers[2]=-1.;
if (rand()>5000) type=SUM_THRESHOLD;
else type=(functions)((int)(rand()%3));
which[pos].function=type;
switch(type) {
case SUM_THRESHOLD: numinputs=3; numconstants=1; break; case FSENSOR: numinputs=1; numconstants=0; break;
case TSENSOR: numinputs=1; numconstants=0; break;
}
which[pos].numinputs=numinputs;
which[pos].numconstants=numconstants;
}


void remove_link(struct neuralnode which[]) {
int node, input, fromnode;

while (1) {
node=(int)(MAX_NEURAL*rand()/32768.); if (which[node].used) break;
}
input=(int)(which[node].numinputs*rand()/32768.); which[node].inpointers[input]=-1;
}


void add_link(struct neuralnode which[]) {
int node, input, fromnode;

while (1) {
node=(int)(MAX_NEURAL*rand()/32768.); if (which[node].used) break;
}
input=(int)(which[node].numinputs*rand()/32768.); while (1) {
fromnode=(int)(MAX_NEURAL*rand()/32768.); if (which[fromnode].used) break;
}
which[node].inpointers[input]=fromnode;
}


/* Recursively mark connected nodes to protect from garbage collection */

void connected_node(struct neuralnode which[], int node) {
int i;

if (which[node].connected==1) return; which[node].connected=1;
for (i=0; i<which[node].numinputs; i++)
if (which[node].inpointers[i]>-1)
connected_node(which, which[node].inpointers[i]);
}


/* Mark unconnected nodes as not used */

void garbage_collect(struct neuralnode which[]) {
int j;

for (j=0; j<MAX_NEURAL; j++) which[j].connected=0; connected_node(which,0);
for (j=0; j<MAX_NEURAL; j++)
if (which[j].connected==0) which[j].used=0;
}


void mutate(struct neuralnode which[]) {
mutate_parameters(which,10);
add_random_node(which);
if (rand()<2000) remove_link(which); if (rand()<20000) add_link(which);
garbage_collect(which);
}


/* Recursively connect one node input to another node's output and its parents */ 

void connect_node(struct neuralnode parent1[], struct neuralnode parent2[],
int node1, int input1, int node2)
{
int i, pos=0;

if (parent2[node2].connected==1) return; parent2[node2].connected=1;
while (parent1[pos].used) {
pos++; if (pos==MAX_NEURAL) return;
}
memcpy(&(parent1[pos]), &(parent2[node2]), sizeof(struct neuralnode)); parent1[node1].inpointers[input1]=pos;  
for (i=0; i<parent1[pos].numinputs; i++)
if (parent1[pos].inpointers[i]>-1)
connect_node(parent1, parent2, pos, i, parent1[pos].inpointers[i]);
}


void init_population(void)
{
int i, j;

for (i=0; i<POPULATION; i++) {
animals[i].living=1;
animals[i].fitness=0.;
brains[i][0].function=TURN;
brains[i][0].weights[0]=1.;
brains[i][0].weights[1]=1.;
brains[i][0].numinputs=2;
brains[i][0].used=1;
brains[i][0].inpointers[0]=-1;
brains[i][0].inpointers[1]=-1;
brains[i][0].inpointers[2]=-1;
for (j=0; j<rand()/8192; j++)
mutate(brains[i]);
}
}


/* Kill the inefficient animals */

void survival_of_the_fittest(void)
{
int animal, i, minnum;
double minfit;

for (i=0; i<POPULATION; i++) animals[i].oldfitness=animals[i].fitness; for (i=0; i<POPULATION*4/5; i++) {
minfit=999999.;
for (animal=0; animal<POPULATION; animal++) {
if (animals[animal].fitness<minfit) {
minfit=animals[animal].fitness;
minnum=animal;
}
}
animals[minnum].living=0; animals[minnum].fitness=9999999.;
}
for (i=0; i<POPULATION; i++) animals[i].fitness=animals[i].oldfitness;
}


void make_children(void)
{
int i, j, k, parent, parent2, state; double maxfit=-999999.;

for (i=0; i<POPULATION; i++) {
if (animals[i].fitness>maxfit) maxfit=animals[i].fitness;
}

for (i=0; i<POPULATION; i++) if (animals[i].living==0) {

/* Find two parents, usually in geographical proximity */ parent=i;
if (maxfit<=0.) parent=(int)(POPULATION*rand()/32768.); else while (1) {
parent+=(int)(POPULATION*(rand()/327680.-0.05)); if (rand()<10000) parent=rand()%POPULATION; while (parent<0) parent+=POPULATION;
while (parent>=POPULATION) parent-=POPULATION; if ((animals[parent].living) &&
(animals[parent].fitness/maxfit>rand()/32768.)) break;
}
parent2=i;
if (maxfit<=0.) parent2=(int)(POPULATION*rand()/32768.); else while (1) {
for (j=0; j<3; j++) parent2+=(int)(POPULATION*(rand()/327680.-0.05)); if (rand()<10000) parent2=rand()%POPULATION;
while (parent2<0) parent2+=POPULATION;
while (parent2>=POPULATION) parent2-=POPULATION; if ((animals[parent2].living) &&
(animals[parent2].fitness/maxfit>rand()/32768.)) break;
}

for (j=0; j<MAX_NEURAL; j++) memcpy(&(parent1b[j]),&(brains[parent][j]),
sizeof(struct neuralnode));
memcpy(&(parent1a), &(animals[parent]), sizeof(struct animal));
for (j=0; j<MAX_NEURAL; j++) memcpy(&(parent2b[j]),&(brains[parent2][j]),
sizeof(struct neuralnode));
memcpy(&(parent2a), &(animals[parent2]), sizeof(struct animal)); memcpy(&(animals[i]),&(parent1a),sizeof(struct animal));

if (rand()<11000) {      /* CROSSOVER */
state=0;
for (j=0; j<MAX_NEURAL; j++) {
if (state==0)
memcpy(&(brains[i][j]), &(parent1b[j]), sizeof(struct neuralnode));
else
memcpy(&(brains[i][j]), &(parent2b[j]), sizeof(struct neuralnode));
if (rand()<4000) state=(state?0:1);
}
for (j=0; j<MAX_NEURAL; j++) if (brains[i][j].used) {
for (k=0; k<brains[i][j].numinputs; k++)
if (brains[i][j].inpointers[k]!=-1) {
if (brains[i][brains[i][j].inpointers[k]].used==0)
brains[i][j].inpointers[k]=-1;
}
}
} else if (rand()<0) {   /* GRAFT */
int node1, node2, input;
while (1) {
node1=(int)(MAX_NEURAL*rand()/32768.); if (parent1b[node1].used) break;
}
input=(int)(parent1b[node1].numinputs*rand()/32768.); parent1b[node1].inpointers[input]=-1; garbage_collect(parent1b);

while (1) {
node2=(int)(MAX_NEURAL*rand()/32768.); if (parent2b[node2].used) break;
}

for (j=0; j<MAX_NEURAL; j++) parent2b[j].connected=0; connect_node(parent1b,parent2b,node1,input,node2);      
} else {                     /* ASEXUAL */
for (j=0; j<MAX_NEURAL; j++)
memcpy(&(brains[i][j]), &(parent1b[j]), sizeof(struct neuralnode));
}
if (rand()<30000) mutate(brains[i]); animals[i].living=1;
}
}

void Run(w, client, call)
Widget w;
XtPointer client, call;
{
int generation, animal, maxnum;
double maxfitness;

init_population();

for (generation=0; generation<GENERATIONS; generation++) {
fprintf(stderr,"Generation %d\n",generation); maxfitness=-999999.;
for (animal=0; animal<POPULATION; animal++)  {
/* Evaluate twice to decrease the effects of bad luck */ animals[animal].fitness=fitness(animal,0)+fitness(animal,0)
+fitness(animal,0);
if (animals[animal].fitness>maxfitness) {
maxfitness=animals[animal].fitness; maxnum=animal;
}
}
fitness(maxnum,1);
survival_of_the_fittest();
make_children();
}
}

void Quit(w, client, call)
Widget w;
XtPointer client, call;
{
exit(0);
}

void main(int argc, char **argv)
{
/* INITIALIZE X */
topLevel=XtVaAppInitialize(
&app_context,"Dino",NULL,0,&argc,argv,NULL,NULL);

/* CREATE MAIN WINDOW & IMMEDIATE CHILDREN */ mainWindow=XtVaCreateManagedWidget(
"mainWindow",xmMainWindowWidgetClass,topLevel,NULL);

menuBar=XmCreateMenuBar(mainWindow,"menuBar",NULL,0); XtManageChild(menuBar);

frame=XtVaCreateManagedWidget(
"frame",xmFrameWidgetClass,mainWindow,NULL);

XmMainWindowSetAreas(mainWindow, menuBar, NULL, NULL, NULL, frame); XtVaSetValues(mainWindow,XmNwidth,810,XmNheight,860,NULL);


/* CREATE GRAPHICS */
sketchpad = XtVaCreateManagedWidget(
"sketchpad",xmDrawingAreaWidgetClass, frame,
XmNwidth,810,XmNheight,860,NULL);

theDisplay = XtDisplay(sketchpad);
theWindow = XtWindow(sketchpad);
screen = DefaultScreen(theDisplay);
theRoot = RootWindowOfScreen(XtScreen(sketchpad));
theCmap = DefaultColormap( theDisplay, DefaultScreen(theDisplay) ); bitmap = XCreatePixmap(XtDisplay(sketchpad),theRoot,810,860,
DefaultDepthOfScreen(XtScreen(sketchpad)));
gc = XCreateGC( theDisplay, bitmap, 0, 0 ); XtAddCallback(sketchpad,XmNexposeCallback,RestoreWin,0);

XParseColor(theDisplay,theCmap,"black",&black); XAllocColor(theDisplay, theCmap,&black); XParseColor(theDisplay,theCmap,"white",&white); XAllocColor(theDisplay, theCmap,&white); XParseColor(theDisplay,theCmap,"brown",&brown); XAllocColor(theDisplay, theCmap,&brown);

/* CREATE FILE MENU */
fileButton=XtVaCreateManagedWidget(
"fileButton",xmCascadeButtonWidgetClass,menuBar,NULL);
text=XmStringCreateLocalized("File"); XtVaSetValues(fileButton,XmNlabelString,text,NULL);

fileMenu=XmCreatePulldownMenu(menuBar,"fileMenu",NULL,0); XtVaSetValues(fileButton,XmNsubMenuId,fileMenu,NULL);

/* CREATE RUN BUTTON */
run=XtVaCreateManagedWidget(
"run",xmPushButtonWidgetClass,fileMenu,NULL);
text=XmStringCreateLocalized("Run"); XtVaSetValues(run,XmNlabelString,text,NULL); XtAddCallback(run,XmNactivateCallback,Run,NULL);

/* CREATE QUIT BUTTON */
quit=XtVaCreateManagedWidget(
"quit",xmPushButtonWidgetClass,fileMenu,NULL);
text=XmStringCreateLocalized("Quit"); XtVaSetValues(quit,XmNlabelString,text,NULL); XtAddCallback(quit,XmNactivateCallback,Quit,NULL);


XtRealizeWidget(topLevel);
XSetForeground(theDisplay, gc, white.pixel); XFillRectangle(theDisplay, bitmap, gc, 0, 0, 810, 860); XtAppMainLoop(app_context);

}