Canvas: Pathfinding

Part 9 of the HTML5 Canvas series — see the full series.

Breadth First Search (BFS) Algorithm

Pathfinding is simply the problem of finding the shortest route between two points on a grid, working around any obstacles in the way — the same thing a game character does when it walks around a wall to reach you. Breadth-First Search is one of the classic ways to solve it. It explores the grid in expanding rings: it checks every square one step away from the start, then every square two steps away, and so on, until it reaches the target. Because it always reaches nearer squares before farther ones, the first time it touches the end point it has, by definition, found one of the shortest possible paths. That ring-by-ring exploration is exactly what you can watch happening in the demo below.

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

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

← Previous: A big ball of particles | Next: A simple drawing application →