#depth-first

In this tutorial, we will learn how to generate mazes using depth-first algorithm. To do this firstly, I will define the problem, then I will explain the algorithm and finally demonstrate the implementation in Javascript. We will use P5js to demonstrate the working of the maze generation. Read Also:  Solving the 8 puzzle problem using A* (star) algorithm

Introduction to Maze Generation

A maze is a path or collection of paths, typically from an entrance to a goal. Maze generation is the process of designing the layout of passages and walls within a maze by using a computer program. In this tutorial, we will concentrate only on the generation of the maze and not on solving how to traverse a maze. Before continuing with the tutorial take a look at the final implementation below using P5js. (Note: Although I have used pre tag, yet the formatting is not retained. Not sure how to solve the formatting issue). Click on the Play button to see the maze generation in action. Read Also: What Are C# Delegates And How To Use Them

How to Generate Mazes

The goal is to create a layout of passages and walls within a maze using Javascript. Before we can solve the problem we will need to model the problem. But what is meant by Modelling the Problem? In generic terms, modelling a problem is the art of formulating the problem at hand in terms of precisely described, well-understood building blocks and logic to reach a solution. In computer science, proper modelling is the key to applying algorithmic design techniques to any real-world problems. Real-world applications involve real-world problems. You might be working on a system that simulates air traffic in and around an airport, you might be working on optimizing the dispatch of delivery vans for an e-commerce application, or you might be working to search through patterns in a large image set. To solve such problems you will use some sort of modelling techniques to reduce the problem in terms of rigorously defined abstract structures such as graphs, trees, permutations, sets and so on.

Depth-First Algorithm

We will use the depth-first search algorithm to solve our problem of maze generation. We will implement the depth-first algorithm with a stack. This approach is one of the simplest ways to generate a maze using a computer program. To do this we will first create a grid of cells to represent the room structure. For our problem we will only have 4 sided cells, each cell starting with four walls. The program will start from a random cell, then selects a random neighbour cell that has not yet been visited. The program then removes the wall between the two cells and marks the new cell as visited. It also adds it to the stack to facilitate backtracking. When a cell is found to have no unvisited neighbours the program backtracks through the path by popping cells from the stack until it reaches a cell that has an unvisited neighbour. This process continues until every cell has been visited, causing the program to backtrack all the way back to the starting cell.

Implementation of Maze Generation Using Javascript

I will demonstrate the implementation of the above algorithm P5 Javascript API. The reason to choose P5 is convenience and experimentation of ideas with Javascript. First of all, let’s define a few variables that are global in nature. These will be used for drawing of the grid and finally the maze.

The array Directions refer to sort of enumeration of the wall direction for a cell. CELL_WIDTH and CELL_HEIGHT are the width and height of each cell in terms of pixels. OFFSET is an offset from the top left corner of the canvas to start drawing the grid. Cell A cell is an independent unit of a grid. For our problem, we will model the cell with 4 walls. Each cell comprises of an x, y position, a boolean flag to indicate whether or not the cell has been visited and 4 boolean flags to indicate which walls need to be drawn. The cell is constructed with an x and y coordinate.

Utility function to set the colour of the wall lines using P5 API.

Utility function to draw the 4 walls of the cell based on the flag values of which walls are present for the given cell. A value of true for the boolean type means wall exists and a value of false means the wall is taken down by the algorithm as the cell was visited.

Mouse The mouse is the red colour block that moves while searching. This is just for visual purposes. With every visit to a cell, the mouse moves to the location of that cell. This shows the movement of the search visually.

Maze The Maze class comprises the list of cells as a 2d array. Besides, a few utility functions, there are two main functions to the Maze class. They are getNeighbours and removeCellWall. Get Neighbours The getNeighbours function returns a list of cells that are neighbours to a given cell and have not been visited.

Remove Cell Wall The removeCellWall function removes a wall of the current cell based on the direction from where it came and the wall of the neighbour cell from where it came.

Other Utility functions of Maze The other utility functions include setting the line colours of the walls, getting a specific cell given its coordinates and drawing of the maze. These functions are simple and self-explanatory.

Maze Generator The MazeGenerator class handles the generation of the mesh using the generateNext function. This function handles the exploring of the neighbours, adding them to the stack, marking them visited and popping from the stack if no neighbours are found.

The Main App The main app called MyApp just encapsulates MazeGenerator, Maze and the Mouse into a simple class (for convenience).

Week one of Fullstack complete! I am happy to report that so far, so good. I’m sure that it would have been totally possible to learn these concepts on my own, but I’m feeling pretty confident that personally I’m learning things much, much more quickly with a group.

While the first week definitely had a lot of review, and a fair share of obligatory non-program related topics (games, norms, orientation, that sort of thing), I’ve also been introduced to several new topics this week that I’m totally obsessed with right now, that I felt obligated to mention here, if only in a sort of cursory way.

My favorite a-ha this week was probably learning about breadth-first vs depth-first searching. Near the end of this week we tried to recreate (some of) the functionality of the $() selector function in jQuery. In doing so we created what I later learned was a recursive depth-first search function. While for most programmers I’m sure the phrase “recursive depth-first search function” does not seem all that surprising or interesting but as I reflect back I realize that it’s the kind of thing that would have felt super overwhelming to me last month (or even maybe last week). So let’s break it down.

First some (maybe overly obvious) context: websites have what is called the DOM. Which stands for the Document Object Model. The DOM is simply an organizational structure for what to go where on the page. For example how might you tell a computer to put all of your navigation buttons inside a navigation bar? I guess you could just stack each other, but wouldn’t it be nice to instead have the navigation bar own or be the “parent” of each individual button? You can! (and do!). This organizational structure is known as the DOM, and is basically a hierarchal tree. jQuery, a javascript library, allows you to add some nice functionality to your website (think drop-down menus, filters, and other fun things). And jQuery does this by traversing the DOM. Basically it goes through this hierarchal tree and gathers the right elements (maybe only the photos for example) and allows you to do cool stuff with it. We do this in our javascript file by writing something sort of like this:

 $(“stuffYouWantToSelectForGoesInHere”).on(when you click on the selected thing){

            exactly what cool stuff will happen to the selected stuff

}

Ok, ok. So that’s pretty nice. But how exactly does it do this…traversing stuff? How do we walk the DOM and determine “is this the right element?...nah…the next one”? What order do you look for things? Does the order even matter?

In comes our recursive depth-first search. When recreating our $()selector, we made a function that basically does the following:

creates an array which will eventually store all the matching elements

decides that if we haven’t given it an area to search, it takes in the Body of the DOM (the main part of the DOM that we are interested in)

determines if that particular section has any children

if it does, it waits to run this exact same function on those children, and then concatenates whatever is returned from those functions in our array.

then returns the newly filled array of matched items.

Recursion is a cool concept that feels very magical. Which may seem like reason alone to use this type of function. But just because it’s magical doesn’t mean it’s the only way or the best way to solve this problem. This type of search is known as depth-first, which means that it goes down/deep into the DOM tree, then back up and to the right. For example let’s say you’re looking through your family tree to find all the family members that have red hair. With a depth first search you would first search through the eldest great grandmother’s children, grand children, and great grandchildren before going to the great grandmother’s younger brother.  This I find hard to describe in words and easier to describe in pictures.

This differs from say a breadth-first search, which says let’s look at all the great grandparents first, then the grandparents, then the parents, then the children, then the great grandchildren, etc.

But why does it matter? Well in our particular case of recreating the jQuery selector it probably doesn’t really matter that much, what order you find things in. But what if you were searching for something in all of the interwebs? Would you want to return all matches from one particular website’s children’s children’s children? Or would you want to just return the homepages for the most popular websites? Do you want to return your emails that ever mention the word Sarah? Or do you want to first return all emails that are from Sarah first, then have Sarah in the subject, and then have Sarah in the text? These are probably more analogies/metaphor than actual implementations of breadth first searches, but still I think it helps to put in context why we’re learning what we’re learning. Essentially if you need to return all of the matches then depth-first searches are fine, but if you’ve got a huge number of potential matches and would like to return the top results first and continue searching in the background then a breadth-first search might be a better fit.