Hallo, für die programmierung des "Game of Life" muss ich unbedingt die Rechenzeit für die Neuberechumng des Feldes runter bekommen. Das Feld hat 800 x 600 Bytes und für die Berechnung sind 800 x 600 x 8 Betrachtungen nötig. Da der größte teil des Feldes aber leer ist brauche ich einen schnellen Algorithmus, um nur die Bereiche heraus zu fischen, wo sich "Zellen" befinden. leider "sieht" die CPU ja nicht das ganze Feld von oben so wie ich sondern muss sich jede einzelne Zelle anschauen ob da etwas ist. es gibt ja auch fertige Programme die quasi in Echtzeit laufen trotz riesieger Felder. Gibt es da irgendetwas? Zb aus der Bildverarbeitung?
du weißt doch von der vorherigen Berechnung welche Felder belegt sind un damit auch welchen Bereich du als nächstes betrachten musst
Walter schrieb: > du weißt doch von der vorherigen Berechnung welche Felder belegt Das "Array" weiss es.... nur muss das immer wieder neu durchsucht werden, oder aber ich lege noch eines an, wo nur die Veränderungen drin sind, d.h. viele Zeiger die nur angeben wo was ist.
Du kannst um alle nicht leeren Felder einen rechteckigen Kasten ziehen, und beim nächsten Zyklus nur diesen und einen Rand rundherum prüfen.
Leg halt noch ein 80x60 Raster darüber und in dem speicherst du für jedes 10x10 Teilstück (oder besser 8x8, kann die CPU leichter rechnen), ob leer oder nicht leer. Gruß Roland
:
Bearbeitet durch User
Christian J. schrieb: > Das "Array" weiss es.... nur muss das immer wieder neu durchsucht > werden, oder aber ich lege noch eines an, wo nur die Veränderungen drin > sind, d.h. viele Zeiger die nur angeben wo was ist. Dann kehrst du es eben um: Du hast nicht mehr ein Array von 600x800, sondern eine Liste mit den Koordinaten aller nicht-leerer Felder. Das bringt natürlich neue Probleme mit sich, ist aber bei einer kleinen Anzahl nicht-leerer Felder sicher eine gute Option. Grundsätzlich muss man sagen, dass ein Algorithmus, der mit einer Video-tauglichen Framerate auf einem Gitter von 800x600 in jeder Zelle etwas tun soll, auch auf moderner Hardware noch ziemlich ambitioniert ist. Bei 24 Bildern und einer halben Million Zellen hat ein moderner Prozessorkern gerade noch rund 200 Zyklen pro Zelle...
Roland Praml schrieb: > oder besser 8x8, kann die CPU leichter rechnen Kannst du das etwas ausführen?
P. M. schrieb: > Grundsätzlich muss man sagen, dass ein Algorithmus, der mit einer > Video-tauglichen Framerate auf einem Gitter von 800x600 in jeder Zelle > etwas tun soll, auch auf moderner Hardware noch ziemlich ambitioniert > ist. Bei 24 Bildern und einer halben Million Zellen hat ein moderner > Prozessorkern gerade noch rund 200 Zyklen pro Zelle... Den würde ich sowieso in einem FPGA realisieren mit Parallelverarbeitung oder mit einem DSP.
Christian J. schrieb: > Den würde ich sowieso in einem FPGA realisieren mit Parallelverarbeitung > oder mit einem DSP. Ich dachte du hättest gerade eben nach einem Algorithmus für eine CPU gefragt? ;-) Naja, was sich für dieses Projekt nun wirklich anbietet, ist die Verwendung der GPU! Mit Nvidia CUDA könnte man sowas sehr elegant lösen. Falls du Zeit und Lust hast, würde ich mich da mal einen halben Tag einlesen. Ist längst nicht so schwierig, wie einen FPGA zu programmieren.
Angehängte Dateien:
-
DSC08177__1024_x_768_.jpg
110 KB
P. M. schrieb: > Naja, was sich für dieses Projekt nun wirklich anbietet, ist die > Verwendung der GPU! Ich suche die gerade ........ kopfkratz
Christian J. schrieb: > Ich suche die gerade ........ kopfkratz Achso - um welche Plattform geht's denn letztlich? 800x600 auf dem Z80 dürfte ja wohl utopisch sein?
P. M. schrieb: > Achso - um welche Plattform geht's denn letztlich? 800x600 auf dem Z80 > dürfte ja wohl utopisch sein? Synchron auf dem PC unter Linux, erstmal da gescheit, dann portiere ich es mit weniger Auflösung......
Welche CPU? Wenn du mehrere Kerne hast, können die ja alle arbeiten...
Du brauchst doch pro Zelle nur zwei Zustände, oder? Dann kannst du 8 nebeneinander liegende Zellen auf die 8 Bits eines Bytes zusammenfassen. Und schon kannst du mit einem Vergleich auf 0 sehen ob irgendeine der 8 Zellen "an" ist.
du kannst auch ganze auch ohne großen Spielfeld lösen. speichere einfach jede lebende Zelle in einem Array. Da es recht wenig aktive Zellen gibt sollte das etwas effektiver sein. Etwas komplizierter ist dann nur die suche nach den Nachbarn. Wenn man es so macht, dann skaliert die Rechenzeit mit der Anzahl der lebenden Zellen und ist nicht mehr abhängig von der Spielgröße.
Peter II schrieb: > Etwas komplizierter ist dann nur die suche nach den Nachbarn. > Wenn man es so macht, dann skaliert die Rechenzeit mit der Anzahl der > lebenden Zellen und ist nicht mehr abhängig von der Spielgröße. Die Rechenzeit skaliert dann mindestens quadratisch mit der Anzahl lebenden Zellen. (Anzahl Zellen, die man verarbeiten muss multipliziert mit der Anzahl Zellen, die man in jedem Schritt fragen muss, ob sie Nachbarn sind = Anzahl lebende Zellen x Anzahl lebende Zellen) Man könnte es aber stark beschleunigen, indem man für jede Spalte und jede Zeile je eine eigene Liste hat. Die Zelle an Position (49, 75) würde dann in der Zeilenliste 49 und in der Spaltenliste 75 geführt. Such man nun ihre Nachbarn, so muss man in der Spaltenliste 74 und 76 sowie Zeilenliste 48 und 50 schauen, ob dort etwas drin ist. Wenn ja, noch kurz schauen, ob die Zellen tatsächlich Nachbarn sind.
P. M. schrieb: > Roland Praml schrieb: >> oder besser 8x8, kann die CPU leichter rechnen > > Kannst du das etwas ausführen? Ich dachte mir, dass du das 800x600 Gitter in je 8x8 Blöcke unterteilst (und somit ein Gitter von 100x75 Blöcke bekommst) Für jeden Block kannst du dann abspeichern, ob es aktive Zellen gibt (ggf. sogar die Anzahl), somit kannst du gleich für 256 Pixel entschieden, ob sie leer sind oder nicht. Gruß Roland
Roland Praml schrieb: > P. M. schrieb: >> Roland Praml schrieb: >>> oder besser 8x8, kann die CPU leichter rechnen >> >> Kannst du das etwas ausführen? > > Ich dachte mir, dass du das 800x600 Gitter in je 8x8 Blöcke unterteilst > (und somit ein Gitter von 100x75 Blöcke bekommst) Für jeden Block kannst > du dann abspeichern, ob es aktive Zellen gibt (ggf. sogar die Anzahl), > somit kannst du gleich für 256 Pixel entschieden, ob sie leer sind oder > nicht. Und inwiefern sollen hier 8x8 Blöcke vorteilhaft sein gegenüber 10x10 Blöcken?
Hi, ich habe erstmal die menschliche Denkweise umgesetzt, die nicht unbedingt die optimale für den Computer sein muss. Und da mein System auzs einer Zeit kommt wo man noch optimal programmieren musste und 8kb "viel" sind sollte ich es optimieren auf Kosten der Komplexität des Programmes. Ein 2D Array ist ja keine natürliche Datentype sondern ein Konstrukt von C, Speicher läuft ja nunmal in einer Reihe und nicht 2D. Da das Feld meist nur 1/3 voll ist bzw sich sehr schnell reduziert wäre die Einführung von Look Up Tabeles vielleicht sinnvoll, aber die Auswertung wäre komplizierter.
P. M. schrieb: > Und inwiefern sollen hier 8x8 Blöcke vorteilhaft sein gegenüber 10x10 > Blöcken? Eine Division durch 8 bzw. Multiplikation ist für eine CPU einfacher. /edit: 8x8=64 (und nicht 256 Pixel wie im Vorpost)
:
Bearbeitet durch User
Roland Praml schrieb: > Eine Division durch 8 bzw. Multiplikation ist für eine CPU einfacher. > > /edit: 8x8=64 (und nicht 256 Pixel wie im Vorpost) Ob das allerdings relevant ist...? Ohne Division sollte man auskommen und die Multiplikation wird man wenig (oder gar nicht) brauchen und sie ist sowieso nicht viel teurer gegenüber einem Shift. Ich würde mir auf jeden Fall eher Gedanken zu Grösse und Alignment der Cache-Blöcke machen.
:
Bearbeitet durch User
Auf einer x86 CPU magst du in allen Punkten recht haben, so wie ich den OP verstanden habe, soll es aber später auf einer Z80 CPU laufen und da sieht die Sache wieder ganz anders aus. Vermutlich wäre es aber wirklich besser, ein (Hash)Set mit aktuell lebenden Zellen zu führen, wie in den anderen Posts schon angesprochen wurde
Ich würde über eine andere datenstruktur nachdenken. Kein array... Evtl. eine baumstruktur mit informationen in den nodes ob sich weiter hinten belegte zellen befinden. Diese informationen aktualisierst du dann beim schreiben und ändern der daten, so dass du zwar mehr instruktionen beim speichern brauchst aber dadurch deine suchfunktion beschleunigst.
Der vermutlich schnellste Algoritmus ist übrigens "Hashlife". Soweit ich das überflogen habe, hat das aber mit dem ursprünglichen Algorithmus nicht mehr viel zu tun.
http://en.wikipedia.org/wiki/Hashlife Frage ist ob mein resturlaub von 6 Tage dazu ausreicht diese Doktorarbeit zu implementieren auf einem Z80 im Eurokarten Format :-) Ich schaue grad auf den 1/2m hohen Schnee draußen und die Bergkuppe gegenüber und schreibe eine Lookup Tabelle, Kerze an, Tee dabei.... so macht Programmieren Spass. >>Evtl. eine baumstruktur mit informationen in den nodes ob sich weiter >>hinten belegte zellen befinden. Setzt einen Heap voraus, der etwas größer ist als meine 2KB... sonst gute Idee.
So,
ich denke damit ist mein "Spass am Kreuzworträtsel" auch erstmal
befriedigt, denn aus dem Thema wurde sicher mehr als eine Doktorarbeit
gemacht. Es läuft signifikant schneller, je weniger Zellen es werden
aber der "Effekt" eines sich aufbauenden Bildes ist weg, da die
Veränderungen wahllos erscheinen auf dem Bildschirm. Es werden nur noch
belebte Bereiche betrachtet aber die Iterationschritte sind trotzdem
noch recht hoch, auch wenn man ein 9er Feld um die betrachtete Zelle
legt.
"Hashlife" ist ein sehr komplexer Mechanismus und übersteigt auch meine
Lust an der Sache deutlich, da es nur als Spielerei gedacht war.
// Koordinaten der lebenden Zellen
struct pos_t {
uint8_t x,y;
};
struct pos_t lcell_pos[MAX_ZELLEN];
// 2 Spielfelder alt+neu
struct feld_t {
uint8_t last[MAX_X+1][MAX_Y+1];
uint8_t next[MAX_X+1][MAX_Y+1];
uint16_t n_cells_old,n_cells_new;
};
// Berechne die nächste Generation
uint16_t calc_nextgen()
{
uint8_t x,y,i;
uint16_t mods,count;
// Koordinaten der 8 Nachbarn + eigene Zelle
struct pos_t {
uint8_t x,y;
} nb[9];
mods = 0;
// Neue Generation initialisieren
memset(feld.next,DEAD,sizeof(feld.next));
// Durchlaufe die Hash Tabelle lebender Zellen
for (count=0;count<feld.n_cells_old;count++)
{
// Hole Koordinaten lebender Zelle
x = lcell_pos[count].x;
y = lcell_pos[count].y;
// Eintragen
nb[0].x = x;
nb[0].y = y;
// Definiere die 8 Nachbarkoordinaten
// schneller als indizierte Schleife
nb[1].x = x-1;
nb[1].y = y-1;
nb[2].x = x;
nb[2].y = y-1;
nb[3].x = x+1;
nb[3].y = y-1;
nb[4].x = x-1;
nb[4].y = y;
nb[5].x = x+1;
nb[5].y = y;
nb[6].x = x-1;
nb[6].y = y+1;
nb[7].x = x;
nb[7].y = y+1;
nb[8].x = x+1;
nb[8].y = y+1;
// Berechne den neuen Status dieser 9 Zellen
for (i=0;i<9;i++)
{
x = nb[i].x;
y = nb[i].y;
//Trage neuen Status in nächste Generation ein
feld.next[x][y] = cell_status(x,y);
// Bei Veränderung neu zeichnen
if (feld.next[x][y] != feld.last[x][y])
{
move(MAX_Y-y,x);
if (feld.next[x][y] == ALIVE)
addch('O');
else
addch(' ');
mods++;
}
}
}
// Erstelle neue Hash Tabelle
count = 0;
for (x=1;x <= MAX_X;x++) {
for (y=1;y <= MAX_Y;y++) {
if (feld.next[x][y]==ALIVE) {
lcell_pos[count].x = x;
lcell_pos[count++].y = y;
}
}
}
// Passe Werte an
feld.n_cells_old = count;
// Altes Feld = Neues Feld
memcpy(feld.last,feld.next,sizeof(feld.next));
// Anzahl Veränderungen zurück
return (mods);
}
Hmm, wenn ich richtig verstehe hast du ein Feld mit 800*600 Bytes. Was ist denn in jedem Feld, doch nur "Null" oder "Eins". Warum denn nicht ein Bitfeld nehmen ???
Hans Ulli Kroll schrieb: > Hmm, > > wenn ich richtig verstehe hast du ein Feld mit 800*600 Bytes. > Was ist denn in jedem Feld, doch nur "Null" oder "Eins". > > Warum denn nicht ein Bitfeld nehmen ??? Seufz...... die 800x600 waren für den PC, es werden 80x24 später auf einem Z80. Bitfelder haben den Vorteil, dass sie wenig Ram brauchen. Daran herrscht aber kein Mangel. Bitfelder haben den Nachteill, dass der "Verwaltungsaufwand" mit "C COMPILERN" deutlich höher ist, weil die nicht unbedingt die Bitbfehle der CPU konsequent nutzen sondern in AND und OR umsetzen als Read/Mopdify/Write. Ein Byte ist eindeutig adressierbar über seinen Index, ein Bit ganz bestimmt nicht, da haben wir schon 2 Indizes, einen fürs Byte und einen für Bit in dem Byte. Ich muss als eine Funktion schreiben calc_bit (&bitnr, &bytenr, x,y) die mir nochmal Zeit verbrät, da sie bei jedem Zugriff aufgerufen werden muss. Ich habe auch irgendwann mal eingebleut bekommen, dass 1 Byte die kleinste Einheit ist mit der man rechnen soll.Es gibt zwar bei MCS51 sowas wie "packed array", auch der PIC hat (oder hatte?) einen bit adressierbaren RAM Bereich aber eine normale CPU arbeitet Byte bezogen. Und auf dem ARMJ arbeite ich mit 32Bit-Integer, weil das die optimale Einheit ist für eine 32 Bit Maschine.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.