Playing with Mazes in JavaScript
As a curious web developer and addicted guy to search algorithms, I faced several challenging questions about solving mazes in Javascript with different conditions and capabilities. In this article, I’ll show you several mazes and solutions, based on my own experience.
Prerequisites
Before we start handling the mazes, let’s talk about the board itself. The 2-d board includes zeros and ones: “zero” represents an available cell (one can go through) and “one” represents a blocked cell, which one cannot go through. The board is represented by an array of arrays: every sub-array is a row in the board and every element is a cell. For example, board of 3*2 can be represented by [[0,1,1],[0,0,0]). In this case, the value of board[0][2] is “1”.
In addition, I’ve created a class which represents “Point” which gets row and column in the constructor. The class itself includes several functions for getting adjacent points (right, left, bottom, top and diagonal). Moreover, a function for checking whether a point is reachable is represented by the function of “isValid”. It’s checking not only whether the point is located in the grid, but also whether the value of the point is zero (“available”).
The small functions of “isEqual” is aimed to compare two points by comparing their rows and columns. The function “getString” used to record the path of maze’s solution. Printing the path in “printPath” method is using path array which includes the points in string format. For example, the printed path can be “00”->”10"->”11".
Classic Maze (four directions) using Recursion
The classic maze which is represented by board of zeros for available cells and ones for blocked cells. In this example, I used recursion for finding the available path. If no path was found, the program returns “undefined”.
In order to avoid an infinite loop in opposite directions (right-left, top-bottom), I’ve added a “discovered” object. After visiting a point in the maze, I added the point to this map object and as a result, points aren’t visited more than once.
The problem can be when the board is becoming big and recursion in this case can lead to stack overflow error. In this case, I’ll suggest using BFS/DFS search algorithms as a solution and this will be explained in the next paragraphs.
Maze with three directions (right, bottom, diagonal) using BFS and DFS
Now, let’s look on a maze with only three directions (right, bottom and diagonal) which I’ve used BFS and DFS search algorithms to solve. It’s clear that both algorithms are finding the route from the start point to the end (if exists of course), but the number of steps are not always the same if there are multiple possible routes. Take a look on the pros and cons of these both algorithms and play with the start and end points in order to see the difference in the paths.
The ideas behind BFS and DFS search algorithms are very similar, but pay attention that in DFS mode, I’m using stack and a loop which takes the last point in every cycle. In this method, I’m going deeply in the tree (vertically search). This is different from BFS algorithm, which I’m searching horizontally and using a queue to take the first point in the queue every cycle. DFS search can be sometimes inefficient when the end point is a sibling of the current point (waiting till moving all the descendants of the point will be finished).
To sum up, there are many versions of mazes and different approaches how to deal with them with possible solutions. In this article, I tried to share two mazes questions and their implementations using recursions and search algorithms. You more than welcome to comment and share your personal experiences as well in the bottom of this article.
Thank you!
