9. An Abstract Data Type for Animating the Game of Life

To animate the Game of Life, we introduce the Lifestate abstract data type, defined in the lifestate module. We will use this abstract data type for both character-based and GUI-based animations.

IMPLEMENTATION MODULE lifestate;
IMPORT lifepoint;

This abstract data type is implemented as a tuple which contains all the information required for animation. This includes the number of steps performed, the number of live cells, and the status of the pattern. This status is an element of an enumerated type, which is DEAD for patterns containing no live cells, STABLE for patterns which do not change when a step is performed, and DYNAMIC otherwise:

 
TYPE
:: STEPNUM -> INT;
:: Lifestatus -> DYNAMIC | STABLE | DEAD;

The tuple also contains the coordinates of the upper left corner of the viewing window, the width and height of the viewing window, the statistics for the pattern as discussed in section 4, the sorted list of points constituting the pattern, and the sorted list of points visible in the viewing window. Laziness is essential in this last element, since we do not want to compute it if it is not needed.

 
:: WIDTH -> INT;
:: HEIGHT -> INT;
:: Lifestate -> (!STEPNUM, !INT, !Lifestatus, !Pnt, 
                 !WIDTH, !HEIGHT, !Lifestats, PntList, PntList);

The Emptystate function initialises an empty pattern:

 
RULE
:: Emptystate !WIDTH !HEIGHT -> Lifestate;
   Emptystate w h -> (0,0,DEAD,(0,0),w,h,(0,0,0,0,0,0),[],[]);

There are a number of projection functions for extracting the components of the tuple. Since Lifestate will be declared as an abstract data type, it will only be accessible via the operations in this module. Since a DEAD pattern is a special case of a STABLE one, the Stable function returns true for DEAD patterns.

 
:: Stepno !Lifestate -> STEPNUM;
   Stepno (step, n, status, upleft, w, h, stats, pts, crp) -> step;

:: Numcells !Lifestate -> INT;
   Numcells (step, n, status, upleft, w, h, stats, pts, crp) -> n;

:: Status !Lifestate -> Lifestatus;
   Status (step, n, status, upleft, w, h, stats, pts, crp) -> status;

:: Dead !Lifestate -> BOOL;
   Dead (step, n, DEAD, upleft, w, h, stats, pts, crp) -> TRUE;
   Dead (step, n, status, upleft, w, h, stats, pts, crp) -> FALSE;

:: Stable !Lifestate -> BOOL;
   Stable (step, n, STABLE, upleft, w, h, stats, pts, crp) -> TRUE;
   Stable (step, n, DEAD, upleft, w, h, stats, pts, crp) -> TRUE;
   Stable (step, n, status, upleft, w, h, stats, pts, crp) -> FALSE;

:: Width !Lifestate -> WIDTH;
   Width (step, n, status, upleft, w, h, stats, pts, crp) -> w;

:: Height !Lifestate -> HEIGHT;
   Height (step, n, status, upleft, w, h, stats, pts, crp) -> h;

:: Allpoints !Lifestate -> PntList;
   Allpoints (step, n, status, upleft, w, h, stats, pts, crp) -> pts;

:: Croppedpoints !Lifestate -> PntList;
   Croppedpoints (step, n, status, upleft, w, h, stats, pts, crp) -> crp;

The Picrect function calculates the rectangle ((a,b),(c,d)) occupied by the points in the pattern, for use with e.g. WritePS:

 
:: Picrect !Lifestate -> Rect;
   Picrect (step, n, status, upleft, w, h, 
                        (minx,totx,maxx,miny,toty,maxy), pts, crp) 
                                        -> ((minx,miny), (maxx,maxy));

On the other hand, the Winrect function calculates the rectangle ((a,b),(c,d)) occupied by the viewing window:

 
:: Winrect !Lifestate -> Rect;
   Winrect (step, n, status, upleft:(a,b), w, h, stats, pts, crp)
     -> (upleft, (c,d)),
        c: -- (+ a w),
        d: -- (+ b h);

The CentOfGrav function calculates the average value of the coordinates of live cells, giving the 'centre of gravity' of the picture:

 
:: CentOfGrav !Lifestate -> Pnt;
   CentOfGrav (step, n, status, upleft, w, h, 
                        (minx,totx,maxx,miny,toty,maxy), pts, crp) 
                                        -> (0,0), IF = n 0
                                        -> (/ totx n, / toty n);

The coordinates of the centre of the viewing window are calculated by ActualCent:

 
:: ActualCent !Lifestate -> Pnt;
   ActualCent (step, n, status, (a,b), w, h, stats, pts, crp) 
     -> (+ a (/ w 2), + b (/ h 2));

The CentreAt function moves the viewing window so that it is centred on a given point (x,y). This requires re-cropping the pattern to fit the new window:

 
:: CentreAt !Pnt !Lifestate -> Lifestate;
   CentreAt (x,y) (step, n, status, upleft, w, h, stats, pts, crp) 
     -> (step,  n, status, (a,b), w, h, stats, pts, newcrp),
        a: - x (/ w 2), 
        b: - y (/ h 2),
        newcrp: CropPnt a b c d pts,
        c: -- (+ a w),
        d: -- (+ b h);

We can use this operation to define a function which centres the viewing window on the 'center of gravity' of the pattern:

 
:: GoCentre !Lifestate -> Lifestate;
   GoCentre s -> s, IF = 0 (Numcells s)
              -> CentreAt (CentOfGrav s) s;

The Resize function alters the width and height of the viewing window, while maintaining the coordinates of the centre. The CentreAt operation will re-crop the pattern to fit the new window:

 
:: Resize !WIDTH !HEIGHT !Lifestate -> Lifestate;
   Resize w h s:(step, n, status, upleft, oldw, oldh, stats, pts, crp)
     -> CentreAt centre (step, n, status, upleft, w, h, stats, pts, crp),
        centre: ActualCent s;

The Loadpoint function places a list of points representing a new pattern into the tuple. This list must be sorted, and the statistics recalculated. The step count must also be reset to zero. The GoCentre function will centre the viewing window on the new pattern and re-crop:

 
:: Loadpoint !PntList !Lifestate -> Lifestate;
   Loadpoint l (step, n, status, upleft, w, h, stats, pts, crp)
     -> Emptystate w h, IF = m 0
     -> GoCentre (0, m, DYNAMIC, upleft,  w, h, newstats, newpts, []),
        newpts: SortPnt l,
        (m, newstats): StatPnt newpts;

The Changepoint function inverts the state of a cell in the pattern, specified using absolute coordinates, or relative to the upper left corner of the viewing window. An enumerated type PntRefKind is used to identify the two types of call:

 
TYPE
:: PntRefKind -> RELATIVE | ABSOLUTE;

RULE
:: Changepoint !PntRefKind !Pnt !Lifestate -> Lifestate;
   Changepoint ABSOLUTE (x,y) 
        s:(step, n, status, upleft:(a,b), w, h, stats, pts, crp)
                -> ChangepointAux x y (- x a) (- y b) s;
   Changepoint RELATIVE (x,y) 
        s:(step, n, status, upleft:(a,b), w, h, stats, pts, crp)
                -> ChangepointAux (+ a x) (+ b y) x y s;

The auxiliary function inverts the cell in the pattern, and also in the viewing window if it falls inside the window area. The statistics are recalculated, and the step count reset to zero:

 
:: ChangepointAux !INT !INT !INT !INT !Lifestate -> Lifestate;
   ChangepointAux absx absy relx rely 
        (step, n, status, upleft, w, h, stats, pts, crp)
             -> Emptystate w h, IF = m 0
             -> (0, m, DYNAMIC, upleft, w, h, newstats, newpts, newcrp),
                        IF >= relx 0 && >= rely 0 && < relx w && < rely h
             -> (0, m, DYNAMIC, upleft, w, h, newstats, newpts, crp),
                newpts: SwapPnt absx absy pts,
                newcrp: SwapPnt relx rely crp,
                (m, newstats): StatPnt newpts;

The most important function is Lifestep which increments the step count and calculates a new list of points using the Step function from section 4. The statistics are recalculated, and the points are re-cropped to fit the viewing window. However, if the step resulted in no change to the list of points, these alterations are not performed, and only the status is changed to indicate that the pattern has become stable:

 
:: Lifestep !Lifestate -> Lifestate;
   Lifestep (step, n, status, upleft:(a,b), w, h, stats, pts, crp)
     -> (++ step, 0, DEAD, upleft, w, h, newstats, [], []), 
                                                    IF = m 0
     -> (step, n, STABLE, upleft, w, h, stats, pts, crp),
                                                    IF Same pts newpts
     -> (++ step, m, DYNAMIC, upleft, w, h, newstats, newpts, newcrp),
        newpts: Step pts,
        newcrp: CropPnt a b c d newpts,
        c: -- (+ a w),
        d: -- (+ b h),
        (m, newstats): StatPnt newpts;

A variation of Lifestep is Trackstep, which follows the step by readjusting the viewing window, if the boolean argument is true. Since GoCentre re-crops to fit the viewing window, the cropped list produced by Lifestep is lazily replaced without being evaluated:

 
TYPE
:: TRACKMODE -> BOOL;

RULE
:: Trackstep !TRACKMODE !Lifestate -> Lifestate;
   Trackstep track s -> GoCentre s', IF track
                     -> s',
                        s': Lifestep s;

The lifestate definition module (lifestate.dcl) exports the name of the Lifestate type as an abstract data type, using ABSTYPE. Its implementation as a tuple is hidden, so that the type can only be accessed using the exported functions.

UpTop Level

BackA GUI-Based Conversion Program

DCLlifestate.dcl

ForwardAn Animation Program