?? notes.html
字號(hào):
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html>
<head>
<title>Programming Info</title>
</head>
<body BGCOLOR="#FFFFE0" TEXT="#000000">
<DIV ALIGN="center"><H2>Notes for Programmers</H2></DIV>
<P>If you are a programmer and are interested in the underlying processing algorithm used in this application, here are few insights. No doubt it could be improved upon and I would be grateful for any related feedback.</P>
<P>As you may imagine, a large grid could contain hundreds, if not thousands, of cells living and dying every generation. The computer must work furiously, calculating the number of neighbors for each cell in the grid, then creating cells, killing them, or allowing them to survive based on these counts. Keep in mind that counting the neighbors for a single cell requires checking each adjacent cell - as many as eight.</P>
The first approach that comes to most people's mind is to simulate the world grid with a 2D array representing each cell's col, row coordinates - with each array element containing either a 0 (dead) or 1 (alive). We should call this the "world" array. They would then iterate the array, applying Conway's rules for each element, updating that element for the next generation. This is wrong for two reasons. Look at a very simple example:<BR>
<IMG SRC="cells1.gif" WIDTH="250" HEIGHT="150" BORDER="0" ALT="">
<P>First, if you start at the top and process the grid by creating and killing cells as you go, you get incorrect results. Notice, when you get to cell (1,1) you'll kill it because it has only one neighbor. Then, when you get to empty cell (1,2), even though it should have come to life, having three neighbors originally, 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!</P>
<P>In short, in each generation, you must determine which cells COULD live or die, without changing the grid. Then when you finish, you must simultaneously create and kill the appropriate cells based on Conway's rules. 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? </P>
<P>To help matters out let's add a second 2D array - the neighbor(col, row) array. Every cell on the grid is a potential neighbor so the array is is sized according to how many cols and rows are actually in the world grid. Every alive cell has up to 8 neighbor cells (cells on on the grid's borders have less). The neighbor array contains the running count of adjacent alive cells for each of those neighbors. In the illustration above, cell 1,1 is a neighbor of alive cell 2,1 so it's coordinates would define an element in the neighbor array neighbor(1,1). Neighbor(0,0) would equal zero, neighbor(1,1) would = 1 (cell 2,1 is it's only alive adjacent cell). Similarly, neighbor(1,2) would contain the number 3, etc. From then on, instead of re-calculating 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 rather than the entire grid. </P>
<P>Even though the original world array records the status of each and every cell, you add two lists of cells: one for cells about to be created, and another for cells about to die. These are the only cells that affect the map; so why check the entire grid every generation?</P>
Let's see how to put all this together:<BR>
First we define the objects which we need to simulate Life.<BR>
We define a Cell object as nothing more than two numbers - a col coordinate and a row coordinate.
We define two 2D arrays:<BR>
<OL>
<LI>The world(col,row) array - this maps all the cells to either being alive (1) or dead (0).</LI>
<LI>The neighbor(col,row) array - described above.</LI>
</OL>
<P>We also define four Collections (or lists) of Cell objects (remember - a Cell object is nothing more than an row and col coordinate).<BR>
<OL>
<LI>The CouldLive list - the "maybe" list of Cell objects that could possibly live the next generation. </LI>
<LI>The CouldDie list - the "maybe" list of Cell objects that could possibly die the next generation. </LI>
<LI>The Live list - a list of Cell objects that will be made alive. This list is actually the the end result of the CouldLive list.</LI>
<LI>The Die list - a list of Cell objects that will be killed (made a 0 in the world array). This list is actually the the end result of the CouldDie list.</LI>
</OL>
</P>
Here's the flow of processing:<BR>
<OL>
<LI>When the program begins, all arrays are zeroed and all lists are empty.</LI>
<LI>The user sets the initial pattern. If she left clicks a cell to life a one is added to the appropriate world array element and a Cell object having the associated col, row coordinates is added to the Live list.. Right clicking an alive cell replaces the one with a zero in that world array element and the associated object is removed from the Live list. This defines the first (or initially placed) generation.</LI>
<LI>When the user Starts the simulation for the first time (or initially clicks the Step button), we scan the Live list and increment the neighbor count of every cell adjacent to a cell in the list. Cells that might come to life in the next generation are added to the CouldLive list, and cells that might die in the next generation are added to the CouldDie list.</LI>
<LI>Empty the Live list.</LI>
<LI>Process the resulting neighbor array. For every element in the array, if the associated cell is alive and the count is less than 2 or more than 3 we add the Cell object to the CouldDie list.</LI>
<LI>Transfer the CouldLive list to the Live list and the CouldDie list to the Die list.</LI>
<LI>Scan the Live list and if the cell was dead and it has exactly 3 neighbors, bring it to life (update it's world array element with a 1 and paint it as alive on the screen). Otherwise remove it from the Live list.</LI>
<LI>Scan the Die list and if the cell was alive and it doesn't have 2 or 3 neighbors, kill it (update it's world array element with a 0 and erase it from the screen). Otherwise remove it from the Die list.</LI>
<LI>Scan the Live list and increment the neighbor count of every cell adjacent to a cell in the list. Cells that might come to life in the next generation are added to the CouldLive list, and cells that might die in the next generation are added to the CouldDie list. </LI>
<LI>Scan the Die list and decrement the neighbor count of every cell adjacent to a cell in the list. Cells that might come to die in the next generation are added to the CouldDie list, and cells that might live in the next generation are added to the CouldLive list.</LI>
<LI>Transfer the CouldLive list to the Live list and the CouldDie list to the Die list.</LI>
<LI>This ends the processing for the second generation. For each subsequent generation we just repeat steps 7 - 11.</LI>
</OL>
<P>Pretty simple, huh?<BR>
If you have the VB6 source code it becomes much easier to get a feel for the algorithm by using the debugger to set breakpoints and single step the following procedures that do most of the work:</P>
<P><STRONG>UpdateDisplay()</STRONG> - Called to start a new generation - this procedure calls each of the following which actually do all the processing:<BR></P>
<P><STRONG>CreateLists()</STRONG> - Steps 3-6 - Only used on the first pass to set up the lists.<BR>
<PRE>
--------> <STRONG>Live()</STRONG> Step 7
| <STRONG>Die()</STRONG> Step 8
| <STRONG>AddNbrs()</STRONG> Step 9
<-------- <STRONG>SubNbrs()</STRONG> Step 10
</PRE></P>
</body>
</html>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -