|Previous||Table of Contents||Next|
David Stafford won my first Optimization Challenge by means of a huge look-up table and an incredible state machine driven by that table. The table didnt cause Davids entry to exceed the line limit because Davids submission included code to generate the table on the fly as part of the build process. David has done himself one better this time with his QLIFE program; not only does his build process generate a 64K table, but it also generates virtually all his code, consisting of 17,000-plus lines of assembly language spanning another 64K. What David has done is write the equivalent of a bitblt compiler for the Game of Life; one might in fact call it a Life compiler. What Davids code generates is still a general-purpose program; it takes arbitrary seed values, and can run for an arbitrary number of generations, so its not as if David simply hardwired the instructions to draw each successive screen. However, its a general-purpose program that is exquisitely tailored to the task it needs to perform.
All the pieces of QLIFE are shown in Listings 18.1 through 18.5, as follows: Listing 18.1 is BUILD.BAT, the batch file used to build QLIFE; Listing 18.2 is LCOMP.C, the program used to generate the assembler code and data file QLIFE.ASM; Listing 18.3 is MAIN.C, the main program for QLIFE; Listing 18.4 is VIDEO.C, the video-related functions, and Listing 18.5 is LIFE.H, the header file. The following sidebar contains Davids build instructions, exactly as he wrote them. I certainly wont have room to discuss all the marvelous intricacies of Davids code; I suggest you look over these listings until you understand them thoroughly (it took me a day to pick them apart) because theres a lot of neat stuff in there, and its an approach to performance programming that operates at a more efficient, tightly integrated level than you may ever see again. One hint: It helps a lot to build and run LCOMP.C, redirect its output to QLIFE.ASM, and look at the assembly code in that file. This code is the entirety of Davids generation engine, and its almost impossible to visualize its operation without actually seeing it.
How To Build Qlife
QLIFE is written for Borland C++, but it shouldnt be too difficult to convert it to work with Microsoft C++. To build QLIFE, run the BUILD.BAT batch file with the size of the life grid on the command line (see below). The command-line options are:
WIDTH 32 Sets the width of the life grid to 96 cells (divided by 3). HEIGHT 96 Sets the height of the life grid to 96 cells. NOCOUNTER Turns off the generation counter (optional). NODRAW Turns off drawing of the cell map (optional). GEN 1000 Calculates 1,000 generations (optional).
These must be in uppercase. For example, the minimum you really need is WIDTH 40 HEIGHT 120. I used WIDTH 46 HEIGHT 138 NOCOUNTER NODRAW GEN 7000 during testing.
If you have selected the GEN option, you will have to press a key to exit QLIFE when it is finished. This is so I could visually compare the result of N generations under QLIFE with N generations under Abrashs original life program. You should be aware that the program from the listing contains a small bug, which may make it appear that they do not generate identical results. The original program does not display a cell until it changes, so if a cell is alive on the first generation and never dies, then it will never be displayed. This bug is not present in QLIFE.
You should have no trouble running QLIFE with cell grids up to 210×200.
You must have a VGA and at least a 386 to run QLIFE. The 386 features that it uses are not integral to the algorithm (theyre a convenience for the code), so feel free to modify QLIFE to run on earlier CPUs if you wish. QLIFE works best if you have a large CPU cache (256K is recommended).
|Previous||Table of Contents||Next|