Creating and Solving Mazes on a 128 x 64 LED Panel

Two years ago, I published a tutorial about building a 128 x 64 LED two color panel and controlling it with an Arduino Mega. It's here: LED Flat Panel with Arduino MEGA. The most popular software I included with it was a sketch to create and solve mazes. In this tutorial, I will upgrade the system by changing the processor to an 84 MHz Arduino Due and also provide a lot of new information about the software required to build and solve mazes!

So this tutorial is divided into two parts - first a detailed discussion about how we create and solve mazes in software, and then in part II, I will discuss the construction and software to control the large LED panel using the Arduino Due.

Mazes

If you are interested in mazes, and the software to create and solve them, this section will be of interest. There are many ways to display a maze. If you are just interested in mazes, you may not want to tackle as much hardware as I will describe later in this project You could use a smaller LED display or perhaps a large OLED display. Whatever you choose, the software I describe in this section could be adapted to it, so don't abandon the maze idea just because you don't want to tackle this rather big display project.

The software included in the download does several things:

• It builds a random maze from an array of 32 x 16 cells.

• It creates a single random point of escape.

• It places our searcher (red search token) at a randomly selected point in the maze.

• It proceeds to run the maze and eventually escape.

• It then shows you the unique path it found from the starting point to the point of escape.

• It then creates a new random maze and repeats the process.

The maze itself is constructed inside an array of 32 x 16 cells. A single byte in memory defines the status of each cell. The first 4 bits define whether the North, East, South, and West walls are open to the adjacent cell or closed. Open is 1, while Closed is 0. The 5th bit called Active is set if the cell is currently on the active path of escape. The 6th bit is Visited which is set when a cell has been visited and is no longer a new path to search. (This is how the program marks and rejects a path that failed to lead anywhere.)

Creating a Maze

The make_maze routine builds a random maze. We want it to create what is called a "perfect" maze, meaning there is always a unique single path between any two points in it. The maze is created using what is called a regressive backtracking algorithm. Here’s how it works: We create a stack, which is a list of cells. It is initially empty. Add one cell to the stack, at random. Now choose that most recent addition to the stack, and carve a passage to any unvisited neighbor of that cell (at random from among neighbors), adding that neighbor cell to the stack. By “carve a passage”, I mean set the bits of both cells to show the wall between them is open. Now move to the new cell and repeat this process again and again. If there are no unvisited neighbors, remove the cell from the stack and backtrack until you find a cell with unvisited neighbors. Repeat this process until the stack is empty. Surprisingly, that is all that is required to create a “perfect” maze. It will always have a path between any two points, regardless of where we start and regardless of where we end. And that path will always be unique!

Our make_maze routine then picks a random spot on an outside wall and opens a path of escape. (The escape point is not truly random, as I only picked a few spots to set up as escape points, but it picks one of them at random.)

Running the Maze

Now that we have a maze, let’s run it using our solve_maze routine. Solve_maze starts by randomly selecting a starting point and showing it to us. It then runs the maze and finds the point of escape. Here is how it escapes the maze: It starts by visiting a previously unvisited neighbor cell where the wall is open. It first looks North, then East, then South and finally West to do this. It then continues to repeat this process. If it gets to a point where there are no unvisited cells available, it starts backing up until if finds a new unvisited neighbor. It keeps track of where it has been by putting new visited cells on the path array (similar to the stack we used to build the maze). It takes cells off the path array when backing up and marks them as visited.

To help you watch how the maze is run and follow the procedure, I have the search token colored Red whenever it is visiting new cells and it turns Yellow whenever it is backtracking over already visited cells. A common variant of the search algorithm I described above is to have the search proceed by hugging the right wall (or left). It is a little easier to see how the search progresses when done that way, but no more effective than the way it’s done here. In either case, the algorithm will sometimes get lucky and escape right away, and other times search the entire maze before succeeding. However, it always does succeed in either case!

Showing the Solution

Once the escape is accomplished, our Solve_maze routine shows us the solution, i.e. the direct path it found from the starting point to the escape point. Again, this is a "perfect maze" and the escape path is unique. It is easy to show it, because our search algorithm ended with the solution stored in the path array. So all it needs to do to show you the solution it found is to dump the content of the path array!

So now you know how to create and solve mazes. If you build my display or have one big enough to handle a 32 x 16 array, you can incorporate my software. But if you want to build your own larger or smaller array, the instructions above should get you there!

The Display

This is a big display – it is approximately 40 inches wide and 20 inches high. Most LED displays use a 4 mm pitch – these panels use an 8 mm pitch. These panels have red and green LEDs, so they are not RGB. Of course, we would prefer RGB, but large RGB panels are pretty expensive. I settled for red/green instead of RGB because they were reasonably affordable. Also, as I mentioned in my original article, it would have been impossible to manage this size RGB panel with the Mega, both because of speed and RAM limitations.

Our panel is actually made up of four 64 x 32 LED panels. The panels have built in shift registers which must be loaded with the on/off status of each LED. There are 128 x 64 LEDs on my display = 8192 LEDs. Each LED is actually a red and a green LED, so we are controlling 16, 384 LEDs. The Mega is barely able to handle the task of controlling this many LEDs, so as described in this tutorial, I decided to upgrade to the Arduino Due.

If you want to seriously consider building this panel, I suggest reading the original article - again, it is here. While I am including the parts list and schematic for the Due version in this article, I am not repeating all the construction details included in the original. What I will discuss here is the differences between the Mega and Due, the performance differences of the panel between the two processors, and some detail about how the display is programmed and refreshed using the Due.

The Due versus the Mega

The Mega has the ATmega2560 - an 8 bit, 16 MHz microcontroller. The Due has an ARM 32bit, 84 MHz microcontroller. At first, I naively thought of the Due was just a fast version of the Mega. After all, it has the same form factor and pinouts. I was aware that the Due was 3.3 volts vs 5 volts for the Mega, so I knew I would need to add level-shifters to all my output pins. However, the conversion of my LED panel from the Mega to the Due turned out to be a little more complicated than I originally thought it would be.

The 32 bit ARM processor on the Due is very different than the ATmega2560. While the pins on the Mega and Due are almost identical, they are connected to completely different ports. In addition, direct port access is handled completely differently, with different instructions and different procedures. Setting up a timed interrupt for doing refreshes is totally different as well. But on the plus side, the Due is almost 10X faster than the Mega, so working through all these changes was clearly worth it! The Due also has more than 10X the RAM of the Mega. That eliminated a lot of issues I had using the Mega for this display.

There are 15 digital pins that control the display. 4 red data lines, 4 green data lines, 4 address lines, 1 Shift pin, 1 Latch pin, and 1 Enable pin. These 15 pins require level-shifters with the Due, as the panels are 5 volt. I originally planned to keep the pin assignments all the same. But to keep the software update as simple as possible, I decided to put all 15 digital outputs on Port C, one of Due’s 32bit digital I/O registers. That required changing some but not all of the pin assignments.

Technical Discussion of Refreshing the Display

For the combined 4 panels, 4 bit address lines divide our panel into 16 groups of 4 lines each. So, for each of those 16 groups, we need to upload to shift registers 4 lines of red data and 4 lines of green data x 128 LEDs across. Because we need to move a lot of data quickly, we do not use digital Write(). It is way too slow – we must use direct port access. The process of loading all the shift registers 16 different times takes about 19 msec. on the 16 MHz Mega but only 2.25 msec. on the 84 MHz, 32 bit Due - a huge improvement!

On the original Mega design, the Mega was barely up to the task. I got it to work with a couple of tricks. First, we did not add any time for the LEDs to be on. The shift registers can be loaded with new data while the LEDs are on, then the LEDs are turned off, and then new data latched into the shift register outputs. Once the shift registers data are latched, the LEDs are turned on again, while new data is loaded. Even with that, I could not use a timed interrupt to update the display. Refresh only occurred on demand, i.e. we made some changes to the display, and then requested a refresh, made some more changes and then requested another refresh. This was not nearly as elegant as a timed ISR (interrupt service routine), but it worked.

With the Due, everything works much better. The total time spent loading shift registers drops to 2.25 msec. We can turn on LEDs for 500 microseconds for each of the 16 different zones and still have our total refresh down to 10.25 msec. We refresh every 15 msec. with a timed ISR, giving our processor plenty of time between refreshes to do other things.

The Due is also fast enough to do limited bit angle modulation or BAM. With BAM we don’t just turn LEDs on or off - we turn them on at various brightness giving us the ability to create a spectrum of rainbow colors and also the ability to fade or gradually brighter LEDs. Our eyes see the shorter times as dim and longer times as bright, so BAM works by turning LEDs on for a long time when the most significant bit is set, for half that time if the next bit is set, etc., down to short time when the least significant bit is set. The Due is fast enough to allow us to do 4 bit BAM. With 4 bit BAM, we can get rainbow colors from red to green in 32 shades, and primary colors (Red, Green, and Yellow) have 16 levels of brightness. 4 bit BAM for two colors can be stored in 1 byte - red in lower 4 bits and green in upper 4 bits. So our brightness levels for each LED are stored in an array of 64 x 128 bytes.

Construction of the Display

As said earlier, most of the construction detail for our panel can be found in my previous tutorial. I have included here a revised parts list and schematic to account for the changes to Arduino Due and the addition of level-shifters. Please refer to the previous tutorial for more information on construction.

The photo above shows the addition of level shifters. It got a little messy in there with the level-shifting of 15 digital pins, but was otherwise straight forward. It would have been much neater looking if I wasn't starting from the original Mega. Keeping all the existing wires labelled correctly was necessary during the processor swap.

More on Software

I have two sketches you can download; both are in the attached ZIP file. Obviously, the Maze sketch is the first one. It is similar to the one I originally published for the Mega. The second one is a demo of some of the things the Due is capable of, that we couldn't do with the Mega, both because of speed and memory limitations.

As I said, the maze sketch was done originally on the Mega system. I have updated it here for the Due by updating pinouts and the refresh routine. I added an ISR, so refresh now occurs with a timed interrupt every 15 msec. One thing I did not update was the way the main array is stored. Because the Mega only had 8 KB of RAM, I had stored the status of each LED in two bits, with 4 LEDs sharing each byte. The color of an LED could be Black (0, 0), Red(1, 0), Green(0, 1), or Yellow(1, 1). I left it that way on the maze sketch, even though the Due has 96KB of RAM or 12X the RAM on the Mega.

If you compare the video in this tutorial with the old one of the maze in the original tutorial, the improvement with the Due is obvious. The display is brighter, and has no traces of the flicker you could see in the original video.

For the new stuff that I have done specifically for the Due, each LED gets its own byte of RAM. In that byte we store a 4 bit value for the Red intensity in the lower 4 bits and a 4 bit value of the Green intensity in the upper 4 bits. The second sketch is shown below and demonstrates what we can do with BAM. You can see we get many more colors than just red, green and yellow. We can also dim LEDs.