×

SparkFun will be closed on Monday for Memorial Day (5/27). Orders placed after 2pm MT on Friday (5/24) will process and ship out on Tuesday (5/28).

Enginursday: Creating Random Sequences with Rules

Let's take a closer look at the quasi-random sequence generator for the Simon Says Trampolines project, and how a buggy first attempt was improved!

Favorited Favorite 0

When you put a bunch of electronics around trampolines in a room, and ask thousands of kids to jump on them, it’s only a matter of time before something fails. About three weeks after Boulder Bounces opened, we got an email telling us that it was failing on occasion.

alt text

Background of the project

We recently designed and installed an exhibit at the Museum of Boulder called Boulder Bounces. It's a memory game much like the Simon Says Soldering Kit, but with trampolines. You can read more about it at this blog post, or watch the following video:

The original Simon Says uses the built-in random() Arduino function. While this works fine for the original game, Boulder Bounces needed some extra rules in the sequence generation to avoid "boring" bounce patterns. It's not that fun to have many repetitions of the same trampoline, and any repetitions in the beginning of the sequence are not only difficult, but can lead to some serious confusion for the first-time player. Plus, when you're playing with a group of jumpers (each standing on their own trampoline), it is loads more fun to ensure everyone gets to jump.

Let the investigation begin!

I have a lot of serial debug messages sending out from my Arduino Pro Mini on this project, so I was eager to plug in a FTDI basic and hear what was going on. My original email from the museum said that if they simply cycled power, it would start working again. Because of this, my first thought was that it was most likely failing in software, and not a hardware issue.

When I opened up the panel on the wall, it looked like the LEDs had been mistaken for buttons and pushed completely back into the panel. Those darn kids! I guess I can’t blame them; the gumdrop LEDs are big enough to be a button, but I needed to stay focused on the problem at hand.

Jumping right in

I played through an entire game once. It worked just fine. I played another round. No issue. Again, and again. Nothing. Then on the sixth game, right before I should have heard the winning sounds, it seemed to stall out.

I went to look at my serial debug, but it seemed to stop spitting out any serial debug at all. Hmmmm. When I am troubleshooting a code bug that involves a "stall out" like this, my first approach is to verify the point of failure and then work backward to find out the potential issue.

During my last game (right before the failure), I remember my serial debug was working properly. It was outputting each new sequence after each successful play correctly. But at my "win," the serial debug stopped, so the failure must be occurring somewhere immediately after the last add_to_moves() was called.

A high-level look at the original code

Before we jump into any of the original code, I think it would be beneficial to share the high-level plan for gameplay, and my higher-level approach to creating the random sequence with rules.

The original gameplay code worked like this:

When you are playing a game, the Arduino will "play" back the sequence to you. At first, it only shows one trampoline light up, and you jump on it. Then the Arduino "randomly" chooses the next trampoline to add to the sequence. It plays back the entire sequence (which at this point is only two jumps long), and you must jump the sequence in order. Then it adds another, and so on. Once the sequence reaches eight and you successfully jump in the correct order, you win!

The specific part of the code that I'm talking about today is a function called "add_to_moves()". This is a simple enough function in theory. Let's take a look at the original function from the original Simon Says to start. Note, this code is from the button game, and was not used on the trampolines installation, but it's a good place to start.

void add_to_moves(void)
{
  byte newButton = random(0, 4); //min (included), max (exluded)

  // We have to convert this number, 0 to 3, to CHOICEs
  if(newButton == 0) newButton = CHOICE_RED;
  else if(newButton == 1) newButton = CHOICE_GREEN;
  else if(newButton == 2) newButton = CHOICE_BLUE;
  else if(newButton == 3) newButton = CHOICE_YELLOW;

  gameBoard[gameRound++] = newButton; // Add this new button to the game array
}

First, you notice that the "random(0,4);" is generating the next "newButton" in the sequence. The following five lines of code are not really important in this discussion, but to quickly explain, we need to change them to the defined variables associated with each button choice available. For today, let's just focus on the creation of newButton and then how it is added to the array, gameBoard[].

Looking at the original function add_to_moves(), it simply uses random() to add a new button to the sequence. This worked fine for the original Simon Says, but for Boulder Bounces, we needed to add in some rules to make it more interesting.

Add a while loop and some rules

My first approach to adding rules was to put it in a while loop. Inside this while loop, it would first grab a random newButton value from random(), then compare it against some rules. If it passes all the rules, then it would use it, and break out of the while loop. If it doesn't pass a rule, then it would do nothing, stay in the while loop and try again.

alt text

The problem with this approach is that it is living on a prayer that random will eventually return something that will pass the rules. I knew this wasn't perfect, but in all my development work on this project I never saw it get stuck. It usually tried a couple times at most, but eventually returned something that would work. It turns out that it can get stuck there, and something was causing it to stop trying.

For reference, the original code (with the actual rules - aka "if" statements) is as follows. You can see all of it here on my github commit. Specifically, here is my original add_to_moves():

void add_to_moves(void)
{
  while (1)
  {
    newButton = random(0, 3);
    if (!((newButton == gameBoard[gameRound - 1]))) // avoid repeats
    {
      // check to see if that button is already "maxed out"
      if ((newButton == 0) && (RED_seq_count == 2)); // do nothing
      else if ((newButton == 1) && (GREEN_seq_count == 3)); // do nothing
      else if ((newButton == 2) && (BLUE_seq_count == 3)); // do nothing
      //else if((newButton == 3) && (YELLOW_seq_count == 2)); // do nothing
      else break; // get out of this while loop and continue playing.
    }
  }

  // We have to convert this number, 0 to 3, to CHOICEs
  if (newButton == 0)
  {
    newButton = CHOICE_RED;
    RED_seq_count++;
  }
  else if (newButton == 1)
  {
    newButton = CHOICE_GREEN;
    GREEN_seq_count++;
  }
  else if (newButton == 2)
  {
    newButton = CHOICE_BLUE;
    BLUE_seq_count++;
  }
  else if (newButton == 3)
  {
    newButton = CHOICE_YELLOW;
    YELLOW_seq_count++;
  }

  gameBoard[gameRound++] = newButton; // Add this new button to the game array
}

You may also notice that my rules rely heavily on some new variables: RED_seq_count, BLUE_seq_count, etc. These are helping me keep track of how many times I've already included a specific color button in the sequence, so I can avoid favoring any button and ensure everyone gets to jump.

In an attempt to hone in on the problem, I added a little line of debug at the end of my add_to_moves() function.

if(debug) Serial.println("add_to_moves attempting...");

Now I would know whether it was trying at all, getting stuck in this while loop or stalling out elsewhere.

After much jumping and winning, I got another failure in the middle of a round. It stalled out, and my serial monitor looked like this:

alt text

Remember, my first failure was just before a "win." Because this second failure was in the middle of a game, this was a new clue! This means that the failure is caused somewhere else in the code, and probably has nothing to do with the code just before a win.

Right before it stalled out, the entire serial monitor was filled with the message “add_to_moves attemping…” It was sending this message again and again as fast as my little Pro Mini could go. Something strange was going on. Why would it get stuck repeating this message, and then eventually give up?

The speed of the repetition of the debug message was also strange. When it seemed to be trying normally, the message would spit out to the terminal at a moderate pace. But when the failure would occur, the messages would speed up dramatically and eventually cause a stall out. After much finagling and many attempts to cause failures, I eventually gave up trying to find the root cause. I knew there was a better way, and so decided to start a different approach the the random generator with rules.

A better approach

alt text

To elliminate the possibility of any stall-outs, I introduced a new array called "on_deck_buttons[]." I would have my rules adjust this array, and then my random function can just choose from the good options. That way, random() will only be called once, and this removes the need to loop back around and try again and again.

I also beefed up my debug to get a better view into what was actually going on with all my variables and arrays.

Here is my new add_to_moves() function:

// Adds a new random button to the game sequence
void add_to_moves(void)
{
  byte newButton = random(0, 3); //min (included), max (exluded)
  int add_to_moves_counter = 0; // keep track of our while loop below for finding good new buttons, and see if this is jamming the game.
  if(gameRound == 0); // do nothing - newButton is randomly set above.
  else if((gameRound == 1) || (gameRound == 2)) // jumps 2 and 3 are important. for the first 3 jumps we want these to always hit each tramp once
  {
    while(1)
    {
      add_to_moves_counter++; // keep track of how many times we are trying to find a good new button to use (random might be stalling out here)
      int on_deck_buttons[2] = {0,0}; // these are used to help reandomize below
      newButton = random(0, 3); // pull in a first attempt at a nice new random button
      if((newButton == 0) && (RED_seq_count > 0))
      {
        on_deck_buttons[0] = 1;
        on_deck_buttons[1] = 2;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;
      }
      else if((newButton == 1) && (GREEN_seq_count > 0))
      {
        on_deck_buttons[0] = 0;
        on_deck_buttons[1] = 2;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;
      }
      else if((newButton == 2) && (BLUE_seq_count > 0))
      {
        on_deck_buttons[0] = 0;
        on_deck_buttons[1] = 1;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;        
      }
      //else if((newButton == 3) && (YELLOW_seq_count == 2)); // do nothing
      //else break; // get out of this while loop and continue playing. This means that the new button is good to go. 
      else
      {
        Serial.println("error");
        break;
      }
      if(debug) Serial.println("add_to_moves attempting...");
      if(debug) Serial.print("gameBoard[gameRound-1]:");
      if(debug) Serial.println(gameBoard[gameRound-1]);
      if(debug) Serial.print("gameBoard[gameRound-2]:");
      if(debug) Serial.println(gameBoard[gameRound-2]);      
    }
    if(debug)
    {
      Serial.print("add_to_moves_counter: ");
      Serial.println(add_to_moves_counter);
      Serial.print("RED_seq_count: ");
      Serial.println(RED_seq_count);
      Serial.print("GREEN_seq_count: ");
      Serial.println(GREEN_seq_count);
      Serial.print("BLUE_seq_count: ");
      Serial.println(BLUE_seq_count);
    }
  }  
  else // only after you make it to step 3.
  {
      // attempt 1, works.
      // while((newButton == gameBoard[gameRound-1]) && (newButton == gameBoard[gameRound-2])) newButton = random(0, 4); // keep pulling in more variables until this isn't true.
      // basically, if it's the same as the previous 2 buttons, then it will keep finding a random number until it's "fresh".

      // attempt 2, attempting to add in limit per button to avoid leaving one jumper out.
    while(1)
    {
      add_to_moves_counter++; // keep track of how many times we are trying to find a good new button to use (random might be stalling out here)
      int on_deck_buttons[2] = {0,0}; // these are used to help reandomize below
      newButton = random(0, 3); // pull in a first attempt at a nice new random button

      // This ensures it's not going to repeat same button 3 times
      //if((convert_to_choice_byte(newButton) == gameBoard[gameRound-1]) && (convert_to_choice_byte(newButton) == gameBoard[gameRound-2])); // do nothing, try again 
      // check to see if that button is already "maxed out" (aka it has been used twice already)

      if((newButton == 0) && (RED_seq_count == 2))
      {
        on_deck_buttons[0] = 1;
        on_deck_buttons[1] = 2;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;
      }
      else if((newButton == 1) && (GREEN_seq_count == 3))
      {
        on_deck_buttons[0] = 0;
        on_deck_buttons[1] = 2;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;
      }
      else if((newButton == 2) && (BLUE_seq_count == 3))
      {
        on_deck_buttons[0] = 0;
        on_deck_buttons[1] = 1;
        newButton = on_deck_buttons[random(0, 2)]; // chooose randomly from on_deck_buttons - aka the only ones we want to choose from
        break;        
      }
      //else if((newButton == 3) && (YELLOW_seq_count == 2)); // do nothing
      //else break; // get out of this while loop and continue playing. This means that the new button is good to go. 
      else
      {
        Serial.println("error");
        break;
      }
      if(debug) Serial.println("add_to_moves attempting...");
      if(debug) Serial.print("gameBoard[gameRound-1]:");
      if(debug) Serial.println(gameBoard[gameRound-1]);
      if(debug) Serial.print("gameBoard[gameRound-2]:");
      if(debug) Serial.println(gameBoard[gameRound-2]);      
    }
    if(debug)
    {
      Serial.print("add_to_moves_counter: ");
      Serial.println(add_to_moves_counter);
      Serial.print("RED_seq_count: ");
      Serial.println(RED_seq_count);
      Serial.print("GREEN_seq_count: ");
      Serial.println(GREEN_seq_count);
      Serial.print("BLUE_seq_count: ");
      Serial.println(BLUE_seq_count);
    }
  }

  // We have to convert this number, 0 to 3, to CHOICEs
  if(newButton == 0) 
  {
    newButton = CHOICE_RED;
    RED_seq_count++;
  }
  else if(newButton == 1) 
  {
    newButton = CHOICE_GREEN;
    GREEN_seq_count++;
  }
  else if(newButton == 2) 
  {
    newButton = CHOICE_BLUE;
    BLUE_seq_count++;
  }
  else if(newButton == 3) 
  {
    newButton = CHOICE_YELLOW;
    YELLOW_seq_count++;
  }

  gameBoard[gameRound++] = newButton; // Add this new button to the game array
}

The trouble with failures that only happen once in a while is that it can require lots of data points and repeated testing to emulate the failure. For most software issues, this can sometimes be automated and done quickly, however, with exhibits like these that involve physical hardware, the true game play must be cycled again and again to create the failure.

The trampolines were failing randomly every 10-20 game plays, so that meant a lot of jumping. Never in my life have I had such a physically demanding code debug session! I did my fair share of jumping during the development of this project, but that paled in comparison to this debugging session.

If you have experienced any strange stall-out with the random() function, or have any other approaches to creating sequences like this, please share in the comments below. Also, please check out the github repo link below, and if you so feel inclined, we always love seeing any issues, forks, pull requests or comments. Thanks for reading and happy coding!


Comments 14 comments

  • ...repeated testing to emulate the failure. For most software issues, this can sometimes be automated and done quickly, however, with exhibits like these that involve physical hardware, the true game play must be cycled again and again to create the failure.

    Why? Does the randomization depend on the timing between trampoline bounces? Since you had already modified the code to add more debugging output, why not add a modification that doesn't require the trampolines at all? Better yet, why not pull the add_to_moves() code snippet out into a C program that runs on a PC so you can really hammer on it?

    • Hey 278, Good point. I think you are correct that distilling it down to the problem function is a better approach for debugging. Also, the randomization does not depend on the user input in any way, so you are right, actual game-play should not be needed to debug this problem.

      At the time when I was first attempting to fix this, I only had a couple hours to troubleshoot, so I opted to heavily tweak my code and try the "on_deck_array" approach. I'll admit, this was not the most thorough way to fix the problem (and I never got to the root cause). At the time, I was more concerned with getting a working solution in place asap.

      Also, I actually wanted to emulate the problem without changing anything on my installation. I was slightly worried that if I started tweaking code right off the bat, then I'd miss seeing the original problem, or create new ones. So I opted to try and experience the failures just like they were happening for the participants. But I suppose after I had caused a few, then trying out some new code on a different Arduino would have been better and potentially a lot faster. Should have brought another Pro mini with me to the museum. I'm gonna keep working on building up my "in-field" debugging kit.

      FWW, when writing this post last week, (a few months after the original debugging session), I did attempt to pull out the add_to_moves() function and cause failures, but I wasn't able to emulate the same failure. I'm guessing that my "distilled down" version of the code was somehow slightly different (and fixed?), but I didn't track it in github, so I'm not sure.

      Also, thanks to member 993 (see comments below), I now see there was a fatal flaw in my original rules between by "count" rules and my "non-repeat" rules.

      Thanks again 278 for checking out my code and I appreciate your feedback!

  • I've been "doing" computers since a few weeks after Neil Armstrong took his "one small step", and really started programming a few months later (unusual for a high school student in those days!). Testing software can be difficult: in Feb., 1983, I used up more that 1.5 MILLION CPU seconds (Feb has about 2.5 million seconds) on a VAX 11/780 in testing a cross-compiler we were developing.

    I think that I'd try to develop some "test harness" that can run things without the actual "bounce" hardware present (maybe do some "emulation" with a Raspberry Pi, that also looks at the serial debug output to make sure it "looks reasonable"?), and make many runs out to some rediculous number of steps (e.g., 1000 for a "Simon Says"). Then let it sit and "cook" a few days...

    A minor comment on the coding "style": If I'm trying to select between things based on a single integer value, I tend to use "switch-case" rather than a series of "if-else", but in either event ALWAYS include a "default" in case the integer is outside the expected range. (Back in my earliest days with punched cards, in a certain column we had a 1 for a boy and a 2 for a girl -- found one card with a 7 in that column...)

    I have often said I tend to spend about 20% of my time making sure the program works when everything goes right, and about 80% of my time making sure the program works when things go wrong. (BTW, most of my career was spent writing compilers for very specialized languages that were tightly bound to the electronics.)

  • Your rules allow 2 Red, 3 Blue and 3 Green only, and no repeats.

    Blue, Green, Blue, Green, Blue, Green, what happens now?

    Blue, Red, Blue, Red, Blue, ???

    Green, Blue, Red, Blue, Red, Blue, Green, ???

    I'd say a hang is worse than a repeat or somebody's feelings being hurt by not getting to jump as many times. Long term, your new solution is fine, but in general I would consider making these "suggestions" rather than rules by replacing the while(true) with a for loop.

    • Thanks 993! I love the FOR loop idea as a "suggestion" idea. That is a much safer approach!

      I'm slightly confused about the first problem you explained.

      Blue, Green, Blue, Green, Blue, Green, what happens now?

      I'm thinking that it would force a Red next. Yes, it may take a while, but the hope was that random() would eventually return a "0" (aka red), and this would make all of my rules false, so it would make it to the final else and break.

        if ((newButton == 0) && (RED_seq_count == 2)); 
      

      False (because RED_seq_count is 0)

        else if ((newButton == 1) && (GREEN_seq_count == 3)); 
      

      False (because random() finally returned "0" and newButton is "0")

        else if ((newButton == 2) && (BLUE_seq_count == 3)); 
      

      False (because random() finally returned "0" and newButton is "0")

        else break;
      

      We made it here, and so newButton will be "0" (aka RED).

      I must be missing something?

      • I was trying to leave you the "a-ha" moment instead of bludgeoning you with it.

        Yes, the next button is Red. And then...

        Rule 1 : The only choice remaining is Red. Rule 2: The choice must not be Red.

        • "AHA!!!" Durp. My bad. Thanks 993.

          I totally forgot to think about the previous line...

          if (!((newButton == gameBoard[gameRound - 1]))) // avoid repeats
          

          Nothing like a fresh set of eyes to see the problem right in front of you.

          THANKS!

          • Is this only called on the second and subsequent rounds, or also on the first round?

            If it's called on the first round then the [gameRound - 1] will be the element before [0], which is an out-of-bound access.

            • Hey 769, Thanks for checking this out. Definitely a good question. The "non-repeat" rule is only used after gameRound becomes greater than 1. There is one more if statement before it enters the dangerous "while loop with rules". This is found at the top of add_to_moves():

              if(gameRound > 1) // only after you make it to step 3.
              

              And see the full code (at that commit time) here.

              Looking at it now, I see that my comment is slightly confusing too (probably out-of-date for a previous tweak). As it sits here, this would actually allow the first two buttons in the sequence to be simply called from random(), and this would explain why sometimes I would still see a repeat on the first two. It's all becoming so clear now :)

              I seem to remember having an issue with the out-of-bound access potential problem early on during development. Always a bit risky calling a "-1" position of an array.

              Thanks for your feedback, and I appreciate you helping out to dig further into this code. Cheers!

          • I have never played the game, but I would imagine the win % is not super high, otherwise you would have heard more complaints sooner.

            As written, your rules have a 68% of success, a 6% chance of failing at step 7 and a 26% chance of failing at step 8. As you discovered, it only took a relatively small number of wins to reproduce the problem. Turns out your quads got lucky that you decided to treat red differently and limit it to 2 instead of 3. If you do nothing except allow red to appear up to 3 times like the other two colors, your odds of success jump to 96% with a 4% chance of failing at step 8. That would have required a lot more jumping to reproduce!

            If you want 100% success, while disallowing repeats, you need to permit two of the three colors to appear 4 times in an 8 step sequence, and the other to appear 3 times. Simply allowing all colors to appear at most 4 times is a reasonable choice, again for 8 steps.

            Of course, if you do not want to re-jigger the odds every time you change the game (add steps or a fourth trampoline), be sure to avoid while(true) and forever [for(;;)] as well.

  • Did you ever output the selected random number generated from add_to_moves? What if the random number generator, for whatever reason, had a bug and continually put out the exact same number? If the RNG were to fail after X calls, that would show the behavior you got. It would never happen at the beginning, but you couldn't predict the exact time it would fail because the number of random() calls would vary from game to game, depending on how non-repetitive the RNG decides to be. Now I don't know WHY that would happen, and it your commented out "attempt 1" in the new code would suffer the same problem, so if it worked, then my theory's no good.

    Personally, while I've been programming for a long time, I'm newer to Arduino and C# in particular. Debugging a VBA macro is cake when you can just step through the lines one at a time, but on Arduino I'm learning a new syntax plus debugging hardware, all while having very limited debugging options -- it's a ton harder for me to chase down bugs! On my current project, I spent 3 days chasing down what I thought was a software issue that ended up actually being a component wired backwards!

    • Hey Bryan M, Thanks for your comment! That is definitely a good idea to output the actual return values from random(). Now it seems like that is the most important thing to look at, and I can't believe I didn't think to try it out first.

      While writing up this blog post, I tried emulate the problem with a Redboard and some simplified code. (because I wasn't at the museum with access to the actual problematic setup). My Redboard was simply generating random sequences to the gameBoard[] array, and then serial printing them. I was working quite well with the original method, and so I was having trouble getting it to fail. After this, I assumed it might have had something to do with the rest of my gameplay code (which doesn't really work without the actual exhibit hardware).

      Ultimately, I'd like to understand what's behind random(). The reference page doesn't really give ya much as to what's going on inside the function.

      The good news is that my new approach with on_deck_buttons[] didn't cause any stall outs in the following 4 months that it was up. We actually just took down the exhibit this week, and it will be in storage for a couple weeks. Once it is setup again (hoping for the Lafayette children's museum), then I will try out some debugging with the actual setup again.

      Thanks again, and if you come across any info on the Arduino random(), please let us know!

      • You can change the random seed with this command: randomSeed(0)
        A good way to more randomly randomize the number, use an open analog input for the seed: i.e. randomSeed(analogRead(0));

        • Hey asciirory, Thanks for your comment. randomSeed() is definitely a good idea. Another tip I've learned is (if your project has some sort of user input - like a button press to begin a game) is to send randomSeed the value from millis().

          I did this each time a new game round was started here.

          randomSeed(millis()); // Seed the random generator with random amount of millis()
          

          Thanks again and happy randomizing!

Related Posts

Recent Posts

Tags


All Tags