# Canvas: Pathfinding

on in Canvas

## Breadth First Search (BFS) Algorithm

• 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.

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.

See the Pen Breadth First Search (BFS) Algorithm by Ciprian (@ciprian) on CodePen.

### Breadth First Search JavaScript algorithm

``````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();
};
}

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;
}
}
}
}

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);
};

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
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 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];
path1 = search1.findPath(begin);
} else if (moveState === 2) {
target = [xGrid, yGrid];
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);
}
}

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);
}``````
Previous article

Next article

April 12, 2022

March 21, 2022

April 28, 2023