Cellular Automata
A cellular automaton is a mathematical model which is based on a very simple set of rules, but gives rise to often complex outcomes. You may be familiar with Conway’s Game of Life, a popular and extensively studied cellular automaton, which is a more complex example of what I dealt with in this project.
Conway’s Game of Life in Action. Source: http://cultsoftware.blogspot.com/
As part of an assignment for my Object Oriented C++ class at San Diego City College, the program I’ve created here, called James’ Cellular Automata, deals with a row of cells in a one-dimensional grid. Each cell exists in a finite state of being either “alive” or “dead”, represented in this program as a # symbol or a blank space respectively. An initial one-dimensional generation of cells is formed with a single alive cell “seeded” in a particular position inside the grid. Then, for a given number of cycles successive generations of grids are created. The cells that make up these grids inherit their state based on the configuration of the previous state according to a specific set of rules. Consider that any given cell in a one-dimensional grid may have two “neighbor” cells, the cell to its left and the cell to its right. A neighborhood as a whole can exist in one of eight possible configurations giving rise to the possibility of forming a simple set of rules that can govern whether a given cell in the next generation will be either alive or dead. For example, one rule you could think of is if a cell’s two neighbors are alive and the cell itself is dead, then in the following generation, the cell will switch states from dead to alive. However, this example is just one of eight possible configurations meaning that a full set of rules must take into account all possibilities. Here is an example of a simple rule-set:
Example of a rule-set for a simple 1D cellular automata. Source: http://natureofcode.com/
As it turns out, there are exactly 2^8 or 256 unique rules you could think of to determine the state of a cell in succeeding generations based on its previous state and that of its neighbors. The purpose of this project was to create a GUI-like console program to display the results of all 256 possible rule-sets over a given amount of generations. In this post I will detail my experiences working on this project over the weekend as well as outline my methods of implementation.
Creating Menu Items
My goal in undertaking this project was not just to explore cellular automata or get a good grade on the assignment, but also to attempt to implement a GUI-like menu system inside of a console window. To that end, I’ve adopted a library called PDCurses to build menu items that are useful for navigating through the various sections of the program. For how to set up the PDCurses library with Visual Studio 2013, view my post here.
Before I even began writing code I started poring over the PDCurses documentation in an attempt to understand how I would go about constructing basic UI elements like windows, colors, and text and also functionalities like taking input through the keyboard and being able to manipulate items on the screen. What stuck out to me at first was just how extensive the library was and how tedious it would be to constantly have to refer to the documentation just to remember the correct implementation of a function. I quickly realized that the first thing I was going to do was build a wrapper library consisting of only the PDCurses functions I would need, but with better documentation and easier to understand parameter names. The result worked out quite nicely and allowed me to spend less time referring back to the PDCurses website. Compare the following two examples.
Implementation of a standard PDCurses function.
Implementation of a function from my PDCurses wrapper.
Once I had an easy to use set of functions, my next step was to construct a class of commonly used menu items that would appear frenquently throughout the program. I included things like standard sized popup messages for alerts or for taking single lines of user input as well as menus that interfaced with the keyboard to navigate and select between a given set of options. This step saved me time as I didn’t have to rewrite the entire code for the window every time I needed to show a simple message to the user. All I had to do was standardize its border, size, color scheme and functionality and then simply construct an instance of the window and change the text to my desired message. Here is an example of some code I wrote that will display a popup message on the screen asking the user whether he or she would like to continue or go back that gets used several times throughout the program:
bool JamesConsoleUI::popUpConfirm(char* choice)
{
char *menuItems[] = { "Continue", "Back"};
int menuItemSelection;
//Another custom menu item - creates a blank frame of a standard size/color
WINDOW *win = popUpWindow();
//Confirms user selection (specification requirement)
JamesCurses::wattron(win, A_BOLD);
JamesCurses::mvwprintw(win, 2, 2, "Thanks for selecting <%s>", choice);
JamesCurses::wattroff(win, A_BOLD);
//a custom menu functionality that allows keyboard input and selection
menuItemSelection = navigationMenu(win, menuItems, 2);
//return either true or flase based on user input
if (menuItemSelection == 1)
{
JamesCurses::werase(win);
return true;
}
JamesCurses::wrefresh(win);
return false;
}
Building Menus
As I mentioned before, this was a class project, so I did have to build the program around certain specifications that may or may not have been included had this project been just something I did for fun. However, the basic gist of the task assigned to me was to create a console program that displayed a welcome message and then allowed the user to navigate to specific parts of the program. The main menu would be the hub to move between the different parts, including an option to sign in, display a custom ASCII-art logo, display the cellular automata patterns, and exit the program.
Here is an example of a simple credits menu that can be accessed through the main menu:
void JamesCA::credits()
{
//creates a large popup window with the option to hit enter to close
WINDOW* creditsWindow = JamesConsoleUI::largePopUpWindow();
//print information in center of window
JamesCurses::mvwprintwCentered(creditsWindow, 2, "CREDITS");
JamesCurses::mvwprintwCentered(creditsWindow, 5, "James' Cellular Automata Program was created by James McCarthy for");
JamesCurses::mvwprintwCentered(creditsWindow, 6, "Larry Forman's Fall 2014 CISC 205 Object Oriented C++ class at San");
JamesCurses::mvwprintwCentered(creditsWindow, 7, "Diego City College. Thank you to Nils Olsson for introducing me to");
JamesCurses::mvwprintwCentered(creditsWindow, 8, "PDCurses and helping me set it up in Visual Studio. Thank you to ");
JamesCurses::mvwprintwCentered(creditsWindow, 9, "the creators of PDCurses and ncurses for providing documentation ");
JamesCurses::mvwprintwCentered(creditsWindow, 10, "that helped me learn the ins and outs of ncurses/PDCurses. ");
JamesCurses::mvwprintwCentered(creditsWindow, 12, "PDCurses Website : www.pdcurses.sourceforge.net ");
JamesCurses::mvwprintwCentered(creditsWindow, 13, "My Personal Blog : www.jdonaldmccarthy.wordpress.com ");
JamesCurses::mvwprintwCentered(creditsWindow, 14, "My Github Profile : www.github.com/fanfare00 ");
//draws to screen
JamesCurses::wrefresh(creditsWindow);
//pause and wait for user to hit enter
JamesConsoleUI::hitEnter(creditsWindow);
//refresh background and return to main menu
refreshBackground();
mainMenu();
}
Menu Interactions
My top priority in designing the interface of this program was to make sure that moving between menus through the main menu hub worked smoothly and in a user-friendly way.
To accomplish this, I made sure that built the bulk of my program around the following mainMenu function:
void JamesCA::mainMenu()
{
//set up the options for the navigation menu
char *menuItems[] = {
"SIGN IN",
"DISPLAY LOGO",
"CELLULAR AUTOMATA",
"ID INFORMATION",
"CREDITS",
"STARS",
"EXIT" };
//variable to hold user menu selection
int choice = 0;
//function to avoid having to reprint everything upon return to main menu
refreshBackground();
//set framed title
WINDOW* titleBox = JamesConsoleUI::titleBox();
JamesCurses::mvwprintw(titleBox, 2, 5, "James Cellular Automata Program");
JamesCurses::wrefresh(titleBox);
//create frame to hold navigation menu
WINDOW *win = JamesCurses::newwin(15, 40, 14, (COLS / 2) - 20);
JamesCurses::wbkgd(win, COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::White_Yellow)));
JamesCurses::mvwprintw(win, 2, 15, "-MAIN MENU-");
JamesCurses::wrefresh(win);
//print instructions outside of main menu window
JamesCurses::wattron(mainWindow, A_BOLD | COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::Yellow_Cyan)));
JamesCurses::mvwprintwCentered(mainWindow, 30, "Use the arrow keys to move up and down");
JamesCurses::mvwprintwCentered(mainWindow, 31, "Press <ENTER> to make a selection");
JamesCurses::wattron(mainWindow, A_BOLD | COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::Yellow_Cyan)));
JamesCurses::wrefresh(mainWindow);
//deploy navigatable and selected list of menu options and get user selection
choice = JamesConsoleUI::navigationMenu(win, menuItems, 7);
//confirm user choice via a popup yes/no message
if (JamesConsoleUI::popUpConfirm(menuItems[choice - 1]))
{
//deploy appropriate menu based on user choice
switch (choice)
{
case 1:
signIn();
break;
case 2:
displayLogo();
break;
case 3:
patternMenu();
break;
case 4:
idInfo();
break;
case 5:
credits();
break;
case 6:
displayStars();
break;
case 7:
farewell();
break;
}
}
//if user answers no to popup yes/no, return to main menu
else
{
mainMenu();
}
}
There are many other examples of menus interacting with each other throughout the program, but the central hub is the main menu. The main point here is that PDCurses easily allows for this kind of functionality.
Generating One-dimensional Cellular Automata
Above you can see an example of one of the 256 available patterns printed over 30 lines inside of a PDCurses window. The user can enter a select the pattern number and generate an automaton based on the binaragy digits of the number. For example, the pattern you see here is #105, based off the rule-set 01101001 (64+32+8+1 = 105) as previously discussed. To accomplish this, the following code is used:
void JamesCA::displayPattern(int nSteps, char* ruleSet, char* patternCode)
{
int i; //iterate for
int j;
int nCells = 90;
char *x = new char[nCells + 2];;
char *x_old = new char[nCells + 2];;
bool rules[7]; //array of possible neighbor configurations
//resize the console window based on number of lines user asked to see
JamesCurses::resize_term(nSteps + 15, nCells + 6);
//title box that displays the code# and ruleset of the current pattern
WINDOW* patternTitle = JamesConsoleUI::titleBox();
JamesCurses::mvwprintw(patternTitle, 1, 16, "%s", ruleSet);
JamesCurses::mvwprintwCentered(patternTitle, 3, "PATTERN # %s", patternCode);
JamesCurses::wrefresh(patternTitle);
//window the pattern is displayed inside
WINDOW* patternWindow = JamesCurses::newwin(LINES - 12, COLS - 4, 8, (COLS / 2) - ((COLS - 4) / 2));
JamesCurses::wbkgd(patternWindow, A_BOLD | COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::Yellow_Black)));
JamesCurses::wbox(patternWindow, 0, 0);
JamesCurses::wrefresh(patternWindow);
//dont pause for input
nodelay(patternWindow, TRUE);
//allow window to scroll down and replace lines at the top
scrollok(patternWindow, TRUE);
//fill array with "dead" cells
for (i = 0; i <= nCells + 1; i++)
{
x[i] = ' ';
}
//seed cell in the middle in "alive" state
x[nCells/2] = '#';
//print "generation 1"
for (i = 1; i <= nCells; i++)
{
JamesCurses::mvwprintw(patternWindow, 1, i,"%c", x[i]);
}
//repeat for each row user asked for
for (j = 1; j <= nSteps; j++)
{
//put generation 1 into a seperate array for checking
for (i = 0; i < nCells + 2; i++)
{
x_old[i] = x[i];
}
for (i = 1; i <= nCells; i++)
{
//define each possible rule in the neighborhood
rules[7] = (x_old[i - 1] == ' ' && x_old[i] == ' ' && x_old[i + 1] == ' ');
rules[6] = (x_old[i - 1] == ' ' && x_old[i] == ' ' && x_old[i + 1] == '#');
rules[5] = (x_old[i - 1] == ' ' && x_old[i] == '#' && x_old[i + 1] == ' ');
rules[4] = (x_old[i - 1] == ' ' && x_old[i] == '#' && x_old[i + 1] == '#');
rules[3] = (x_old[i - 1] == '#' && x_old[i] == ' ' && x_old[i + 1] == ' ');
rules[2] = (x_old[i - 1] == '#' && x_old[i] == ' ' && x_old[i + 1] == '#');
rules[1] = (x_old[i - 1] == '#' && x_old[i] == '#' && x_old[i + 1] == ' ');
rules[0] = (x_old[i - 1] == '#' && x_old[i] == '#' && x_old[i + 1] == '#');
//loop through each binary digit int he user defined ruleset
for (int a = 0; a < 8; a++)
{
//if binary digit is a 0, dont use rule
if (ruleSet[a] == '0')
{
rules[a] = false;
}
}
//check if character in old generate satisfies rule and set character in new array to "alive"
if (rules[0] || rules[1] || rules[2] || rules[3] || rules[4] || rules[5] || rules[6] || rules[7])
{
x[i] = '#';
}
//otherwise, if rules are not satisfied, set new character to "dead"
else
{
x[i] = ' ';
}
}
x[0] = x[nCells];
x[nCells + 1] = x[1];
for (i = 1; i <= nCells; i++)
{
JamesCurses::mvwprintw(patternWindow, j+1, i, "%c", x[i]);
}
//if key is pressed, end pattern loop
if ((JamesCurses::wgetch(patternWindow) != ERR))
{
break;
}
//refresh after printing line
JamesCurses::wrefresh(patternWindow);
//pause thread for .25 seconds before printing next line
napms(250);
}
//free memory
delete[] x;
delete[] x_old;
JamesCurses::attron(A_BOLD | WA_BLINK | COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::Yellow_Black)));
JamesCurses::mvprintw( LINES-3, (COLS/2) - 2, "BACK");
JamesCurses::attroff(A_BOLD | WA_BLINK | COLOR_PAIR(static_cast<int>(JamesConsoleUI::Color::Yellow_Black)));
JamesCurses::refresh();
//if user hit enters return to main menu
JamesConsoleUI::hitEnter(patternWindow);
refreshBackground();
mainMenu();
}
That’s all folks. If you’d like to see this program in action, check out the github repository: https://github.com/fanfare00/James-Cellular-Automata
There are still a few minor improvements to make, but luckily it’s not due until this Thursday.
J. Donald McCarthy's Blog 