Chapter 33
Programming Linked Lists
-
About John Conway's Game of Life
Back in the dark ages of computing, a guy named John Conway came up with
simple mathematical rules that simulated a group of cells living and dying.
-
How to program a linked list
A linked list is a powerful data structure that enables you to store complex
data.
-
How to create a linked-list class
By encapsulating the linked list data type into a class, the linked list
becomes much easier to create and manage.
-
How to use linked lists to speed up the Life application
Linked lists can make complex programming tasks easier to tackle.
-
How to program the Game of Life for Windows 95
By the end of this chapter, you'll have your own Windows version of this
popular simulation.
Now that you know how to whip your MFC programs into shape, you'll spend
the last few chapters of this book learning some new techniques that'll
help you write more professional and effective applications. Linked
lists, for example which are the subject of this chapter provide an
excellent structure for storing certain types of data. Linked lists are
so important and are used so often in professional programs that MFC includes
classes for handling various types of linked lists. These classes are CObList,
CStringList, and CPtrList.
The Story of Life
Over 30 years ago, a fine English fellow by the name of John Conway invented
simple rules for a system that simulated the lives of special, one-celled
animals. Although the rules of the simulation were simple, the results
were fascinating. Before long, every computer scientist worth his or her
degree had written a version of Conway's Game of Life and had spent hours
trying different combinations of cells to see what patterns might emerge.
Today, people are still fascinated by Conway's computer simulation. Many
computer science books at least mention Life, and each year thousands of
computer science students write versions of Life as part of their programming
curriculum. The simplest implementations result in programs that accurately
portray the simulation but run too slowly to be practical. Other implementations
blaze across the screen in vivid colors and kaleidoscopic patterns, hypnotizing
any viewer who happens to glance in its direction.
What do linked lists and MFC have to do with a simulation of one-celled
creatures? That's a question whose answer you'll know by the time you get
to the end of this chapter. But before you get started with this chapter's
programming, take a little time to read the next section, where you'll
learn about Life and how the program works.
The Rules of Life
The Life simulation is played on a grid of any size. In the original rules,
the grid is unbounded, but you can limit the grid to the screen. You might
want to think of the screen display as a sort of petri dish holding a culture
of microscopic cells. Cells are placed randomly on the grid, and the simulation
is started. The cells then run through their life cycles a given number
of generations, living and dying according to the rules set forth by Conway.
The rules are simple and elegant: In any given generation, any live cell
with less than two neighbors dies of loneliness. Any live cell with more
than three neighbors dies of crowding. Any dead cell with exactly three
neighbors comes to life. And, finally, any live cell with two or three
neighbors lives, unchanged, to the next generation.
Life Implementation
As you might imagine, a large grid could contain hundreds if not thousands
of cells living and dying in every generation. The computer must work furiously,
calculating the number of neighbors for each cell in the grid and then
creating or killing cells based on these counts. And keep in mind that
counting the neighbors for a single cell requires checking each adjacent
cell as many as eight.
Suppose you implemented the grid as a two-dimensional array of integers,
like this:
int map[32][32];
Each element of the map can be one of two values: 0 if the cell is dead,
and 1 if the cell is alive. The logical way to process this grid is to
check each element of the array, counting its neighbors and marking it
as alive or dead.
In the example 32 [ts] 32 array, 1,024 cells must be processed every generation.
Each cell processed must check the status of as many as eight adjacent
cells to count its neighbors. That's over 8,000 operations for the entire
grid. Worse, this processing must be performed for every generation of
the simulation. A single run of the simulation might have as many as 10,000
generations!
All of this calculating wouldn't be a problem if you planned to let the
simulation run all night. However, to make the simulation interesting,
you must update the screen as quickly as possible, ideally several times
a second. Obviously, this creates a problem in the speed department.
Creating and Killing Cells
Speed is not the only problem. You also must consider the effects of prematurely
creating or killing cells. It's not enough to scan though the grid, creating
and killing cells as you go, because the cells that you create or kill
might affect cells that you have not yet processed. Suppose cell X in a
grid has only two neighbors. Now assume that a cell next to X dies as you
process the grid. Although this cell died, cell X should still remain alive
for this generation because it had two neighbors; it won't be lonely until
the next generation. When you finally process cell X, however, the counting
function recognizes cell X as having only one neighbor. As a result, cell
X dies prematurely.
Confused? Look at Figure 33.1. Three cells are in the first-generation
grid, which is on the left. In this generation, the uppermost cell must
die because it has only one neighbor. The middle cell must remain alive
until the next generation, because it has two neighbors. The bottom cell
must die because, like the top cell, it has only one neighbor. The empty
cells to the left and right of the center cell must be brought to life
because both have exactly three neighbors. After processing the grid, you
should have the second-generation grid, which is on the right.
FIG. 33.1
Applying the rules of Life to three cells yields the results shown in
the right hand grid.
However, if you start at the top and process the grid by creating and killing
cells as you go, you'll get incorrect results. First, you kill the top
cell, because it has only one neighbor. Then when you get to empty cell
1,2, even though it should have come to life, you determine that it has
only two neighbors and leave it alone. When you get to cell 2,2, you think
it has only one neighbor and kill it, even though this cell should have
survived to the next generation. After processing the entire grid, you
don't have the correct second-generation result. Instead, you have an empty
grid!
In short, in each generation, you must determine which cells will live
and die, without changing the grid. Then when you are finished, you must
simultaneously create and kill the appropriate cells. This requires tricky
algorithms, especially when you consider that all these calculations must
be performed at a speed that allows fast screen updates. Sound like fun?
Let's give it a shot.
Dealing with the Speed Problem
What can you do to speed things up? First, add another map array to keep
a running count of each cell's neighbors. When the simulation starts, the
program will do a full update of the neighbor count. From then on, rather
than recalculating the entire grid in each generation, the program changes
neighbor counts for only those cells adjacent to cells that have just been
created or killed. This method cuts processing time significantly: In a
given generation, the program must change the neighbor counts of only a
small number of cells instead of the entire grid.
Then, although the original map grid will record the status of each cell,
add two lists of cells one for cells about to be created and one for cells
about to die. These are the only cells that affect the map, so there's
no reason to check the entire grid every generation.
But what type of data structure enables you to build lists of items lists
that can grow or shrink dynamically? You've probably already guessed that
the answer is a linked list.
Linked Lists
Linked lists are an incredibly useful data structure for organizing information
in memory. One of their big advantages is that you can add, remove, and
move items in the list just by manipulating a couple of pointers. And because
the contents of a linked list are determined dynamically as the program
runs, you don't need to decide on a size for the list ahead of time, as
you would with a data structure like an array. This enables you to utilize
memory to its fullest. In the sections that follow, you'll learn the basic
techniques used for creating and managing linked lists. This background
will help you to better understand the linked-list classes provided by
MFC.
Creating a Linked List
To create a linked list, you first must decide what information makes up
the items, or nodes, that will be stored in the list. In the simulation
program, you must store enough data to identify a cell. All the information
that you need to identify a cell are its X and Y coordinates in the grid,
so a node could be the structure shown in Listing 33.1.
Listing 33.1 lst33_01.cpp A Structure for a Node
struct Node
{
int x, y;
};
When a cell is born or dies, you can create a node for the cell like this:
Node *node = new Node;
node->x = x_ccord;
node->y = y_coord;
This code creates a new Node structure
on the heap and sets its X and Y
members to the coordinates of a cell. But what good is it to have a bunch
of these nodes sitting around in memory? You must link them into a list.
To do this, you must add to your structure a pointer to a node. You can
then use this pointer to point to the next node in the list. The new Node
structure, then, looks like Listing 33.2.
Listing 33.2 lst33_02.cpp A Node for a Linked List
struct Node
{
int x, y;
Node *next;
};
In addition to the data structure for a node, you also need a pointer to
the first node of the list (a head pointer) and a pointer to the
end of the list (a tail pointer). Having a pointer to the head of
the list is most important. Without it, you can't find the list in memory.
A pointer to the tail is a convenience. You can use it to quickly add new
nodes to the end of the list, without having to scan the list from the
first node. The head and tail pointers look like this:
Node *list_h, *list_t;
Figure 33.2 illustrates how a linked list looks in memory. The list_h
pointer points to the first node in the list. Each node has a pointer that
leads to the next node in the list. The next pointer in the last node is
left NULL, which indicates the end
of the list. Finally, the list_t
pointer points to the last node in the list.
FIG. 33.2
This is what a linked list looks like in memory.
Listing 33.3 is the source code for a simple list-handling program. Note
that this program is not meant to run under Windows and is presented here
only to demonstrate the basic techniques of programming a linked list.
Listing 33.3 lst33_03.cpp A Simple Linked List Demonstration
struct Node
{
int x, y;
Node *next;
};
Node *node = NULL,
*list_h = NULL,
*list_t = NULL;
void main(void)
{
for (int i = 0; i < 10; ++i)
{
node = new Node;
node->x = i;
node->y = i * 10;
if (!list_h)
list_h = node;
else
list_t->next = node;
list_t = node;
list_t->next = NULL;
}
while (list_h)
{
node = list_h;
list_h = list_h->next;
cout << node->x << ',' << node->y << '\n';
delete node;
}
}
Study Listing 33.3 carefully, so you're sure you understand how to create
and manage a linked list. This knowledge will help you better understand
how to take advantage of MFC's list classes. In Listing 33.3, the Node
structure is the type of item stored in the list. This structure contains
two data elements, as well as a pointer to a Node.
This pointer, next, is used to point
to the next node in the list.
The program begins with a for loop,
in which ten nodes are created and linked. In the loop, the new
operator creates a new node on the heap, after which the node's data elements
are set to the values of i and i*10.
(These values hold no particular significance.) After creating the node,
the program checks whether list_h
is NULL. If it is, the program has
a new list, so it sets list_h to
point to node. Then list_t
is set to point to the same node (if the list has only one item, the head
and tail of the list are the same), and list_t's
next pointer is set to NULL,
indicating there are no other items in the list.
Getting back to the if statement,
if list_h isn't NULL,
there's already at least one node in the list. In this case, list_h
shouldn't be changed. Rather, the new node must be added to the end of
the list. This is where list_t comes
in handy. Rather than having to scan through the whole list, looking for
a NULL next,
the program can use list_t to tack
the new node onto the end of the list. It does this by setting list_t's
next pointer to point to the new
node and then changing list_t to
point to the new last node. Figures 33.3 through 33.6 illustrate this process.
FIG. 33.3
Step 1 of creating a linked list.
FIG. 33.4
Step 2 of creating a linked list.
FIG. 33.5
Step 3 of creating a linked list.
FIG. 33.6
Step 4 of creating a linked list.
After the program creates the linked list, a while
loop scans the list, printing each node's contents before deleting the
node. Notice how the temporary node pointer keeps track of the current
node. By setting node to list_h
and then setting list_h to point
to the next item in the list, you effectively "pop off" the first
node. Without saving the pointer in node,
you could not access this node. The program's output follows:
0,0
1,10
2,20
3,30
4,40
5,50
6,60
7,70
8,80
9,90
An Object-Oriented List
If you've an idea that a linked list might be the perfect candidate for
a class, you could be correct, depending on how you plan to use the list.
Creating a linked list class to handle only a single list in a small program
such as Listing 33.3 is overkill (or is it?). However, if you plan to use
many different lists in a program that is, the class won't be a single-instance
class it might be worthwhile to create a linked list class.
For the sake of discussion, you'll now convert Listing 33.1 into an object-oriented
program. Listing 33.4 is the header for the resultant List
class.
Listing 33.4]em]lst33_04.cpp The Header File for the List Class
#ifndef _LIST_H
#define _LIST_H
class List
{
struct Node
{
int x, y;
Node *next;
};
Node *node, *list_h, *list_t;
public:
List(void);
~List(void);
void MakeNewNode(int n1, int n2);
void DisplayList(void);
};
#endif
As you can see, all of the list-handling operations have been taken out
of the main program and placed into the List
class. The data that defines the list the pointers and the node declaration
are placed inside the class also. The main program no longer has to know
how a linked list works. It only has to draw on the capabilities of the
class. First, look at the class's constructor, as shown in Listing 33.5.
Listing 33.5 lst33_05.cpp The List Class's Constructor
List::List(void)
{
list_h = list_t = NULL;
}
This function initializes a new list by setting its pointers to NULL.
This creates an empty list which isn't particularly useful. The class needs
a way to add nodes to the list, as shown in Listing 33.6.
Listing 33.6 lst33_06.cpp The MakeNewNode() Member Function
void List::MakeNewNode(int n1, int n2)
{
node = new Node;
node->x = n1;
node->y = n2;
if (!list_h)
list_h = node;
else
list_t->next = node;
list_t = node;
list_t->next = NULL;
}
This function takes as parameters the values for the new node's x
and y members. First the new node
is allocated on the heap, after which the x
and y members are set to their appropriate
values. Then, using the same code examined in Listing 33.3, the new node
is added to the list.
To display the contents of the list, you can call this class's DisplayList()
function, which is shown in Listing 33.7.
Listing 33.7 lst33_07.cpp The DisplayList() Member Function
void List::DisplayList(void)
{
node = list_h;
while (node)
{
cout << node->x << ',' << node->y << '\n';
node = node->next;
}
}
This function simply scans the list (using the temporary node pointer,
so it doesn't destroy list_h), printing
the contents of x and y.
Unlike the program in Listing 33.3, each node isn't deleted after it's
printed. That job is left for the class's destructor, shown in Listing
33.8.
Listing 33.8 lst33_08.cpp The List Class's Destructor
List::~List(void)
{
while (list_h)
{
node = list_h;
list_h = list_h->next;
delete node;
}
}
As with any class, the List class's
destructor is called when a List
object goes out of scope or when a dynamically allocated List
object is deleted. The destructor then deletes every node in the list,
using the same method that you saw in Listing 33.3 (but without printing
the contents of the node before deleting it).
Listings 33.9 and 33.10 are the List
class's implementation and the new main program, respectively.
Listing 33.9 lst33_09.cpp The List Class's Implementation
#include "list.h"
List::List(void)
{
list_h = list_t = NULL;
}
List::~List(void)
{
while (list_h)
{
node = list_h;
list_h = list_h->next;
delete node;
}
}
void List::MakeNewNode(int n1, int n2)
{
node = new Node;
node->x = n1;
node->y = n2;
if (!list_h)
list_h = node;
else
list_t->next = node;
list_t = node;
list_t->next = NULL;
}
void List::DisplayList(void)
{
node = list_h;
while (node)
{
cout << node->x << ',' << node->y << '\n';
node = node->next;
}
}
Listing 33.10 lst33_10.cpp A Test Program for the List Class
#include "list.h"
void main(void)
{
List list;
for (int i = 0; i < 10; ++i)
list.MakeNewNode(i, i*10);
list.DisplayList();
}
The main program is much shorter and clearer than the original program.
Although the effort of creating the class for such a small program might
or might not be worthwhile, imagine how much easier it would be to use
a similar class in a large program that must handle multiple lists. By
using a list class, you no longer must worry about initializing pointers
or linking nodes. You don't even have to worry about releasing nodes from
memory, because the class's destructor takes care of this task for you.
By using the class, your main program is clean and to the point, uncluttered
with the details of handling a linked list.
The Life Program
You now know what linked lists are and how to handle them. You've even
created a simple list class that demonstrates how you might go about using
objected-oriented programming techniques to better organize programs that
need to use linked lists. It's time to put your knowledge of linked lists
to work, by examining the Life program, which uses MFC's more complicated
and complete linked list class, called CPtrList.
This program's listing will be explored a piece at a time, in the order
in which it is executed. But first, run the program and see what it does.
You can find the executable file, as well as all of the source code, in
the Chap33\LIFE folder at this book's Web site.
When you run Life, the main screen appears, as shown in Figure 33.7. Most
of the screen is made up of the grid in which your cells will live and
die. Above the grid is the toolbar, which contains several command buttons
used to control the program. At the bottom of the screen is the status
bar, where you can see the current speed setting for the simulation, the
maximum number of generations for a run of the simulation, and the currently
displayed generation. Before the simulation starts, the speed is set to
10, the maximum generations to 100, and the currently displayed generation
to 0.
FIG. 33.7
Life's main window features a toolbar and a status bar.
To get started, you must first seed the grid with cells. To do this, place
your mouse pointer where you want to place a cell, and then click the left
button. A red cell appears where you clicked. If you want to place cells
quickly, click the Random toolbar button (the fourth button) or press F5
on your keyboard. Each time you choose the Random command, the program
places more cells on the grid.
When you've placed your cells, activate the simulation by selecting the
Start button, or by pressing F2. When you select Start, the simulation
springs to life, with cells living and dying as they speed through their
life cycles. To stop the simulation before the generations run out, click
the Stop button or press F3.
Right after the Stop button is the Clear button, which removes all of the
cells from the grid. You can also select the Clear command by pressing
F4. The Generation button (F6) sets the generation count. When you select
this button, the Generations dialog box appears, as shown in Figure 33.8.
To change the generation setting, type a number from 1 to 64,000.
FIG. 33.8
The Generations dialog box sets the maximum number of generations.
You might want to view the simulation at slower speeds so that you can
see more clearly the patterns that emerge from specific cell configurations.
You can set the simulation to one of ten speeds by selecting the Speed
button (F7). The Simulation Speed dialog box then appears, as shown in
Figure 33.9. Enter a value from 1 to 10. (1 is the slowest, and 10 is the
fastest.) Invalid entries yield the default value of 10.
FIG. 33.9
The Speed dialog box enables you to run the simulation at one of ten
speeds.
Examining Life
Now that you know how to use the program, it's time to examine the listing
and see how Life works, especially how it handles its linked list using
MFC's CPtrList class. Listings 33.11
through 33.18 comprise the program's source code.
Listing 33.11 lifeapp.h The Application Class's Header File
///////////////////////////////////////////////////////////
// LIFEAPP.H: Header file for the CLifeApp class, which
// represents the application object.
///////////////////////////////////////////////////////////
class CLifeApp : public CWinApp
{
public:
CLifeApp();
// Virtual function overrides.
BOOL InitInstance();
};
Listing 33.12 lifeapp.cpp The Application Class's Implementation File
///////////////////////////////////////////////////////////
// LIFEAPP.CPP: Implementation file for the CLifeApp,
// class, which represents the application
// object.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "lifeapp.h"
#include "mainfrm.h"
// Global application object.
CLifeApp LifeApp;
///////////////////////////////////////////////////////////
// Construction/Destruction.
///////////////////////////////////////////////////////////
CLifeApp::CLifeApp()
{
}
///////////////////////////////////////////////////////////
// Overrides
///////////////////////////////////////////////////////////
BOOL CLifeApp::InitInstance()
{
m_pMainWnd = new CMainFrame();
m_pMainWnd->ShowWindow(m_nCmdShow);
m_pMainWnd->UpdateWindow();
return TRUE;
}
Listing 33.13 mainfrm.h The Main Window Class's Header File
///////////////////////////////////////////////////////////
// MAINFRM.H: Header file for the CMainFrame class, which
// represents the application's main window.
///////////////////////////////////////////////////////////
#include <afxext.h>
const SQUARESIZE = 12;
const NUMBEROFROWS = 32;
const NUMBEROFCOLS = 32;
const VEROFFSET = 34;
const HOROFFSET = 4;
const ALIVE = 1;
const DEAD = 0;
class CMainFrame : public CFrameWnd
{
// Protected data members.
protected:
CToolBar m_toolBar;
CStatusBar m_statusBar;
CBitmap* m_pBitmap;
BOOL m_world[NUMBEROFROWS][NUMBEROFCOLS];
UINT m_nbrs[NUMBEROFROWS][NUMBEROFCOLS];
UINT m_curGeneration;
UINT m_generations;
UINT m_speed;
CPtrList* m_pLive;
CPtrList* m_pDie;
CPtrList* m_pNextLive;
CPtrList* m_pNextDie;
// Constructor and destructor.
public:
CMainFrame();
~CMainFrame();
// Overrides.
protected:
virtual BOOL PreCreateWindow(CREATESTRUCT& cs);
// Message map functions.
protected:
afx_msg void OnPaint();
afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);
afx_msg void OnLButtonDown(UINT nFlags, CPoint point);
afx_msg void OnTimer(UINT nIDEvent);
afx_msg void OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags);
afx_msg void OnDestroy();
afx_msg void OnStart();
afx_msg void OnStop();
afx_msg void OnClear();
afx_msg void OnRandomCells();
afx_msg void OnGenerations();
afx_msg void OnSpeed();
afx_msg void OnAbout();
// Update command UI handlers.
afx_msg void OnUpdateStartUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateStopUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateSpeedUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateGenerationsUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateClearUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateRandomCellsUI(CCmdUI* pCmdUI);
// Protected member functions.
protected:
void ClearBitmap();
void DrawGrid();
BOOL ClickInsideGrid(CPoint point);
void DrawCell(UINT col, UINT row, BOOL alive);
void CreateLists();
void ReleaseNodes(CPtrList* pList);
void Live();
void Die();
void AddNbrs();
void SubNbrs();
void CalcLimits(int c, int r, int &xlow, int &xhigh,
int &ylow, int &yhigh);
void TransferList(CPtrList** pDestList, CPtrList** pSrcList);
DECLARE_MESSAGE_MAP()
};
Listing 33.14 mainfrm.cpp The Main Window Class's Implementation File
///////////////////////////////////////////////////////////
// MAINFRM.CPP: Implementation file for the CMainFrame
// class, which represents the application's
// main window.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "resource.h"
#include "mainfrm.h"
#include "gendlg.h"
#include "spddlg.h"
BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
ON_WM_CREATE()
ON_WM_PAINT()
ON_WM_LBUTTONDOWN()
ON_WM_TIMER()
ON_WM_DESTROY()
ON_WM_KEYDOWN()
ON_COMMAND(ID_START, OnStart)
ON_COMMAND(ID_STOP, OnStop)
ON_COMMAND(ID_CLEAR, OnClear)
ON_COMMAND(ID_RANDOMCELLS, OnRandomCells)
ON_COMMAND(ID_GENERATIONS, OnGenerations)
ON_COMMAND(ID_SPEED, OnSpeed)
ON_COMMAND(ID_ABOUT, OnAbout)
ON_UPDATE_COMMAND_UI(ID_START, OnUpdateStartUI)
ON_UPDATE_COMMAND_UI(ID_STOP, OnUpdateStopUI)
ON_UPDATE_COMMAND_UI(ID_CLEAR, OnUpdateClearUI)
ON_UPDATE_COMMAND_UI(ID_RANDOMCELLS, OnUpdateRandomCellsUI)
ON_UPDATE_COMMAND_UI(ID_GENERATIONS, OnUpdateGenerationsUI)
ON_UPDATE_COMMAND_UI(ID_SPEED, OnUpdateSpeedUI)
END_MESSAGE_MAP()
///////////////////////////////////////////////////////////
// CMainFrame: Construction and destruction.
///////////////////////////////////////////////////////////
CMainFrame::CMainFrame()
{
// Create the main window.
Create(NULL, "Conway's Life",
WS_OVERLAPPED | WS_SYSMENU | WS_CLIPCHILDREN);
// Initialize the world array.
for (UINT row=0; row<NUMBEROFROWS; ++row)
for (UINT col=0; col<NUMBEROFCOLS; ++col)
m_world[row][col] = DEAD;
// Initialize member variables.
m_generations = 100;
m_curGeneration = 0;
m_speed = 10;
// Create the starting linked lists.
m_pLive = new CPtrList;
m_pDie = new CPtrList;
m_pNextLive = new CPtrList;
m_pNextDie = new CPtrList;
}
CMainFrame::~CMainFrame()
{
// Delete the bitmap from memory.
delete m_pBitmap;
// Delete all cells from the linked lists.
ReleaseNodes(m_pLive);
ReleaseNodes(m_pDie);
ReleaseNodes(m_pNextLive);
ReleaseNodes(m_pNextDie);
// Delete the linked-list objects.
delete m_pLive;
delete m_pDie;
delete m_pNextLive;
delete m_pNextDie;
}
///////////////////////////////////////////////////////////
// Overrides.
///////////////////////////////////////////////////////////
BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
// Set size of the main window.
cs.cx = 403;
cs.cy = 470;
// Call the base class's version.
BOOL returnCode = CFrameWnd::PreCreateWindow(cs);
return returnCode;
}
///////////////////////////////////////////////////////////
// System message map functions.
///////////////////////////////////////////////////////////
int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
// Call base class's OnCreate() to be sure
// the window's default initialization is performed.
CFrameWnd::OnCreate(lpCreateStruct);
// Create and load the window's toolbar.
m_toolBar.Create(this);
m_toolBar.LoadToolBar(IDR_TOOLBAR1);
m_toolBar.SetBarStyle(m_toolBar.GetBarStyle() |
CBRS_TOOLTIPS | CBRS_FLYBY);
static UINT indicators[] =
{
ID_SEPARATOR,
ID_INDICATOR_SPEED,
ID_INDICATOR_GENERATIONS,
ID_INDICATOR_CURGENERATION
};
m_statusBar.Create(this);
m_statusBar.SetIndicators(indicators, 4);
m_statusBar.SetPaneInfo(0, m_statusBar.GetItemID(0),
SBPS_STRETCH, 0);
m_statusBar.SetPaneText(1, "Speed: 10", TRUE);
m_statusBar.SetPaneText(2, "Max Gens: 100", TRUE);
m_statusBar.SetPaneText(3, "Generation: 0", TRUE);
// Get a device context for the window.
CClientDC clientDC(this);
// Create a bitmap compatible with the window DC.
m_pBitmap = new CBitmap;
m_pBitmap->CreateCompatibleBitmap(&clientDC, 640, 480);
// Clear the contents of the bitmap.
ClearBitmap();
// Draw the world grid on the memory bitmap.
DrawGrid();
return 0;
}
void CMainFrame::OnPaint()
{
CPaintDC paintDC(this);
CDC memDC;
memDC.CreateCompatibleDC(&paintDC);
// Select the bitmap into the memory DC.
memDC.SelectObject(m_pBitmap);
// Blit the bitmap onto the screen.
paintDC.BitBlt(0, 0, 640, 480, &memDC, 0, 0, SRCCOPY);
}
void CMainFrame::OnLButtonDown(UINT nFlags, CPoint point)
{
// Don't let user plant cells while
// the simulation is running.
if (m_curGeneration != 0)
return;
// If the user clicked in the world grid...
if (ClickInsideGrid(point))
{
// Calculate the selected square's column and row.
UINT gridCol = (point.x - HOROFFSET) / SQUARESIZE;
UINT gridRow = (point.y - VEROFFSET) / SQUARESIZE;
// If there's no cell in the square...
if (m_world[gridRow][gridCol] == DEAD)
{
// Bring the cell to life and draw it.
m_world[gridRow][gridCol] = ALIVE;
DrawCell(gridCol, gridRow, TRUE);
}
}
}
void CMainFrame::OnTimer(UINT nIDEvent)
{
// Increment generation count and stop
// the timer if the last generation is done.
++m_curGeneration;
if (m_curGeneration > m_generations)
{
KillTimer(1);
m_curGeneration = 0;
return;
}
// Update the status bar with the
// current generation count.
char s[20];
wsprintf(s, "Generation: %d", m_curGeneration);
m_statusBar.SetPaneText(3, s, TRUE);
// Process one generation of cells.
Live();
Die();
AddNbrs();
SubNbrs();
TransferList(&m_pLive, &m_pNextLive);
TransferList(&m_pDie, &m_pNextDie);
}
void CMainFrame::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags)
{
// Respond to all hot keys but Stop when
// the simulation is not running.
if (m_curGeneration == 0)
{
switch(nChar)
{
case VK_F2:
OnStart();
break;
case VK_F4:
OnClear();
break;
case VK_F5:
OnRandomCells();
break;
case VK_F6:
OnGenerations();
break;
case VK_F7:
OnSpeed();
break;
case VK_F8:
OnAbout();
}
}
// Respond only to the Stop command when
// the simulation is running.
else
if (nChar == VK_F3)
OnStop();
}
void CMainFrame::OnDestroy()
{
KillTimer(1);
}
///////////////////////////////////////////////////////////
// Command message map functions.
///////////////////////////////////////////////////////////
void CMainFrame::OnStart()
{
// Create the linked lists of cells.
CreateLists();
// Change the value of the generation count first,
// so idle-time processing has time to update the
// command buttons before WM_TIMER messages come
// flooding in to the application.
m_curGeneration = 1;
// Start the simulation timer.
SetTimer(1, 2100-m_speed*200, NULL);
}
void CMainFrame::OnStop()
{
// Stop the simulation timer.
KillTimer(1);
// Reset the generation count so that the
// command buttons are reenabled properly.
m_curGeneration = 0;
}
void CMainFrame::OnClear()
{
for (UINT row=0; row<NUMBEROFROWS; ++row)
for (UINT col=0; col<NUMBEROFCOLS; ++col)
m_world[row][col] = DEAD;
ClearBitmap();
DrawGrid();
Invalidate();
}
void CMainFrame::OnRandomCells()
{
// Seed the random-number generator.
srand((unsigned)time( NULL ));
// Place 200 cells randomly.
for (UINT cell=0; cell<200; ++cell)
{
UINT col = rand() % NUMBEROFCOLS;
UINT row = rand() % NUMBEROFROWS;
m_world[row][col] = ALIVE;
DrawCell(col, row, TRUE);
}
}
void CMainFrame::OnGenerations()
{
CGenDlg dialog(this);
dialog.m_generations = m_generations;
int result = dialog.DoModal();
if (result == IDOK)
{
m_generations = dialog.m_generations;
char s[20];
wsprintf(s, "Max Gens: %d", m_generations);
m_statusBar.SetPaneText(2, s, TRUE);
}
}
void CMainFrame::OnSpeed()
{
CSpeedDlg dialog(this);
dialog.m_speed = m_speed;
int result = dialog.DoModal();
if (result == IDOK)
{
m_speed = dialog.m_speed;
char s[20];
wsprintf(s, "Speed: %d", m_speed);
m_statusBar.SetPaneText(1, s, TRUE);
}
}
void CMainFrame::OnAbout()
{
// Display the About dialog box.
CDialog dialog(MAKEINTRESOURCE(IDD_ABOUTDLG), this);
dialog.DoModal();
}
///////////////////////////////////////////////////////////
// Update UI message map functions.
///////////////////////////////////////////////////////////
void CMainFrame::OnUpdateStartUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration == 0);
}
void CMainFrame::OnUpdateStopUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration != 0);
}
void CMainFrame::OnUpdateClearUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration == 0);
}
void CMainFrame::OnUpdateRandomCellsUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration == 0);
}
void CMainFrame::OnUpdateGenerationsUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration == 0);
}
void CMainFrame::OnUpdateSpeedUI(CCmdUI* pCmdUI)
{
pCmdUI->Enable(m_curGeneration == 0);
}
///////////////////////////////////////////////////////////
// Protected member functions.
///////////////////////////////////////////////////////////
void CMainFrame::ClearBitmap()
{
// Get a client-window DC.
CClientDC dc(this);
// Create a memory DC compatible with the window DC.
CDC memDC;
memDC.CreateCompatibleDC(&dc);
// Select the bitmap into the memory DC.
memDC.SelectObject(m_pBitmap);
// Clear the bitmap to white.
CBrush brush(RGB(255,255,255));
memDC.FillRect(CRect(0, 0, 639, 479), &brush);
}
void CMainFrame::DrawGrid()
{
// Get a client-window DC.
CClientDC dc(this);
// Create a memory DC compatible with the window DC.
CDC memDC;
memDC.CreateCompatibleDC(&dc);
// Select the bitmap into the memory DC.
memDC.SelectObject(m_pBitmap);
// Draw the grid's vertical lines.
for (int x=0; x<=NUMBEROFCOLS; ++x)
{
memDC.MoveTo(SQUARESIZE*x+HOROFFSET, VEROFFSET);
memDC.LineTo(SQUARESIZE*x+HOROFFSET,
SQUARESIZE*NUMBEROFROWS+VEROFFSET + 1);
}
// Draw the grid's horizontal lines.
for (int y=0; y<=NUMBEROFROWS; ++y)
{
memDC.MoveTo(HOROFFSET, SQUARESIZE*y+VEROFFSET);
memDC.LineTo(SQUARESIZE*NUMBEROFCOLS+HOROFFSET,
SQUARESIZE*y+VEROFFSET);
}
}
BOOL CMainFrame::ClickInsideGrid(CPoint point)
{
// Calculate width and height of grid in pixels.
int gridSize = SQUARESIZE * NUMBEROFROWS;
// If the user clicked within the grid, return TRUE.
if ((point.x < gridSize + HOROFFSET) && (point.x > HOROFFSET) &&
(point.y < gridSize + VEROFFSET) && (point.y > VEROFFSET))
return TRUE;
// Otherwise, return FALSE.
return FALSE;
}
void CMainFrame::DrawCell(UINT col, UINT row, BOOL alive)
{
CBrush* pBrush;
// Create a DC for the window and a memory
// DC compatible with the window DC.
CClientDC clientDC(this);
CDC memDC;
memDC.CreateCompatibleDC(&clientDC);
// Select the world-grid bitmap into the memory DC.
memDC.SelectObject(m_pBitmap);
// Create a red brush if the cell is living;
// otherwise, create a white brush.
if (alive)
pBrush = new CBrush(RGB(255,0,0));
else
pBrush = new CBrush(RGB(255, 255, 255));
// Select the brush into both DCs.
CBrush* pOldBrush1 = memDC.SelectObject(pBrush);
CBrush* pOldBrush2 = clientDC.SelectObject(pBrush);
// Calculate the drawing column and row.
UINT drawCol = col * SQUARESIZE + HOROFFSET;
UINT drawRow = row * SQUARESIZE + VEROFFSET;
// Draw the cell in both DCs.
memDC.Rectangle(drawCol, drawRow,
drawCol + SQUARESIZE + 1, drawRow + SQUARESIZE + 1);
clientDC.Rectangle(drawCol, drawRow,
drawCol + SQUARESIZE + 1, drawRow + SQUARESIZE + 1);
// Restore DCs and delete the brush.
memDC.SelectObject(pOldBrush1);
clientDC.SelectObject(pOldBrush2);
delete pBrush;
}
void CMainFrame::CreateLists()
{
int c, r;
CPoint* pCell;
// Clear cells from all lists.
ReleaseNodes(m_pLive);
ReleaseNodes(m_pDie);
ReleaseNodes(m_pNextLive);
ReleaseNodes(m_pNextDie);
// Build the live list.
for (c=0; c<NUMBEROFCOLS; ++c)
for (r=0; r<NUMBEROFROWS; ++r)
{
m_nbrs[r][c] = 0;
if (m_world[r][c] == ALIVE)
{
pCell = new CPoint(c, r);
m_pLive->AddTail(pCell);
}
}
// Calculate cell neighbors.
AddNbrs();
for (c=0; c<NUMBEROFCOLS; ++c)
{
for (r=0; r<NUMBEROFROWS; ++r)
{
if (((m_nbrs[r][c] < 2) || (m_nbrs[r][c] > 3))
&& (m_world[r][c] == ALIVE))
{
pCell = new CPoint(c, r);
m_pNextDie->AddTail(pCell);
}
}
}
TransferList(&m_pLive, &m_pNextLive);
TransferList(&m_pDie, &m_pNextDie);
}
void CMainFrame::TransferList(CPtrList** pDestList,
CPtrList** pSrcList)
{
ReleaseNodes(*pDestList);
CPtrList* pTempList = *pDestList;
*pDestList = *pSrcList;
*pSrcList = pTempList;
}
void CMainFrame::AddNbrs()
{
int xlow, xhigh, ylow, yhigh;
int c, r;
CPoint* pCell;
// Process the entire live list.
while (!m_pLive->IsEmpty())
{
// Get and delete the head cell.
pCell = (CPoint*)m_pLive->RemoveHead();
c = pCell->x;
r = pCell->y;
delete pCell;
CalcLimits(c, r, xlow, xhigh, ylow, yhigh);
// Calculate the neighbor count for each cell
// adjacent to the cell at coordinates c,r.
// Also, build the nextLive and nextDie lists.
for (int x=xlow; x<=xhigh; ++x)
for (int y=ylow; y<=yhigh; ++y)
if ((x != c) || (y != r))
{
m_nbrs[y][x] += 1;
switch (m_nbrs[y][x])
{
case 1:
case 2: break;
case 3:
if (m_world[y][x] == DEAD)
{
pCell = new CPoint(x, y);
m_pNextLive->AddTail(pCell);
}
break;
case 4:
if (m_world[y][x] == ALIVE)
{
pCell = new CPoint(x, y);
m_pNextDie->AddTail(pCell);
}
break;
case 5:
case 6:
case 7:
case 8: break;
}
}
}
}
void CMainFrame::SubNbrs()
{
int xlow, xhigh, ylow, yhigh;
int c, r;
CPoint* pCell;
// Process the entire die list.
while (!m_pDie->IsEmpty())
{
// Get and delete the head cell.
pCell = (CPoint*)m_pDie->RemoveHead();
c = pCell->x;
r = pCell->y;
delete pCell;
CalcLimits(c, r, xlow, xhigh, ylow, yhigh);
// Calculate the neighbor count for each cell
// adjacent to the cell at coordinates c,r.
// Also, build the nextLive and nextDie lists.
for (int x=xlow; x<=xhigh; ++x)
for (int y=ylow; y<=yhigh; ++y)
if ((x != c) || (y != r))
{
m_nbrs[y][x] -= 1;
switch (m_nbrs[y][x])
{
case 0: break;
case 1:
if (m_world[y][x] == ALIVE)
{
pCell = new CPoint(x, y);
m_pNextDie->AddTail(pCell);
}
break;
case 2: break;
case 3:
if (m_world[y][x] == DEAD)
{
pCell = new CPoint(x, y);
m_pNextLive->AddTail(pCell);
}
break;
case 4:
case 5:
case 6:
case 7: break;
}
}
}
}
void CMainFrame::Live()
{
int r, c;
CPoint* pCell;
// Transfer live list to a temp list,
// leaving the live list empty.
CPtrList* pTempList = new CPtrList;
TransferList(&pTempList, &m_pLive);
// Process the entire temp list.
while(!pTempList->IsEmpty())
{
// Get and delete the head cell.
pCell = (CPoint*)pTempList->RemoveHead();
c = pCell->x;
r = pCell->y;
delete pCell;
// If a dead cell has three neighbors,
// bring the cell to life.
if ((m_world[r][c] == DEAD) &&
(m_nbrs[r][c] == 3))
{
m_world[r][c] = ALIVE;
DrawCell(c, r, TRUE);
CPoint* pCell = new CPoint(c, r);
m_pLive->AddTail(pCell);
}
}
delete pTempList;
}
void CMainFrame::Die()
{
int c, r;
CPoint* pCell;
// Transfer die list to a temp list,
// leaving the die list empty.
CPtrList* pTempList = new CPtrList;
TransferList(&pTempList, &m_pDie);
while(!pTempList->IsEmpty())
{
// Get and delete the head cell.
pCell = (CPoint*)pTempList->RemoveHead();
c = pCell->x;
r = pCell->y;
delete pCell;
// If a living cell doesn't have two or three
// neighbors, kill the poor sucker off.
if ((m_world[r][c] == ALIVE) &&
(m_nbrs[r][c] != 2) && (m_nbrs[r][c] != 3))
{
m_world[r][c] = DEAD;
DrawCell(c, r, FALSE);
CPoint* pCell = new CPoint(c, r);
m_pDie->AddTail(pCell);
}
}
delete pTempList;
}
void CMainFrame::CalcLimits(int c, int r,
int& xlow, int& xhigh, int& ylow, int& yhigh)
{
if (c == 0) xlow = 0;
else xlow = c - 1;
if (c == NUMBEROFCOLS-1) xhigh = NUMBEROFCOLS-1;
else xhigh = c + 1;
if (r == 0) ylow = 0;
else ylow = r - 1;
if (r == NUMBEROFROWS-1) yhigh = NUMBEROFROWS-1;
else yhigh = r + 1;
}
void CMainFrame::ReleaseNodes(CPtrList* pList)
{
UINT count = pList->GetCount();
for (UINT i=0; i<count; ++i)
{
CPoint* pCell = (CPoint*)pList->RemoveHead();
delete pCell;
}
}
Listing 33.15 gendlg.h The Generation Dialog Box's Header File
///////////////////////////////////////////////////////////
// GENDLG.H: Header file for the CGenDlg class.
///////////////////////////////////////////////////////////
class CGenDlg : public CDialog
{
// Constructor.
public:
CGenDlg(CWnd* pParent);
// Data transfer variables.
public:
UINT m_generations;
// Overrides.
protected:
virtual void DoDataExchange(CDataExchange* pDX);
};
Listing 33.16 gendlg.cpp The Generation Dialog Box's Implementation
File
///////////////////////////////////////////////////////////
// GENDLG.CPP: Implementation file for the CGenDlg class.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "resource.h"
#include "gendlg.h"
///////////////////////////////////////////////////////////
// CONSTRUCTOR
///////////////////////////////////////////////////////////
CGenDlg::CGenDlg(CWnd* pParent) :
CDialog(IDD_GENERATIONSDLG, pParent)
{
// Initialize data transfer variables.
m_generations = 100;
}
///////////////////////////////////////////////////////////
// Overrides.
///////////////////////////////////////////////////////////
void CGenDlg::DoDataExchange(CDataExchange* pDX)
{
// Call the base class's version.
CDialog::DoDataExchange(pDX);
// Associate the data transfer variables with
// the ID's of the controls.
DDX_Text(pDX, IDC_GENERATIONS, m_generations);
DDV_MinMaxUInt(pDX, m_generations, 1, 64000);
}
Listing 33.17 spddlg.h The Speed Dialog Box's Header File
///////////////////////////////////////////////////////////
// SPDDLG.H: Header file for the CSpeedDlg class.
///////////////////////////////////////////////////////////
class CSpeedDlg : public CDialog
{
// Constructor.
public:
CSpeedDlg(CWnd* pParent);
// Data transfer variables.
public:
UINT m_speed;
// Overrides.
protected:
virtual void DoDataExchange(CDataExchange* pDX);
};
Listing 33.18 spddlg.cpp The Speed Dialog Box's Implementation File
///////////////////////////////////////////////////////////
// SPDDLG.CPP: Implementation file for the CSpeedDlg class.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "resource.h"
#include "spddlg.h"
///////////////////////////////////////////////////////////
// CONSTRUCTOR
///////////////////////////////////////////////////////////
CSpeedDlg::CSpeedDlg(CWnd* pParent) :
CDialog(IDD_SPEEDDLG, pParent)
{
// Initialize data transfer variables.
m_speed = 1;
}
///////////////////////////////////////////////////////////
// Overrides.
///////////////////////////////////////////////////////////
void CSpeedDlg::DoDataExchange(CDataExchange* pDX)
{
// Call the base class's version.
CDialog::DoDataExchange(pDX);
// Associate the data transfer variables with
// the ID's of the controls.
DDX_Text(pDX, IDC_SPEED, m_speed);
DDV_MinMaxUInt(pDX, m_speed, 1, 10);
}
The Application and Dialog Box Classes
Most of the action in the Life program takes place in the CMainFrame
class. However, you should take some time now to look over all of the listings
that make up the program so that you get a good overview of all of the
classes used. These last few chapters are designed to, not only provide
you with new programming techniques, but also to reinforce and review the
basic MFC programming techniques that you've developed over the course
of reading this book.
Listings 33.11 and 33.12, for example, are the header and implementation
files for the program's application class, CLifeApp.
You should now fully understand why the class overrides the base class's
InitInstance() virtual member function,
as well as why the program must create its application object as a global
object. If you're still a little fuzzy on the ins and outs of writing an
application class, please refer back to Chapter 4, "Constructing an
MFC Program from Scratch."
Skipping over the main window class, CMainFrame,
for the time being, I will mention that the Life program also features
two dialog box classes, one for the Generations dialog box and one for
the Speed dialog box. These dialog box classes CGenDlg
and CSpeedDlg are shown in listings
33.15 through 33.18. Notice that the classes are very similar, both providing
data members for data that must be copied from the dialog box, as well
as overriding the base class's DoDataExchange()
virtual member function to transfer data to and from the dialog box. If
none of this stuff rings a bell, march right over to Chapter 7, "Programming
Dialog Boxes," to get the inside story.
The Main Window Class
As I mentioned previously, the main window class, CMainFrame,
is where the Life program gets its life. Start by examining the class's
header file, as shown in Listing 33.13. At the top of the header file,
you see some constants declared, as shown in Listing 33.19.
Listing 33.19 lst33_19.cpp The Life Application's Constants
const SQUARESIZE = 12;
const NUMBEROFROWS = 32;
const NUMBEROFCOLS = 32;
const VEROFFSET = 34;
const HOROFFSET = 4;
const ALIVE = 1;
const DEAD = 0;
Using these constants in the program, not only makes the program easier
to modify, but also makes the program much easier to read.
Inside the class's declaration, the program declares a number of data members.
The first two represent the program's toolbar and status bar objects, as
shown here:
CToolBar m_toolBar;
CStatusBar m_statusBar;
Next, the class declares a pointer to a CBitmap
object, like this:
CBitmap* m_pBitmap;
The bitmap whose address will be stored in this pointer holds the main
window's graphical data that gets displayed each time the application receives
a WM_PAINT message.
After the bitmap pointer, the class declares two arrays for storing information
about the cells in the simulation, like this:
BOOL m_world[NUMBEROFROWS][NUMBEROFCOLS];
UINT m_nbrs[NUMBEROFROWS][NUMBEROFCOLS];
The m_world[][] array holds the status
living or dead of the cells in the simulation's on-screen grid. A value
of ALIVE in an array element means
that that cell is living, whereas a value of DEAD
means, of course, that the cell is not living. The m_nbrs[][]
array holds the neighbor counts for each cell in the grid. For example,
if cell 0,0 in the m_world[][] array
has three living, adjacent cells, the value in element 0,0 of the m_nbrs[][]
array will be 3.
The class then declares data members to hold status information for the
simulation, like this:
UINT m_curGeneration;
UINT m_generations;
UINT m_speed;
The m_curGeneration variable holds
the number of the current generation of cells on the screen, whereas m_generations
holds the setting for the maximum generations, and m_speed
holds the currently selected simulation speed.
Finally, the class declares pointers to CPtrList
objects, which are linked lists of pointers. Each pointer in one of these
lists will hold the address of the data for a single cell. The m_pLive
and m_pDie lists hold the cells that
will live and die in a given generation. The m_pNextLive
and m_pNextDie lists are used as
temporary storage for cells that are eventually transferred to the live
and die lists. You'll see how this works when you get further into the
program's code.
The CMainFrame class's header file
also lists the class's member functions. The first of these is the overridden
PreCreateWindow() function:
virtual BOOL PreCreateWindow(CREATESTRUCT&
cs);
As you should already know, in PreCreateWindow(),
the program can modify the application's main window before it's displayed.
Next are the message-map functions, which respond to, not only Windows
messages, but also messages generated by the toolbar's buttons and by MFC's
command-UI system. The message map functions for system messages are listed
first, as shown in Listing 33.20.
Listing 33.20 lst33_20.cpp Message Map Functions for System Messages
afx_msg void OnPaint();
afx_msg int OnCreate(LPCREATESTRUCT lpCreateStruct);
afx_msg void OnLButtonDown(UINT nFlags, CPoint point);
afx_msg void OnTimer(UINT nIDEvent);
afx_msg void OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags);
afx_msg void OnDestroy();
After the system message map functions come the response functions for
the toolbar's buttons (see Listing 33.21).
Listing 33.21 lst33_21.cpp Response Functions for the Toolbar Buttons
afx_msg void OnStart();
afx_msg void OnStop();
afx_msg void OnClear();
afx_msg void OnRandomCells();
afx_msg void OnGenerations();
afx_msg void OnSpeed();
afx_msg void OnAbout();
The last message map functions listed (see Listing 33.22) handle the command-UI
messages.
Listing 33.22 lst33_22.cpp The Command-UI Response Functions
afx_msg void OnUpdateStartUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateStopUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateSpeedUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateGenerationsUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateClearUI(CCmdUI* pCmdUI);
afx_msg void OnUpdateRandomCellsUI(CCmdUI* pCmdUI);
The command-UI functions control how the toolbar buttons look and act.
If you don't remember about command-UI functions, turn back to Chapter
4, "Constructing an MFC Program from Scratch," and Chapter 6,
"Using Menus."
See ?Responding to Windows Messages,? (ch.
4)
See ?Defining the Message Map,? (ch.
6)
Finally, the CMainFrame class has
many protected member functions that
control the simulation (see Listing 33.23).
Listing 33.23 lst33_23.cpp The Class's Protected Member Functions
void ClearBitmap();
void DrawGrid();
BOOL ClickInsideGrid(CPoint point);
void DrawCell(UINT col, UINT row, BOOL alive);
void CreateLists();
void ReleaseNodes(CPtrList* pList);
void Live();
void Die();
void AddNbrs();
void SubNbrs();
void CalcLimits(int c, int r, int &xlow, int &xhigh,
int &ylow, int &yhigh);
void TransferList(CPtrList** pDestList, CPtrList** pSrcList);
You will see what all these functions do as you dig deeper into the program
which you'll do in the very next section.
Creating the Window and Initializing Variables
Now you're ready to see what makes this program tick. As you know, when
the application object is created, the program's main window is also created,
in the CLifeApp class's InitInstance()
function. The main window's constructor first creates the window:
Create(NULL, "Conway's Life",
WS_OVERLAPPED | WS_SYSMENU | WS_CLIPCHILDREN);
The constructor also initializes the m_world[][]
array to all dead cells:
for (UINT row=0; row<NUMBEROFROWS; ++row)
for (UINT col=0; col<NUMBEROFCOLS; ++col)
m_world[row][col] = DEAD;
It then initializes the simulation's status variables, like this:
m_generations = 100;
m_curGeneration = 0;
m_speed = 10;
Finally, the constructor creates the program's linked lists, as shown in
Listing 33.24.
Listing 33.24 lst33_24.cpp Creating the Linked Lists
m_pLive = new CPtrList;
m_pDie = new CPtrList;
m_pNextLive = new CPtrList;
m_pNextDie = new CPtrList;
The Toolbar and Status Bar
In this program, the toolbar is created from the old CToolBar
class rather than from the CToolBarCtrl
class, which can be used only with Windows 95 or Windows NT. The CToolBar
class isn't as fancy as CToolBarCtrl,
but it can definitely get the job done. The same thing can be said for
the CStatusBar control which is the
basis for the Life application's status bar and its relationship with the
Windows 95 and NT CStatusBarCtrl
class. For more information on the CToolBarCtrl
and CStatusBarCtrl classes, see Chapter
11, "Toolbars and Status Bars."
The OnCreate() function, which responds
to Windows' WM_CREATE message, is
where the program creates its toolbar and status bar. First OnCreate()
calls the base class's OnCreate()
function to ensure that the base class gets to do its thing:
CFrameWnd::OnCreate(lpCreateStruct);
Then the function creates the toolbar object, like this:
m_toolBar.Create(this);
The constructor's single argument is a pointer to the parent window.
Next the program loads the toolbar from the resource file.
m_toolBar.LoadToolBar(IDR_TOOLBAR1);
The LoadToolBar() member function
takes as its single argument the toolbar resource ID. Obviously, you must
create the toolbar resource ahead of time, using Developer Studio's toolbar
editor. (You can also find the resources at this book's Web site, in the
Chap33\Life folder.) Creating the resource is a simple matter of drawing
the icons for the buttons and giving the buttons their IDs. Consult your
Visual C++ online documentation for more information on constructing toolbars
with the toolbar editor.
The last thing the OnCreate() function
does with the toolbar is set its style to display ToolTips, like this:
??? Author, I made "tool tips" "ToolTips," per Que's convention; OK?-- m_toolBar.SetBarStyle(m_toolBar.GetBarStyle() |
CBRS_TOOLTIPS | CBRS_FLYBY);
The nested call to the GetBarStyle()
member function retrieves the toolbar's current style. The program ORs
this style with the style constants CBRS_TOOLTIPS,
which allows the toolbar to display ToolTips, and CBRS_FLYBY;
this, in turn, enables the status bar to display message text for the ToolTip
at the same time that the ToolTip is displayed. Where do the ToolTips and
message text come from? When you're constructing your toolbar with the
toolbar editor, double-click an icon in the toolbar to display the button's
Toolbar Button Properties property sheet. In the prompt line, type the
button's message text and ToolTip, separated by the newline control character
(\n).
Creating the status bar is just a little bit trickier, except for the fact
that you don't have to create a resource for the status bar. In the Life
application, the program first creates an array containing IDs with which
panels in the status bar are associated, as shown in Listing 33.25.
Listing 33.25 lst33_25.cpp Defining the Structure for the Status Bar's
Panels
static UINT indicators[] =
{
ID_SEPARATOR,
ID_INDICATOR_SPEED,
ID_INDICATOR_GENERATIONS,
ID_INDICATOR_CURGENERATION
};
Each of the IDs in the indicators[]
array is the ID of a string resource in a string table. You have to create
this string resource in your resource file, matching up the strings that
you want displayed in the status bar with their IDs. When your program
is running, MFC takes care of displaying the correct strings in the status
bar's panels. The ID_SEPARATOR ID
in the array saves a space for the panel that will display the toolbar's
ToolTip messages.
After defining the array of IDs, the program calls the status bar's SetIndicators()
member function to tell MFC what panels the program needs, like this:
m_statusBar.SetIndicators(indicators, 4);
This function's two arguments are the address of the array containing the
string IDs and the number of IDs in the array.
Next, the program sets the first pane's style, like this:
m_statusBar.SetPaneInfo(0, m_statusBar.GetItemID(0),
SBPS_STRETCH, 0);
The SetPaneInfo() function's four
arguments are the pane's zero-based index (that is, 0 is the index of the
first pane), the pane's new ID, the pane's new style, and the pane's new
width. In this case, the program wants only to set the style, so the nested
call to GetItemID() returns the pane's
current ID. The SBPS_STRETCH style
sets the first pane so that it stretches to fill all remaining space in
the status bar. Because of this style, the pane's new width, which is SetPaneInfo()'s
last argument, can be set to 0. Other styles you can use are SBPS_NOBORDERS,
SBPS_POPOUT, SBPS_DISABLED,
and SBPS_NORMAL.
Finally, three calls to the status bar's SetPaneText()
function set the strings in the panes exactly as the program wants them:
m_statusBar.SetPaneText(1, "Speed: 10", TRUE);
m_statusBar.SetPaneText(2, "Max Gens: 100", TRUE);
m_statusBar.SetPaneText(3, "Generation: 0", TRUE);
The SetPaneText() function's three
arguments are the pane's index, the new text, and a Boolean value indicating
whether the pane should be redrawn immediately with the new text. Why set
the pane's text when the program's resource file already included strings
for the status bar? In this program's case, the strings in the string-table
resource are used only to reserve the right amount of space in each pane.
The strings themselves will change continuously as the user uses the program,
changing the options and running the simulation.
The Window's Bitmap
Because of the nature of the user's interaction with the program, the Life
application uses an in-memory bitmap to store the current image being displayed
in the window. Life's main window (CMainFrame)
uses its OnPaint() function to transfer
a bitmap from memory to the screen. Other than that bitmap transfer, OnPaint()
does no other window painting.
Obviously, the bitmap that OnPaint()
displays must be modified somewhere in the program. These modifications
occur whenever the user places a new cell on the grid. Later in this section,
you'll see what happens in the program when the user adds a cell to the
world grid. For now, this discussion concentrates on the OnCreate()
function, which creates the in-memory bitmap at the start of the program
run.
In the previous section, you saw how OnCreate()
gives the window its toolbar and status bar. The last few lines take care
of the bitmap. First the program creates a device context (DC) for the
window's client area:
CClientDC clientDC(this);
Then the program creates a new bitmap object and makes the bitmap compatible
with the window's client DC:
m_pBitmap = new CBitmap;
m_pBitmap->CreateCompatibleBitmap(&clientDC, 640, 480);
The CreateCompatibleBitmap() function
requires three arguments: the DC with which the bitmap should be compatible
and the width and height of the bitmap.
To draw the starting image on the bitmap, OnCreate()
calls the ClearBitmap() and DrawGrid()
member functions. The ClearBitmap()
function clears the bitmap to a white rectangle. To do this, the program
creates a DC for the window's client area, and that creates a memory DC
that's compatible with the window, like this:
CClientDC dc(this);
CDC memDC;
memDC.CreateCompatibleDC(&dc);
Because the bitmap is compatible with the window DC and the memory DC is
compatible with the window DC, the bitmap can be selected into the memory
DC, like this:
memDC.SelectObject(m_pBitmap);
By selecting the bitmap into the DC, the program can draw on the bitmap
(just as if the bitmap were any other type of display device), which it
does by creating a white brush and using the brush in a call to the FillRect()
function. The FillRect() function
then fills the entire bitmap with white:
CBrush brush(RGB(255,255,255));
memDC.FillRect(CRect(0, 0, 639, 479), &brush);
As you might have guessed, the DrawGrid()
function paints the gridlines on the bitmap. In that function, the program
creates a memory DC and selects the bitmap into it, just as was described
for ClearBitmap(). With the DC in
hand, the program can draw the gridlines on the bitmap in memory. The first
for loop draws the grid's vertical
lines, as shown in Listing 33.26.
Listing 33.26 lst33_26.cpp Drawing the Vertical Gridlines
for (int x=0; x<=NUMBEROFCOLS; ++x)
{
memDC.MoveTo(SQUARESIZE*x+HOROFFSET, VEROFFSET);
memDC.LineTo(SQUARESIZE*x+HOROFFSET,
SQUARESIZE*NUMBEROFROWS+VEROFFSET + 1);
}
In a similar manner, DrawGrid() also
draws the horizontal gridlines, as seen in Listing 33.27.
Listing 33.27 lst33_27.cpp Drawing the Horizontal Gridlines
for (int y=0; y<=NUMBEROFROWS; ++y)
{
memDC.MoveTo(HOROFFSET, SQUARESIZE*y+VEROFFSET);
memDC.LineTo(SQUARESIZE*NUMBEROFCOLS+HOROFFSET,
SQUARESIZE*y+VEROFFSET);
}
As I said previously, the main window class's OnPaint()
function ordinarily takes care of every case of window repainting. In Life,
however, trying to update the screen in OnPaint()
using the raw data stored in the m_world[][]
array makes the program look clunky. This is because it takes a couple
of seconds to read through the array and to paint each cell found there
onto the on-screen grid. Painting a bitmap in the window is much faster.
So when the user clicks the mouse inside the grid, the OnLButtonDown()
function takes care of the drawing tasks in an unusual way, painting the
selected cell both on the screen and on the in-memory bitmap. By the program's
keeping the bitmap up-to-date, when the program needs to update a portion
of its window, it can just copy the bitmap rather than updating the window
by reading through the m_world[][]
array.
If you look at OnLButtonDown(), you'll
see that it first checks the value of m_curGeneration,
like this:
if (m_curGeneration != 0)
return;
The variable m_curGeneration holds
the number of the generation of cells displayed on the screen. This value
is nonzero only when the simulation is actually running (after the user
selects the Go command). Because the program doesn't let the user add cells
while the simulation is going, the preceding lines cause an immediate return
from OnLButtonDown() when m_curGeneration
is not 0.
If the simulation is not active, the program must check whether the user
actually clicked inside the grid rather than somewhere else in the window.
It does this by calling the ClickInsideGrid()
function, which returns TRUE if the
click was inside the grid:
if (ClickInsideGrid(point))
If the click is valid, the program calculates the column and row of the
cell that the user selected:
UINT gridCol = (point.x - HOROFFSET) / SQUARESIZE;
UINT gridRow = (point.y - VEROFFSET) / SQUARESIZE;
Then the program checks whether the clicked cell is dead:
if (m_world[gridRow][gridCol] == DEAD)
The program checks the cell's status because there's no point in bringing
a living cell to life. If the cell is dead, the program brings it to life
by adding it to the m_world[][] array
and drawing it on the screen and the bitmap:
m_world[gridRow][gridCol] = ALIVE;
DrawCell(gridCol, gridRow, TRUE);
The DrawGrid() function must draw
the cell on the screen and on the in-memory bitmap, so its first task is
to create both a window and memory DC, like this:
CClientDC clientDC(this);
CDC memDC;
memDC.CreateCompatibleDC(&clientDC);
Next, DrawGrid() selects the bitmap
into the memory DC so the program can draw on the bitmap:
memDC.SelectObject(m_pBitmap);
Then the function must determine whether it needs to create a white brush
(to erase dead cells) or a red brush (to draw living cells). It does this
by checking the alive flag, which
is passed as the function's last argument. If alive
is TRUE, the function must draw a
living cell; otherwise, it must erase the cell. A simple if
statement takes care of either eventuality, as shown in Listing 33.28.
Listing 33.28 lst33_28.cpp Creating the Correct Brush for the Cell
if (alive)
pBrush = new CBrush(RGB(255,0,0));
else
pBrush = new CBrush(RGB(255, 255, 255));
As you know, to use the brush, it must first be selected into the DC. In
this case, two DCs the window DC and the memory DC need the brush, so the
program selects the brush into both:
CBrush* pOldBrush1 = memDC.SelectObject(pBrush);
CBrush* pOldBrush2 = clientDC.SelectObject(pBrush);
Now that everything's ready to draw on the DCs, the program calculates
the pixel coordinates at which to draw the cell:
UINT drawCol = col * SQUARESIZE + HOROFFSET;
UINT drawRow = row * SQUARESIZE + VEROFFSET;
A call to each DC's Rectangle() member
function draws the new cell both in the window and on the bitmap, as you
can see in Listing 33.29.
Listing 33.29 lst33_29.cpp Drawing the New Cell
memDC.Rectangle(drawCol, drawRow,
drawCol + SQUARESIZE + 1, drawRow + SQUARESIZE + 1);
clientDC.Rectangle(drawCol, drawRow,
drawCol + SQUARESIZE + 1, drawRow + SQUARESIZE + 1);
Finally, the program selects the old brushes back into the DCs, which frees
up the created brush for deletion:
memDC.SelectObject(pOldBrush1);
clientDC.SelectObject(pOldBrush2);
delete pBrush;
The Simulation's Main Loop
After the user has placed cells in the grid, he or she can select the Start
command to put the simulation into action. When the user does this, the
OnStart() member function gets the
program's motor humming. It accomplishes this by creating the starting
cell lists and setting a Windows timer, like this:
CreateLists();
m_curGeneration = 1;
SetTimer(1, 2100-m_speed*200, NULL);
As you can see, the timer's setting is based upon the current value of
the m_speed variable. But no matter
what the selected speed, when the timer starts generating WM_TIMER
messages for the window, the OnTimer()
function acts as the simulation's main loop, performing the same set of
tasks again and again until the simulation ends.
Before starting in on OnTimer(),
take a look at CreateLists(). This
function is responsible for initializing the lists pointed to by m_pLive
and m_pDie the two linked lists that
the simulation needs to get started as well as initializing the starting
neighbor counts. The function first calls ReleaseNodes()
for each linked list, as shown in Listing 33.30.
Listing 33.30 lst33_30.cpp Calling ReleaseNodes() for Each List
ReleaseNodes(m_pLive);
ReleaseNodes(m_pDie);
ReleaseNodes(m_pNextLive);
ReleaseNodes(m_pNextDie);
ReleaseNodes() simply empties the
given list.
When the program is first started, the lists are empty. But in subsequent
calls to OnTimer(), your linked lists
probably won't be empty because it is rare for every cell on the screen
to be dead after the generations run out.
After clearing the lists, CreateLists()
scans the newly created world array, creating a new node for each living
cell in the array, as shown in Listing 30.31.
Listing 30.31 lst30_31.cpp Initializing the List for the Living Cells
for (c=0; c<NUMBEROFCOLS; ++c)
for (r=0; r<NUMBEROFROWS; ++r)
{
m_nbrs[r][c] = 0;
if (m_world[r][c] == ALIVE)
{
pCell = new CPoint(c, r);
m_pLive->AddTail(pCell);
}
}
As CreateLists() scans the world
array, it also takes advantage of the loop to initialize all of the neighbor
counts in the m_nbrs[][] array to
0. Each cell in the Life program is represented by a CPoint
object that holds the cell's coordinates in the grid. To add a cell to
the linked list, the program first creates a CPoint
object for the cell. Calling the list's AddTail()
member function then adds the new cell to the end of the list.
After creating the linked list pointed to by m_pLive,
the CreateLists() function calls
the AddNbrs() function, which updates
the neighbor counts and creates the m_pNextLive
and m_pNextDie list for cells that
might (or might not) live and die in the next generation.
As you can see, AddNbrs() scans the
m_pLive list, which contains all
of the cells that have just come to life. The while
loop iterates until this list has been emptied:
while (!m_pLive->IsEmpty())
The CPtrList member function IsEmpty()
returns TRUE when the list has no
nodes.
Inside the while loop, the program
first gets the cell's coordinates by calling the list's RemoveHead()
member function, saving the coordinates found in the returned CPoint
object, and then deleting the CPoint
object, as shown in Listing 30.32.
Listing 33.32 lst33_32.cpp Getting the Next Node in the List
pCell = (CPoint*)m_pLive->RemoveHead();
c = pCell->x;
r = pCell->y;
delete pCell;
Keep in mind that RemoveHead() doesn't
just return the next node; it also removes the node from the head of the
list. In other words, if a list has x
nodes, after calling RemoveHead()
x times, the list is empty.
After getting the next cell's coordinates, the program calls CalcLimits()
to determine the minimum and maximum columns and rows that might contain
neighbor cells. This calculation is important, because while most cells
in the grid have eight adjacent cells, not all do. Any cell on any edge
of the grid has less than eight adjacent cells.
After the program calculates the coordinates, nested for
loops in AddNbrs() increment the
neighbor count for every adjacent cell, as shown in Listing 33.33.
Listing 33.33 lst33_33.cpp Incrementing a Cell's Neighbor Count
for (int x=xlow; x<=xhigh; ++x)
for (int y=ylow; y<=yhigh; ++y)
if ((x != c) || (y != r))
{
m_nbrs[y][x] += 1;
After incrementing a cell's neighbor count, the switch
statement checks the count, adding new nodes to the m_pNextLive
or m_pNextDie list as appropriate
(see Listing 30.34).
Listing 33.34 lst33_34.cpp Adding to the "Next to Live" and
"Next to Die" Lists
switch (m_nbrs[y][x])
{
case 1:
case 2: break;
case 3:
if (m_world[y][x] == DEAD)
{
pCell = new CPoint(x, y);
m_pNextLive->AddTail(pCell);
}
break;
case 4:
if (m_world[y][x] == ALIVE)
{
pCell = new CPoint(x, y);
m_pNextDie->AddTail(pCell);
}
break;
case 5:
case 6:
case 7:
case 8: break;
}
Keep in mind that the nodes on the m_pNextLive
and m_pNextDie lists are only "maybes."
That is, by adding nodes to these two lists, you are saying, "When
I finish counting all neighbors, I'll check these cells again to see whether
they'll actually live or die." Not every cell on the m_pNextLive
list will come to life, and not every cell on the m_pNextDie
list will die. Some cells might even appear in both lists at the same time.
Using these temporary lists, you can keep track of cells that might change
without changing the grid, which, as you learned, could really mess up
the simulation.
Getting back to CreateLists(): After
the call to AddNbrs(), the function
must scan the neighbor counts, looking for cells with less than two neighbors.
It'll add these cells to the m_pNextDie
list that AddNbrs() started, as shown
in Listing 30.35.
Listing 33.35 lst33_35.cpp Adding More Cells to the "Next to Die"
List
for (c=0; c<NUMBEROFCOLS; ++c)
{
for (r=0; r<NUMBEROFROWS; ++r)
{
if (((m_nbrs[r][c] < 2) || (m_nbrs[r][c] > 3))
&& (m_world[r][c] == ALIVE))
{
pCell = new CPoint(c, r);
m_pNextDie->AddTail(pCell);
}
}
}
Unfortunately, AddNbrs() finds only
cells that are being crowded to death (have four or more neighbors), not
those that are about to die of loneliness, which is why you must look for
lonely cells in CreateLists(). After
building the m_pNextLive and m_pNextDie
lists, CreateLists() finally transfers
them to the m_pLive and m_pDie
lists, where OnTimer() expects to
find them.
When CreateLists() has finished initializing the starting lists, the program
sets the timer going, which sends program execution to OnTimer()
each time a WM_TIMER event arrives.
Each call to OnTimer() processes
one generation of cells. Because OnTimer()
gets called again and again, you can think of the code in this function
as the simulation's main program loop.
Execution of the code in this "loop" is controlled by the m_curGeneration
data member. That is, when m_curGeneration
reaches the maximum number of generations that the player set, the program
kills the timer, resets m_curGeneration,
and returns from OnTimer(), as shown
in Listing 30.36.
Listing 33.36 lst33_36.cpp Stopping the Simulation after the Maximum
Number of Generations Have Been Processed
++m_curGeneration;
if (m_curGeneration > m_generations)
{
KillTimer(1);
m_curGeneration = 0;
return;
}
After checking that the simulation hasn't reached the end, OnTimer()
displays the current generation number in the status bar, like this:
char s[20];
wsprintf(s, "Generation: %d", m_curGeneration);
m_statusBar.SetPaneText(3, s, TRUE);
At last you get to the meat of the simulation. After updating the generation
count, OnTimer() calls the various
functions that process one generation of cells, as shown in Listing 30.37.
Listing 33.37 lst33_37.cpp Processing One Generation of Cells
Live();
Die();
AddNbrs();
SubNbrs();
TransferList(&m_pLive, &m_pNextLive);
TransferList(&m_pDie, &m_pNextDie);
First OnTimer() calls the Live()
function, which checks all of the nodes on the m_pLive
list, bringing to life only the nodes that meet the requirements for life.
Live() first creates a temporary
list and transfers the m_pLive list
to it:
CPtrList* pTempList = new CPtrList;
TransferList(&pTempList, &m_pLive);
This leaves the m_pLive list empty,
ready to receive any cells now in the temporary list that pass the requirements
for life. The program finds these cells by processing the temporary list
one cell at a time, in a while loop:
while(!pTempList->IsEmpty())
Inside the loop, the program first retrieves the next cell from the head
of the list:
pCell = (CPoint*)pTempList->RemoveHead();
The program then saves the cell's coordinates and deletes the cell:
c = pCell->x;
r = pCell->y;
delete pCell;
The requirements for life are that the cell in the grid is not yet alive
and that it has exactly three neighbors. The program checks these conditions
for the current cell in an if statement:
if ((m_world[r][c] == DEAD) &&
(m_nbrs[r][c] == 3))
If the cell meets these requirements, the program marks the cell as alive
in the grid, draws the cell, and adds the cell to the m_pLive
list, as shown in Listing 30.38.
Listing 30.38 lst30_38.cpp Bringing a Cell to Life
m_world[r][c] = ALIVE;
DrawCell(c, r, TRUE);
CPoint* pCell = new CPoint(c, r);
m_pLive->AddTail(pCell);
When the while loop finishes, the
m_pLive list contains all of the
cells that met the requirements for life, whereas the temporary list is
now empty. The last thing that Live()
must do is delete the temporary list, like this:
delete pTempList;
After calling Live() and handling
the m_pLive list, OnTimer()
calls Die(), which is Live()'s
counterpart. The Die() function works
almost exactly like Live(), except
that it processes the m_pDie list
and must check those cells against the requirements for death. As you can
see in Listing 30.39, which is the main loop in the Die()
function, the requirements for death are that the cell be currently alive
and have less than two or more than three neighbors:
Listing 33.39 lst33_39.cpp Checking Cells for Death
if ((m_world[r][c] == ALIVE) &&
(m_nbrs[r][c] != 2) && (m_nbrs[r][c] != 3))
{
m_world[r][c] = DEAD;
DrawCell(c, r, FALSE);
CPoint* pCell = new CPoint(c, r);
m_pDie->AddTail(pCell);
}
Getting back to OnTimer(), now that
all the cells on the "maybe" lists have been processed, it's
time to update the neighbor counts for all cells adjacent to any cells
that were just created or killed, all of which are now in the m_pLive
or m_pDie list. First OnTimer()
handles the m_pLive list by calling
AddNbrs(). (You looked at this function
already.) Then OnTimer() calls SubNbrs(),
which scans the m_pDie list, decrementing
the neighbor counts for any cells adjacent to a cell that just died.
SubNbrs() works similarly to its
counterpart, AddNbrs(), except that
it processes the m_pDie list, adding
to the m_pNextLive list all cells
that have three neighbors (even though the cells might not keep all three
neighbors) and adding to the m_pNextDie
list all cells with less than two neighbors (even though the cell's final
neighbor count might not qualify it to die). Remember, these are "maybe"
lists. After the neighbor counts are fully updated, OnTimer()
transfers the m_pNextLive and m_pNextDie
lists to the m_pLive and m_pDie
lists, respectively.
Five functions not yet discussed OnClear(),
OnRandomCells(), OnGenerations(),
OnSpeed(), and OnStop()
handle the remaining simulation commands. OnClear()
responds to the Clear command by first removing all living cells from the
world grid:
for (UINT row=0; row<NUMBEROFROWS; ++row)
for (UINT col=0; col<NUMBEROFCOLS; ++col)
m_world[row][col] = DEAD;
Clear() then calls ClearBitmap()
to erase the in-memory bitmap, calls DrawGrid()
to redraw the blank grid, and calls Invalidate()
to force the window to redraw its client area with the newly cleared grid:
ClearBitmap();
DrawGrid();
Invalidate();
OnRandomCells(), which responds to
the Random command, starts off by seeding the random-number generator,
like this:
srand((unsigned)time( NULL ));
The random-number generator must be seeded so that it always begins with
a different value. If you didn't seed the generator, you get the exact
same sequence of "random" numbers every time, which, of course,
would make the random placement of cells predictable.
After seeding the random-number generator, OnRandomCells()
starts a for loop that'll place 200
cells in the grid:
for (UINT cell=0; cell<200; ++cell)
Inside the loop, the program first calculates a random column and row in
the grid:
UINT col = rand() % NUMBEROFCOLS;
UINT row = rand() % NUMBEROFROWS;
The modulo operator, which returns the remainder of a division, is a handy
way to force the random number into a range from zero to the value of the
divisor.
After getting the new cells coordinates, the program brings the cell to
life by marking it as alive in the world-grid array and drawing the cell
on the screen and on the in-memory bitmap:
m_world[row][col] = ALIVE;
DrawCell(col, row, TRUE);
The OnGenerations() function is responsible
for retrieving a new maximum-generations setting from the user. It does
this by first displaying the Generations dialog box, transferring the current
setting of m_generations into the
box:
CGenDlg dialog(this);
dialog.m_generations = m_generations;
int result = dialog.DoModal();
When the user dismisses the dialog box, OnGenerations()
checks whether the user clicked the OK button. If so, the program extracts
the new value for m_generations from
the dialog box, creates a display string, and displays the string in the
application's status bar, as shown in Listing 33.40.
Listing 33.40 lst33_40.cpp Setting the New Maximum Generations Value
if (result == IDOK)
{
m_generations = dialog.m_generations;
char s[20];
wsprintf(s, "Max Gens: %d", m_generations);
m_statusBar.SetPaneText(2, s, TRUE);
}
The OnSpeed() function works in almost
exactly the same way as OnGenerations(),
except that it retrieves from the user a new value for the simulation's
speed setting. Finally, OnStop()
halts the simulation by turning off the timer and setting m_curGeneration
back to 0, like this:
KillTimer(1);
m_curGeneration = 0;
And there you go. Not only have you learned how to use linked lists, but
you also have a fascinating new program to fiddle with. Conway's Game of
Life is surprisingly hypnotic. After you get started, you might find yourself
hooked!