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.
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:
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.
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.