window.onload = function(){ var W = 600; var canvas = document.createElement('canvas'); canvas.setAttribute('width',W); canvas.setAttribute('height',W); var D = window.innerWidth; canvas.setAttribute('style','width: '+D+'px; height: '+D+'px;'); document.body.appendChild(canvas); var p = document.createElement('p'); p.innerHTML = 'Generation: 1'; document.body.appendChild(p); var c = canvas.getContext('2d'); var FPS = 50; var getDist = function(x1,y1,x2,y2){ var xx = x1-x2; var yy = y1-y2; return Math.sqrt(xx*xx+yy*yy); } var createVector = function(vx,vy){ return { x:vx, y:vy, add:function(ov){ this.x += ov.x; this.y += ov.y; return this; }, heading:function(){ return Math.atan2(this.y,this.x); }, setMag:function(nlen){ var clen = getDist(0,0,this.x,this.y); this.x *= nlen/clen; this.y *= nlen/clen; return this; } }; } var vectRan2D = function(){ var angle = Math.PI*2*Math.random(); var vect = createVector(Math.cos(angle),Math.sin(angle)); return vect.setMag(magnitude); } function Population(){ this.rockets = []; this.popsize = 100; this.matingPool; for(var i = 0; i < this.popsize; i++){ this.rockets[i] = new Rocket(); } this.evaluate = function(){ var maxFit = 0; for(var i = 0; i < this.popsize; i++){ this.rockets[i].calcFitness(); if(this.rockets[i].fitness > maxFit){ maxFit = this.rockets[i].fitness; } } this.matingPool = []; for(var i = 0; i < this.popsize; i++){ var n = this.rockets[i].fitness*10/maxFit; for(var j = 0; j < n; j++){ this.matingPool.push(this.rockets[i]); } } } this.selection = function(){ var newRockets = []; this.rockets.sort(function(a,b){ return b.fitness-a.fitness; }); for(var i in this.rockets){ var parent = this.matingPool[Math.floor(this.matingPool.length*Math.random())].dna; var child = new DNA(parent.genes.slice()); child.mutation(); var rocket = new Rocket(child); if(i < 10) rocket.color = 'red'; newRockets.push(rocket); } this.rockets = newRockets; p.innerHTML = 'Generation: '+(++generation); } this.run = function(){ for(var i = 0; i < this.popsize; i++){ this.rockets[i].update(); this.rockets[i].show(); } } } function DNA(genes){ if(genes){ this.genes = genes; }else{ this.genes = []; for(var i = 0; i < lifespan; i++){ this.genes.push(vectRan2D()); } } this.mutation = function(){ for(var i in this.genes){ if(Math.random() < mutation/100){ this.genes[i] = vectRan2D(0.1); } } } } function Rocket(dna){ this.pos = createVector(start.x,start.y); this.spd = createVector(0,0); this.acc = createVector(0,0); this.completed = false; this.crash = false; this.color = '#0AF'; if(dna){ this.dna = dna; }else{ this.dna = new DNA(); } this.applyForce = function(force){ this.acc.add(force); } this.calcFitness = function(){ var d = getDist(this.pos.x,this.pos.y,target.x,target.y); this.fitness = 1/d; if(this.completed){ this.fitness *= 10; } if(this.crash){ this.fitness /= 10; } } this.update = function(){ if(this.pos.x > target.x-7.5 && this.pos.x < target.x+7.5 && this.pos.y > target.y-7.5 && this.pos.y < target.y+7.5){ this.completed = true; } for(var o in obstacles){ if(this.pos.x > obstacles[o].x && this.pos.x < obstacles[o].x+obstacles[o].w && this.pos.y > obstacles[o].y && this.pos.y < obstacles[o].y+obstacles[o].h){ this.crash = true; } } this.applyForce(this.dna.genes[count]); if(!this.completed && !this.crash){ this.spd.add(this.acc); this.pos.add(this.spd); this.acc.x = 0; this.acc.y = 0; } } this.show = function(){ c.save(); c.translate(this.pos.x,this.pos.y); c.rotate(this.spd.heading()); c.fillStyle = this.color; c.globalAlpha = 0.5; c.beginPath(); c.moveTo(15,0); c.lineTo(-10,-5); c.lineTo(-5,0); c.lineTo(-10,5); c.lineTo(15,0); c.fill(); c.restore(); } } var newObstacle = function(x,y,w,h){ var obs = { x:x, y:y, w:w, h:h }; obs.draw = function(){ c.fillStyle = '#AA8'; c.fillRect(x,y,w,h); } obstacles.push(obs); } var start = { x:W/5, y:4*W/5, col:'#06F' }; var target = { x:4*W/5, y:W/5, col:'#0FA' }; /* var swapY = false; var but = document.createElement('button'); but.innerHTML = 'Swap'; but.addEventListener('click',function(){ if(!swapY){ start.x += target.x; target.x = start.x-target.x; start.x -= target.x; }else{ start.y += target.y; target.y = start.y-target.y; start.y -= target.y; } swapY = !swapY; }); document.body.appendChild(but); */ var generation = 1; var lifespan = 200; var magnitude = 0.2; var mutation = 1; var count = 0; var obstacles = []; newObstacle(25,25,25,550); newObstacle(25,25,550,25); newObstacle(550,25,25,550); newObstacle(25,550,550,25); newObstacle(200,200,200,200); var pop = new Population(); setInterval(function(){ c.clearRect(0,0,W,W); c.fillStyle = start.col; c.fillRect(start.x-7,start.y-7,15,15); c.fillStyle = target.col; c.fillRect(target.x-7,target.y-7,15,15); for(var i in obstacles){ obstacles[i].draw(); } pop.run(); if(++count == lifespan){ count = 0; pop.evaluate(); pop.selection(); } },1000/FPS); }

Genetic path finding