Programming by Example

 

A BB4W Compendium

freeman69@gmx.com

IDIC BBC_Owl2 M&P

Conway's Game of Life

Similar to Bugs, Conway's Game of Life attempts to model primitive life. The simulation can be run on any size of grid. The rules of the simulation were carefully chosen and are as follows:

 

         If a grid cell is currently alive then...

         If the cell has less than 2 or more than 3 neighbours then the cell dies.

 

         If a grid cell is currently dead then...

         If the cell has exactly 3 neighbours then it is given life.

 

  10 MODE 9:OFF

  20 size=76:size+=2

  30 DIM grid% size^2

  40 scale=(240 DIV size)*4

  50 COLOUR 1,64,0,0

  60

  70 PROCrandomizegrid

  80 PROCdrawgrid

  90

 100 REPEAT

 110   TIME=0

 120   PROCcountneighbours

 130   PROCupdategrid

 140   IF INKEY(-99) PROCrandomizegrid:PROCdrawgrid

 150   PRINTTAB(12,1);generation

 160   WAIT 4-TIME

 170 UNTIL FALSE

 180 END

 190

 200 DEF PROCcountneighbours

 210 LOCAL a,x,y

 220 FOR y=1 TO size-2

 230   FOR x=1 TO size-2

 240     a=y*size+x

 250     IF (grid%?a AND 16)=16 THEN

 260       grid%?(a-1)+=1

 270       grid%?(a+1)+=1

 280       grid%?(a-size-1)+=1

 290       grid%?(a-size)+=1

 300       grid%?(a-size+1)+=1

 310       grid%?(a+size-1)+=1

 320       grid%?(a+size)+=1

 330       grid%?(a+size+1)+=1

 340     ENDIF

 350   NEXT

 360 NEXT

 370 ENDPROC

 380

 390 DEF PROCupdategrid

 400 LOCAL a,x,y,ncount

 410 GCOL 3,7

 420 FOR y=1 TO size-2

 430   FOR x=1 TO size-2

 440     a=y*size+x

 450     ncount=(grid%?a) AND 15

 460     IF (grid%?a AND 16)=0 THEN

 470       IF ncount=3 grid%?a=16:RECTANGLEFILL x*scale,y*scale,scale

 480     ELSE

 490       IF ncount<2 OR ncount>3 grid%?a=0:RECTANGLEFILL x*scale,y*scale,scale

 500     ENDIF

 510     grid%?a AND=16:REM zero the neighbour count

 520   NEXT

 530 NEXT

 540 generation+=1

 550 ENDPROC

 560

 570 DEF PROCrandomizegrid

 580 LOCAL a

 590 FOR a=0 TO size^2-1

 600   IF RND(2)=1 grid%?a=16 ELSE grid%?a=0

 610   IF (a MOD size)=0 OR (a MOD size)=size-1 OR a<size OR a>size^2-size grid%?a=0

 620 NEXT

 630 generation=0

 640 ENDPROC

 650

 660 DEF PROCdrawgrid

 670 LOCAL side,a,x,y

 680 CLS

 690 PRINT"Press SPACE to reset"

 700 PRINT"Generation:"

 710 side=size*scale

 720 GCOL 0,1

 730 FOR a=0 TO size

 740   LINE a*scale,0,a*scale,side

 750   LINE 0,a*scale,side,a*scale

 760 NEXT

 770 GCOL 3,7

 780 a=0

 790 FOR y=0 TO size-1

 800   FOR x=0 TO size-1

 810     IF ((grid%?a)AND16)=16 RECTANGLEFILL x*scale,y*scale,scale

 820     a+=1

 830   NEXT

 840 NEXT

 850 ENDPROC

Life

Conway's Game of Life: Code explained...

 

  10 MODE 9:OFF

  20 size=76:size+=2

 

'size' defines the length of one side of our square grid. We add 2 to create a border around the grid, which simplifies the processing.

 

  30 DIM grid% size^2

 

'grid%' is an array of a different kind, much simpler than any array previously defined.

Usually, arrays hold strings or numeric variables. Numeric variables in BASIC tend to be values that can include fractions.

'grid%' is actually a block of computer memory; a list of bytes. Our first program, the character designer, used a grid of 8 rows of 8 pixels. We can think of that character grid as a list of 8 bytes, where a byte consists of 8 binary digits. 'grid%' is also list of bytes (78*78=6084 bytes in total).

An 8 bit byte can only hold whole values between zero and 255, which is more than enough for this application. Each byte will store information relating to a single cell.

 

  40 scale=(240 DIV size)*4

 

The scale of the grid is maximised, to be drawn as large as possible.

 

  50 COLOUR 1,64,0,0

 

COLOUR usually specifies the text colour to be used. However, in this instance the colour specified (1=red) is followed by three more numbers. These additional values represent amounts of red, green and blue (between zero and 255 each). This command is actually redefining the colour red to be a darker red than normal.

 

  70 PROCrandomizegrid

  80 PROCdrawgrid

 

Before the simulation begins we must randomly add living cells to our empty grid.

 

 100 REPEAT

 110   TIME=0

 120   PROCcountneighbours

 130   PROCupdategrid

 

Each animation cycle recalculates the status of each cell on the grid.

 

 140   IF INKEY(-99) PROCrandomizegrid:PROCdrawgrid

 

Pressing space resets the simulation by filling the grid randomly.

 

 200 DEF PROCcountneighbours

 210 LOCAL a,x,y

 220 FOR y=1 TO size-2

 230   FOR x=1 TO size-2

 240     a=y*size+x

 250     IF (grid%?a AND 16)=16 THEN

 260       grid%?(a-1)+=1

 270       grid%?(a+1)+=1

 280       grid%?(a-size-1)+=1

 290       grid%?(a-size)+=1

 300       grid%?(a-size+1)+=1

 310       grid%?(a+size-1)+=1

 320       grid%?(a+size)+=1

 330       grid%?(a+size+1)+=1

 340     ENDIF

 350   NEXT

 360 NEXT

 370 ENDPROC

 

The rules of the simulation require us to determine how many living neighbours each cell has.

'grid%' holds a total count of each cell's neighbours (zero to 8). A quick and efficient way to count neighbours is to check each cell in turn and if the cell is alive then we add one to each of that cell's neighbours.

Because 'grid%' is not a normal array, but a block of memory, we have to use a special method to access and update each byte e.g.

 

grid%?n refers to byte n of the array.

 

Returning to the analogy of the character designer, we can see that a value between zero and 8 only requires 4 binary digits (bits) e.g. 0000 = 0, 0101 = 5, 1000 = 8, 1111 = 15.

A byte consists of 8 bits, so we have 4 bits of each byte to spare. We will use one of these bits (bit 5) to indicate the status of the cell i.e. whether the cell is dead or alive. Bit 5 has a unique value of 16.

Line 250 shows how we can test an individual bit by using the logical AND function. AND returns the following results:

 

00000000 AND 16 = 0

00000001 AND 16 = 0

00010000 AND 16 = 16

00011010 AND 16 = 16

 

The AND command masks the bits we're not interested in, allowing us to test the status (or value) of specific bits.

 

 390 DEF PROCupdategrid

 400 LOCAL a,x,y,ncount

 410 GCOL 3,7

 420 FOR y=1 TO size-2

 430   FOR x=1 TO size-2

 440     a=y*size+x

 450     ncount=(grid%?a) AND 15

 460     IF (grid%?a AND 16)=0 THEN

 470       IF ncount=3 grid%?a=16:RECTANGLEFILL x*scale,y*scale,scale

 480     ELSE

 490       IF ncount<2 OR ncount>3 grid%?a=0:RECTANGLEFILL x*scale,y*scale,scale

 500     ENDIF

 510     grid%?a AND=16:REM zero the neighbour count

 520   NEXT

 530 NEXT

 540 generation+=1

 550 ENDPROC

 

PROCupdategrid applies the rules of Life to each cell in turn (ignoring the cells around the border). Each living cell is initially drawn as a filled square. However, because we're using GCOL 3,7 (exclusive-or) then each square will erase itself if drawn for a second time. This simplifies the updating process because if the status of a cell has changed then we always draw a square. If the status of the cell hasn't changed then we do nothing.

Line 450 accesses the value for the total count of a cell's neighbours (bits 1 through 4).

Line 460 tests the status bit (bit 5) of the cell.

Line 510 is equivalent to grid%?a=grid%?a AND 16, which masks all bits except bit 5, zeroing the neighbour count in preparation for the next cycle.

 

 570 DEF PROCrandomizegrid

 580 LOCAL a

 590 FOR a=0 TO size^2-1

 600   IF RND(2)=1 grid%?a=16 ELSE grid%?a=0

 610   IF (a MOD size)=0 OR (a MOD size)=size-1 OR a<size OR a>size^2-size grid%?a=0

 620 NEXT

 630 generation=0

 640 ENDPROC

 

Creating a random grid is simply a matter of setting bit 5 of each byte if the cell is alive.

Line 610 ensures that the border cells are always dead.

 

 660 DEF PROCdrawgrid

 

This routine draws the grid lines and fills the squares of those cells that are alive to begin with. Note that line 810 is testing the status bit (bit 5).

Arrow black large Arrow black large