Its been a rough day at work and out of the blue, I decide I'm going to write an implementation of Conway's Game of Life. I've written one with practically every other Pascal compiler I've used, but never with Delphi.
For those of you that have never encountered the Game of Life, there's a good article on Wonders Of Math.
Why is any of this relevant? Because over the course of the next couple of hours, I put together what is essentially a very untidy little program, with no glitz (the GUI is basic) and no glam (it uses TPaintBox as its output), but, that does provide some useful points about the basics of optimization.
So what is the Game of Life?
Just in case you don't know what the Game of Life is and haven't read the excellent article at Wonders of Math, it goes something like this... the Game of Life is a simulation of a simple cell based system. It is supposed to use an infinitely sized grid. Cells within the system follow these basic rules:-
- If I have less than 2 neighbours, I die of loneliness
- If I have exactly 3 neighbours and I'm not alive, I am born
- If I have 2 or 3 neighbours and I'm alive, then I survive
- If I have more than 3 neighbours, its too cramped... I die of overcrowding
So, you activate some cells and then apply these rules to every cell in the grid. Repeat, add infinitum. This sounds like an easy little program, and it is, a really easy little program, but one that does have some good scope for introducing some basic optimization.
There is a ZIP file containing the source code and various EXE's that illustrate the points discussed in the article. It is available for download from here.
The Original Program
From the rules, you can see there are certain values that are important. When I originally started writing it, I couldn't remember these values and I didn't want to Google them... I wanted to code, so I added some edit boxes to allow me to tweak them.
I decided I would do a small grid (80 x 80, although this quickly became 282 x 282 - the size used for all the timings) and that I would render this on a 705 x 705 paint box control with a cell size of 8 pixels. First thing to do is write a renderer and hook up events to activate/deactivate cells when the user clicks on the grid.
The renderer is incredibly basic. Using only TCanvas's fillRect method it fills the paint box clipping area with white and then proceeds to render each cell by filling it with the appropriate colour (governed by how long the cell has been alive). Moving onto the editor, the code works out where the mouse was on the click and then calculates a grid reference by div'ing them by the cell size. It then toggles the cell and redraws the display.
Once you have placed your cells, you click 'Start' and off it goes. The cells spring into life and begin their journey. When this happens, all hell break lose. The system uses TTimer to call the code that generates the next generation of cells from the existing grid. It does this repeatedly as long as the system is set to run.
If you look at the source code, you will notice a whole bunch of conditional defines at the top. What I've actually done, is deoptimise the source to take it back to the original version. This can be tried out by running the Life_Original.exe or compiling the code with none of the conditional defines set (stuff a _ in front of them), except 'optimisedvariablerules'.
Editing the grid is a nightmare.. lots of screen flicker and actually running the simulation... painfully slow. So lets tackle the least important of these first... editing the grid.
You will have undoubtedly noticed the horrendous screen flicker when you edit the grid. This is caused by the full screen refresh that occurs whenever you toggle a cell. The original mouseUp event handler that forms the editor can be seen below.
procedure TfrmMain.pbMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var mapX : integer; mapY : integer; begin if (fStopped) then begin mapX:=(x div _cellSize)+1; mapY:=(y div _cellsize)+1; if (fCurrentMap[mapX,mapY]>0) then fCurrentMap[mapX,mapY]:=0 else fCurrentMap[mapX,mapY]:=1; paintMap; if (frmOverview.visible) then frmOverview.pbo.invalidate; end; end;
This is relatively easy to achieve with the simple addition of a timer (tmrRefresh) to the form. This timer is disabled when the application starts and is only enabled by the mouseUp event handler of the TPaintBox (pb), after it has finished toggling the cell. This event handler also disables the timer when it starts... this means that so long as we click again before the interval of the timer has expired, a repaint won't occur, this means we can click click click click then pause and see our handy-work when the timer fires.
tmrRefresh Event Handler
procedure TfrmMain.tmrRefreshTimer(Sender: TObject); begin tmrRefresh.enabled:=false; paintMap; if frmOverview.visible then begin frmOverview.pbo.invalidate; end; end;
procedure TfrmMain.pbMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var mapX : integer; mapY : integer; begin if (fStopped) then begin tmrRefresh.enabled:=false; if (fCurrentMap[mapX,mapY]>0) then begin fCurrentMap[mapX,mapY]:=0; end else begin fCurrentMap[mapX,mapY]:=1; end; tmrRefresh.enabled:=true; end; end;
The second and most obvious method is to simply update the cell thats changed. You can see the difference by enabling editoroptimisation2 or running Life_EditOpt2.exe.
The revised mouseUp handler looks like this...
procedure TfrmMain.pbMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var mapX : integer; mapY : integer; begin if (fStopped) then begin mapX:=(x div _cellSize)+1; mapY:=(y div _cellsize)+1; if (fCurrentMap[mapX,mapY]>0) then begin fCurrentMap[mapX,mapY]:=0; end else begin fCurrentMap[mapX,mapY]:=1; end; drawCell(mapX,mapY); if (frmOverview.visible) then begin frmOverview.pbo.canvas.pixels[mapx-1,mapy-1]:=colors[fCurrentMap[mapx,mapy]]; end; end; end;
My options at that point were also restricted by the routines I had coded. Initially, the only routine that updated the canvas displaying the map was 'paintmap'. It wasn't until I added the 'drawcell' routine during my optimization of the code that prodcues the next generation of cells that I went back and finished off optimizing the editor. I could have coded it, but it was late, I was lazy and I could live without it... for a while anyway.
This does illustrate a very valuable point about optimization. The process of optimizing your software should have started even before you write the first line of code. Good design can often highlight potential problems before they occur, the more experience you get, the more potential pitfalls you may be able to avoid during the design phase.
Had I spent any time thinking about it before hand, its highly likely that I would have had a 'drawCell' routine in my original code and as such, probably wouldn't have had to worry about optimizing the editor since it would make use of 'drawCell' in the original design.