Arduino TVout library showing a maze

We are wasteful in modern computing, mainly in the area of memory and computing power. Both are so inexpensive that we (I mean programmers) become careless about how much we use of either. All of that changed for me, however, when I started playing with an Arduino.

This is a quick post comparing two different ways of solving a simple problem, yet with precious little resources. In my case, I found the TVout library for Arduino and decided to try to make a maze generation program. That's when everything I learned about structured programming went out the window.

I'm Losing My Memory!

My first lesson was the issue of memory constraints. I am using an Arduino Uno which has a "cavernous" 2K of RAM. That should be enough for anybody, right? To generate my mazes, I used a beautifully elegant, recursive algorithm... and it died. I specifically limited the possible depth of recursion and found that anything beyond 6 levels deep was corrupting my memory space. (As a side note, I would like to thank Dr. Passos for making sure that I learned how the stack and heap function, and the scary implications of this in low memory situations.) After some experimentation, I found out that, after implementing the TVout library, I was left with a paltry 428 bytes of RAM with which to generate my maze. Recursion was definitely out; I had to come up with a method to generate my maze linearly.

The Problem

One function that I needed was the ability to choose a random element from an elastically-sized set. The elements were basically cells of a grid which had different states associated with them. I needed to be able to pick out a random element that matched a certain criteria and to do it quickly and without bias. The problem was, though, at that point in the code, I was down to only 135 bytes of RAM available.

The Method That Didn't Work

My first solution was to choose an element at random from the grid and, if it did not meet the criteria, advance to the next cell. The problem with this approach is that the criteria-matching cells do not have an equal probability of selection. Furthermore, I needed to also know if there were no matching cells, so I could not simply just keep picking things at random. While this first solution half-worked and allowed me to see that the remainder of my linear maze generation algorithm functioned correctly, it was not the best solution.

Correct Method 1

The first solution that both worked and yielded equal bias for matching cells was to scan the matrix while tracking two variables, the coordinates of the cell to be chosen and the total number of matching cells found (initialized to 0 at the beginning of every run). The pseudocode can be found below:

matrix = {val1, val2, val3, ... , valX}; // one-dimensional for clarity
totalFound = 0;
coordinate = x;
 
for (int i = 0; i < matrix.size; i++)
{
  if (matrix[i] == criteria)
  {
    totalFound++;
    if ((random() % totalFound) == 0)
    {
      coordinate = i;
    }
  }
}

As the matrix is scanned, totalFound is incremented when a cell with matching criteria is found, and coordinate is replaced only if (random() % totalFound) == 0. This method is certain to be without bias towards any particular cell, and, when the entire matrix is scanned, the first matched cell has an equal probability of being the final coordinate value as does the last matched cell (and all of the cells in between). I wrote out a proof by induction just to make sure of this point, but I will not post it here. In the tradition of the great textbooks of our time, this will be an exercise left to the reader.

Correct Method 2

While the previous method worked well and without bias, I wanted to improve my execution time, so I decided to try to elimiate as much scanning as possible and time-consuming calls to random(). I realized that, since I am modifying this matrix internally, it would be very easy to keep a running total of the matching-criteria cells and to modify that value when cells are changed. The modified approach is below in pseudocode:

matrix = {val1, val2, val3, ... , valX}; // one-dimensional for clarity
// totalMatching is tracked internally and reliably accurate
chosen_index = random() % totalMatching;
coordinate = 0;
 
for (int i = 0, j = 0; i < matrix.size && j <= chosen_index; i++)
{
  if (matrix[i] == criteria)
  {
    if (j == chosen_index)
    {
      coordinate = i;
    }
    j++;
  }
}

As long as totalMatching is protected and accurately updated, this method will function flawlessly. In this method, only one random() is called, and only enough of the matrix is scanned so as to find the right cell. These two factors are enough for intuition to make us think that it is superior, but the proof is in the execution.

The Showdown

While I did not make millisecond-accurate measurements of the above two methods, I did stare at the second hand of a clock for a while as my program generated maze after maze. Here's the long and the short of it: Method 1 was consistent in generating a maze every 7-10 seconds. Method 2 was consistent in generating a maze every ~1 second. In other words, I didn't feel the need for more accurate measurements: Method 2 was superior in this implementation in terms of execution time. For memory usage, they are nearly identical in that neither one needs to allocate a separate array to hold the matching cells, however Method 2 does require two additional variables. In this circumstance, I judge that giving up 4 bytes was worth it when it resulted in a speed-up by a factor of ten.

Devil's Advocate

Does this mean that Method 1 is bad and should never be used? Absolutely not! Method 2 works mainly because I was able to anticipate and keep a tally of the cells with matching criteria. Without this, all bets would be off. If the matrix is large, there are relatively few expected matching cells, and the number of matching cells is not know beforehand, then Method 1 may indeed be quicker. Detail of implementation is definitely where the issue lies.

Lessons Learned

Memory is precious, especially in an IC. Bit packing doesn't have near the overhead that one might think and it comes in handy when bytes are at a premium. Recursion is a luxury you probably can't afford on an IC. And, finally, programming in these environments truly reveals your programming prowess (or lack thereof!), so I now have a huge appreciation for the talent and ingenuity of the early programmers!

What's Next

I'm planning on wiring in a Wii Nunchuck so that a person can navigate the maze. I'm not sure how much I can do, however, since I know that I only have 256 bytes of RAM available to do it all in. We shall see.