Universität Ulm, Fakultät für Mathematik und Wirtschaftswissenschaften, SAI, WS 1998/99, Allgemeine Informatik I

Lösung zu Blatt 12 --- Allgemeine Informatik I (WS 1998/99)

14. Conway's Game of Life

(*
   Allgemeine Informatik I / Programmieren I    WS 1998/1999
   Musterloesung fuer das Blatt 12, Aufgabe 14
   Ingo Melzer und Andreas Borchert
*)
MODULE GameOfLife;

   FROM Arguments IMPORT InitArgs, GetFlag, FetchString, AllArgs, Usage;
   FROM ASCII IMPORT nl;
   FROM FtdIO IMPORT FwriteString, FwriteLn;
   FROM MainWin IMPORT WriteString, Write, WriteLn, Read,
      Flush, SetPos, Clear, lines, columns;
   FROM StdIO IMPORT FILE, MODE, Fopen, Fgetc, stdin, stderr;
   FROM SysExit IMPORT Exit;
   FROM SysPerror IMPORT Perror;

   CONST
      maxsize = 80; (* maximale Seitenlaenge *)
      space = " "; (* unbesetzt *)
      inhabitated = "X"; (* besetzt *)
   TYPE
      NeighbourCount = [0..8];
      NeighbourCountSet = SET OF NeighbourCount;
   CONST
      lonely = NeighbourCountSet{0, 1};
      birth = NeighbourCountSet{3};
      overpop = NeighbourCountSet{4..8};
   TYPE
      WorldSize = INTEGER [0..maxsize];
      WorldIndex = INTEGER [-1..maxsize];
         (* schliesst einen unsichtbaren Rand ein, der immer
            unbelegt ist (bei der Option border)
         *)
      World = ARRAY WorldIndex, WorldIndex OF CHAR;

   VAR
      world, newWorld: World;
      noflines, nofcolumns: WorldSize;
         (* verwendete Groesse, jeweils Minimum(Bildschirm, maxsize) *)

      (* Kommandozeilenargumente *)
      query: BOOLEAN; (* mit Rueckfragen? *)
      border: BOOLEAN; (* Torus oder mit Rand? *)
      input: FILE; (* von hier ist die Ausgangssituation einzulesen *)

      (* Abfragestatus *)
      continue: BOOLEAN;

   PROCEDURE ProcessArgs;
      VAR
         flag: CHAR;
         filename: ARRAY [0..511] OF CHAR;
   BEGIN
      InitArgs("[-q] [-b] world");
      query := FALSE; border := FALSE;
      WHILE GetFlag(flag) DO
         CASE flag OF
         | "q":   query := TRUE;
         | "b":   border := TRUE;
         ELSE
            Usage;
         END;
      END;
      FetchString(filename);
      IF ~Fopen(input, filename, read, (* buffered = *) TRUE) THEN
         Perror(filename); Exit(1);
      END;
      AllArgs;
   END ProcessArgs;

   PROCEDURE InitWorld(VAR world: World);
      (* initialisiert die Welt fuer die Eingabe *)
      VAR i, j: WorldIndex;
   BEGIN
      FOR i := MIN(WorldIndex) TO MAX(WorldIndex) DO
         FOR j := MIN(WorldIndex) TO MAX(WorldIndex) DO
            world[i, j] := space;
         END;
      END;
   END InitWorld;

   PROCEDURE ReadWorld(input: FILE; VAR world: World;
                       VAR noflines, nofcolumns: WorldSize) : BOOLEAN;
      (* Einlesen der Welt von ``input'':
         -  Bei Problemen wird eine Fehlermeldung ausgegeben und
            FALSE zurueckgeliefert.
         -  Im Erfolgsfall wird in world die Eingabe in der
            vorgefundenen Form abgelegt.
         -  Die Limits, die durch die Bildschirmgroesse (lines + columns)
            und maxsize gegeben sind, werden beruecksichtigt.
      *)
      VAR
         line, column: WorldSize; (* aktuelle Position in der Welt *)
         ch: CHAR; (* zuletzt eingelesenes Zeichen *)
   BEGIN
      InitWorld(world);
      line := 0; column := 0;
      WHILE Fgetc(ch, input) DO
         IF ch = nl THEN
            INC(line); column := 0;
         ELSE
            IF (line = maxsize) OR (column = maxsize) THEN
               WriteString("Die Eingabe ist zu gross!"); WriteLn;
               RETURN FALSE
            END;
            world[line, column] := ch; INC(column);
         END;
      END;
      IF (ORD(column) >= columns) OR (ORD(line) >= lines) THEN
         WriteString("Diese Welt ist zu gross fuer diesen Bildschirm!");
         WriteLn;
         RETURN FALSE
      END;
      nofcolumns := maxsize; noflines := maxsize;
      IF ORD(nofcolumns) > columns THEN nofcolumns := columns END;
      (* die letzte Zeile wird fuer die Eingabe reserviert *)
      IF ORD(noflines) > lines-1 THEN noflines := lines-1 END;
      RETURN TRUE
   END ReadWorld;

   PROCEDURE NextGeneration(world: World;
                            noflines, nofcolumns: WorldSize;
                            VAR newWorld: World);
      (* Berechnung der naechsten Generation von `world',
         das Resultat wird in `newWorld' zurueckgegeben
      *)

      PROCEDURE Neighbours (l, c: WorldIndex) : NeighbourCount;
         (* Zaehlt die Anzahl der belegten Felder in
            der Nachbarschaft von world[l, c]
         *)
         VAR
            neighbours: NeighbourCount;
            i, j: [-1..1];
            nl, nc: WorldIndex;
      BEGIN
         neighbours := 0;
         FOR i := -1 TO 1 DO 
            FOR j := -1 TO 1 DO 
               IF (i # 0) OR (j # 0) THEN (* eigenes Feld ignorieren *)
                  IF border THEN
                     nl := l + i; nc := c + j;
                  ELSE (* Torus *)
                     nl := (noflines + l + i) MOD noflines;
                     nc := (nofcolumns + c + j) MOD nofcolumns;
                  END;
                  IF world[nl, nc] # space THEN
                     INC(neighbours);
                  END;
               END;
            END;
         END;
         RETURN neighbours
      END Neighbours;

      VAR
         i, j: WorldIndex;
         neighbours: NeighbourCount;

   BEGIN (* NextGeneration *)
      IF border THEN
         (* den nicht sichtbaren Rand mit `space' initialisieren *)
         FOR i := -1 TO noflines DO
            world[i, -1] := space; world[i, nofcolumns] := space;
         END;
         FOR j := -1 TO nofcolumns DO
            world[-1, j] := space; world[noflines, j] := space;
         END;
      END;
      FOR i := 0 TO noflines -1 DO
         FOR j := 0 TO nofcolumns -1 DO
            neighbours := Neighbours(i, j);
            IF neighbours IN (lonely + overpop) THEN
               newWorld[i, j] := space;
            ELSIF neighbours IN birth THEN
               newWorld[i, j] := inhabitated;
            ELSE
               newWorld[i, j] := world[i, j];
            END;
         END;
      END;
   END NextGeneration;

   PROCEDURE Weiter() : BOOLEAN;
      (* Implementierung der Option -q *)
      VAR
         answer: CHAR;
   BEGIN
      IF continue THEN
         RETURN TRUE
      ELSE
         SetPos(lines-1, 0);
         WriteString("Weiter?"); Read(answer);
         SetPos(lines-1, 0);
         WriteString("        "); Flush;
         CASE answer OF
         | "c":   continue := TRUE; RETURN TRUE
         | "n":   RETURN FALSE
         ELSE
            RETURN TRUE
         END;
      END;
   END Weiter;

   PROCEDURE WriteWorld(world: World; height, width: WorldSize);
      (* Ausgabe von world auf stdout *)
      VAR
         line, column: WorldIndex;
   BEGIN
      FOR line := 0 TO height-1 DO
         SetPos(line, 0);
         FOR column := 0 TO width-1 DO
            Write(world[line, column]);
         END;
      END;
      Flush;
   END WriteWorld;

BEGIN
   Clear; Flush;
   ProcessArgs;
   IF ReadWorld(input, world, noflines, nofcolumns) THEN
      continue := FALSE;
      REPEAT
         NextGeneration(world, noflines, nofcolumns, newWorld);
         WriteWorld(world, noflines, nofcolumns);
         world := newWorld;
      UNTIL query & ~Weiter();
   END;
   SetPos(lines-1, 0); Flush;
END GameOfLife.

Andreas Borchert, 3. Februar 1999