Maze Solver

Background

Programmers create many games, like board games and first-person shooters. Most games have a primary goal. Once achieved, the player wins the game. One common gaming problem is maze solving. Take, for example, Pac-Man. The player traverses a maze to reach the treat. The end goal is to reach every treat in the maze. Level by level, the maze gets more and more complicated. Let’s see how to automate this task!

Introduction to Maze Solving

Maze solving is a simple programming problem. It requires users to traverse a given maze and see if a certain target position can or cannot be reached through a valid path. To automate the task, the computer needs a technique to traverse the maze and exhaustively search for a certain path. One technique to exhaustive search is depth-first search.

Depth-first search

Depth-first search (DFS) is an algorithm for traversing or searching a data structure. The algorithm starts at one position and traverses as deep as possible in one direction while doing the same for other directions. This goes on until the goal is reached or all possible paths have been exhaustively searched.

We’d be applying this concept in this project to get more hands-on experience.

Problem Description

A gaming company YAMCO created a game called Mind the App where players solve puzzles to advance to the next level. Part of the game called BACMAN is designed for players to complete a maze in record time. Some designers are struggling to create multiple variants of the maze. Some mazes are unsolvable while others are too easy. The chief of designers has assigned you to create a solution in JavaScript which can take or generate any maze to tell if it is solvable.

Task

Use your JavaScript knowledge to create a solution that tells if a given maze is, or is not solvable. This way, the chief of designers can prevent her team from wasting their time on failed mazes.

The above illustration shows how a maze looks like. Make a JavaScript version of the maze so it can tell whether the maze is solvable or not. Good Luck!