In a nutshell, the "game" (I use quotes because it is not a game in the traditional, competitive sense, although some people have created variants that allow two players to "compete") is staged in a 2-D world that one can think of as a grid of "cells." The life of each cell depends upon its neighbors; cells like some company, but not too much! For each "step" in the game, each cell's life is evaluated based on the number of living neighbors it has (above and below, left and right, and the four diagonals). The life of the cell following the step is determined by three rules:
- If the number of living neighbors is exactly 2, the cell remains alive or dead (whichever it was previously).
- If the number of living neighbors is exactly 3, the cell is "born" (or remains alive).
- Otherwise, the cell "dies" (or remains dead).
Pretty simple, right? So simple that an entire implementation with an ncurses interface takes less than 200 lines of code (as sloccount reports; minus whitespace and comments). So, let's get to it!
Creating Life
I chose C++ for this because encapsulating the functionality of Life is quite easy; however, most of the code is written in a structured programming style so you may choose to modify it into a C program. My choice of API is based on a very basic set of capabilities I wanted in my program; you may wish to design it differently to fit your needs. The class definition is as follows:
class Life {
private:
char *world; // Pointer to current world representation
char *_world[2]; // Two mirrors, used for stepping evaluation
int cur_world; // Tracks which mirror is "current"
int width; // Width of world
int height; // Height of world
public:
Life(); // Initialize with default width and height
Life(int, int); // Initialize with custom width and height
~Life();
char get(int, int); // Get cell state
char toggle(int, int); // Toggle cell state
void step(); // Step evaluation once
};
Recall that in C++, class members prior to the first label are private by default; I include it merely as a friendly reminder. The Life "world" is a 2-D array, but I chose to implement this as a 1-D array and compute the 2-D position manually (dynamically allocating a 2-D array in C gets a bit ugly and this is a "fun" project, after all!). If the desired 2-D dimensions are defined as W x H and each array position holds 1 byte, then the array can be allocated using
char *myArray = (char *)malloc(W*H);
and the 2-D position at x, y can be accessed using
myArray[x*W+y]
As a side note, this is called "row major" ordering of the array memory. Alternatively, one could compute the position as y*H+x ("column major"). Depending upon how indices in the array are typically accessed, choosing row major versus column major can have a performance impact - though not noticeably so for my small program!
Most of the Life functions are straightforward so I won't go into their details. The only sneaky thing going on in this class definition is the use of world and _world[]. When evaluating each step in the game, every array position is potentially updated based on the previous value of its neighbors' positions. This means that the previous positions need to be retained until all new positions that depend on them have been computed. It is possible to copy each old position into a smaller temporary buffer just until the next row is computed, but on a small scale it is reasonable to simply maintain two copies or "mirrors" of the world, one for the previous step and one for the new step.
Rather than compute the new world in a temporary array and then copy that full array back into the main array, we can use pointers to change which mirror is the "main" array at each step:
void Life::step() {
...
char *oldworld = _world[cur_world];
cur_world ^= 1;
world = _world[cur_world];
...
world always points to the main array, and cur_world is an index into _world[] that tracks which mirror is current. When stepping, pointer oldworld is set to the current world, cur_world is flipped (from 0 to 1 or 1 to 0, recalling that 1 XOR 1 = 0 and 0 XOR 1 = 1), and world is set to the new current world. Now, all Life functions can simply reference world. For the remainder of the stepping function, world is the new step being updated and oldworld is the previous step used in its computation.
The rest of the stepping function computes the new state of each cell in the world:
...
int x, y;
for (x=0; x<width; x++) {
for (y=0; y<height; y++) {
...
Variables x and y iterate over all positions in the 2-D interpretation of the array. At each position, I must count up the number of living neighbors of the cell from the previous step. This brings up another sneaky thing: how are cells on the edges of the grid computed, since they have fewer neighbors? For this, I allow the world to wrap in both the horizontal and vertical dimensions. This complicates the math for computing array positions, but we can break it down and consider one component at a time. Suppose the horizontal position of the current cell is x, and we wish to get its "right" neighbor (which, if x is width-1, will be at horizontal position 0). This can be generally computed, using the modulo operator, as
(x+1)%width
noting that (width-1+1)%width = width%width = 0. Computing the "left" neighbor is only slightly harder. We don't want to end up with a negative number, so we must first add width to x and then subtract 1 before taking the modulo:
(x+width-1)%width
Supposing x is 0, (0+width-1)%width = (width-1)%width = width-1, which is the "left" neighbor's horizontal position. As can be shown with a quick test, this math works for all non-edge cases as well.
Combining this math with our row major calculation from above, we get eight indices into the 1-D array that are summed as living neighbor count n:
...
int n = oldworld[(x+width-1)%width*width+(y+height-1)%height]
+ oldworld[(x+width-1)%width*width+y]
+ oldworld[(x+width-1)%width*width+(y+1)%height]
+ oldworld[x*width+(y+height-1)%height]
+ oldworld[x*width+(y+1)%height]
+ oldworld[(x+1)%width*width+(y+height-1)%height]
+ oldworld[(x+1)%width*width+y]
+ oldworld[(x+1)%width*width+(y+1)%height];
...
The rest of the loop carries out the decision whether the cell is left as-is, born, or killed. Notice again that the updated value is placed into world, not oldworld:
...
if (n == 2)
world[x*width+y] = oldworld[x*width+y];
else if (n == 3)
world[x*width+y] = (char)1;
else
world[x*width+y] = (char)0;
}
}
...
A simple ncurses interface
As I mentioned at the outset, I wanted to do a bit of basic programming with ncurses. This library allows one to create nice interfaces inside a text terminal. Among its niceties is the ability to place characters at arbitrary locations in the terminal screen and to capture keyboard key presses. This is plenty of capability for a simple implementation of Life.
There is already a great howto guide for ncurses, so again I won't belabor its details except to point out in general how I designed my program. (Actually, the author wrote another implementation of Life that that goes with the guide. I have not looked at this implementation however since my goal was practice and creativity.)
Nearly all the interface functionality of my implementation resides in main(), since it is really that simple a program. The only separated function is drawlife(), which (re)draws the entire world. It only requires two ncurses functions, move() that repositions the cursor and addch() that places a character at the cursor and moves the cursor one position to the right. This function iterates through each row, moving the cursor to the start of that row on the screen, then printing each character (ON_CH or 'X' for a living cell and OFF_CH or '.' for a dead cell). Since characters in a terminal are taller than they are wide, I added the ability to scale the x or horizontal dimension using xspace to make the grid appear closer to square. This is the purpose of the innermost loop that prints spaces between each cell:
...
for (u=border; u<=height-1+border; u++) {
move(u, border);
for (v=border; v<=width-1+border; v++) {
addch((life->get(v-border, u-border)) ? ON_CH : OFF_CH);
for (z=xspace-1; z>0; z--)
addch(' ');
}
}
...
Variable border is set to 1 if a nice 1-character border is desired around the top, bottom, left, and right edges, and 0 otherwise. If it is set, all computed positions in the program are offset by one spot vertically and horizontally; this is seen wherever border appears elsewhere in the code.
The start of the main function is concerned with creating a Life class instance, initializing ncurses, and drawing the initial screen; this can be seen in the full code below. Then the function enters a loop on user input. Function getch() fetches the next key pressed by the user, which is used to select the appropriate action:
...
while ((ch = getch()) != KEY_F(1)) {
switch(ch) {
case KEY_LEFT:
if (x > 0 + border)
x -= xspace;
break;
...
Macro KEY_F(n) maps to constants for the function key Fn; I chose F1 to be the "quit" key. Inside the loop is a switch on the pressed key ch. If the left arrow key (KEY_LEFT) was pressed and the cursor is not at the far left of the screen already, then the cursor is moved to the left one cell (adjusted for horizontal spacing). Similar cases are defined for the right, up, and down keys. The space key toggles the cell at the current cursor position between alive and dead. Since it is unnecessary to redraw the entire world for one cell change, the new character is written manually:
...
case ' ':
z = myLife.toggle((x - border)/xspace, y - border);
if (z == 1)
addch(ON_CH);
else if (z == 0)
addch(OFF_CH);
break;
...
Notice again that the math gets a bit tricky, since both horizontal spacing and an optional border have to be taken into account: the onscreen position may be an offset multiple of the array position.
Since it is tedious to toggle many individual cells, I also made a way to toggle all cells with a certain probability. Keys 1 through 9 map to (roughly speaking) a 10% to 90% chance of toggling each individual cell in the world. This logic is handled in the default case of the main switch statement; I won't show it here but simply note how the probability is computed. For whichever key is pressed, I get a number between 1 and 9 using
z = ch - '0';
I then use rand() to get a random number between 0 and RAND_MAX (a constant defined in the include file cstdlib). This number is scaled to a value between 0 and 9, and if that number is below z then that cell is toggled. Each cell is statistically toggled independent of every other cell. The comparison used is:
if (int(10*(double)rand()/RAND_MAX) < z) ...
The 's' key performs the step function once and redraws the world. To make the game more lively, I added the ability to animate the game by stepping at a set rate, using the 'r' key. It simply runs through its own loop, stepping once, redrawing, and sleeping for a bit. In order to stop this animation, another key press is needed; however, getch() blocks by default, so further steps cannot occur without user intervention. Fortunately, ncurses provides timeout(), which when given 0 makes getch() non-blocking (when it is called and there is no input, its result does not match any valid key value). Another switch statement is used to check if 'r' is pressed again (which sets variable u to 0, stopping the animation on the next iteration). If 1 through 9 are pressed during animation, they change the rate of the animation (9 being fastest at one step per 0.1 second). When the loop ends, timeout() is called with -1 to restore blocking mode.
Finally, at the end of the outer while loop, move() is called with the current expected position of the cursor. Since some of the operations move the cursor to redraw portions of the screen, this ensures that when the operation is done the cursor will be where the user left it.
The code
The full program code follows. It should be easy to compile on any Linux or or Unix-variant system that has the ncurses library and development headers installed ("sudo apt-get install libncurses5-dev" should do the trick on a Debian or Ubuntu system). You will of course need g++ or a similar C++ compiler installed as well. The program can be compiled using "g++ life-ncurses.cpp -o life -lncurses" (assuming you save the text below as "life-ncurses.cpp"). Note that the default world size is 40x40; with borders turned off and horizontal spacing set to 2, this should be run in a terminal with dimensions at least about 80x45 (wide by high) to fit everything onto the screen.
This code is free for any use at your own risk (it may contain bugs); enjoy!
Download: life-ncurses.cpp
Download: life-ncurses.cpp
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <unistd.h>
#include <ncurses.h>
#define DEFAULT_WIDTH 40
#define DEFAULT_HEIGHT 40
#define ON_CH 'X'
#define OFF_CH '.'
//
// Life class
//
class Life {
private:
char *world; // Pointer to current world representation
char *_world[2]; // Two mirrors, used for stepping evaluation
int cur_world; // Tracks which mirror is "current"
int width; // Width of world
int height; // Height of world
public:
Life(); // Initialize with default width and height
Life(int, int); // Initialize with custom width and height
~Life();
char get(int, int); // Get cell state
char toggle(int, int); // Toggle cell state
void step(); // Step evaluation once
};
Life::Life() {
Life(DEFAULT_WIDTH, DEFAULT_HEIGHT);
}
Life::Life(int w, int h) {
if (w <= 0 || h <= 0) // If invalid width/height, use defaults
Life();
// Set class instance parameters
width = w;
height = h;
cur_world = 0;
// Allocate space for two mirrors of world
_world[0] = (char *)malloc(sizeof(char)*width*height);
_world[1] = (char *)malloc(sizeof(char)*width*height);
// Initialize one mirror and set pointer as "current" world
memset(_world[cur_world], 0, sizeof(char)*width*height);
world = _world[cur_world];
}
Life::~Life() {
free(_world[0]);
free(_world[1]);
world = _world[0] = _world[1] = NULL;
}
free(_world[0]);
free(_world[1]);
world = _world[0] = _world[1] = NULL;
}
char Life::get(int x, int y) {
// Make sure world is initialized and position is valid
if (!world)
return -1;
if (x < 0 || x >= width)
return -1;
if (y < 0 || y >= height)
return -1;
// world is simulated 2D array; have to computer absolute position
return world[x*width+y];
}
char Life::toggle(int x, int y) {
// Make sure world is initialized and position is valid
if (!world)
return -1;
if (x < 0 || x >= width)
return -1;
refresh();
if (y < 0 || y >= height)
return -1;
// world is simulated 2D array; have to computer absolute position
return world[x*width+y] ^= (char)1;
}
void Life::step() {
// Make sure world is initialized
if (!world)
return;
// Flip mirrors
char *oldworld = _world[cur_world];
cur_world ^= 1;
world = _world[cur_world];
// Iterate through entire world
int x, y;
for (x=0; x<width; x++) {
for (y=0; y<height; y++) {
// Each cell in updated world is computed from 8 neighbors
// Note that neighbors wrap across width/height boundaries
int n = oldworld[(x+width-1)%width*width+(y+height-1)%height]
+ oldworld[(x+width-1)%width*width+y]
+ oldworld[(x+width-1)%width*width+(y+1)%height]
+ oldworld[x*width+(y+height-1)%height]
+ oldworld[x*width+(y+1)%height]
+ oldworld[(x+1)%width*width+(y+height-1)%height]
+ oldworld[(x+1)%width*width+y]
+ oldworld[(x+1)%width*width+(y+1)%height];
if (n == 2) // Cell stays as-is
world[x*width+y] = oldworld[x*width+y];
else if (n == 3) // Cell is "born"
world[x*width+y] = (char)1;
else // Cell "dies"
world[x*width+y] = (char)0;
}
}
}
//
// UI functions and main loop
//
// Redraw full Life world
void drawlife(Life *life, WINDOW *win, int height, int width, int border, int xspace) {
int u, v, z;
// For each row
for (u=border; u<=height-1+border; u++) {
move(u, border); // Move to start of row then draw each cell
for (v=border; v<=width-1+border; v++) {
addch((life->get(v-border, u-border)) ? ON_CH : OFF_CH);
for (z=xspace-1; z>0; z--) // Correct for width spacing
addch(' ');
}
}
}
int main(int argc, char **argv) {
int width = DEFAULT_WIDTH; // Width of world
int height = DEFAULT_HEIGHT; // Height of world
int border = 0; // 0=no border, 1=border
int xspace = 2; // spacing factor for width (x)
// Initialize Life world
Life myLife(width, height);
// Initialize ncurses
initscr();
cbreak();
noecho();
keypad(stdscr, TRUE);
// Set up window, border, and on-screen help
WINDOW *myWin;
myWin = newwin(height + (border*2), width + (border*2), 0, 0);
if (border)
wborder(myWin, '|', '|', '-', '-', '+', '+', '+', '+');
move(height + (border*2), border);
printw("SPACE Toggle selected cell\t1-9 Toggle with N*10%% chance (when stopped)\n");
printw("r Run/stop stepping \t1-9 Set stepping speed (when running)\n");
printw("s Step forward once \tF1 Quit (when stopped)");
// Draw Life world for first time
drawlife(&myLife, myWin, height, width, border, xspace);
// Initialize cursor
int x = border, y = border;
move(y, x);
curs_set(2);
// Temp variables used in loop
int ch, u, v;
char z;
// Loop on input commands until quit is called
while ((ch = getch()) != KEY_F(1)) {
switch(ch) {
case KEY_LEFT: // Move cursor left
if (x > 0 + border)
x -= xspace;
break;
case KEY_RIGHT: // Move cursor right
if (x < xspace*(width - 1) + border)
x += xspace;
break;
case KEY_UP: // Move cursor up
if (y > 0 + border)
--y;
break;
case KEY_DOWN: // Move cursor down
if (y < height - 1 + border)
++y;
break;
case ' ': // Toggle cell at cursor
z = myLife.toggle((x - border)/xspace, y - border);
if (z == 1)
addch(ON_CH);
else if (z == 0)
addch(OFF_CH);
break;
case 's': // Step world once
myLife.step();
drawlife(&myLife, myWin, height, width, border, xspace);
break;
case 'r': // Step world continuously
timeout(0); // Enable non-blocking input checking
u=1; // u is the "keep going" variable
v=5; // v is the stepping speed variable
while (u) {
// Step once, redraw, and sleep briefly
myLife.step();
drawlife(&myLife, myWin, height, width, border, xspace);
usleep(100000 * v);
// Check for input
switch (z = getch()) {
case 'r': // Stop running
u=0;
break;
default:
if (z >= '1' && z <= '9') // Adjust running speed (9 is fastest)
v = 10 - (z - '0');
}
}
timeout(-1); // Disable non-blocking input checking
break;
default:
if (ch >= '1' && ch <= '9') { // Randomly toggle all cells with chance
z = ch - '0';
for (u=0; u<=width; u++)
for (v=0; v<=height; v++)
if (int(10*(double)rand()/RAND_MAX) < z)
myLife.toggle(u, v);
// Redraw world
drawlife(&myLife, myWin, height, width, border, xspace);
}
}
move(y, x); // Update cursor position
}
// Shut down world and quit
endwin();
return 0;
}
// end of file
No comments:
Post a Comment