Schwierigkeiten mit Game of Life Algorithmus

[fabiO]

Hallo,

Ich bin zur Zeit dabei, mir mal das allseits beliebte Game of Life anzuschauen.
Ich weiß, dass es schon eine Menge Algorithmen gibt, doch hat mir keiner von denen, die ich bisher gesehen habe geholfen.

Mein Problem ist simpel: Die Anzahl der lebenden Nachbarfelder wird richtig ermittelt, doch erfolgt die berechnung des neuen Spielfeldes fehlerhaft.
Hier einmal mein Code:

( alt ist global deklariert als Array[1..50,1..50] of Integer)

Delphi-Quellcode:

function nachbarn(i,k : Integer):Integer;
var a,b,c : Integer;
begin
  c := 0;
  for a:=i-1 to i+1 do
    for b:=k-1 to k+1 do
      if ((a<>i) OR (b<>k)) AND (alt[a,b] = 1) then inc(c);

  nachbarn := c;

end;

procedure Tform1.ausgeben;
var i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do
      Stringgrid1.Cells[i-1,k-1] := IntToStr(alt[i,k]);
end;

procedure TForm1.StringGrid1SelectCell(Sender: TObject; ACol,
  ARow: Integer; var CanSelect: Boolean);
begin
  alt[ACol+1,ARow+1] := 1;
  ausgeben;
  xselect := ACol+1;
  yselect := ARow+1;
end;

procedure TForm1.StringGrid1DrawCell(Sender: TObject; ACol, ARow: Integer;
  Rect: TRect; State: TGridDrawState);
var f : TColor;
begin
  if Stringgrid1.Cells[ACol,ARow] = '1'
    then f := clBlue
  else f := clwhite;

  Stringgrid1.Canvas.Brush.Color := f;
  Stringgrid1.Canvas.FillRect(Rect);
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do
    begin
      if (alt[i,k] = 1) AND (nachbarn(i,k) <> (2 OR 3))
        then alt[i,k] := 0;
      if (alt [i,k] = 0) AND (nachbarn(i,k) = 3)
        then alt[i,k] := 1;

  ausgeben;
end;

procedure TForm1.Button2Click(Sender: TObject);
begin
  if (xselect and yselect) < 1 then
    Showmessage('Keine Zelle ausgewählt!')
  else
    Showmessage('Lebende Nachbarn: ' + IntToStr(nachbarn(xselect,yselect)));
end;

Wähle ich zum Beispiel ein Feld des Stringgrids aus und drücke den Button2, so gibt er mir die richtige Anzahl der lebenden Nachbarn aus.

Beispiel: [o] = tot, [x] = lebend

[o][o][o][o][o]
[o][x][x][x][o]
[o][o][o][o][o]

nach einem Zyklus sollte es so aussehen:

[o][o][x][o][o]
[o][o][x][o][o]
[o][o][x][o][o]

Bei mir sieht es aber so aus:

[o][o][o][o][o]
[o][o][o][o][o]
[o][o][o][o][o]

Kann mir jemand sagen, wieso das nicht klappt?
Und noch etwas, wie verfährt man mit Randfeldern ?
Danke schonmal im Vorraus

gruß fabio

[Grishnak]

Wenn ich deinen Code richtig lese, dann prüfst du für jede Zelle, wieviele Nachbarn sie hat und änderst entsprechend ihren zustand (lebendig/tod). D.h. du änderst sie direkt ab und bei der Überprüfung weiterer Zellen wird ihr neuer Zustand geprüft und nicht ihr alter.

Ich denke du solltest ein zweites temporäres Array anlegen, und darin den jeweils neuen Zustand der Zellen übernehmen und erst am Ende (wenn alle Zellen überprüft wurden) seinen kompletten Inhalt in das ursprüngliche Array übertragen.

Zu Randfeldern: Da gibt es mWn zwei Möglichkeiten: a) Randfelder sind grundsätzlich tod; b) es gibt keine Randfelder, sondern das Feld ist umlaufend (z.B. die Nachbarn von [3;1] sind dann [2;50], [3;50], [4;50], [2;1], [4;1], [2;2], [3;2] und [4;2].

[monta]

Bin zur Zeit auch dabei etwas ähnliches zu programmieren. Ich schließ mich Grishnak an.

Du musst ein temporäres Array nehmen, da du ja sonnst die falsche mit der neuen Nachbarschaft weiterrechnest.

Was die Ränder betrifft seiht es deutlich schöner aus, wenn die Welt umlaufend ist, ist allerdings auch etwas schwieriger.

[fabiO]

Hallo,

Danke für den Tipp mit dem 2ten Feld.
Ich hab das mal so realisiert:

(neu ist wie alt ein Array[1..50] of Integer)

Delphi-Quellcode:

procedure Tform1.ausgeben;
var i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do
      Stringgrid1.Cells[i-1,k-1] := IntToStr(alt[i,k]);
end;

procedure Tform1.einlesen;
var i,k : Integer;
begin
  for i := 1 to 50 do
    for k := 1 to 50 do
      alt[i,k] := neu[i,k];
end;

procedure TForm1.Button1Click(Sender: TObject);
var i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do
    begin
      if (alt[i,k] = 1) AND (nachbarn(i,k) <> (2 or 3))
        then neu[i,k] := 0;
      if (alt [i,k] = 0) AND (nachbarn(i,k) = 3)
        then neu[i,k] := 1;
    end;

  einlesen;
  ausgeben;
end;

Funktionieren tuts nun fast richtig, denn nun geschiet folgendes:

Beispiel: [o] = tot, [x] = lebend

[o][o][o][o][o]
[o][x][x][x][o]
[o][o][o][o][o]

nach einem Zyklus sollte es so aussehen:

[o][o][x][o][o]
[o][o][x][o][o]
[o][o][x][o][o]

Bei mir sieht es aber so aus:

[o][o][x][o][o]
[o][o][o][o][o]
[o][o][x][o][o]

Das heisst, es wird immernoch nicht richtig umgesetzt...
Wieso funktioniert es immernoch nicht ?
Und desweiteren, wie sag ich dem Programm, dass das Feld umlaufend sein soll?

gruß fabiO

[monta]

Hast du schon probiert, ob es funktioniert, wenn du auch die überlebenden Zellen neu schreibst:

Delphi-Quellcode:

if (alt [i,k] = 0) AND (nachbarn(i,k) = 2)
        then alt[i,k] := 1;

[fabiO]

Mhh dein Code, mit der überlebenden Zelle, leuchtet nich so ganz ein!

Delphi-Quellcode:

if (alt [i,k] = 0) AND (nachbarn(i,k) = 2)
        then alt[i,k] := 1;

Dass würde ja beudeten, dass ein Feld, das vorher tot war und 2 lebende Nachbarn besitzt, nun lebendig ist, und das wäre ja gegen die Spielregeln.

Das mit den überlebenden habe ich mal so eingearbeitet:

Delphi-Quellcode:

procedure TForm1.Button2Click(Sender: TObject);
var i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do
    begin
      if (alt[i,k] = 1) AND (nachbarn(i,k) = (2 or 3))
        then neu[i,k] := 1
        else neu[i,k] := 0;

      if (alt [i,k] = 0) AND (nachbarn(i,k) = 3)
        then neu[i,k] := 1;
    end;

  einlesen;
  ausgeben;
end;

Also falls eine Zelle lebt (=1) und sie 2 ODER 3 lebende Nachbarn hat, lebt sie weiter (:=1).
Andernfalls stirbt sie (:=0).

Falls eine Zelle tot ist und genau 3 lebende Nachbarn hat, wird sie belebt (:=1).

Aber trotzdem erhalte ich dieses Bild:

[o][o][x][o][o]
[o][o][o][o][o]
[o][o][x][o][o]

d.h. es wird immernoch nicht richtig umgesetzt...?!?

[alzaimar]

Zitat von fabiO:

Delphi-Quellcode:

...
      if (alt[i,k] = 1) AND (nachbarn(i,k) = (2 or 3))
...

Wirklich so implementiert? Oder ist das Pseudocode? Du vergleichst, ob die Anzahl der Nachbarn gleich dem Ergebnis des Terms '2 or 3' ist.
Denn (2 or 3) ergibt 10 or 11 (binär) ergibt 11(binär) also 3. Nur wenn ich 3 Nachbarn habe, bleibe ich am Leben. Der Mittlere würde demnach auch sterben, denn er hat 2 Nachbarn. Genau das passiert bei Dir aber.

Du müsstest das umformulieren:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var n,i,k : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do begin
      n := Nachbarn (i,k);
      if (alt[i,k] = 1) AND not (n in [2,3]) then // <---
        neu[i,k] := 0;
      if (alt [i,k] = 0) AND (n = 3) then 
        neu[i,k] := 1;
    end; 
...
end;

Dann sollte alles so funktionieren.

[fabiO]

Danke für deine Antwort!
Es funktioniert nun, jedoch musste ich noch 2 extra if-Anweisungen mit einbinden, weil es nur mit deinem code immernoch das falsche ergebniss lieferte!
Ich habe nun folgendes stehen:

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var i,k,n : Integer;
begin
  for i := 1 to high(alt) do
    for k := 1 to length(alt) do begin
      n := Nachbarn (i,k);
      if (alt[i,k] = 1) AND not (n in [2,3]) then
        neu[i,k] := 0
      else if (alt[i,k] = 1) AND (n in [2,3]) then
        neu[i,k] := 1;
      if (alt [i,k] = 0) AND (n = 3) then
        neu[i,k] := 1
      else if (alt [i,k] = 0) AND not (n = 3) then
        neu[i,k] := 0;
    end;

  einlesen;
  ausgeben;
end;

Jedoch besteht mein Problem mit den Randfeldern immernoch. Ich habe keine Vorstellung, wie ich Delphi sagen soll, dass wenn ein Feld den x-Wert oder y-Wert 1 oder 50, oder auch beides, hat, dass es dann beim überschreiten der Feldgrenzen auf die gegenüberliegende Seite wechseln soll.

Ich hatte mal folgendes probiert:

Delphi-Quellcode:

if (k = 1) then
    begin
      if alt[i+1,k] = 1 then inc(c);
      if alt[i+1,k+1] = 1 then inc(c);
      if alt[i,k+1] = 1 then inc(c);
      if alt[i-1,k+1] = 1 then inc(c);
      if alt[i-1,k] = 1 then inc(c);
      if alt[i-1,50] = 1 then inc(c);
      if alt[i,50] = 1 then inc(c);
      if alt[i+1,50] = 1 then inc(c);
    end;

Nur ist diese Variante ja nicht gerade sehr effizient, weil es einfach nur Zeile für Zeile aufgeschrieben wird, was man natürlich auch machen könnte

Wie Grishnak in seinem Post (#2) schon bemerkte:

Zitat von Grishnak:

Zu Randfeldern: (...) es gibt keine Randfelder, sondern das Feld ist umlaufend (z.B. die Nachbarn von [3;1] sind dann [2;50], [3;50], [4;50], [2;1], [4;1], [2;2], [3;2] und [4;2].

Nur wie mache ich das ? Wäre echt dankbar für einen effizienteren Denkanstoß als der Meinige

gruß fabiO

[alzaimar]

Deine Funktion zum Zählen der Nachbarn ist doch fast schon perfekt, nur musst Du eben dafür sorgen, das nur legale Felder gezählt werden. Du kannst dazu aber der Einfachheit halber dein Feld etwas größer machen und die zusätzlichen Randfelder einfach leer lassen:

Delphi-Quellcode:

Var
  LifeWelt : Array [-1..51,-1..51] Of Integer; // bzw. Byte, reicht ja

So, nun zur Routine, die die nächste Generation ausrechnet. Ob eine Zelle stirbt oder geboren wird, hängt eindeutig von der Anzahl der Nachbarn ab, also mach es doch so:

Delphi-Quellcode:

For i:=0 to 50 do
  For j := 0 to 50 do
    Case Nachbarn (i,j) of
      2 :  // Zwei Nachbarn: Die Zelle überlebt
        If alt[i,j]=1 then neu[i,j] := 1 else neu[i,j]:=0;
      3 : // Drei Nachbarn: Die Zelle überlebt bzw. wird neu geboren, also...
        neu[i,j] := 1; // lebt sie jetzt in jedem Fall
     else 
       neu[i,j] := 0;  // Alle anderen Fälle...
   End;

[Nikolas]

Zitat:

Nur wie mache ich das ? Wäre echt dankbar für einen effizienteren Denkanstoß als der Meinige Smile

Wenn du Zelle x/y in einem [0..X]*[0..Y] Feld untersuchen willst, findest du so alle Nachbarn:

Delphi-Quellcode:

 // nach rechts:
 if x<X then x_neu:=x+1 else x:=0;
 // nach links:
 if x>0 then x_neu:= x-1 else x:= X;

 // Nach oben:
 if 0<y then y_neu:=y-1 else y:=Y;
 // Nach unten:
 if y<Y then y_neu:=y+1 else y:=0;

Schau dir vielleicht mal auf Luckies Homepage seine Version an.