+/GENN

genetically evolving neural networks

git clone https://git.julia.blue/+/GENN

Joseph RyanRestructure file system add graphics libcc48e92

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