Algorithmus zum Durchsuchen großer Felder

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.

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.

P. M. schrieb:

> Naja, was sich für dieses Projekt nun wirklich anbietet, ist die
> Verwendung der GPU!

Ich suche die gerade ........ kopfkratz

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......

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.

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.

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.

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.