// initializing global variables var columns = 20, rows = 20, counter = 0, grid; //---- Some useful functions ---------- Array.prototype.remove = function(elem){ if (this.indexOf(elem) == -1){ console.log(this); console.log(elem) console.log(this.includes(grid.start)) throw "Please comment if you see this error" } this.splice(this.indexOf(elem), 1); return this } // for phones without es6 support Array.prototype.includes = function(elem) { return this.indexOf(elem) != -1 } // the main hero of the algorithm // finds the distance between a given cell and the destination // There are 2 main types of heuristics // |---Exact: exact euclidean distance // |---Approximate: the name suggests... // I've used approximate distance here // Just calculated the sum of the vertical and horizontal distances function heuristic(current, end){ return Math.abs(current.x - end.x) + Math.abs(current.y - end.y) } // the main grid object function Grid(columns, rows, start, end, width, height){ this._arr = []; this.columns = columns; this.rows = rows; // this map is really important as it keeps track of the path // in the best way I can put this, it acts like a traceback where each cell points to the cell traversed next this.cameFrom = new Map(); // cells kept for analysing this.openSet = []; // cells analysed this.closedSet = []; // builds and renders the grid let c = 0, top = 0; for (let i = 0; i < columns; i++){ let temp = []; for (let j = 0; j < rows; j++){ let cell = new Cell(i, j, ++c) if ((i == start[0]) && (j == start[1])) cell.is_start = true; if ((i == end[0]) && (j == end[1])) cell.is_end = true $(".grid").append( `

` ) $("#cell-done").text(c); top += height temp.push(cell); } top = 0; this._arr.push(temp); } // the starting cell this.start = this._arr[start[0]][start[1]] this.start.is_start = true; this.start.visited = true; this.start.gScore = 0; this.openSet.push(this.start) // the destination this.end = this._arr[end[0]][end[1]]; this.end.is_end = true; // finds the cell at a given coordinate this.at = function(x, y){ return (y === undefined)?this._arr[x[0]][x[1]]:this._arr[x][y] } // finds the lowest f-score (see the Cell object below) in the openSet (the cells to be analysed) this.lowest_f = function() { let lowest = this.openSet[0]; for (let j of this.openSet){ if (lowest.fScore > j.fScore) lowest= j } return lowest } this.reset = function(){ this.openSet = [this.start]; this.cameFrom.clear(); this.closedSet =[] for (let row of this._arr){ for (let cell of row){ cell.gScore = Infinity; cell.fScore = 0; } } this.start.visited = true; this.start.gScore = 0; } } function Cell(x, y, id){ this.x = x; this.y = y; this.id = id this.isObstacle = false; // in the simplest words this is the distance from the starting cell to the current cell this.gScore = Infinity; // the f-score decides where the code will go next // the f-score of a cell is the g-score of the cell + the distance to the destination // the lower the f-score, the better // so the f-score is a guess as to how close a cell is to the start as well as the end point this.fScore = 0; this.get_id = function() { return this.id } // finds all the neighbors of the cell // Very inefficient i know this.neighbors = function(grid) { let neighbors = []; if (this.x < grid.columns - 1) neighbors.push(grid.at(this.x + 1, this.y)) if (this.x > 0) neighbors.push(grid.at(this.x - 1, this.y)) if (this.y > 0) neighbors.push(grid.at(this.x, this.y - 1)) if (this.y < grid.rows - 1) neighbors.push(grid.at(this.x, this.y + 1)) if (this.y < grid.rows - 1 && this.x < grid.columns - 1) neighbors.push(grid.at(this.x + 1, this.y + 1)) if (this.y > 0 && this.x > 0) neighbors.push(grid.at(this.x - 1, this.y - 1)) if (this.y < grid.rows - 1 && this.x > 0) neighbors.push(grid.at(this.x - 1, this.y + 1)) if (this.y > 0 && this.x < grid.columns - 1) neighbors.push(grid.at(this.x + 1, this.y - 1)) return neighbors; } } // Just a helper function for generating random numbers function gen_random(start, end){ if (end === undefined){ end = start; start = 0; } return Math.floor(Math.random() * Math.abs(end - start)) + start + 1 } let start, end $(function(){ alert("This is the A-start pathfinding algorithm (Just google it, you'll find a wikipedia page)\n\n1. The blue blocks denote the cells that were analysed\n2. The purple blocks are those kept for analysing\n3.The black blocks are obstacles\n4. The yellow blocks denote the path\n5. The green and red block are the start and end point repectively\n\nPlease don't go on the looks as I've just focused on making the algorithm.") alert("Try increasing the number of rows, columns and obstacles.\n\nClick 'Make board' to make the board and 'Start' to begin the algorithm") // initially set to 40% of the total no. of cells let obstacles = (rows * columns) * 0.4 start = [null, null]; end = [null, null]; //---All this is just input handling and rendering, skip below to the main a_star function----- $("input").attr("min", 0); if ($("#rows").val()) rows = parseInt($("#rows").val()); if ($("#columns").val()) columns = parseInt($("#columns").val()); $("#obstacles").val(obstacles) $("#rows").val(rows) $("#columns").val(columns) if ($("#obstacles").val()) obstacles = parseInt($("#obstacles").val()) $("#obstacles").on("input", function(){ if ($("#obstacles").val()){ try { obstacles = parseInt($("#obstacles").val()) if (obstacles > (rows * columns) - 2){ obstacles = rows * columns * 0.4; alert("Please enter a number smaller than the number of total cells available. No. of obstacles set to " + obstacles + " for now (40% of the total cells)") $(this).val(obstacles) } } catch (e) { alert("Please enter a valid number") } } }) $("#rows,#columns").on("input", function(){ try{ if (!$("#rows").val()) rows = 30; if (!$("#columns").val()) columns = 20; let cells = $("#rows").val() * $("#columns").val() if (cells > 3600){ if (confirm(`You are trying to make a board that has a large number of cells (${cells}). This might take some significant amout of "seconds" to render. Do you wish to continue?`)) { alert("Ok. Click 'Make board' to continue") } else { $("#rows,#columns").val(20); } } if ($(this).val()){ window[$(this).attr("id")] = Number($(this).val()); } obstacles = Math.floor((rows * columns) * 0.4) $("#obstacles").val(obstacles) $(".init").removeAttr("disabled") } catch(e) { alert(e) $(this).val(0) $(".init").attr("disabled", "") } }) $(".reset").on("click", function(){ grid.reset() $(".cell").removeClass("path closed open") $(".init").removeAttr("disabled") }) $(".mk-board").on("click", function(){ let width = (window.outerWidth * 0.95)/ columns; let height = (window.outerHeight * 0.95) / rows; let up_or_down = gen_random(2) let left_or_right = gen_random(2) let rand = [], rand2 = []; if (left_or_right == 1){ rand.push(gen_random(Math.floor(columns * 0.5) - 1, columns - 2)) rand2.push(gen_random(-1, Math.floor(columns / 2) - 2)) } else { rand2.push(gen_random(Math.floor(columns / 2) - 1, columns - 2)) rand.push(gen_random(-1, Math.floor(columns / 2) - 2)) } if (up_or_down == 1){ rand.push(gen_random(-1, Math.floor(rows * 0.5) - 2)) rand2.push(gen_random(Math.floor(rows * 0.5) - 1, rows - 1)) } else { rand2.push(gen_random(-1, Math.floor(rows * 0.5) - 2)) rand.push(gen_random(Math.floor(rows * 0.5) - 1, rows - 2)) } for (let i = 0; i < 2; i++){ if (end[i] !== null) rand[i] = end[i]; if (start[i] !== null) rand2[i] = start[i]; } $(".cell").remove() let top = 0; let en = 1; grid = new Grid(columns, rows, rand2, rand, width, height) for (let i = 0; i < obstacles; i++){ let random = [gen_random(-1, columns - 1), gen_random(-1, rows - 1)] while (grid.at(random).isObstacle && ![grid.start, grid.end].includes(grid.at(random))) random = [gen_random(-1, columns - 1), gen_random(-1, rows - 1)] grid.at(random).isObstacle = true; $("#" + grid.at(random).get_id()).addClass("obstacle") } $(".init").removeAttr("disabled") }); $(".init").on("click", function(){ $("button").attr("disabled", "") a_star(columns, rows, grid) }); $(".mk-board").trigger("click") $(".init").trigger("click") }) // collects the final path when the end point is found function finish(current, map){ // this loop traces the path backwards // it finds from where the current cell came from and then furthur finds from where that cell came from while (grid.cameFrom.get(current)){ if (current != grid.end){ let obj = $(`#${current.get_id()}`) setTimeout(function(){ obj.removeClass('open') obj.removeClass('closed') obj.addClass('path'); }, (++counter) * 10 ) } current = grid.cameFrom.get(current); } setTimeout(function(){ $(".mk-board,.reset").removeAttr("disabled") }, counter * 10) } // this is the juicy stuff function a_star(columns, rows, grid){ while (grid.openSet.length){ // the cell with the lowest f-score let current = grid.lowest_f(); // if it is the destination cell, finish up if (current == grid.end){ finish(current, grid.cameFrom) counter = 0; return } // else remove the current cell from the openSet and move to the set of analysed cells grid.openSet.remove(current); grid.closedSet.push(current); // add the closed class to the current cell if (![grid.start, grid.end].includes(current)) setTimeout(function(){ $(`#${current.get_id()}`).addClass("closed") $(`#${current.get_id()}`).removeClass("open") }, (++counter) * 10 ) // iterate through the neighbor cell of the current cell for (let neighbor of current.neighbors(grid)){ // if neighbor is the destination, end if (neighbor == grid.end){ finish(current, grid.cameFrom) counter = 0; return } // if the neighbor is an obstacle or if it bas already been anayzed, skip this cell if (grid.closedSet.includes(neighbor) || neighbor.isObstacle){ continue; } // if neighbor is not already in openSet add it if (!grid.openSet.includes(neighbor)){ grid.openSet.push(neighbor) if (![grid.start, grid.end].includes(neighbor)) setTimeout(function(){ $(`#${neighbor.get_id()}`).addClass("open") }, (++counter) * 10) } // as each cell has a distance of 1 unit, the next g-score will be the current g-score + 1 let tentative_g = current.gScore + 1; if (tentative_g >= neighbor.gScore) continue // link the neighbor to the current cell // when we are finding the final path, this will tell us where we went from the current cell grid.cameFrom.set(neighbor, current) // set the g-score neighbor.gScore = tentative_g // as stated above, the f-score is the approx. distance from the start + the approx distance till the end neighbor.fScore = neighbor.gScore + heuristic(neighbor, grid.end); } } // if the path is not found yet, there is no path between the start and the ends setTimeout(function(){ $(".mk-board,.reset").removeAttr("disabled"); alert("Path not found") }, ++counter * 10) counter = 0; }

Pathfinding algorithm (A*)