What is Depth-First Search?

Depth-first search is an algorithm that can be used to generate a maze. The idea is really simple and easy to implement using recursive method or stack.

Basically, you start from a random point and keep digging paths in one of 4 directions(up, right, down, left) until you can’t go any further. Once you are stuck, you take a step back until you find an open path. You would continue digging from there. It’s just the repetition of these.

First of all, I would like to explain the general idea a little deeper which you can apply using your choice of programming language. After you have the picture in your mind, you can take a look at the sample code and applet in java.

Explanation

Create a 2-dimensional int array with odd row and column size. 0 represents paths(orange cell) and 1 would be walls(black cell).

Set all cells to 1(wall). There are no paths right now.

[Continue reading…]