const w = innerWidth, h = innerHeight const v = Math.min(w, h), scale = 0.85 var ctx var maze = [], walkers = [] const mazeSize = 7, complexity = 0.1 const generationSize = 60, mutationFactor = 0.05 var generationNumber = 0 onload = () => { let cvs = document.querySelector("canvas") cvs.width = w, cvs.height = h ctx = cvs.getContext("2d") ctx.font = "14px sans-serif" setup() run() } function setup() { // generating maze // start point: (0,0) // end point: (mazeSize-1,mazeSize-1) for(let y = 0; y < mazeSize; y++) { maze.push([]) for(let x = 0; x < mazeSize; x++) { if(x+y==0||x+y==2*mazeSize-2) maze[y].push(false) else maze[y].push(Math.random() < complexity) } } // creating first generation of walkers for(let i = 0; i < generationSize; i++) walkers.push(new Walker()) } function makeNewGeneration() { generationNumber++ // pick most traveled walker to grab its gens const parent = walkers.sort((w, u) => u.traveled() - w.traveled() )[0] walkers = [] for(let i = 0; i < generationSize; i++) { const w = new Walker() if(parent) w.cloneGens(parent) walkers.push(w) } } function run() { ctx.clearRect(0, 0, w, h) renderMaze() renderInfo() // prepare a step for each walker // keep updating alive only walkers.forEach(w => { if(w.isDead()) return w.render() w.makeStep() }) // find someone who has reached the end if(walkers.map(w => w.isAtEnd()).includes(true)) { setTimeout(() => { alert("it tooks " + generationNumber + " generations for walkers to learn correct path, wow!") alert("thanks for watching this code and waiting so long. Please, give it a like 😊") }, 500) ctx.clearRect(0, 0, w, h) renderMaze() renderInfo() walkers.forEach(w => !w.isDead() && w.render()) return } // if there is no walker alive // make new generation if(!walkers.map(w => w.isDead()).includes(false)) makeNewGeneration() // repeat forever setTimeout(run, 1) } function renderMaze() { const d = scale*v/mazeSize for(let y = 0; y < mazeSize; y++) for(let x = 0; x < mazeSize; x++) { const sx = w/2-scale*v/2 + x*d const sy = h/2-scale*v/2 + y*d ctx.strokeRect(sx, sy, d, d) if(maze[y][x]) ctx.fillRect(sx, sy, d, d) } } function renderInfo() { ctx.fillText('generation #' + generationNumber, 4, 20) } function Walker() { let x = 0, y = 0 let lifespan = mazeSize*4 // adding random gens let gens = [] for(let j = 0; j < mazeSize; j++) { gens.push([]) for(let i = 0; i < mazeSize; i++) gens[j].push(~~(4*Math.random())) } this.getGens = () => { return gens } this.cloneGens = parent => { const parentGens = parent.getGens() for(let j = 0; j < mazeSize; j++) for(let i = 0; i < mazeSize; i++) { // mutation factor if(Math.random() < mutationFactor) gens[j][i] = ~~(4*Math.random()) else gens[j][i] = parentGens[j][i] } } this.traveled = () => { return x + y } this.makeStep = () => { switch(gens[y][x]) { case 0: y--; break; case 1: x++; break; case 2: y++; break; case 3: x--; break; } lifespan--; } this.isDead = () => { // out of boundaries or staying in the wall // or making a loop over time return x < 0 || y < 0 || x >= mazeSize || y >= mazeSize || maze[y][x] || lifespan <= 0; } this.isAtEnd = () => { return x == mazeSize - 1 && y == mazeSize - 1 } this.render = () => { const d = scale*v/mazeSize const sx = w/2-scale*v/2 + (x+0.5)*d const sy = h/2-scale*v/2 + (y+0.5)*d ctx.beginPath() ctx.arc(sx, sy, 0.25*d, 0, 2*Math.PI) ctx.fill() } }

path finding genetic algorithm