Spiel des Lebens Feld Programmieren

ojoj321

Hallo,

ich bin grad dabei das "Game of Life" zu programieren.
Wer nicht weiß was das ist:
http://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens

Ich weiß noch nicht wie groß das Feld werden soll (20x20 oder so). Jetzt weiß ich nicht wie ich die Objekte (Gleiter oder andere Objekte) die über den Rand hinausfliegen kontroliert "löschen" soll. Ich kann ja nicht einfach jede Zelle die über den Rand hinausfliegt löschen. Denn wenn dann die erste Zelle vom Gleiter das über den Rand hinausfliegt gelöscht wird, hört der Gleiter auf zu fliegen und die restlichen Zellen bleiben einfach im Feld hängen.
Ich könnte es theoretisch so programmieren, das wenn ein Objekt links rausfliegt einfach am rechten Rand wieder in das Feld reinfliegt.
Die andere Version wäre mir jedoch lieber.

Hoffe ich habs genug verständlich erklärt und jemand hat ne Idee.

LG ojoj321

User1291

Versteh nicht ganz ... Was spricht dagegen, die Repräsentation des Feldes als Matrix zu implementieren, und nur ihre Einträge upzudaten?

SeppJ

Nun, die üblichen Vorgehensweisen sind:
-Randbedingung, dass alle Felder jenseits des Randes tot sind. Das führt dann eben zu Ungenauigkeiten, wenn das Muster gegen den Rand läuft. Genau das ,was du beschreibst. Ist aber sehr einfach zu implementieren.
-periodische Randbedingunen: Was an einer Seite rausgeht, kommt an der anderen Seite rein. Führt dann eben zu Ungenauigkeiten, wenn das Muster zu groß für die Simulationsbox wird. Ist ebenfalls sehr einfach zu implementieren.
-Dynamisches Wachstum der Simulationsbox. So lange genug Speicher da ist, bleibt alles exakt. Ist schon deutlich schwieriger zu implementieren.
-Ganz anderer Lösungsweg: Anstatt das Feld zu speichern, speichert man die Koordinaten der besetzten Felder. So kann man auch ewig weiter machen, so lange der Datentyp für die Koordinaten mitmacht. Ist ganz anders zu implementieren als die "traditionellen" Implementierungen. Du solltest dir zudem noch Gedanken machen über die genaue Datenstruktur. Alle Felder ganz naiv ohne weitere Organisation zu speichern, würde nämlich zu einer sehr aufwändigen Suche nach dem Zustand der Nachbarfeldern führen. Eine sehr interessante Herangehensweise. Aber deiner Frage nach solltest du wohl erst einmal eine der direkteren Implementierungen versuchen, um ein bisschen Erfahrung zu sammeln.

Was davon für dich richtig ist, hängt davon ab, was du genau möchtest und für wie gut du deine Programmierfähigkeiten einschätzt.

mit dem seppj'schen vorschlag, die koordinaten zu speichern, könntest du dann den anzezeigten bereich flexibel umschalten, um zellaktivitäten sichtbar zu machen, die außerhalb des sichtbaren startbereichs hinauswandern.

It0101

Performant und auch leicht zu vergrößern wäre ein Variante in der jedes Feld seine 8 Nachbarn direkt kennt, also quasi mit Verkettungen. So könnte man das Spielfeld relativ einfach vergrößern, hat aber den Nachteil des erheblichen Overheads durch die ganzen Pointer. Oder man macht die Matrix gleich so groß wie man maximal zulässt und arbeitet dann mit Indizierung bei bekannter Breite, Höhe und Position. Hat auch seinen Charme.

Viele Wege führen letztendlich nach Rom. Jede Variante hat ihre Vor- und Nachteile.

Nirvash

Denkbar wäre sicherlich auch eine Baumstruktur. Mir würde da folgendes Format einfallen:

struct cell {
int8_t neighborhood;
struct cell *t;
struct cell *tl;
struct cell *l;
struct cell *dl;
struct cell *d;
struct cell *dr;
struct cell *r;
struct cell *tr;
}

Jenachdem welche Bits in neighborhood gesetzt sind lässt sich beim Objekt bestimmen, ob es Nachbarn besitzt oder nicht. Diese sind über die Pointer erreicher und ergeben durch die Verkettung eine Baumstruktur.

Interessant wird es, wenn im Fortlauf des Spiels sich die Teilbäume vom Wurzelbaum isolieren. Dann müsste jeder Teilbaum wieder als eigenständiger Wurzelbaum betrachtet werden...

Vom Rechenaufwand sicherlich sehr intensiv, gerade in den tieferen Ebenen, wenn mehrere Teilbäume entstehen. Dafür jedoch so lange anwendbar, wie Speicher vorhanden ist.

Je nach gewählter Ausgangsbasis der Zellen könnte der Speicherverbrauch sogar konstant bleiben.

volkard

SeppJ schrieb:

-Dynamisches Wachstum der Simulationsbox. So lange genug Speicher da ist, bleibt alles exakt. Ist schon deutlich schwieriger zu implementieren.
-Ganz anderer Lösungsweg: Anstatt das Feld zu speichern, speichert man die Koordinaten der besetzten Felder. So kann man auch ewig weiter machen, so lange der Datentyp für die Koordinaten mitmacht. Ist ganz anders zu implementieren als die "traditionellen" Implementierungen. Du solltest dir zudem noch Gedanken machen über die genaue Datenstruktur. Alle Felder ganz naiv ohne weitere Organisation zu speichern, würde nämlich zu einer sehr aufwändigen Suche nach dem Zustand der Nachbarfeldern führen. Eine sehr interessante Herangehensweise.

Mir fiel sofort ein, diese beiden Wege zu mischen. Man zerhackt die Welt in z.B. 16x16 große Quadrate und speicher nur die Quadrate, die nicht leer sind.

SeppJ schrieb:

Aber deiner Frage nach solltest du wohl erst einmal eine der direkteren Implementierungen versuchen, um ein bisschen Erfahrung zu sammeln.

Jo, mit 1G Ram kommt man ja schonmal bis 15000 Generationen weit.

SeppJ

@Nirvash: Gefällt mir nicht. Einen Nachteil (Teilung des Musters) hast du schon selber erkannt. Was mir auch nicht gefällt ist der zusätzliche Buchhaltungsaufwand, um Zirkelschlüsse zu verhindern.

alles viel zu kompliziert!
machste einfach

int main(void)
{	
	char* feld;
	unsigned bytes = 1E9;

	feld = malloc(bytes); // speicher reservieren
	if(feld != NULL)
		printf("%s\n", "Juhuu ich habe 1 Gigabyte Speicher für mein Feld reserviert!"); // sich freuen
//... todo ...
	free(feld); // speicher freigeben
	return 0;
}

haste erstmal fett das riesenteil von feld mit rund 31622 x 31622 zellen.
legste koordinatenursprung auf die mitte des fensters und schon kanns losgehen.

ogottogottogott schrieb:

alles viel zu kompliziert!
machste einfach
int main(void)
{	
	char* feld;
	unsigned bytes = 1E9;
	
	feld = malloc(bytes); // speicher reservieren
	if(feld != NULL)
		printf("%s\n", "Juhuu ich habe 1 Gigabyte Speicher für mein Feld reserviert!"); // sich freuen
//... todo ...
	free(feld); // speicher freigeben
	return 0;
}
haste erstmal fett das riesenteil von feld mit rund 31622 x 31622 zellen.
legste koordinatenursprung auf die mitte des fensters und schon kanns losgehen.

gleich 1E9 auf einmal, könnt eng werden. brauchste n coh platz für die liste nämlich!

ojoj321

Ok danke für die ganzen Tipps ich werd einfach mal ein bisschen rumprobieren.