Breadth First Search (BFS) Algorythm
- Breadth First Search (BFS) is an algorithm for traversing an unweighted Graph or a Tree.
- BFS starts with the root node and explores each adjacent node before exploring node(s) at the next level.
- BFS makes use of Queue for storing the visited nodes of the graph / tree.
Below is a Breadth First Search implementation using Canvas and Vanilla JavaScript.
This article is part of the JavaScript Canvas series where I post experiments, JavaScript generative art, visualizations, Canvas animations, code snippets and how-to’s.
You can drag the start point (blue) and the end point (red) to change the path. Click and drag your mouse on empty blocks to add walls. Click and drag your mouse on walls to remove them.
Breadth First Search JavaScript algorythm
function Graph(w, h) {
this.width = w;
this.height = h;
this.walls = [];
}
/**
* @param id: [x, y]
* @returns {boolean}
*/
Graph.prototype.inBounds = function (id) {
return (0 <= id[0] && id[0] < this.width && 0 <= id[1] && id[1] < this.height);
};
Graph.prototype.passable = function (id) {
for (var i = 0; i < this.walls.length; i++) {
if (this.walls[i][0] === id[0] && this.walls[i][1] === id[1]) {
return false;
}
}
return true;
};
Graph.prototype.neighbors = function (id) {
var x = id[0];
var y = id[1];
var results = [[x+1, y], [x,y-1], [x-1,y], [x,y+1]];
results = results.filter(this.passable, this);
results = results.filter(this.inBounds, this);
return results;
};
Graph.prototype.print = function () {
var info = '';
for (var j = 0; j < this.height; j++) {
for (var i = 0; i < this.width; i++) {
if (this.walls.hasArray([i, j])) {
info += "#";
}
else {
info += ".";
}
}
info += "\n";
}
// console.log(info);
};
function Queue() {
this.elements = [];
this.empty = function() {
return elements.length === 0;
};
this.put = function(x) {
this.elements.push(x);
};
this.get = function() {
return this.elements.shift();
};
}
function BreadthFirstSearch(graph, start) {
this.graph = graph;
this.width = graph.width;
this.height = graph.height;
this.start = start;
var frontier = new Queue;
frontier.put(start);
var visited = [start];
this.came_from = [];
for (var i = 0; i < this.width; i++) {
this.came_from[i] = [];
for (var j = 0; j < this.height; j++) {
this.came_from[i][j] = null;
}
}
this.distance = [];
for (i = 0; i < this.width; i++) {
this.distance[i] = [];
for (j = 0; j < this.height; j++) {
this.distance[i][j] = -1;
}
}
var current;
var curNeighbors = [];
while (frontier.elements.length !== 0) {
current = frontier.get();
curNeighbors = graph.neighbors(current);
for (i = 0; i < curNeighbors.length; i++) {
var next = curNeighbors[i];
if (! visited.hasArray(next)) {
frontier.put(next);
visited.push(next);
this.came_from[next[0]][next[1]]= current;
this.distance[next[0]][next[1]] = this.distance[current[0]][current[1]] + 1;
}
}
}
}
BreadthFirstSearch.prototype.showPath = function(id) {
var info = '';
for (var j = 0; j < this.height; j++) {
for (var i = 0; i < this.width; i++) {
if (this.graph.walls.hasArray([i, j])) {
info += "#\t\t";
}
else {
info += this.came_from[i][j]+"\t\t";
}
}
info += "\n";
}
console.log(info);
};
BreadthFirstSearch.prototype.showDistance = function() {
var info = '';
for (var j = 0; j < this.graph.height; j++) {
for (var i = 0; i < this.graph.width; i++) {
if (this.graph.walls.hasArray([i, j])) {
info += "#\t";
}
else {
info += this.distance[i][j]+"\t";
}
}
info += "\n";
}
console.log(info);
};
// This path includes both start and end point
BreadthFirstSearch.prototype.findPath = function(id) {
var ret = [];
var curX = id[0];
var curY = id[1];
if (this.came_from[curX][curY] === null) {return [];}
ret.push(id);
while(curX !== this.start[0] || curY !== this.start[1]) {
var x = this.came_from[curX][curY][0];
var y = this.came_from[curX][curY][1];
ret.push([x, y]);
curX = x;
curY = y;
}
return ret;
};
Array.prototype.hasArray = function(arr) {
for (var i = 0; i < this.length; i++) {
if (this[i][0] === arr[0] && this[i][1] === arr[1]) {
return true;
}
}
return false;
};
Array.prototype.removeArray = function(arr) {
for (var i = 0; i < this.length; i++) {
if (this[i][0] === arr[0] && this[i][1] === arr[1]) {
this.splice(i, 1);
return true;
}
}
return false;
};
/*
g = new Graph(10, 10);
var walls = [[1, 7], [1, 8], [2, 7], [2, 8], [3, 7], [3, 8], [0,0], [6,2], [6,3], [6,4]];
for (var i = 0; i < walls.length; i++) {
g.walls.push(walls[i]);
}
g.print();
/**/And this is the pathfinding scene setup for the demo above:
let canvas = document.getElementById('drawing');
let context = canvas.getContext('2d');
canvas.width = 800;
canvas.height = 420;
let sizeX = 40;
let sizeY = 20;
let gridWidth = 20;
let gridHeight = 20;
// Which grid your mouse is in now
let xGrid = 0;
let yGrid = 0;
let drawPathCount = 0;
let pathChanged = true;
function fillGrid(x, y, color) {
context.fillStyle = color || '#b8e994';
context.fillRect(x * (gridWidth + 1), y * (gridHeight + 1), gridWidth + 1, gridHeight + 1);
}
let map = new Graph(sizeX, sizeY);
let mapState = [];
for (var i = 0; i < sizeX; i++) {
mapState[i] = [];
for (var j = 0; j < sizeY; j++) {
mapState[i][j] = 0;
}
}
let walls = [
[4, 3],
[4, 4],
[4, 5],
[4, 6],
[4, 7],
[4, 8],
[4, 9],
[4, 10],
[4, 11],
[4, 12],
[4, 2],
[5, 2],
[6, 2],
[7, 2],
[8, 2],
[9, 2],
[9, 3],
[9, 4],
[9, 5],
[9, 6],
[8, 7],
[7, 7],
[6, 7],
[5, 7],
[9, 7],
[9, 8],
[9, 9],
[9, 10],
[9, 11],
[9, 12],
[8, 12],
[7, 12],
[6, 12],
[5, 12],
[13, 2],
[14, 2],
[15, 2],
[16, 2],
[17, 2],
[18, 2],
[13, 3],
[13, 4],
[13, 5],
[13, 6],
[13, 7],
[13, 8],
[13, 9],
[13, 10],
[13, 11],
[13, 12],
[14, 7],
[15, 7],
[16, 7],
[17, 7],
[18, 7],
[22, 2],
[23, 2],
[24, 2],
[25, 2],
[26, 2],
[27, 2],
[22, 3],
[22, 4],
[22, 5],
[22, 6],
[22, 7],
[23, 7],
[24, 7],
[25, 7],
[26, 7],
[27, 7],
[27, 8],
[27, 9],
[27, 10],
[27, 11],
[26, 12],
[27, 12],
[25, 12],
[24, 12],
[23, 12],
[22, 12]
];
for (i = 0; i < walls.length; i++) {
map.walls.push(walls[i]);
mapState[walls[i][0]][walls[i][1]] = 1;
}
drawWalls();
function drawWalls() {
for (i = 0; i < map.walls.length; i++) {
fillGrid(map.walls[i][0], map.walls[i][1], '#3c6382');
}
}
let target = [1, 1];
let begin = [20, 12];
let moveState = 0;
let search1 =new BreadthFirstSearch(map, target);
let path1 = search1.findPath(begin);
pathChanged = true;
drawPath(path1);
function drawBoard() {
context.clearRect(0, 0, canvas.width, canvas.height);
context.beginPath();
context.strokeStyle = '#3c6382';
context.lineWidth = 1;
// Draw vertical lines
for (var i = 0; i < sizeX + 1; i++) {
context.moveTo(i * (gridWidth + 1), 0);
context.lineTo(i * (gridWidth + 1), sizeY * (gridHeight + 1));
}
context.stroke();
// Draw horizontal lines
for (i = 0; i < sizeY + 1; i++) {
context.moveTo(0, i * gridWidth + i);
context.lineTo(sizeX * (gridWidth + 1), i * gridWidth + i);
}
context.stroke();
}
function mouseDown(e) {
if (xGrid < sizeX && yGrid < sizeY) {
if (begin[0] === xGrid && begin[1] === yGrid) {
moveState = 1; // Change begin (green) point's position
} else if (target[0] === xGrid && target[1] === yGrid) {
moveState = 2; // Change target (red) point's position
} else if (map.walls.hasArray([xGrid, yGrid])) {
moveState = 3; // Turn walls to blank
} else {
moveState = 4; // Turn blank to walls
}
}
}
function mouseUp(e) {
moveState = 0; // move and do nothing
}
function mouseMove(e) {
let mouseX, mouseY;
if (e.offsetX) {
mouseX = e.offsetX;
mouseY = e.offsetY;
} else if (e.layerX) {
mouseX = e.layerX;
mouseY = e.layerY;
}
// Calculate which grid mouse is in
xGrid = Math.floor(mouseX / (gridWidth+1));
yGrid = Math.floor(mouseY / (gridHeight+1));
if (xGrid < sizeX && yGrid < sizeY) {
if (moveState === 0) {
return;
} else if (moveState === 1) {
begin = [xGrid, yGrid];
search1 = new BreadthFirstSearch(map, target);
path1 = search1.findPath(begin);
} else if (moveState === 2) {
target = [xGrid, yGrid];
search1 = new BreadthFirstSearch(map, target);
path1 = search1.findPath(begin);
} else if (moveState === 3) { // Turn walls to blank
map.walls.removeArray([xGrid, yGrid]);
mapState[xGrid][yGrid] = Math.abs(mapState[xGrid][yGrid] - 1);
} else if (moveState === 4) {
if (!map.walls.hasArray([xGrid, yGrid])) {
map.walls.push([xGrid, yGrid]);
mapState[xGrid][yGrid] = Math.abs(mapState[xGrid][yGrid] - 1);
}
}
search1 = new BreadthFirstSearch(map, target);
if (search1.came_from[begin[0]][begin[1]] === null) {
path1 = [];
pathChanged = true;
} else {
path1 = search1.findPath(begin);
pathChanged = true;
}
// console.log(map.walls.length);
}
}
function drawPath(path) {
for (i = 0; i < path.length; i++) {
fillGrid(path[i][0], path[i][1], '#b8e994');
}
}
function drawPathAnimation(path) {
if (drawPathCount >= path.length) {
drawPathCount = 0;
pathChanged = false;
} else {
drawPathCount ++;
for (i = 0; i < drawPathCount; i++) {
fillGrid(path[i][0], path[i][1], '#b8e994');
}
}
}
requestAnimationFrame = (function () {
return window.requestAnimationFrame ||
window.webkitRequestAnimationFrame ||
window.mozRequestAnimationFrame ||
window.oRequestAnimationFrame ||
window.msRequestAnimationFrame ||
function (callback) {
window.setTimeout(callback, 1000/30);
};
})();
requestAnimationFrame(draw);
function draw() {
requestAnimationFrame(draw);
drawBoard();
drawWalls();
if (path1 !== [] && moveState === 0) {
if (pathChanged ) {
drawPathAnimation(path1);
} else {
drawPath(path1);
}
}
fillGrid(target[0], target[1], '#e55039');
fillGrid(begin[0], begin[1], '#4a69bd');
}
function printWallsPos() {
let posInfo = '';
for (i = 0; i < map.walls.length; i++) {
posInfo += '[' + map.walls[i][0] + ', ' + map.walls[i][1] + '],';
}
//console.log(posInfo);
}
