+/GENN
genetically evolving neural networks
git clone https://git.julia.blue/+/GENN
ae5ad7f
v0.1
1import sys 2import pygame 3import time 4import math 5import random 6 7 8class Vector (): 9x = 0 10y = 0 11 12def __init__ (self ,pos = (0 ,0 )): 13self .x = float (pos [0 ]) 14self .y = float (pos [1 ]) 15 16def magnitude (self ): 17return math .sqrt (self .x ** 2 + self .y ** 2 ) 18 19def norm (self ): 20m = self .magnitude 21return Vector ((self .x / m ,self .y / m )) 22 23def dot (self ,other ): 24return self .x * other .x + self .y * other .y 25 26def rotate (self ,angle ): 27return Vector ((self .x * math .cos (angle )- self .y * math .sin (angle ),self .x * math .sin (angle )+ self .y * math .cos (angle ))) 28 29def __add__ (self ,other ): 30return Vector ((self .x + other .x ,self .y + other .y )) 31 32def __sub__ (self ,other ): 33return Vector ((self .x - other .x ,self .y - other .y )) 34 35def __mul__ (self ,other ): 36return Vector ((self .x * other .x ,self .y * other .y )) 37 38def __div__ (self ,other ): 39return Vector ((self .x / other .x ,self .y / other .y )) 40 41def __eq__ (self ,other ): 42return self .x == other .x and self .y == other .y 43 44def toTup (self ): 45return (self .x ,self .y ) 46 47def toTupInt (self ): 48return (int (self .x ),int (self .y )) 49 50 51class Car (): 52position = Vector ((0. ,0. )) 53lastPos = Vector ((0. ,0. )) 54direction = 0. 55speed = 0. 56steerAngle = 0. 57length = 0. 58width = 0. 59previous = [0. ] 60points = [(0. ,0. )] 61color = (0 ,0 ,0 ) 62sensors = [0. ] 63sensorStrength = 0 64 65def __init__ (self ,x ,y ,length ,width ,sensorNum = 5 ,sensorStr = 200 ,drift = 2 ,c = (255 ,255 ,255 )): 66self .position = Vector ((x ,y )) 67self .length = length 68self .width = width 69self .color = c 70for i in range (drift ): 71self .previous .append (0. ) 72for i in range (sensorNum - 1 ): 73self .sensors .append (0. ) 74self .sensorStrength = sensorStr 75 76def updatePoints (self ): 77self .points = [(self .position + Vector ((self .length / 2 ,self .width / 2 )).rotate (self .direction )).toTup (), 78 (self .position + Vector ((self .length / 2 ,- 79self .width / 2 )).rotate (self .direction )).toTup (), 80 (self .position + Vector ((- self .length / 2 ,- 81self .width / 2 )).rotate (self .direction )).toTup (), 82 (self .position + Vector ((- self .length / 2 ,self .width / 2 )).rotate (self .direction )).toTup ()] 83 84def draw (self ,s ): 85self .updatePoints () 86pygame .draw .polygon (s ,self .color ,self .points ,0 ) 87 88def move (self ): 89self .lastPos .x = self .position .x 90self .lastPos .y = self .position .y 91front = self .position + \ 92Vector ((self .length / 2 ,0 )).rotate (self .direction ) 93back = self .position + \ 94Vector ((self .length / 2 ,0 )).rotate (self .direction + math .pi ) 95front += Vector ((math .cos (self .previous [0 ]+ self .steerAngle )* self .speed ,math .sin ( 96self .previous [0 ]+ self .steerAngle )* self .speed )) 97back += Vector ((math .cos (self .previous [0 ])* self .speed , 98math .sin (self .previous [0 ])* self .speed )) 99self .position = (front + back )/ Vector ((2 ,2 )) 100self .direction = math .atan2 (front .y - back .y ,front .x - back .x ) 101for i in range (len (self .previous )- 1 ): 102self .previous [i ]= self .previous [i + 1 ] 103self .previous [- 1 ]= self .direction 104 105def applyFriction (self ,strength ): 106self .speed *= 1 - strength 107 108def updateSensors (self ,t ,s ): 109temp = self .direction - math .pi / 2 110drawPoints = [] 111for i in range (len (self .sensors )): 112drawPoints .append ( 113self .position + Vector ((self .sensors [i ]* math .cos (temp ),self .sensors [i ]* math .sin (temp )))) 114self .sensors [i ]= self .sensorStrength 115for e in range (len (t .outside )): 116p = intersectionPoint (self .position ,self .position + Vector ((self .sensors [i ]* math .cos ( 117temp ),self .sensors [i ]* math .sin (temp ))),Vector (t .outside [e - 1 ]),Vector (t .outside [e ])) 118if p .x != - 1 or p .y != - 1 : 119m = (self .position - p ).magnitude () 120self .sensors [i ]= m 121drawPoints [i ]= p 122for e in range (len (t .inside )): 123p = intersectionPoint (self .position ,self .position + Vector ((self .sensors [i ]* math .cos ( 124temp ),self .sensors [i ]* math .sin (temp ))),Vector (t .inside [e - 1 ]),Vector (t .inside [e ])) 125if p .x != - 1 or p .y != - 1 : 126m = (self .position - p ).magnitude () 127self .sensors [i ]= m 128drawPoints [i ]= p 129temp += math .pi / (len (self .sensors )- 1 ) 130for i in drawPoints : 131pygame .draw .circle (s , (255 ,255 ,0 ),i .toTupInt (),5 ) 132pygame .draw .line ( 133s , (255 ,0 ,0 ),self .position .toTupInt (),i .toTupInt ()) 134 135 136class Track (): 137outside = [] 138inside = [] 139path = [] 140start = (0. ,0. ) 141startDir = 0 142totalLength = 0 143trackColor = (0 ,0 ,0 ) 144bgColor = (0 ,0 ,0 ) 145backwards = True 146laps = 0 147newLap = False 148 149def __init__ (self ,f ,tCol = (0 ,0 ,0 ),bgCol = (100 ,100 ,100 )): 150self .trackColor = tCol 151self .bgColor = bgCol 152self .inputFile (f ) 153self .start = self .path [0 ] 154self .startDir = math .atan2 ( 155self .path [0 ][1 ]- self .path [1 ][1 ],self .path [0 ][0 ]- self .path [1 ][0 ])+ math .pi 156for i in range (len (self .path )): 157self .totalLength += math .sqrt ((self .path [i - 1 ][0 ]- self .path [i ][0 ])** 2 + ( 158self .path [i - 1 ][1 ]- self .path [i ][1 ])** 2 ) 159 160def draw (self ,s ): 161pygame .draw .polygon (s ,self .trackColor ,self .outside ,0 ) 162pygame .draw .polygon (s ,self .bgColor ,self .inside ,0 ) 163#pygame.draw.lines(s, (255,0,0), 1, self.path) 164 165def inputFile (self ,fileName ): 166f = open (fileName + ".txt" ) 167lines = f .read ().splitlines () 168for i in range (3 ): 169lines [i ]= lines [i ].translate (None ,'() ' ) 170data = lines [i ].split (',' ) 171for j in range (0 ,len (data ),2 ): 172temp = (int (data [j ]),int (data [j + 1 ])) 173if i == 0 : 174self .outside .append (temp ) 175elif i == 1 : 176self .inside .append (temp ) 177elif (i == 2 ): 178self .path .append (temp ) 179f .close () 180 181def collision (self ,c ): 182for i in range (len (self .outside )): 183if intersect (Vector (self .outside [i - 1 ]),Vector (self .outside [i ]),c .position ,c .lastPos ): 184return True 185for i in range (len (self .inside )): 186if intersect (Vector (self .inside [i - 1 ]),Vector (self .inside [i ]),c .position ,c .lastPos ): 187return True 188return False 189 190def reset (self ,c ): 191c .position = Vector (self .start ) 192c .direction = self .startDir 193c .speed = 0 194self .laps = 0 195self .newLap = False 196self .backwards = True 197 198def progress (self ,c ): 199length = 0 200closest = 0 201distance = sys .maxint 202point = Vector ((0 ,0 )) 203for i in range (len (self .path )): 204a = Vector (self .path [i ]) 205b = Vector (self .path [(i + 1 )% len (self .path )]) 206va = b - a 207vb = c .position - a 208d = vb .dot (va )/ va .dot (va ) 209p = a + Vector ((d ,d ))* va 210temp = (c .position - p ).magnitude () 211if temp < distance and 0 <= d <= 1 : 212distance = temp 213point = p 214closest = i 215temp = vb .magnitude () 216if temp < distance : 217distance = temp 218point = a 219closest = i 220for i in range (closest ): 221length += math .sqrt ((self .path [i ][0 ]- self .path [(i + 1 )% len (self .path )][ 2220 ])** 2 + (self .path [i ][1 ]- self .path [(i + 1 )% len (self .path )][1 ])** 2 ) 223return length + math .sqrt ((self .path [closest ][0 ]- point .x )** 2 + (self .path [closest ][1 ]- point .y )** 2 ) 224 225 226def ccw (A ,B ,C ): 227return (C .y - A .y )* (B .x - A .x )> (B .y - A .y )* (C .x - A .x ) 228 229 230def intersect (A ,B ,C ,D ): 231return ccw (A ,C ,D )!= ccw (B ,C ,D )and ccw (A ,B ,C )!= ccw (A ,B ,D ) 232 233 234def intersectionPoint (a ,b ,c ,d ): 235denom = (d .y - c .y )* (b .x - a .x )- (d .x - c .x )* (b .y - a .y ) 236tempX = ((d .x - c .x )* (a .y - c .y )- (d .y - c .y )* (a .x - c .x ))/ denom 237tempY = ((b .x - a .x )* (a .y - c .y )- (b .y - a .y )* (a .x - c .x ))/ denom 238if 0 <= tempX <= 1 and 0 <= tempY <= 1 : 239return Vector ((a .x + tempX * (b .x - a .x ),a .y + tempX * (b .y - a .y ))) 240else : 241return Vector ((- 1 ,- 1 )) 242 243 244def step (buttons ,player ,track ,acceleration ,turnRadius ,handling ,friction ): 245if buttons [0 ]: 246player .speed += acceleration 247if buttons [1 ]: 248player .speed -= acceleration / 1.5 249if buttons [3 ]: 250player .steerAngle = min (player .steerAngle + handling ,turnRadius ) 251if buttons [2 ]: 252player .steerAngle = max (player .steerAngle - handling ,- turnRadius ) 253if not (buttons [2 ]or buttons [3 ]): 254player .steerAngle = 0 255 256player .applyFriction (friction ) 257player .move () 258 259playerPos = track .progress (player ) 260if 5 < playerPos < 100 : 261track .backwards = False 262track .newLap = True 263if playerPos > track .totalLength - 100 and track .newLap : 264track .laps += 1 265track .newLap = False 266 267score = - 1 268if not track .backwards : 269score = track .laps * track .totalLength + track .progress (player ) 270if track .collision (player ): 271track .reset (player ) 272return (True ,score ) 273return (False ,score ) 274 275 276def draw (s ,t ,c ): 277s .fill ((100 ,100 ,100 )) 278t .draw (s ) 279c .updateSensors (t ,s ) 280c .draw (s ) 281pygame .display .flip () 282 283 284class Neuron (): 285weights = [] 286 287def __init__ (self ,connections ,read = []): 288if read == []: 289self .weights = [random .randint (- 127 ,127 ) 290for i in range (connections )] 291else : 292self .weights = [binToInt (read [i ])for i in range (connections )] 293 294def activate (self ,connections ): 295temp = 0 296for i in range (len (self .weights )): 297temp += (self .weights [i ]/ 100.0 )* connections [i ] 298return int (temp > 0 ) 299 300def encode (self ): 301return '' .join ([intToBin (self .weights [i ])for i in range (len (self .weights ))]) 302 303 304class Layer (): 305neurons = [] 306 307def __init__ (self ,nodes ,inputs ,read = "" ): 308if read == "" : 309self .neurons = [Neuron (inputs )for i in range (nodes )] 310else : 311temp = [read [i :i + 8 ]for i in range (0 ,len (read ),8 )] 312self .neurons = [ 313Neuron (inputs ,temp [inputs * i :inputs * (i + 1 )])for i in range (nodes )] 314 315def activate (self ,connections ): 316return [self .neurons [i ].activate (connections )for i in range (len (self .neurons ))] 317 318def encode (self ): 319return '' .join ([self .neurons [i ].encode ()for i in range (len (self .neurons ))]) 320 321 322class NeuralNet (): 323layers = [] 324 325def __init__ (self ,size ,inputs ,read = "" ): 326if read == "" : 327self .layers = [Layer (size [i ],inputs if i == 0 else size [ 328i - 1 ])for i in range (len (size ))] 329else : 330temp = read .split (',' ) 331self .layers = [Layer (size [i ],inputs if i == 0 else size [ 332i - 1 ],temp [i ])for i in range (len (size ))] 333 334def activate (self ,inputs ): 335connections = self .layers [0 ].activate (inputs ) 336for i in range (1 ,len (self .layers )): 337connections = self .layers [i ].activate (connections ) 338return connections 339 340def encode (self ): 341return ',' .join ([self .layers [i ].encode ()for i in range (len (self .layers ))]) 342 343 344def breed (a ,b ): 345return '' .join ([a [i ]if random .random ()< .5 else b [i ]for i in range (len (a ))]) 346 347 348def mutate (g ,rate ): 349return '' .join ([g [i ]if random .random ()> rate or g [i ]== ',' else str (int (not (int (g [i ]))))for i in range (len (g ))]) 350 351 352def binToInt (b ): 353return int (b [1 :],2 )* (int (b [0 ],2 )* - 2 + 1 ) 354 355 356def intToBin (i ): 357return ('1' + '0' * (7 - len (bin (i )[3 :]))+ bin (i )[3 :]if i < 0 else '0' * (8 - len (bin (i )[2 :]))+ bin (i )[2 :]) 358 359 360def main (): 361human = True 362viewComputer = True 363 364pygame .init () 365screenSize = screenWidth ,screenHeight = 1200 ,900 366screen = pygame .display .set_mode (screenSize ) 367 368currentTime = time .clock () 369accumulator = 0. 370fps = 1. / 60 371 372player = Car (100 ,100 ,50 ,25 ) 373acceleration = .2 374turnRadius = .425 375handling = .05 376friction = .03 377#maxSpeed = 0 378# for i in range(1000): 379#maxSpeed = (maxSpeed + acceleration) * (1 - friction) 380 381track = Track ("track" ) 382track .reset (player ) 383 384stepsElapsed = 0 385 386networkSize = [6 ,5 ,3 ] 387genSize = 100 388mutationRate = .001 389gen = 0 390genIterator = 0 391genome = [(0 ,"" )for i in range (genSize )] 392dna = '101111110000100100011100001000111101111101100001001010001100100110111001010011110100111100010101111010011001001100010100110011101110000111101101111010011011011111001101011010100100110000000011111100001100100000001101010010110111111110101001,010011001011001100000000000110010111110101001001111011010111101010010011011011011010011110100010010001011111010000111110110011011000011000111001000111101100110001110101010110000000100110101011111000010110011111010000001011000010001010001011,010011010011000001011000000011000111011100001011010110011111101000000010110100101100111001111110011100111001111011111111' 393network = NeuralNet (networkSize ,5 ,dna ) 394 395while 1 : 396for event in pygame .event .get (): 397if event .type == pygame .QUIT : 398sys .exit () 399 400buttons = [] 401 402if human : 403# per second stuff 404# if int(time.clock()) > int(currentTime): 405# print str(int(currentTime)) #+ " "+ str(track.progress(player)) 406# time calculations 407accumulator += time .clock ()- currentTime 408currentTime = time .clock () 409accumulator = min (accumulator ,2 * fps ) 410while accumulator > fps : 411accumulator -= fps 412# game logic 413pressed = pygame .key .get_pressed () 414if pressed [pygame .K_ESCAPE ]: 415sys .exit () 416buttons .append (pressed [pygame .K_UP ]or pressed [pygame .K_w ]) 417buttons .append (pressed [pygame .K_DOWN ]or pressed [pygame .K_s ]) 418buttons .append (pressed [pygame .K_LEFT ]or pressed [pygame .K_a ]) 419buttons .append (pressed [pygame .K_RIGHT ]or pressed [pygame .K_d ]) 420if viewComputer : 421player .updateSensors (track ,screen ) 422buttons = network .activate (player .sensors ) 423buttons .insert (1 ,0 ) 424lost = step (buttons ,player ,track ,acceleration , 425turnRadius ,handling ,friction ) 426if lost [0 ]: 427lost [1 ] 428 429# drawing 430draw (screen ,track ,player ) 431else : 432if pygame .key .get_pressed ()[pygame .K_ESCAPE ]: 433sys .exit 434draw (screen ,track ,player ) 435buttons = network .activate (player .sensors ) 436buttons .insert (1 ,0 ) 437lost = step (buttons ,player ,track ,acceleration , 438turnRadius ,handling ,friction ) 439stepsElapsed += 1 440if lost [0 ]or stepsElapsed > 1500 or (int (player .speed )< 1 and not buttons [0 ]): 441genome [genIterator ]= (int (lost [1 ]),network .encode ()) 442genIterator += 1 443# print "Organism #" + str(genIterator) + " Fitness: " + 444# str(genome[genIterator-1][0]) 445if genIterator == genSize : 446gen += 1 447genome .sort () 448"Generation: " + str (gen )+ " Fitness: " + str (genome [genSize - 1 ]) 449genome = [(0 ,mutate (breed (genome [int (random .triangular (genSize * .75 ,genSize ,genSize ))][1 ],genome [ 450int (random .triangular (genSize * .75 ,genSize ,genSize ))][1 ]),mutationRate ))for i in range (genSize )] 451genIterator = 0 452network = NeuralNet (networkSize ,5 ,genome [genIterator ][1 ]) 453stepsElapsed = 0 454track .reset (player ) 455 456if __name__ == "__main__" : 457main ()