Conway's Game of Life auf einem ATmega32

[Torrentula]

Hallo ihr Programmier-Spezialisten!

Ich möchte Conway's Game of Life auf einem ATmega32 zum laufen bekommen. Zuerst einmal: Was ist das?

Conway's Game of Life ist eine Bevölkerungsimulation. Es gibt n-Zellen auf einem Feld das idealerweise unbegrenzt groß ist. Eine Zelle x hat immer 8 Nachbarn die sie umgeben. Eine Zelle kann sich nur in einem von zwei Stadien befinden: tot oder lebend. Welche Zellen im ersten Zyklus leben und welche nicht werden einfach festglegt.

Das Spiel läuft weiterhin immer in Zyklen ab.

Das Stadium in dem sich eine Zelle befindet wird durch das Befolgen von 4 Regeln bestimmt:

1. Eine tote Zelle mit genau drei lebenden Nachbarn wird in der Folgegeneration (im nächsten Zyklus) neu geboren.

2. Lebende Zellen mit weniger als zwei lebenden Nachbarn sterben in der Folgegeneration an Einsamkeit.

3. Eine lebende Zelle mit zwei oder drei lebenden Nachbarn bleibt in der Folgegeneration lebend.

4. Lebende Zellen mit mehr als drei lebenden Nachbarn sterben in der Folgegeneration an Überbevölkerung.

So nun zu meinem Problem:

Um das ganze ein wenig einzugrenzen möchte ich das "Spielfeld" 3*3 LEDs groß sein lassen. Damit nun aber die Bedingung erfüllt ist, dass jede Zelle 8 Nachbarn hat, kann man sich das auch wie eine 5*5 Matrix vorstellen. Die 9 LEDs befinden sich in der Mitte der 5*5 Matrix und die Felder (Zellen) außen herum befinden sich immer im Status "tot" (deshalb werden diese auch nicht mit LEDs dargestellt).

Nun muss man natürlich für jede der 9 dargestellten Zellen alle 4 Regeln überprüfen. Ich habe mir das so gedacht, dass man die Zellen in einem Array darstellt und dann mit schleifen immer Zelle für Zelle durchlaufen lässt und dies dann am Ende mit den LEDs darstellt.

Wie könnte das Programm aussehen, dass die Stadien der 9 dargestellten Zellen überprüft und die Stadien der Zellen dann eben entsprechend der Regeln auf den Status tot = 0 oder lebend = 1 setzt?

Vielen Dank!

Torrent

[Manf]

Das Spiel lebt von unterschiedlichen Verteilungen und der Dynamik die sich daraus ergibt. Sieh Dir lieber vorher noch einmal Abläufe des Spiels an. Unter 80 x 50 ist es eigentlich kaum interessant eher so 320 x 240. Man kann die Fläche mit totem Rand oder als Toroid ausführen und von Zufallsverteilungen mit 0,5% - 5% lebender Zellen starten.

[Torrentula]

Ja in meinem Fall soll es eine Version mit totem Rand sein.


Unter 80 x 50 ist es eigentlich kaum interessant

Aber nur mal rein von dem Code her wie würde man so eine allgemeine Funktion schreiben?

[BMS]

Hallo,
hab das gerade in Blitzplus (das wird wohl kaum einer kennen^^) programmiert und es läuft für ein 100x75-Feld. (Könnte auch eine exe daraus erzeugen falls erwünscht)


Graphics 400,300,16,2;Grafikauflösung
SeedRnd MilliSecs();Zufallszahlen

Const width=99
Const height=74
Dim bit(width,height) ;Bitfeld
Dim alt(width,height) ;Backup

; ein paar Teilchen aussäen
For c=0 To 500
bit(Rand(1,width-1),Rand(1,height-1))=1
Next

;Schleife
Repeat

Cls

Color 255,255,255
;Alle Positionen durchgehen
For a=1 To width-1
For b=1 To height-1
;in andere Matrix kopieren
alt(a,b)=bit(a,b)
;Nachbarn checken
anz=0
anz=anz+alt(a-1,b-1)+alt(a,b-1)+alt(a+1,b-1)
anz=anz+alt(a-1,b )+ +alt(a+1,b )
anz=anz+alt(a-1,b+1)+alt(a,b+1)+alt(a+1,b+1)
;Wiedergeburt
If anz=3 And bit(a,b)=0 Then bit(a,b)=1
;Einsamkeit
If anz<2 And bit(a,b)=1 Then bit(a,b)=0
;bleibt am Leben
If (anz=2 Or anz=3)And bit(a,b)=1 Then bit(a,b)=1
;Überbevölkerung
If anz>3 Then bit(a,b)=0
Next
Next

;Anzeige
For a=0 To width
For b=0 To height
If bit(a,b)=1 Then Rect 4*a,4*b,4,4
Next
Next

Color 255,0,0
Text 0,0,"Beenden mit ESC"

;Wartezeit
Delay 100

Flip

Until KeyHit(1) ;ESC

End

Grüße, Bernhard

[Torrentula]

Eigentlich meinte ich ein Programm in der Sprache C :D

[BMS]

das lässt sich leicht portieren ;) Es geht ja erst mal nur um die prinzipielle Vorgehensweise.
Ein Bitfeld erzeugen, zufällige Punkte setzen, Backup vom Bitfeld erzeugen, im Backup für jeden Punkt die Anzahl der aktiven Nachbarn bestimmen und dann die Aktion wählen (ins urspr. Bitfeld eintragen), anzeigen.

[Torrentula]

Jo hast recht macht für mich einen Sinn dein Code. Ne exe von dem Spiel zu sehen wäre auch interessant :)

Wie hast du in diesem Fall den toten Rand deklariert? In C würde ich das in einem Array vordefinieren z.B. Feld[0][0]=0;

P.S.: erinnert mich irgendwie an Basic dieses Blitzplus

[BMS]

Hallo,
hab jetzt eine .exe aus dem Code erstellt und gepackt (siehe Anhang). Beenden mit ESC ;)

Zu dem toten Rand: Meine Matrix ist von Anfang an mit Nullen gefüllt. Ich lasse danach aber nicht alle Punkte durchgehen, sondern nur von 1 bis width-1 bzw. 1 bis height-1. Damit bleibt an jedem Rand 1 Position unbeachtet.
Diese Punkte gelten schon als Nachbar, werden aber nie aktiv. Hat auch den Vorteil, dass ich keine ungültigen Lesezugriffe bekomme, wenn ich z.B. von einem Bit in Spalte 0 noch den linken Nachbar (das wäre -1) prüfen wollte, weil ich ja eh erst ab Spalte 1 einlese.

Blitzplus ist ein Basic-Dialekt, die ursprüngliche Version hieß Blitzbasic und war für die Spieleprogrammierung gedacht. Die Weiterentwicklung von Blitzbasic war eben Blitzplus (mit GUI) und Blitz3D (3D halt). Das neueste heißt Blitzmax.

Grüße, Bernhard

[Torrentula]

Sieht cool aus dein Programm!

ok ich habe das jetzt mal versucht umzuschreiben soweit noch keine Probleme mit den Schleifen und allem. Nun aber:

Was stellen die Leerzeichen hier dar:

anz=anz+alt(a-1,b )+ +alt(a+1,b )

[BMS]

Die Leerzeichen haben keine Bedeutung, dient nur der Übersichtlichkeit.
Ein logisches AND in C geht mit && (ja, zwei mal!) , das brauchst du hier

Der Vollständigkeit halber:
Bitweises AND geht mit & (nur eins) , das brauchst du hier aber nicht

[Torrentula]

Mein Code sieht jetzt so aus:


#include <stdlib.h>
#include <avr/io.h>
#include "rn-control.h"

#define width 5 // Breite des Spielfelds
#define height 5 // Höhe des Spielfelds

int bit[width][height]; // Bitfeld
int alt[width][height]; // Backup

int main(void){

//#######################Initialisierungen########## #############

// Deklarieren der Input/Output-Pins

//################################################## #############

int a;
int b;

bit[2][2] == 1;

while(1){
for (a = 1; a <= (width-1); ++a){
for (b = 1; b <= (height-1); ++b){
// in andere Matrix kopieren
alt[a][b] = bit[a][b];

// Nachbarn Checken

int anz = 0;
anz = anz + alt[a-1][b-1]+alt[a][b-1]+alt[a+1][b-1];
anz = anz + alt[a-1][b] + alt[a+1][b];
anz = anz + alt[a-1][b+1] + alt[a][b+1] + alt[a+1][b+1];

// Stadien bestimmen

// Wiedergeburt
if (anz == 3){
if (bit[a][b] == 0){
bit[a][b] = 1;
}
}
// Einsamkeit
if (anz < 2){
if(bit[a][b] == 1) {
bit[a][b] = 0;
}
}

// bleibt am Leben
if (anz == 2){
if (bit[a][b] == 1){
bit[a][b] = 1;
}
}

// bleibt am Leben
if (anz == 3){
if (bit[a][b] == 1){
bit[a][b] = 1;
}
}

// Überbevölkerung
if (anz > 3){
bit[a][b] = 0;
}


}
}

// Ausgebeben

for (a = 0; a = width; ++a){
for (b = 0; b = height; ++b){
if ( bit[a][b] == 1){

}
}
}

}
return 0;
}


Da müssen jetzt halt noch die Pindefinitionen rein. Wie kann ich das dann Ausgeben dass er mir auch die LED anschaltet, die im Spielfeld 1 ist?
Am besten wahrscheinlich einfach if-schleifen die abfragen, wann welches Feld an ist und dementsprechend die LEDs einschaltet...

[BMS]

Ein paar if-Abfragen dürften hier das einfachste sein.
Die letzten zwei Schleifen passen nicht wegen a=width, das sollte eher a<=width oder a<width heißen, das wirst du aber bzgl. der Ausgabe sowieso in if umbauen.
Noch etwas: Zu Beginn hast du nur die mittlere LED auf 1 gesetzt, die wird beim ersten Schritt einfach an Einsamkeit ausgehen ;) Da musst du schon ein paar mehr setzen!

Die Variablen a und b kannst du als unsigned char machen, das spart Speicherplatz.
Bei den Bitfeldern könnte eventuell bool[width][height] klappen.

[Torrentula]

Au stimmt :D

Vielen Dank!

[Torrentula]

So ich habe jetzt die Pindefinitionen drin.

Bin in der zwischenzeit übrigens auf einen ATmega8 umgestiegen.

Der Code sieht im Moment so aus. Irgendwie kann ich keine Veränderung der LED-Stadien sehen. Auch die mittlere LED, die im Seed definiert ist, leuchtet nicht.


#include <stdlib.h>
#include <avr/io.h>
#include <util/delay.h>


#define width 5 // Breite des Spielfelds
#define height 5 // Höhe des Spielfelds

int bit[width][height]; // Bitfeld
int alt[width][height]; // Backup

void LED(unsigned char a, unsigned char b){

if (a == 1 && b == 1){
PORTB |= (1<<PB3);
}
if (a == 1 && b == 2){
PORTB |= (1<<PB4);
}
if (a == 1 && b == 3){
PORTB |= (1<<PB5);
}
if (a == 2 && b == 1){
PORTC |= (1<<PB0);
}
if (a == 2 && b == 2){
PORTC |= (1<<PB1);
}
if (a == 2 && b == 3){
PORTC |= (1<<PB2);
}
if (a == 3 && b == 1){
PORTC |= (1<<PB3);
}
if (a == 3 && b == 2){
PORTC |= (1<<PB4);
}
if (a == 3 && b == 3){
PORTC |= (1<<PB5);
}

}

int main(void){

//#######################Initialisierungen########## #############

DDRC = 0xFF;
DDRB = 0xFF;

//################################################## #############

unsigned char a;
unsigned char b;

bit[2][1] = 1; // Seed
bit[2][2] = 1;
bit[2][3] = 1;


while(1){
for (a = 1; a <= (width-1); ++a){
for (b = 1; b <= (height-1); ++b){
// in andere Matrix kopieren
alt[a][b] = bit[a][b];

// Nachbarn Checken

int anz = 0;
anz = anz + alt[a-1][b-1]+alt[a][b-1]+alt[a+1][b-1];
anz = anz + alt[a-1][b] + alt[a+1][b];
anz = anz + alt[a-1][b+1] + alt[a][b+1] + alt[a+1][b+1];

// Stadien bestimmen

// Wiedergeburt
if (anz == 3){
if (bit[a][b] == 0){
bit[a][b] = 1;
}
}
// Einsamkeit
if (anz < 2){
if(bit[a][b] == 1) {
bit[a][b] = 0;
}
}

// bleibt am Leben
if (anz == 2){
if (bit[a][b] == 1){
bit[a][b] = 1;
}
}

// bleibt am Leben
if (anz == 3){
if (bit[a][b] == 1){
bit[a][b] = 1;
}
}

// Überbevölkerung
if (anz > 3){
bit[a][b] = 0;
}


}
}

// Ausgeben

for (a = 0; a <= width; ++a){
for (b = 0; b <= height; ++b){
if (bit[a][b] == 1){
LED(a, b);
}
}
}

_delay_ms(100);

}
}


Vielleicht ein brutal einfacher Fehler, find ihn aber gerade nicht...

Hoffe ihr könnt mir helfen :D

[sternst]

Ich sehe zwei grundlegende Fehler.

1)
Der Algorithmus kann so nicht funktionieren. Gleichzeitiges Kopieren und Auswerten geht nicht. Spiel deinen Code doch einfach mal mit alt komplett Null und bit mit der Seed Zeile für Zeile durch.

2)
Ich sehe nur, dass LEDs eingeschaltet werden. Wo werden sie wieder ausgeschaltet, wenn ein Feld Null ist?

[Torrentula]

Spiel deinen Code doch einfach mal mit alt komplett Null und bit mit der Seed Zeile für Zeile durch.

Wie meinst du das genau? Den seed in bit einfügen und durchlaufen lassen und dann alt auf 0 setzen und laufen lassen und am Ende kopieren?

[sternst]

Wie meinst du das genau?Ich meine damit, dass du selber mal den Prozessor spielen sollst, um zu merken, woran dein Algorithmus krankt. Du malst dir zwei Felder auf (alt und bit), alt enthält zu Anfang nur Nullen und bit den Seed. Und jetzt gehst du deinen Sourcecode Zeile für Zeile durch und vollziehst die Schritte auf deinem Blatt nach.

[Calis007]

Ich seh das genauso wie sternst. Der Algorithmus hat einen groben Bug ;)
Aber irgendwie kommt mir vor, hier laesst jemand seine Hausaufgaben machen, daher auch von mir nur der Tipp, es mal per Hand nachzuvollziehen.(edit: sehe gerade, dass hier ein alter Thread wiederbelebt wird, daher unwahrscheinlich ;)
Falls ich mich irre, dann bitte ernsthaft wenigstens ueber 6x6 (+Rand) nachdenken. Auf 3x3 gibts nicht viel Spannendes zu sehen ausser dem ewig lebenden 2x2-Block und der oszillierenden 3x1-Linie.