# Pure JavaScript A* maze solving – with a bit of magic thanks to Phaser and EasyStar.js

In my previous post I showed you how to create a pure JavaScript perfect tile maze generation, with a visual step by step process.

There isn’t any maze without an algorithm to solve it, and one of the most famous algorithms used in maze solving is the so-called A*.

From Wikipedia: In computer science, A* (pronounced as “A star”) is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between multiple points, called nodes. Noted for its performance and accuracy, it enjoys widespread use.

Here is the maze of the original post, solved by A* algorithm, going from the top left cell to the bottom right cell:

Phaser was used to draw the maze and animate the red dot as it travels through the maze.

Since there’s no need to reinvent the wheel, I used the amazing EasyStar.js by Bryce Neal. There is also a Phaser plugin but I used the original library.

Here is the source code, with only new lines highlighted:

index.html:

```<!DOCTYPE html>
<html>
<style type="text/css">
body{
margin:0px;
}
</style>
<script src="phaser.min.js"></script>
<script src="easystar-0.2.1.min.js"></script>
<script src = "game.js"></script>
<body>
</body>
</html>```

game.js:

```var game;
var maze = [];
var mazeWidth = 81;
var mazeHeight = 61;
var tileSize = 10;
var mazeGraphics;

game = new Phaser.Game(810, 610, Phaser.CANVAS, "");
game.state.start("PlayGame");
}

var playGame = function(game){};

playGame.prototype = {
create: function(){
var moves = [];
for(var i = 0; i < mazeHeight; i ++){
maze[i] = [];
for(var j = 0; j < mazeWidth; j ++){
maze[i][j] = 1;
}
}
var posX = 1;
var posY = 1;
maze[posX][posY] = 0;
moves.push(posY + posY * mazeWidth);
while(moves.length){
var possibleDirections = "";
if(posX+2 > 0 && posX + 2 < mazeHeight - 1 && maze[posX + 2][posY] == 1){
possibleDirections += "S";
}
if(posX-2 > 0 && posX - 2 < mazeHeight - 1 && maze[posX - 2][posY] == 1){
possibleDirections += "N";
}
if(posY-2 > 0 && posY - 2 < mazeWidth - 1 && maze[posX][posY - 2] == 1){
possibleDirections += "W";
}
if(posY+2 > 0 && posY + 2 < mazeWidth - 1 && maze[posX][posY + 2] == 1){
possibleDirections += "E";
}
if(possibleDirections){
var move = game.rnd.between(0, possibleDirections.length - 1);
switch (possibleDirections[move]){
case "N":
maze[posX - 2][posY] = 0;
maze[posX - 1][posY] = 0;
posX -= 2;
break;
case "S":
maze[posX + 2][posY] = 0;
maze[posX + 1][posY] = 0;
posX += 2;
break;
case "W":
maze[posX][posY - 2] = 0;
maze[posX][posY - 1] = 0;
posY -= 2;
break;
case "E":
maze[posX][posY + 2]=0;
maze[posX][posY + 1]=0;
posY += 2;
break;
}
moves.push(posY + posX * mazeWidth);
}
else{
var back = moves.pop();
posX = Math.floor(back / mazeWidth);
posY = back % mazeWidth;
}
}
drawMaze(posX, posY);
var easystar = new EasyStar.js();
easystar.setGrid(maze);
easystar.setAcceptableTiles([0]);
easystar.findPath(1, 1, 79, 59, drawPath);
easystar.calculate();

}
}

function drawPath(path){
var i = 0;
game.time.events.loop(Phaser.Timer.SECOND/25, function(){
if(i < path.length){
mazeGraphics.beginFill(0xff0000);
mazeGraphics.drawRect(path[i].x * tileSize + 3, path[i].y * tileSize + 3, tileSize - 6, tileSize - 6);
i++;
mazeGraphics.endFill();
}
})
}

function drawMaze(posX, posY){
mazeGraphics.clear();
mazeGraphics.beginFill(0xcccccc);
for(i = 0; i < mazeHeight; i ++){
for(j = 0; j < mazeWidth; j ++){
if(maze[i][j] == 1){
mazeGraphics.drawRect(j * tileSize, i * tileSize, tileSize, tileSize);
}
}
}
mazeGraphics.endFill();
}```

Now that we can generate a maze and solve it, next time I will show you a game built upon these features. Meanwhile, you can download the source code.

215 GAME PROTOTYPES EXPLAINED WITH SOURCE CODE
// 1+2=3
// 10000000
// 2 Cars
// 2048
// Avoider
// Ballz
// Block it
// Blockage
// Bloons
// Boids
// Bombuzal
// Breakout
// Bricks
// Columns
// CubesOut
// Dots
// DROP'd
// Dudeski
// Eskiv
// Filler
// Fling
// Globe
// HookPod
// Hundreds
// InkTd
// Iromeku
// Lumines
// Magick
// MagOrMin
// Maze
// Memdot
// Nano War
// Nodes
// o:anquan
// Ononmin
// Pacco
// Phyballs
// Platform
// Poker
// Pool
// Poux
// Pudi
// qomp
// Racing
// Renju
// SameGame
// Security
// Sling
// Slingy
// Sokoban
// Splitter
// Sproing
// Stack
// Stairs
// Stringy
// Sudoku
// Tetris
// Threes
// Toony
// Turn
// TwinSpin
// vvvvvv
// Wordle
// Worms
// Yanga
// Zhed
// zNumbers