canvas (1)


A* Pathfinding in HTML Canvas

My friend has been working on a new game called Panzer.io, and he reached out to me for the (best) solution for his AI. I instantly thought of the A* algorithm, a simple-to-adapt algorithm that will find the fastest path to a target while avoiding obstacles.

I made a simple HTML canvas app to show it off, check it out:

See the Pen PbKdzw by Stas Darevskiy (@stasadance) on CodePen.

Configuration

This version of the A* requires the game world to be square, but can easily be fixed by modifying the for loops in:

function findPath(world, pathStart, pathEnd)
{
  // shortcuts for speed
    var abs = Math.abs;
    var max = Math.max;
    var pow = Math.pow;
    var sqrt = Math.sqrt;

    // the world data are integers:
    // anything higher than this number is considered blocked
    // this is handy is you use numbered sprites, more than one
    // of which is walkable road, grass, mud, etc
    var maxWalkableTileNum = 0;

    // keep track of the world dimensions
    // Note that this A-star implementation expects the world array to be square: 
    // it must have equal height and width. If your game world is rectangular, 
    // just fill the array with dummy values to pad the empty space.
    var worldWidth = world[0].length;
    var worldHeight = world.length;
    var worldSize = worldWidth * worldHeight;

    // which heuristic should we use?
    // default: no diagonals (Manhattan)
    var distanceFunction = ManhattanDistance;
    var findNeighbours = function(){}; // empty

Modify the heuristic to match your application, in which your game may need the algorithm to speed up or make a more accurate path. You can change var distanceFunction = ManhattanDistance; to DiagonalDistance or EuclideanDistance, and var findNeighbours = function() {}; to var findNeighbours = DiagonalNeighbours; or var findNeighbours = DiagonalNeighboursFree; (allows the path to go in between obstacles diagonally).

Download

Find the source code for my rendition of the A* algorithm on my GitHub here: A* in HTML Canvas, or on the CodePen for it here: A* Pathfinding in HTML Canvas. Thanks to Christer (McFunkypants) Kaitila and Emanuele Feronato for help in the maze generation and overall A* basics.