From 363e3bda2dd91b3715d1dadf59002a45a1039593 Mon Sep 17 00:00:00 2001 From: Brendan Hansen Date: Tue, 12 Mar 2019 00:24:11 -0500 Subject: [PATCH] Kinda workinggit add .git add .! --- main.lua | 72 ++++++++++++++++++++-- src/genetics.lua | 150 ++++++++++++++++++++++++++++++++++++++-------- src/neuralnet.lua | 12 ++-- src/world.lua | 58 +++++++++++++++++- 4 files changed, 256 insertions(+), 36 deletions(-) diff --git a/main.lua b/main.lua index 4325c73..3d0ad3b 100644 --- a/main.lua +++ b/main.lua @@ -2,21 +2,40 @@ local CONF = require "conf" local world_mod = require "src.world" local Input = require "src.input" +local Gen = require "src.genetics" local World = world_mod.World local Enemy = world_mod.Enemy +local Wall = world_mod.Wall +local Population = Gen.Population local world, player local input +local pop +local pop_update + +local enemy_spawn = { 100, 100 } +local enemy function love.load() world, player = World.new() - for _ = 1, 100 do - local enemy = Enemy.new(math.random(800), math.random(600)) - world:add_entity(enemy) - end + enemy = Enemy.new(unpack(enemy_spawn)) + world:add_entity(enemy) + + local wall1 = Wall.new(-20, -20, 840, 20) + local wall2 = Wall.new(-20, 600, 840, 20) + local wall3 = Wall.new(-20, 0, 20, 600) + local wall4 = Wall.new(800, 0, 20, 600) + world:add_entity(wall1) + world:add_entity(wall2) + world:add_entity(wall3) + world:add_entity(wall4) input = Input:new() + pop = Population.new() + pop:create_genomes(100, 16, 8) + pop_update = pop:evolve() + love.graphics.setBackgroundColor(CONF.BACK_COLOR) end @@ -28,17 +47,58 @@ function love.keyreleased(key) input:keyup(key) end +local function network_input(ins, dt) + player.alive = true + for _, v in ipairs(ins) do + --print(v) + end + if ins[1] > 0.5 then input:keydown("w") else input:keyup("w") end + if ins[2] > 0.5 then input:keydown("s") else input:keyup("s") end + if ins[3] > 0.5 then input:keydown("a") else input:keyup("a") end + if ins[4] > 0.5 then input:keydown("d") else input:keyup("d") end + if ins[5] > 0.5 then input:keydown("left") else input:keyup("left") end + if ins[6] > 0.5 then input:keydown("right") else input:keyup("right") end + if ins[7] > 0.5 then input:keydown("up") else input:keyup("up") end + if ins[8] > 0.5 then input:keydown("down") else input:keyup("down") end + + + world:update(dt, input) + + local fitness = 0.5 + + if not player.alive or not enemy.alive then + world:remove_entity(enemy) + enemy = Enemy.new(math.random(800), math.random(600)) + world:add_entity(enemy) + + player.x = 400 + player.y = 300 + + if not enemy.alive then + fitness = fitness + 1000 + end + end + + return fitness, player.alive +end + function love.update(dt) if love.keyboard.isDown "escape" then love.event.quit() end - world:update(dt, input) + for _ = 1, 30 do + local dists = player:get_distances(world) + pop_update = pop_update(dists, network_input, dt) + end end function love.draw() world:draw() love.graphics.setColor(0, 0, 0) - love.graphics.printf(tostring(love.timer.getFPS()) .. " FPS", 0, 0, 800, "center") + --love.graphics.printf(tostring(love.timer.getFPS()) .. " FPS", 0, 0, 800, "center") + if pop.genomes[pop.current_genome] ~= nil then + love.graphics.printf(pop.generation .. " Generation | " .. pop.current_genome .. " Genome | " .. (pop.genomes[pop.current_genome].fitness) .. " Fitness", 0, 0, 800, "center") + end end diff --git a/src/genetics.lua b/src/genetics.lua index 8aa4871..36fbfec 100644 --- a/src/genetics.lua +++ b/src/genetics.lua @@ -1,6 +1,17 @@ local NN = require "src.neuralnet" local NeuralNetwork = NN.NeuralNetwork +-- Globals +local Starting_Weights_Chance = 0.25 +local Starting_Connection_Chance = 2.0 +local Starting_Bias_Chance = 0.4 +local Starting_Split_Chance = 0.5 +local Starting_Enable_Chance = 0.2 +local Starting_Disable_Chance = 0.4 + +local Reset_Weight_Chance = 0.9 +local Crossover_Chance = 0.75 + -- Need a global-ish innovation number, since that depends on the whole training, not just a single genome local Current_Innovation = 1 @@ -53,15 +64,15 @@ function Genome.new(inputs, outputs) genes = {}; fitness = 0; network = {}; -- Neural Network - high_neuron = inputs + outputs; -- Highest numbered neuron in the genome + high_neuron = inputs + outputs + 1; -- Highest numbered neuron in the genome mutations = { -- The different chances of mutating a particular part of the genome - ["weights"] = 1.0; -- Chance of changing the weights - ["connection"] = 1.0; -- Chance of changing the connections (add a gene) - ["bias"] = 1.0; -- Chance of connecting to the bias - ["split"] = 1.0; -- Chance of splitting a gene and adding a neuron - ["enable"] = 1.0; -- Chance of enabling a gene - ["disable"] = 1.0; -- Chance of disablign a gene + ["weights"] = Starting_Weights_Chance; -- Chance of changing the weights + ["connection"] = Starting_Connection_Chance; -- Chance of changing the connections (add a gene) + ["bias"] = Starting_Bias_Chance; -- Chance of connecting to the bias + ["split"] = Starting_Split_Chance; -- Chance of splitting a gene and adding a neuron + ["enable"] = Starting_Enable_Chance; -- Chance of enabling a gene + ["disable"] = Starting_Disable_Chance; -- Chance of disablign a gene } } @@ -80,14 +91,11 @@ function Genome:add_gene(from, to, weight) end function Genome:copy() - local newG = Genome.new() + local newG = Genome.new(self.num_inputs - 1, self.num_outputs) for g = 1, #self.genes do table.insert(newG.genes, self.genes[g]:copy()) end - newG.num_inputs = self.num_inputs - newG.num_ouputs = self.num_outputs - newG.high_neuron = self.high_neuron for mut_name, val in pairs(self.mutations) do @@ -102,6 +110,8 @@ function Genome:create_network() for i = 1, #self.genes do local gene = self.genes[i] + print("----------------------") + print(gene.innovation, gene.from, gene.to, gene.weight) if gene.enabled then if not net:has_neuron(gene.to) then @@ -123,7 +133,8 @@ function Genome:has_gene(from, to) for i = 1, #self.genes do local gene = self.genes[i] - if gene.to == to and gene.from == from then + if (gene.to == to and gene.from == from) + or (gene.to == from and gene.from == to) then return true end end @@ -138,8 +149,7 @@ function Genome:mutate_weights() for i = 1, #self.genes do local gene = self.genes[i] - -- Just some constant, probably put that somewhere... eventually - if math.random() < 0.8 then + if math.random() < Reset_Weight_Chance then gene.weight = gene.weight + math.random() * change * 2 - change -- (-change, change) else gene.weight = math.random() * 4 - 2 -- Randomly change it to be in (-2, 2) @@ -153,7 +163,27 @@ function Genome:mutate_connections(connect_to_bias) local neuron2 = self:get_random_neuron(false) -- NOT an input if connect_to_bias then - neuron2 = self.num_inputs -- This is going to be the id of the bias neuron + neuron1 = self.num_inputs -- This is going to be the id of the bias neuron + end + + -- Cant go to itself + if neuron1 == neuron2 then + return + end + + -- Output cant be input + if (neuron1 > self.num_inputs and neuron1 <= self.num_inputs + self.num_outputs) then + return + end + + -- Cant both be inputs + if neuron1 <= self.num_inputs and neuron2 <= self.num_inputs then + return + end + + -- Cant go to input + if neuron2 <= self.num_inputs then + return end if self:has_gene(neuron1, neuron2) then @@ -161,6 +191,7 @@ function Genome:mutate_connections(connect_to_bias) end local weight = math.random() * 4 - 2 + assert(neuron1 ~= neuron2, "IN MUTATE CONNECTIONS") self:add_gene(neuron1, neuron2, weight) end @@ -189,6 +220,8 @@ function Genome:mutate_neuron() gene1.innovation = Get_Next_Innovation() gene1.enabled = true + assert(gene1.from ~= gene1.to, "IN MUTATE NEURON") + table.insert(self.genes, gene1) local gene2 = gene:copy() @@ -196,6 +229,8 @@ function Genome:mutate_neuron() gene2.innovation = Get_Next_Innovation() gene2.enabled = true + assert(gene2.from ~= gene2.to, "IN MUTATE NEURON") + table.insert(self.genes, gene2) end @@ -231,7 +266,7 @@ function Genome:mutate() end -- Randomly use the mutation functions above to create a slightly different genome - local prob = self.mutation["connections"] + local prob = self.mutations["connection"] while prob > 0 do if math.random() < prob then self:mutate_connections(false) @@ -240,7 +275,7 @@ function Genome:mutate() prob = prob - 1 end - prob = self.mutation["bias"] + prob = self.mutations["bias"] while prob > 0 do if math.random() < prob then self:mutate_connections(true) @@ -249,7 +284,7 @@ function Genome:mutate() prob = prob - 1 end - prob = self.mutation["split"] + prob = self.mutations["split"] while prob > 0 do if math.random() < prob then self:mutate_neuron() @@ -258,7 +293,7 @@ function Genome:mutate() prob = prob - 1 end - prob = self.mutation["enable"] + prob = self.mutations["enable"] while prob > 0 do if math.random() < prob then self:mutate_enabled(true) @@ -267,7 +302,7 @@ function Genome:mutate() prob = prob - 1 end - prob = self.mutation["disable"] + prob = self.mutations["disable"] while prob > 0 do if math.random() < prob then self:mutate_enabled(false) @@ -333,7 +368,7 @@ function Genome:crossover(other) genome2 = tmp end - local child = Genome.new(genome1.num_inputs, genome1.num_outputs) + local child = Genome.new(genome1.num_inputs - 1, genome1.num_outputs) -- Create a list of all the innovation numbers for the 2nd (worse) genome local innov2 = {} @@ -368,6 +403,7 @@ function Population.new() local o = { genomes = {}; generation = 0; + current_genome = 0; high_fitness = 0; avg_fitness = 0; } @@ -381,6 +417,7 @@ function Population:create_genomes(num, inputs, outputs) for i = 1, num do genomes[i] = Genome.new(inputs, outputs) + genomes[i]:mutate() end end @@ -388,8 +425,7 @@ function Population:breed_genome() local genomes = self.genomes local child - -- Another random constant that should be in a global variable - if math.random() < 0.4 then + if math.random() < Crossover_Chance then local g1 = genomes[math.random(1, #genomes)] local g2 = genomes[math.random(1, #genomes)] child = g1:crossover(g2) @@ -409,21 +445,85 @@ function Population:kill_worst() return a.fitness > b.fitness end) - local count = math.floor(#self.genomes / 2) + local count = math.floor(3 * #self.genomes / 4) for _ = 1, count do table.remove(self.genomes) -- This removes the last (worst) genome end + for i = 1, #self.genomes do + self.genomes[i].fitness = 0 + end + collectgarbage() -- Since we just freed a bunch of memory, best to do this now instead of letting it pile up end function Population:mate() - local count = #self.genomes + local count = #self.genomes * 3 -- Double the population size for _ = 1, count do table.insert(self.genomes, self:breed_genome()) end + self.generation = self.generation + 1 end + +function Population:evolve() + local evolve_test, finish_evolve + + -- First we need to calculate the fitnesses of every genome + self.current_genome = 0 + function evolve_test(inputs, output_func, ...) + if self.current_genome == 0 then + self.current_genome = 1 + self.genomes[self.current_genome]:create_network() + end + + if self.current_genome <= #self.genomes then + -- Assumes genome has network generated + local genome = self.genomes[self.current_genome] + inputs[#inputs + 1] = 1 -- Bias neuron + + genome.network:activate(inputs) + + local outputs = genome.network:get_outputs() + local fitness_change, cont = output_func(outputs, ...) + + genome.fitness = genome.fitness + fitness_change + + if cont then + return evolve_test + else + self.current_genome = self.current_genome + 1 + if self.current_genome <= #self.genomes then + self.genomes[self.current_genome]:create_network() + return evolve_test + else + return finish_evolve + end + end + else + return finish_evolve + end + end + + -- Then we need to kill off the worst of them + -- Then we breed more + -- Rinse and repeat! + function finish_evolve() + self:kill_worst() + self:mate() + + self.current_genome = 0 + return evolve_test + end + + return evolve_test +end + +return { + Gene = Gene; + Genome = Genome; + Population = Population; +} diff --git a/src/neuralnet.lua b/src/neuralnet.lua index 720157a..41e6f87 100644 --- a/src/neuralnet.lua +++ b/src/neuralnet.lua @@ -42,7 +42,8 @@ function NeuralNetwork:add_connection(from, to, weight, id) local neurons = self.neurons if type(from) == "table" then - table.insert(neurons[to].inputs, from) + assert(from.to ~= from.from, "NEURON GOING TO ITSELF") + table.insert(neurons[from.to].inputs, from) else table.insert(neurons[to].inputs, { to = to; @@ -75,15 +76,18 @@ function NeuralNetwork:activate(inputs) local ns = self.neurons for i = 1, self.num_inputs do + assert(inputs[i] ~= nil, "INPUT WAS NIL") self.neurons[i].value = inputs[i] end - for i = self.num_inputs + 1, #ns do - ns[i].dirty = true + for i, _ in pairs(ns) do + if i > self.num_inputs then + ns[i].dirty = true + end end -- Iterate backwards since the hidden nodes are going to be at the end of the array - for i = #ns, self.num_inputs + 1, -1 do + for i, _ in pairs(ns) do if ns[i].dirty then self:activate_neuron(i) end diff --git a/src/world.lua b/src/world.lua index 0cd6bae..6c7d03c 100644 --- a/src/world.lua +++ b/src/world.lua @@ -33,6 +33,7 @@ end function Bullet:collide(other, dx, dy, world) if other.ENTITY_TYPE == "Enemy" then + other.alive = false world:remove_entity(other) world:remove_entity(self) end @@ -82,6 +83,7 @@ function Player.new() x = CONF.WINDOW_WIDTH / 2; y = CONF.WINDOW_HEIGHT / 2; r = 20; + alive = true; fire_cooldown = 0; distances = {}; @@ -141,6 +143,10 @@ function Player:get_rect() end function Player:collide(other, dx, dy, world) + if other.ENTITY_TYPE == "Wall" then + self.x = self.x - dx + self.y = self.y - dy + end end function Player:get_distances(world) @@ -188,6 +194,8 @@ function Player:get_distances(world) end end + assert(#ret == 16, "RET NOT LONG ENOUGH") + return ret end @@ -224,7 +232,8 @@ function Enemy.new(x, y) local o = { x = x; y = y; - size = CONF.ENEMY_SIZE + size = CONF.ENEMY_SIZE; + alive = true; } setmetatable(o, Enemy_mt) @@ -251,6 +260,11 @@ function Enemy:collide(other, dx, dy, world) self.x = self.x - dx self.y = self.y - dy end + + if other.ENTITY_TYPE == "Player" then + other.alive = false + world:remove_entity(self) + end end function Enemy:draw() @@ -258,6 +272,39 @@ function Enemy:draw() love.graphics.rectangle("fill", unpack(self:get_rect())) end + +-- Wall class -- + +local Wall = {} +local Wall_mt = { __index = Wall } +Wall.ENTITY_TYPE = "Wall" + +function Wall.new(x, y, w, h) + local o = { + x = x; + y = y; + w = w; + h = h; + } + + setmetatable(o, Wall_mt) + return o +end + +function Wall:update(dt) +end + +function Wall:draw() +end + +function Wall:get_rect() + return { self.x, self.y, self.w, self.h } +end + +function Wall:collide(other, dx, dy, world) +end + + -- WORLD -- local World = {} @@ -315,12 +362,17 @@ function World:remove_entity(ent_or_id) end end + if pos == 0 then return end + table.remove(self.entities, pos) end -- Assumes ent has x, y and get_rect function World:move_entity(ent, dx, dy) ent.x = ent.x + dx + if math.rectintersects(self.player:get_rect(), ent:get_rect()) then + ent:collide(self.player, dx, 0, self) + end for _, e in ipairs(self.entities) do if e.id ~= ent.id then if math.rectintersects(e:get_rect(), ent:get_rect()) then @@ -330,6 +382,9 @@ function World:move_entity(ent, dx, dy) end ent.y = ent.y + dy + if math.rectintersects(self.player:get_rect(), ent:get_rect()) then + ent:collide(self.player, dx, 0, self) + end for _, e in ipairs(self.entities) do if e.id ~= ent.id then if math.rectintersects(e:get_rect(), ent:get_rect()) then @@ -352,4 +407,5 @@ return { Player = Player; Enemy = Enemy; Bullet = Bullet; + Wall = Wall; } -- 2.25.1