Hunter Liu's Website

9. Week 4 Thursday: Algae Simulator

I heard about this project idea from my friend and colleague Elias, and I thought it made for a short and sweet application of for loops and if statements.

Our goal will be to simulate a patch of algae (or perhaps lichen), growing downwards in intricate patterns according to a set of simple rules. If you want to use stuffier language, we’ll be implementing an elementary cellular automaton.

We’ll represent the universe as a chunk of several characters: there is either empty space, a literal space character, or there is algae, which we’ll shade in with #. Perhaps at one moment our patch of algae looks like this:

  # ##  ####  #  # #

The algae will try to grow downwards, guided by gravity. A few moments later and a handful of cell divisions later, perhaps the algae now looks like this:

  # ##  ####  #  # #
   ###  #  #      #

One can imagine the densest regions of algae, i.e. ####, are already using all the available nutrients, and therefore don’t grow as much. The most sparsely regions of algae, such as the lone patch towards the edge, may not have enough structural support to keep growing, etc. (There are lots of ways to rationalise this.)

We can emulate this using a very simple set of eight rules. For every possible arrangement of three “blocks” in our digital world, we’ll play God and determine whether algae will grow in the block immediately below the centre. For instance, I may impose the rule that no algae will grow immediately below any three contiguous algae ###, but algae will grow immediately below two algae separated by a space # #, etc.

This is something we can indeed emulate with a C++ program! We can represent the state of the universe with a (rather long) string of spaces and #’s. We’ll print out the universe, figure out where the algae will grow, then print out the new universe, then rinse and repeat for eternity. Depending on the initial spread of algae and what our rules are, we can end up with some fairly interesting emergent behaviour:

# ##  ##  ##  # #### ###  ## # # #    ##
# ############  #  # # #####      #  ##
  #          ### ##    #   ##    # ####
 # #        ## # ###  # # ####  #  #  ##
    #      ###   # ###    #  ### ## ####
#  # #    ## ## #  # ##  # ### # ## #  #
###   #  ### ##  ##  ####  # #   ##  ###
  ## # ### # #########  ###   # ######
 ###   # #   #       #### ## #  #    ##
## ## #   # # #     ##  # ##  ## #  ####
 # ##  # #     #   #####  ######  ###
#  ####   #   # # ##   ####    #### ##
 ###  ## # # #    ### ##  ##  ##  # ####
 # #####      #  ## # ############  #  #
   #   ##    # ####   #          ### ##
  # # ####  #  #  ## # #        ## # ###
##    #  ### ## ####    #      ###   # #
 ##  # ### # ## #  ##  # #    ## ## #  #

Let’s start by thinking through the pseudocode for our program. We don’t need any user input (for once), and there’s only one piece of information we need to keep track of at any moment in time: the current state of the universe, a string of spaces and #’s.

I’ve already loosely described how the program should work, but here’s some loose pseudocode to get us started:

1. Initialise the universe as a string with spaces and #’s
2. Repeat the following steps indefinitely:
   • Print the current universe to the screen.
   • For every patch of three adjacent characters in the universe, repeat the following:
     • If the patch of three is " ", replace the middle character with a ' '.
     • If the patch of three is " #", replace the middle character with a '#'.
     • And so on and so forth…

This paints a somewhat precise picture of what will happen, but there are many more questions that need to be answered. For instance,

• How many spaces and #’s should I use in step 1?
• What happens to the leftmost spot in the universe, which doesn’t lie directly below a patch of three squares?
• Can algae grow past the “edges” of the universe?
• If I replace the middle character of a patch, will that influence what happens to adjacent patches? If so, which order should I let the algae grow in?

Maybe you have more questions about the details of the implementation. Fortunately for us, nobody is our boss, and we get to decide how we handle these issues!

First, we’ll pick a fixed size for our universe, and algae will not be allowed to grow past the leftmost or rightmost boundaries of the universe. In fact, maybe the leftmost and rightmost spots of the universe are hostile to life, so we can keep them sterile for eternity. This addresses the first three issues we need to resolve.

Second, we’ll try to have all the new algae grow out “at the same time”, so that they don’t interfere with each others’ growth. We’ll accomplish this by creating a “new universe”, assigning spaces and #’s according to the contents of the “old universe”, then overwriting the “old universe” with every iteration of our simulation. More specifically, our pseudocode might look like this:

1. Initialise a string variable universe with 50 spaces or #’s.
2. Repeat the following steps indefinitely:
   • Print the universe to the screen.
   • Create a string variable new_universe with 50 spaces.
   • For each index i = 1, 2, ..., 48:
     • Check the index i - 1, i, i + 1 characters in universe.
     • Assign the index i character in new_universe according to the eight laws of algae.
   • Overwrite the contents of universe with new_universe.

Note the range of the for loop nested within step 2. We only wish to repeat instructions for the triples of characters that are within the confines of our universe, and the index i represents the centre of the triple. There is no triple centred at index 0, the left border of the universe, nor is there a triple centred at index 49, the rightmost border of the universe!

Let’s now begin writing the code. The implementation of step 1 is straightforward: just create a string with 50 spaces, maybe populating a few spots of algae as you see fit.

1// 1. Create a universe of 50 spaces or `#`'s. 
2//                 12345678901234567890123456789012345678901234567890
3string universe = "     # # # ### ##        #             #          "; 

The comment is to help me count the number of characters in my string, just to make sure I get it right.

Next, let’s implement step 2. The command “repeat indefinitely” can be translated in C++ by wrapping its instructions within a while(true) { ... }, which will never end. I’ll omit this for now and fill in the middle steps.

First, we’ll print the universe and create a new barren universe. Although you can type out 50 spaces by hand, you can also add 50 spaces with a for loop: “Repeat 50 times: add a space to new_universe”.

1// print the universe to the screen. 
2cout << universe << endl; 
3
4// create a new_universe of 50 spaces. 
5string new_universe; 
6for(int i = 0; i < 50; i++) {
7    new_universe += " "; 
8} 

Next, we need to write the big for loop. Fortunately, the bounds are written out for us. We’ll create an auxiliary string variable called neighbours, to store the three characters at indices i-1, i, i+1, then compare this variable to all 8 possibilities to decide if there’ll be a new algae there or not. In code,

 1for(int i = 1; i <= 48; i++) {
 2    // we can use the substr command to simplify! 
 3    string neighbours = universe.substr(i - 1, 3); 
 4
 5    // compare neighbours to each of the eight possibilities. 
 6    if     (neighbours == "   ") { new_universe.at(i) = ' '; } 
 7    else if(neighbours == "  #") { new_universe.at(i) = ' '; } 
 8    else if(neighbours == " # ") { new_universe.at(i) = '#'; } 
 9    else if(neighbours == " ##") { new_universe.at(i) = '#'; } 
10    else if(neighbours == "#  ") { new_universe.at(i) = '#'; } 
11    else if(neighbours == "# #") { new_universe.at(i) = '#'; } 
12    else if(neighbours == "## ") { new_universe.at(i) = ' '; } 
13    else if(neighbours == "###") { new_universe.at(i) = ' '; } 
14} 
15
16// replace universe with new_universe 
17universe = new_universe; 

And that’s the whole program!

If you run this, you may find that the output blazes past and you can’t see a thing. To slow the program down, we can use some special libraries that let us pause the program for a split second before printing out each line. Here’s the full program, with this additional delay:

 1#include <iostream> // needed for cout, endl 
 2#include <string>   // needed for strings 
 3
 4using namespace std; 
 5
 6// these two libraries and namespaces will let us 
 7// pause the program for a short time. 
 8#include <chrono> 
 9#include <thread> 
10using namespace std::chrono; 
11using namespace std::this_thread; 
12
13int main() {
14    // 1. Create a universe of 50 spaces or `#`'s. 
15    //                 12345678901234567890123456789012345678901234567890
16
17    string universe = "     # # # ### ##        #             #          "; 
18
19    // 2. repeat indefinitely... 
20    while(true) {
21        // print the universe to the screen. 
22        cout << universe << endl; 
23
24        // create a new_universe of 50 spaces. 
25        string new_universe; 
26        for(int i = 0; i < 50; i++) {
27            new_universe += " "; 
28        }       
29
30        // propogate the algae! 
31        for(int i = 1; i <= 48; i++) {
32            // we can use the substr command to simplify! 
33            string neighbours = universe.substr(i - 1, 3); 
34
35            // compare neighbours to each of the eight possibilities. 
36            if     (neighbours == "   ") { new_universe.at(i) = ' '; } 
37            else if(neighbours == "  #") { new_universe.at(i) = ' '; } 
38            else if(neighbours == " # ") { new_universe.at(i) = '#'; } 
39            else if(neighbours == " ##") { new_universe.at(i) = '#'; } 
40            else if(neighbours == "#  ") { new_universe.at(i) = '#'; } 
41            else if(neighbours == "# #") { new_universe.at(i) = '#'; } 
42            else if(neighbours == "## ") { new_universe.at(i) = ' '; } 
43            else if(neighbours == "###") { new_universe.at(i) = ' '; } 
44        }
45
46        universe = new_universe; 
47
48        // delay so our eyes can catch up 
49        sleep_for(milliseconds(50)); 
50    } 
51
52    return 0; 
53} 

What a beautiful output.

There are some ways in which our code is yet undesirable. For instance, what if I want to make my universe 60 squares across instead of 50? This will take some significant effort: I have to adjust the bounds of the big for loop, change how I initialise new_universe, and change how I initialise universe at the very start.

Let’s fix this issue by introducing a new constant at the beginning of our program, called UNIVERSE_SIZE. We’ll have to tweak the above pieces of code to use UNIVERSE_SIZE instead of 50. But with this effort, we can tweak the size of the universe by only changing the value of this named constant!

 1#include <iostream> // needed for cout, endl 
 2#include <string>   // needed for strings 
 3
 4using namespace std; 
 5
 6// these two libraries and namespaces will let us 
 7// pause the program for a short time. 
 8#include <chrono> 
 9#include <thread> 
10using namespace std::chrono; 
11using namespace std::this_thread; 
12
13int main() {
14    const int UNIVERSE_SIZE = 50; 
15
16    // 1. Create a universe of UNIVERSE_SIZE spaces or `#`'s. 
17    string universe; 
18    for(int i = 0; i < UNIVERSE_SIZE; i++) {
19        universe += " "; 
20    } 
21
22    // I'll throw in one lonely algae at index 25. 
23    universe.at(UNIVERSE_SIZE / 2) = '#'; 
24
25    // 2. repeat indefinitely... 
26    while(true) {
27        // print the universe to the screen. 
28        cout << universe << endl; 
29
30        // create a new_universe of 50 spaces. 
31        string new_universe; 
32        for(int i = 0; i < UNIVERSE_SIZE; i++) {
33            new_universe += " "; 
34        }       
35
36        // propogate the algae! 
37        for(int i = 1; i <= UNIVERSE_SIZE - 2; i++) {
38            // we can use the substr command to simplify! 
39            string neighbours = universe.substr(i - 1, 3); 
40
41            // compare neighbours to each of the eight possibilities. 
42            if     (neighbours == "   ") { new_universe.at(i) = ' '; } 
43            else if(neighbours == "  #") { new_universe.at(i) = ' '; } 
44            else if(neighbours == " # ") { new_universe.at(i) = '#'; } 
45            else if(neighbours == " ##") { new_universe.at(i) = '#'; } 
46            else if(neighbours == "#  ") { new_universe.at(i) = '#'; } 
47            else if(neighbours == "# #") { new_universe.at(i) = '#'; } 
48            else if(neighbours == "## ") { new_universe.at(i) = ' '; } 
49            else if(neighbours == "###") { new_universe.at(i) = ' '; } 
50        }
51
52        universe = new_universe; 
53
54        // delay so our eyes can catch up 
55        sleep_for(milliseconds(50)); 
56    } 
57
58    return 0; 
59} 

One can also replace the 50 in the sleep_for command with another named constant like DELAY_MS. This lets us keep the “settings” for our simulation in one spot, separate from the logic and intricate workings of our “actual” code.