Conway’s ‘Life’

Spillet (oppfunnet av engelsk matematiker John Horton Conway) foregår på et vilkårlig stort, rektangulært brett der det i utgangspunktet plasseres vilkårlig noen brikker. Brikker kan overleve, dø eller bli født fra genereasjon til generasjon etter følgende regler som anvendes samtidig for alle brikkene i en aktuell generasjon. En brikke

• overlever til neste generasjon hviss 2 eller 3 nabofelt har brikker

• dør hviss mer enn 3 eller mindre enn 2 nabofelt har brikker

• fødes i et tomt felt hviss nøyaktig 3 nabofelt har brikker

Nabofelt til et felt defineres her som de tilstøttende – vertikalt, horisontalt eller diagonalt – felt, dvs. feltet x : y i midten har følgende nabofelt (ingen felt er sin egen nabo)

\begin{aligned}−1 : −1 & : −1 & +1 : −1 \\ −1 : & x : y & +1 : \\ −1 : +1 & : +1 & +1 : +1 \end{aligned}

Hvis noen av disse feltene havner utenfor brettet, regnes de ikke med bland naboer.

Eksempel

Her er tre eksempler på spillforløpet fra venstre til høgre – i det første dør alle etter andre generasjon; i det andre, dannes det en stabil formasjone; i det tredje oppnåes en udødelig vekselvirkning mellom en horisontal og en vertikal 3-brikker formasjon:

1)  \begin{matrix}• \\ & • \\ & & • \end{matrix}  •

2)  \begin{matrix}• & • \\ • \end{matrix}  \begin{matrix}• & • \\ • & • \end{matrix}  \begin{matrix}• & • \\ • & • \end{matrix}

3)  \begin{matrix}• \\ • \\ • \end{matrix}  • • •  \begin{matrix}• \\ • \\ • \end{matrix}

1 Oppgave

Vi bruker en heltallsmatrise, int[][] board, der tallet 0 tilsvarer ingen brikke i feltet mens et tall x > 0 indikerer at det finnes en brikke. Vi ønsker å sette spillet inn i en modul som skal ha i det minste følgende grensesnitt:

• public Life(intx, inty) – konstruerer en ny data struktur for å holde en tilstand i en matrise x × y stor

• public setBoard(int[][] tab) – kopierer en gitt matrise tab til den interne data strukturen (x : y dimensjonene kan endres her!)

• public void setBead(int i, int j, int v) – der 1 ≤ i ≤ x og 1 ≤ j ≤ y er koordinater og v > 0 en verdi; tilsvarende felt i den interne datastrukturen skal merkes å inneholde en brikke (v)

• public void remBead(int i, int j) – der 1 ≤ i ≤ x og 1 ≤ j ≤ y er koordinater; brikke i : j skal fjernes

• public void Step() – skal utføre et steg av spillet

[Det er mest naturlig å definere et steg som en overgang fra en generasjon til neste.]

• public void Display() – som viser aktuell tilstand i datastrukturen.

[Det er opp til deg å velge hvordan du vil vise det – det er sikkert ikke så lurt å innlate seg inn på en grafisk fremstilling. Man kan nøye seg med en liste av tripler (x, y, v) for de posisjonene (x, y) som har v ≠ 0.]

• public void init() – fjerner alle brikker fra brettet og bringer hele datastrukturen til en ‘initiell tilstand’

• public void randomBoard() – som setter opp en del tilfeldige brikker inn i matrisen (med gitt størelse x × y)

[Bruk ‘import java.util.Random’ for å hente en ‘random number generator’. Etter å ha initilisert den ved ‘Random R = new Random()’, vil hvert etterfølgende kall ‘R.nextInt()’ returnere et (pseudo)tilfeldig tall.]

2 Implementasjon

1. Design en algoritme for å spille ‘Life’ 2. Implementer alle bitene i en klasse med grensesnitt beskrevet i 1.

3. Lag så et program som bruker klassen implementert over og tillater en å teste den.