Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - Game of Life - alle Zellen sterben


galagher - Sa 31.05.14 07:55
Titel: Game of Life - alle Zellen sterben
Hallo!

Ich programmiere gerade an einem Game of Life. Bin noch ganz am Anfang, und schon da ist mir etwas unklar:
Zitat:
Lebende Zellen mit weniger als zwei lebenden Nachbarn sterben in der Folgegeneration an Einsamkeit.
aus: http://de.wikipedia.org/wiki/Game_of_Life#Conways_Herausforderung

Es gibt doch zwangsläufig immer Zellen, die weniger als zwei lebenden Nachbarn haben: Zunächst jene, die von vornherein keine lebenden Nachbarn hatten, diese sterben also. Da dann jedoch auch jene Zellen, die die soeben gestorbenen als Nachbarn hatten, nun auch keine lebenden Nachbarn mehr haben, sterben diese auch usw. Schon nach 1 Durchlauf des Arrays ist dieses nur noch mit toten Zellen gefüllt.

Konkret: Das Array represäntiert eine quadratische Fläche, auf der dann gezeichnet wird. Egal, wie ich die Zellen nun setze, es wird ja immer Zellen geben, die an einer oder mehreren Seiten an keine anderen angrenzen.

Wie mache ich das richtig?


Horst_H - Sa 31.05.14 08:11

Hallo,

arbeitest Du auch mit ( im übertragendem Sinne ) zwei Spielbrettern, das alte ergibt ein neues.Die neue Generation kommt doch sonst der alten in die Quere und die Regeln stimmen nicht.
Ein leeres Feld mit 2/ 3 Nachbarn wird doch lebendig, es müssen doch irgendwie Kinder da sein ;-)

Gruß Horst


galagher - Sa 31.05.14 08:42

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
arbeitest Du auch mit ( im übertragendem Sinne ) zwei Spielbrettern, das alte ergibt ein neues.Die neue Generation kommt doch sonst der alten in die Quere und die Regeln stimmen nicht.

Momentan durchlaufe ich das Array ganz einfach auf die "klassische" Art:

Delphi-Quelltext
1:
2:
3:
4:
for x := 0 to ...
  for y := 0 to ...
  begin
    if aBoard[x, y] = ...

Was muss ich machen? Verwende ich zwei Arrays und wie?


Horst_H - Sa 31.05.14 09:06

Hallo,

Du kannst zu Beginn mit zwei kompletten Feldern arbeiten.Alt-,NeuFeld.
Du verarbeitest die Daten von Alt- auf NeuFeld und am Ende kopierst Du das neue auf das alte.
Das geht erst einmal am schnellsten.Dann das bestimmen der Anzahl der Nachbarn dauert am längsten.

Dann kannst Du Zeiger auf zwei Felder nehmen und anschließend Zeiger tauschen.
Dann kann man nur 3 alte Zeilen ( 0,1( wird gerade bearbeitet),2) vorhalten ( wieder mit Zeigern ) und kopiert immer eine alte Zeile hinein.Und arbeitet von oben nach unten ( wie im Speicher ). Dann tauscht man nur die Zeiger (1->0, 2->1) kopiert nur die nächste Zeile als Zeile 2 ( Zeiger von ehemals 0 ).
Man kann immer viel machen ;-)

Gruß Horst
P.S.

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
const
//Hat2Oder3Nachbarn arbeitet immer mit aBoard entweder 0 oder 1

for x := 0 to ...
  for y := 0 to ...
    bBoard[x, y] = Hat2oder3Nachbarn(x, y); 
//Kopieren
  aBoard := bBoard;


Delphi-Laie - Sa 31.05.14 09:13

user profile icongalagher hat folgendes geschrieben Zum zitierten Posting springen:
Was muss ich machen?


Horsts Rat mit den beiden Spielbrettern umsetzen.


user profile icongalagher hat folgendes geschrieben Zum zitierten Posting springen:
Verwende ich zwei Arrays und wie?


Zum Beispiel. Oder Du verwendest ein dreidimensionales Array, bei dem eine Dimension nur die Größe zwei hat.

Es gibt auch Game-of-life-Projekte in den Delphiforen. Einfach mal suchen, finden, downloaden und die - hoffentlich und meistens vorhandenen - Quelltexte durchstöbern und daraus lernen.


Horst_H - Sa 31.05.14 09:25

Hallo,

da war mal was vor 5 Jahren...
http://www.entwickler-ecke.de/viewtopic.php?t=89387&highlight=game+life , dann soll es mittlerweile weiter gehen.
p196 habe ich auch mittlerweile auf 10 Sekunden ( 32 Bit Assembler ( ohne SSE ) , aber ich habe noch ein Register über. Den Fehler bei der 64 Bit Version ( 5 Sekunden ) habe ich noch nicht gefunden ( nach 10000 Stellen tritt der auf) ).
Du siehst, dran bleiben lohnt sich :D

Gruß Horst


galagher - Sa 31.05.14 11:06

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Du kannst zu Beginn mit zwei kompletten Feldern arbeiten.Alt-,NeuFeld.
Du verarbeitest die Daten von Alt- auf NeuFeld und am Ende kopierst Du das neue auf das alte.
Ich kopiere also laufend auf das neue, und am Ende wird das neue Array quasi das alte?
Pseudocode: AltFeld := NeuFeld; NeuFeld.Clear;

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Dann kannst Du Zeiger auf zwei Felder nehmen und anschließend Zeiger tauschen.
Dann kann man nur 3 alte Zeilen ( 0,1( wird gerade bearbeitet),2) vorhalten ( wieder mit Zeigern ) und kopiert immer eine alte Zeile hinein.Und arbeitet von oben nach unten ( wie im Speicher ). Dann tauscht man nur die Zeiger (1->0, 2->1) kopiert nur die nächste Zeile als Zeile 2 ( Zeiger von ehemals 0 ).
Man kann immer viel machen ;-)

Gruß Horst
P.S.

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
const
//Hat2Oder3Nachbarn arbeitet immer mit aBoard entweder 0 oder 1

for x := 0 to ...
  for y := 0 to ...
    bBoard[x, y] = Hat2oder3Nachbarn(x, y); 
//Kopieren
  aBoard := bBoard;

Hier steige ich jetzt aus...

Geht das nicht einfacher, mit einem zweidimensionalem Array? :(


Horst_H - Sa 31.05.14 11:18

Hallo,

Gute Güte, ich ging von 2-dimimensionalen Feldern aus...

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
const
  xMax = 10;
  yMax = 10
//Feld um eine Zeile,Spalte  dovor und dahinter erweitern, das lässt sich einfeacher bearbeiten, 
//ohne Sonderregeln für den Rand
type
  tboard = array[0..yMax+1,0..xMax+1of boolean;//0..1;

var
  aBoard,bBoard : tboard;

...

Du musst nur das erste Feld löschen, das andere wird ja immer komplett überschrieben.

Gruß Horst.


galagher - Sa 31.05.14 12:43

user profile iconHorst_H hat folgendes geschrieben Zum zitierten Posting springen:
Gute Güte, ich ging von 2-dimimensionalen Feldern aus...

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
const
  xMax = 10;
  yMax = 10
//Feld um eine Zeile,Spalte  dovor und dahinter erweitern, das lässt sich einfeacher bearbeiten, 
//ohne Sonderregeln für den Rand
type
  tboard = array[0..yMax+1,0..xMax+1of boolean;//0..1;

var
  aBoard,bBoard : tboard;

...

Du musst nur das erste Feld löschen, das andere wird ja immer komplett überschrieben.

Gruß Horst.
Ich verstehe gar nichts!

Das Prinzip ist doch:
- Array1 durchlaufen: Prüfe in Array1 auf Nachbarn, schreibe for ... Array1[x, y] := Array2[x, y]
- Nach dem kompletten Durchlauf schreibe for ... Array2[x, y] := Array1[x, y]
- Zeichne das aktuelle Array1
- Neuer Durchlauf

Oder?


Horst_H - Sa 31.05.14 12:52

Hallo,


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
Program Gol;
// Game of life als "Gol.dpr" speichern
{$Apptype Console}
uses
  crt;

const
  colMax = 62;
  rowMax = 14;
//Feld um eine Zeile,Spalte  davor und dahinter erweitern,
//das laesst sich einfacher bearbeiten, ohne Sonderregeln für den Rand
type
  tboard = array[0..rowMax+1,0..colMax+1of byte;//0..1;
  tTripel = array[0..2of Byte;
  tpTripel = ^tTripel;
var
  aBoard,bBoard : tboard;
  gblGenCount : integer;

function Survive(col,row:integer):byte;
var
  sum: integer;
  pTrip:tpTripel;
  alive :boolean;
begin
  dec(col);// Eine Spalte zurueck -1,0,1 -> 0,1,2
  // Nachbarn zaehlen
  // Zeile darueber
//  sum := aBoard[row-1,col-1]+aBoard[row-1,col]+aBoard[row-1,col+1];
  pTrip := @aBoard[row-1,col];
  sum :=     pTrip^[0]+pTrip^[1]+pTrip^[2];
  // Zeile
  pTrip := @aBoard[row,col];
  alive := pTrip^[1]<>0;
  sum := sum+pTrip^[0]+         +pTrip^[2];
  // Zeile darunter
  pTrip := @aBoard[row+1,col];
  sum := sum+pTrip^[0]+pTrip^[1]+pTrip^[2];
   
  IF sum = 3 then
    survive := 1
  else
  Begin
    IF alive AND (sum = 2)  then
      survive := 1
    else
     survive := 0;
  end;
end;

procedure NextGen;
var
  col,row: integer;
begin
  For row := 1 to rowMax do
    For col := 1 to colMax do
      bBoard[row,col] := Survive(col,row);
  aBoard := bBoard;
  inc(gblGenCount);
end;

procedure PrintGen;
const
  cChar: array[0..1of char = (' ','#');
var
  col,row: integer;
begin
  gotoxy(1,1);
  writeln(gblGenCount:10);
  For row := 1 to rowMax do
  begin
    For col := 1 to colMax do
      write(cChar[aBoard[row,col]]);
    writeln;
  end;
end;

var
  col,row : integer;
begin
  randomize;
  clrscr;
  fillchar(aBoard,SizeOf(aBoard),#0);

  For row := 1 to rowMax do
    For col := 1 to colMax do
      aBoard[row,col]:= Byte(random>0.5);
  repeat
    PrintGen;
    NextGen; 
    delay(100);
  until keypressed;
end.


Vielleicht ist das einleuchtender.

Gruß Horst
P.S.
Die Sonne scheint übrigens...


galagher - So 01.06.14 10:55

Habe das jetzt mit nur einem Array realisiert, allerdings expanderiert die Welt fast jedesmal, es stellt sich meist kein Gleichgewicht ein. Manchmal friert die Welt auch einfach ein. Mal sehen...


trm - So 01.06.14 11:57

Das Problem bei nur EiNEM Array ist, dass die Abbildung nicht funktioniert, da Du nach dem ersten Durchlauf und Änderung einer Zelle einen unbestimmten Zustand hst, da die Änderung direkt in das aktuelle Spielfeld geschrieben wurde.

Wie willst Du nun also vergleichen, wie der iST-Zustand vom kompletten Feld war, um die folgenden Zellen auf 0 oder 1 zu setzen?


Beispiel:

Original-Feld:

0-0-1-1-0-0
0-1-1-1-0-0
0-0-0-0-0-0

Erster Durchlauf des kompletten Feldes in Deinem Beispiel ergibt:

0-1-1-1-0-0
0-1-1-1-0-0
0-0-1-1-0-0

Es sollte aber so aussehen:

0-1-1-1-0-0
0-1-1-1-0-0
0-0-1-0-0-0


Die letzte untere rechte 1 ist bei Dir nicht korrekt, weil Du das Originalfeld inclusive Deiner Änderung als Referenz heranziehst. Daher benötigst Du ein Lese - und ein Änderungsfeld.

Nach dem Ändern kannst Du das Feld in das nur-lesen-Feld kopieren und das Ändernfeld kannst Du nun neu beschreiben, musst noch nicht einmal dieses leeren, da es nicht als Referenz benutzt wird.



Ich hoffe, ich habe keinen Logischen Fehler gemacht.


galagher - So 01.06.14 13:05

user profile icontrm hat folgendes geschrieben Zum zitierten Posting springen:
Nach dem Ändern kannst Du das Feld in das nur-lesen-Feld kopieren und das Ändernfeld kannst Du nun neu beschreiben, musst noch nicht einmal dieses leeren, da es nicht als Referenz benutzt wird.

Ich mache das so:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
//atmpBoard ist das Änderungsarray, aBoard das Lesearray
for x := ...
  for y := ...
   atmpBoard[x, y].Cell := aBoard[x, y].Cell;

//Nun die Schleife:
procedure TForm1.Timer1Timer(Sender: TObject);
var
  x, y: Integer;
begin
  for x := ...
    for y := ...
    begin
      if (atmpBoard[x, y].clCell = clDeathCell) then {mach was den Regeln entspr.};
      if (atmpBoard[x, y].clCell = clLivingCell) then {mach was den Regeln entspr.};
    end;

  //Nun das Änderungsfeld ins "richtige" zurückschreiben
  for x := ...
    for y := ...
     aBoard[x, y].Cell := atmpBoard[x, y].Cell;

  //Und nun noch zeichnen
  DrawBoard;
end;

Wohl nicht ganz korrekt so, denn ich merke keinen Unterschied...


galagher - So 01.06.14 14:38

user profile icongalagher hat folgendes geschrieben Zum zitierten Posting springen:
Ich mache das so:
Das ist Unsinn! Ich denke, jetzt hab ich's:
1. Fülle ein zweites Array - nennen wir es Array2 - mit toten Zellen
2. Lies das erste "Original"-Array (Array1) und schreibe in Array2
3. Schreibe von Array2 nach Array1 und zeichne dieses

Jetzt erhalte ich ähnliche Figuren, wie es vielfach zu diesem Thema beschrieben ist: Wandernde, sich drehende usw. Meist jedoch friert die Welt nach einigen Generationen aus.