\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage{german}
\usepackage{a4}

%\pagestyle{empty}
\renewcommand{\baselinestretch}{0.95}

\begin{document}
\centerline{{\it Vorlesung: Physik auf dem Computer I}}
\bigskip
\centerline{\bf ÜBUNG 12} 
\medskip
\centerline{\it Conway's Game of Life}

%\begin{center}
%Bitte protokollieren Sie Ihre Arbeit an diesem \"Ubungsblatt, 
%und geben Sie die Antworten auf die Fragen am Ende der "Ubung
%Ihrem Assistenten! 
%\end{center}
\bigskip

{\bf Aufgabe\ } {\it Life} --- \\ 
ist ein sogenannter
Zellularautomat, der uns als Beispiel f\"ur ein Programm dienen soll,
das Feldvariablen benutzt und eine einfache ``Dynamik'' besitzt. 
Ein funktionierendes Programmger\"ust ist im Verzeichnis
\verb|~sts/COMPUTERPHYSIK/BLATT12| vorhanden.
  
\smallskip  

{\sc Life} lebt auf einem Quadratgitter. Gitterplätze können belegt
(lebendes Individuum, 1) oder leer (tot, 0) sein.
Als Nachbarn eines Gitterplatzes werden dabei sowohl die 
direkten Nachbarn (links, rechts, oben, unten) 
als auch diejenigen in den Diagonalpositionen gezählt. 
Jeder Gitterplatz hat also 8 Nachbarplätze.
Je nach dem Zustand eines Gitterplatzes und seiner Nachbarn
wird entschieden, ob ein Platz stirbt oder hinzukommt.\\
Die Regeln sind: 
\begin{itemize}
\vspace{-.5\baselineskip}
%\parskip=0pt
%\topsep=-\bigskipamount
%\addtolength{\topsep}{-3\baselineskip}
\addtolength{\itemsep}{-0.7\baselineskip}
%\addtolength{\parsep}{-4\baselineskip}
%\partopsep=-\baselineskip
\item[(i)] ein leerer, toter Platz wird belebt, wenn er genau 3 lebende 
Nachbarn hat; 
\item[(ii)] ein besetzter, lebender Platz stirbt, (Überbevölkerungsregel) 
wenn er mehr als 3 oder
\item[(iii)] (Vereinsamungsregel) weniger als 2 Nachbarn hat.
\vspace{-.5\baselineskip}
\end{itemize}

\smallskip

Ein zweidimensionales Feld wird benötigt als 
``Lebensraum'' der {\sc  Life}-Individuen.
Lebende Plätze werden mit 1, leere mit 0 markiert. 
Wählen Sie zu Anfang zunächst eine kleine Größe, z.B. $5\times 5$. 
Zum Test k\"onnen Sie ausgew\"ahlte Elemente auf 1 setzen, sp\"ater ist es 
besser, die Initialisierung einfach zuf\"allig vorzunehmen. 

Wir be\"notigen eine \"au\ss{}ere Zeitschleife, vielleicht einfach
ein nicht abbrechendes 
\begin{verbatim}
while(true){
  // ...
}
\end{verbatim}
Innerhalb dieser läuft eine doppelte {\tt for(;;)} Schleife
über alle Feldelemente. Diese enthält
\begin{itemize}
\vspace{-.7\baselineskip}
%\parskip=0pt
%\topsep=-\bigskipamount
%\addtolength{\topsep}{-3\baselineskip}
\addtolength{\itemsep}{-0.7\baselineskip}
%\addtolength{\parsep}{-4\baselineskip}
%\partopsep=-\baselineskip
\item[(i)] eine innere Schleife, die die Nachbarn des gerade
bearbeiteten Platzes zählt und
\item[(ii)] ein Programmsegment, das 
erst danach die {\sc Life}-Regeln anwendet und 
entsprechend den neuen Wert in einem weiteren, mit dem ``Lebensraumfeld'' 
gleichgroßen Feld auf 1 oder 0 setzt.
\vspace{-.7\baselineskip}
\end{itemize}
Beachten Sie dabei, daß alle
Zugriffe, auch die auf die Nachbarn, 
{\it innerhalb des korrekten Indexbereiches} liegen müssen. 
An den Feldrändern muß das mit entsprechenden Operationen sichergestellt
werden (z.B. mit periodischen Randbedingungen) oder einer
zus\"atzlichen Reihe von Pl\"atzen, die immer denselben Wert behalten.

Am Schluß müssen die neuen Zustände noch auf die alten kopiert werden, was
wieder in einer Doppelschleife geschehen kann, damit wir die gleichen
Regeln von Neuem anwenden k\"onnen.

Das Beispielprogramm k\"onnen Sie mit \verb|make| kompilieren, wenn
Sie au\ss{}er \verb|life.cc| auch noch das \verb|Makefile| in Ihr
lokales Verzeichnis kopieren. 

{\footnotesize
\begin{verbatim}
#include "XT/XTDisplay.h"
#include "XT/XTX11Dev.h"
#include "XT/XTScalarField.h"
#include "PT/PTSArr.h"       // array with safe access

int main(){
 XTX11Dev  x11(500,500);     // window of size 500 x 500
 XTDisplay d(x11);           // 'real' graphics class, using x11 window as
                             //   output 'device'
 int size = 5;	
 PTS_2DArr<int>  world(size,size);  // 'Lebensraum', size 5 x 5, valid
                             //   indices are 0..4 (index check is done)

 // initialize
 for ( int i=0; i<size; ++i )  
   for ( int j=0;  j<size; ++j )		
      world[i][j] = 0;
	
 // outer loop of some type - here endless loop
 while (true) {
    // inner loop of some type
          ...
         // world[i][j] = ...;  
    // end inner loop
    ...
    // GRAPHICS PART	
    // erase the screen            
    d.clear();   

    // draw the 'world' (can also be a regular C array) 
    // 0..5 / 0..5 is first index .. size in x / y direction
    d << xtScalarField(world,0,5,0,5); 

    // 'display' on the screen what we have drawn so far
    d.display(); 
    ...
 } // 'end' of outer loop
 	
}
\end{verbatim}
}

\medskip

\noindent Literatur: Martin Gardner, {\it On cellular automata, 
self-reproduction, the Garden of Eden and the game ``life,''\/}
Scientific American {\bf 224}, 112 (February 1971).

\vfill

\begin{flushright}
\begin{tabular}{lll}
Michael Brunner & Di 9:45 & {\tt michi@ica1.uni-stuttgart.de}\\
Stefan Schwarzer & Di 11:30 & {\tt sts@ica1.uni-stuttgart.de} 
\end{tabular}
\end{flushright}

\end{document}

                                            











