mikrocontroller.net

Forum: PC-Programmierung 1D Array: Zyklen / Perioden erkennen


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Moin,

ist zwar nur Hobby aber halt spannender als Kreuzworträtsel. Für meine 
ST32 Bastelei muss ich eine Funktion schreiben, die CRC32 Perioden 
erkennt. Exakte Digitalwerte, keine fehlerbehafteten Analogwerte.

Der Array wird laufend und rolierend aktualisiert von einem INT. (20ms) 
der auch den Zeiger verwaltet. Idealerweise erkennt auch der INT 
Perioden, sonst eben im Hauptprogramm.

Es kommt nicht drauf an wann eine Periode erkannt wird, nur dass sie 
erkannt wird, bevor sie wieder weg ist im Array.

Perioden können 2 aber auch 3,4,5 Zyklen haben, daher nehme ich 3 x 5 = 
15 Elemente a 32 Bit. Dann sind 3 Stück sicher drin, zumindest 
kurzzeitig.

Es muss schnell gehen! In 20ms kommt immer schon der nächste Wert 
angeflogen.

Wie würde man das programmtechnisch machen?

Gruss,
Christian

: Bearbeitet durch User
von Random .. (thorstendb) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Auf jeden Fall nicht mit HAL/DriverLib, sondern mit CMSIS-Headerfile und 
schön zu Fuss :-)
Du musst den Read- und Writepointer gegeneinander sichern, ein Überholen 
ist auch dein Testkriterium, ob du schnell genug bist.
Im einfachsten Fall fängst du beim Readpointer an und suchst nach deiner 
Folge, bis du am Writepointer angekommen bist.

Ggf. lässt sich noch einiges optimieren. Additionen mit Überlauf oder 
ähnliches als "Vorsuche".
Die Arraylänge musst du ebenfalls optimieren. Ein zu kleines Array läuft 
dir zu schnell über, ein zu großes kannst irgendwann nicht mehr 
wegarbeiten.
Eventuell bergen deine Zahlenfolgen ein paar Besonderheiten, mit denen 
du optimieren kannst.

Als ersten Ansatz würde ich die Werte im Interrupt eintragen und im 
Hauptprogramm suchen.

Oder andersrum aufgezäumt: Wenn du von vornherein weisst, was du suchst, 
scanne das doch beim Einlaufen der Zahlen mit, anstatt hinterher zu 
suchen. Dafür könntest du alle möglichen Folgen in einem Baum ablegen. 
Hast du eine Folge gefunden, wird irgendwas gemacht (z.B. Zähler 
incrementieren, oder Array Index / Weg durch den Baum dieser Folge 
speichern), fällst du bei der Prüfung raus, brichst du ab und startest 
neu.

: Bearbeitet durch User
von Ben B. (Firma: Funkenflug Industries) (stromkraft)


Bewertung
1 lesenswert
nicht lesenswert
Wie schnell ist der Prozessor getaktet und wieviele Befehle werden pro 
Takt ausgeführt? Damit kannst Du ungefähr abschätzen, wieviele Takte Dir 
zum Erkennen einer Periode zur Verfügung stehen. Bei 50 Mhz Takt und im 
Schnitt zwei Takten pro Befehl hast Du etwa 500.000 Befehle zwischen 
zwei eingehenden Werten, minus das was zur Verwaltung und Ausgabe des 
Ergebnis gebraucht wird.

Wie sehen Deine Perioden aus, wie sieht das Array aus? Wie lang ist das 
Array, ganzzahlige Werte, welcher Wertebereich und immer genaue 
wertgleiche Perioden? Oder können das auch analoge Messwerte sein und 
Perioden sollen trotz eines "leichten Rauschens" in den Messwerten 
erkannt werden?

von Nick M. (muellernick)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> die CRC32 Perioden erkennt.

"CRC32" und "Periode" ist mir ein Begriff.
Ich hab aber keinen Schimmer wonach du suchst. Kannst du das anhand 
eines Beispiels erklären?

von Weber (Gast)


Bewertung
-1 lesenswert
nicht lesenswert
@ TO

Machst du irgendwas mit Glücksspielautomaten?

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Hmm.... hilft mir jetzt nicht weiter. Und der Beitrag wo nur Gegenfragen 
drinstehen (Wie sieht ein Array aus? Es ist egal wie eine Periode 
aussieht, die wiederholt sich nur eben :-) auch nicht. Es geht nur um 
die Strategie Perioden zu erkennen. Das mit dem Timing mache ich schon, 
zwei Ints koppeln durch Puffer ist mir nicht neu.

Welche Suchstrategie braucht man, das ist die Frage?

: Bearbeitet durch User
von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Weber schrieb:
> Machst du irgendwas mit Glücksspielautomaten?

Nein, Periodenerkennung bei "Game of Life"..... ich brauche kein 
Glücksspiel, ich bin Ingenieur.

: Bearbeitet durch User
von Ben B. (Firma: Funkenflug Industries) (stromkraft)


Bewertung
0 lesenswert
nicht lesenswert
Game of Life ist doch aber eine 2D-Oberfläche...

von Nick M. (muellernick)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Wie sieht ein Array aus? Es ist egal wie eine Periode
> aussieht, die wiederholt sich nur eben :-) auch nicht.

Na, dann halt nicht!
Wirst schon selber rausfinden. Irgendwie.
Und wenn dir 20 ms als "muss schnell gehen", dann ist dir sowieso nicht 
zu helfen.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Ben B. schrieb:
> Game of Life ist doch aber eine 2D-Oberfläche...

Der Bitstrom in die Displays ist allerdings 1D. Die 2D Matrix wird ja 
umgerechnet in diesen Bitstrom der MAX7219 füttert und die sind alle in 
Reihe verkettet.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Nick M. schrieb:

> Na, dann halt nicht!
> Wirst schon selber rausfinden. Irgendwie.

Mimimimii.... wer wird denn gleich weinen?

Eine Periode ist eine Reihe von Zahlen, die sich periodisch wiederholt. 
Sowohl die Länge als auch der Inhalt sind undefiniert. Sie lassen sich 
aber hier auf 2 bis 5 eingrenzen und die Inhalte liegen zwischen 0 und 
2^32.

Vielleicht gibt es ja mathematische Verfahren sowas zu lösen ohne 
1000Mal durch den Array zu kurven. Triviale Lösung wäre sich 2,3,4,5 
aufeinander folgende Zahlen zu schnappen und diese dann per Maske 
schrittweise gegen alle weiteren Elemente zu vergleichen. Kostet irre 
Rechenzeit.

Irgendjemand hat sowas sicher schon gemacht.  Sogar nur digitale Werte 
ohne "Rauschen".

: Bearbeitet durch User
von Ben B. (Firma: Funkenflug Industries) (stromkraft)


Bewertung
0 lesenswert
nicht lesenswert
Also angenommen er hat ein 1D-Array mit hoher Länge, Werte nur Null oder 
Eins (Game-of-Life-Spielfeld).

Was ich machen würde, den Abstand zwischen einem Wert und dem nächsten 
entgegengesetzten messen. Ist dieser Wert mehrmals in Folge konstant, 
habe ich eine Periode. Das geht sehr schnell, erkennt aber keine 
komplexeren Perioden wie "00011000110001100011000...", weil der 
Abstandswert ständig springt. Oder "000101000101000101000101000..."

Noch eine Möglichkeit wenn alle wichtigen möglichen Perioden bekannt und 
nicht so viele sind wäre, das Array gezielt nach diesen abzusuchen. 
Quasi einen String in dem Array finden.

Man könnte auch eine FFT drüberjagen und probieren, aus den Peaks 
Rückschlüsse zu ziehen...

von Wilhelm M. (wimalopaan)


Bewertung
0 lesenswert
nicht lesenswert
Autokorrelation

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Ben B. schrieb:
> Noch eine Möglichkeit wenn alle wichtigen möglichen Perioden bekannt und
> nicht so viele sind wäre, das Array gezielt nach diesen abzusuchen.
> Quasi einen String in dem Array finden.

Der eigentliche Bitstream hat keinen logischen Zusammenhang. Es sind 
sture Bitmuster mit Steuercodes vorne, die erst die Adresse des MAX7219 
angeben, daher 8x8 Bytes als Muster. Aber auch diese sind vergleichbar, 
jedes 2D Muster hat genau einen Bitstream. Dieser Bitstream ist in 32Bit 
Vars organisiert, da ich die interne CRC32 benutze im Int, der das 
Display bedient. Während des Raushämmerns über die SPI wird gleich die 
CRC32 gebildet.

Jedes Muster auf dem 24x32 Feld entspricht genau einem 32 Bit Wert. 
Diese werden in einem Array abgelegt. 15 Stück, da ich denke, dass man 
die braucht.

Ich spiele schon länger damit herum und habe festgestellt, dass es nach 
zig Tagen Laufen immer wieder Muster gibt, die ich nicht erkenne als 
"endgültig", zb große pulsierende Sterne. Dazu habe ich das ohne Display 
mit maximaler Speed laufen lassen im debugger. Locker 1000 
Generationen/Sekunden sind drin. Nur auf dem STm32 Board ohne was drum 
herum.

Mein Zufall ist echt, ich nutze einen LDR mit um den Seed zu setzen, 
zusätzlich zur RTC 32 Bit. Gleiter und Raumschiffe werden nicht erkannt 
aber dafür habe ich schon was anderes gefunden, die haben nämlich nahezu 
konstante Anzahl Zellen.

: Bearbeitet durch User
von Ben B. (Firma: Funkenflug Industries) (stromkraft)


Bewertung
0 lesenswert
nicht lesenswert
1000 Generationen/s sind aber deutlich mehr als 50, für Deine 20ms.

Sind also 768 Bit, 96 Byte, 24 32-Bit-Worte. Das ist wenig.

Was spricht bei der geringen Speichermenge dagegen, z.B. 10.000 
Spielfelder im Speicher zu halten (das braucht nur 1Mbyte) und zu 
schauen, ob sich da Bilder wiederholen? Sprich ob das neue Bild einem 
der letzten 10.000 entspricht?

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Triviale Lösung wäre sich 2,3,4,5 aufeinander folgende Zahlen zu
> schnappen und diese dann per Maske schrittweise gegen alle weiteren
> Elemente zu vergleichen. Kostet irre Rechenzeit.

Das sind 4·n-14 Vergleiche (n ist die Länge des Arrays).

Christian J. schrieb:
> 15 Elemente a 32 Bit

Also 46 Vergleiche. Die schafft selbst ein langsamer Prozessor locker in

Christian J. schrieb:
> 20ms

Christian J. schrieb:
> Locker 1000 Generationen/Sekunden sind drin.

Auch in 1ms sind die 46 Vergleiche noch gut machbar.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Ben B. schrieb:
> 1000 Generationen/s sind aber deutlich mehr als 50, für Deine 20ms.

In der Simulation, nicht im Demo-Mode an der Wand. In der Simu läuft nur 
der reine Zell Automat, damit ich möglichst schnell sehen kann wohin der 
Hase läuft. Dazu brauche ich keine spi bedienen, maximale Geschwindgkeit 
ohne jedes Delay fahren. Das geht fix bei einem stm32 mit 72 Mhz Clock.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Das sind 4·n-14 Vergleiche (n ist die Länge des Arrays).

Ja.... ok, dachte vielleicht es gibt da kluge Verfahren für sowas. 
Stures Vergleichen ist nicht gerade das Ei des Kolumbus und etwas 
größere Zahlen und Arrays und schon potenziert sich das.

Ich kann mir also die 2,3,4,5 ersten Elemente einfach rausholen und per 
memcmp vergleichen mit dem Rest, der schrittweise durchlaufen wird, 
immer ein Byte vorsetzen auf den Ringpuffer angewendet.  Dazu einen 
eigenen Zeiger definieren, der unabhängig vom Writze Zeiger des INTs 
ist.

Kriegen wir hin....

: Bearbeitet durch User
von sid (Gast)


Bewertung
0 lesenswert
nicht lesenswert
ben eater hat doch vor urzeiten mal diese hübsche CRC berechnung in 
hardware ausgeführt (youtube)

n paar XOR gates und ne Hand voll flipflops und fertig.

wenn sich die Muster nun ausreichend vordefinieren lassen,
kannst Du vollständig Analog zu Bens CRC

die hardware die Muster erkenenn lassen,
noch ein detection pin und schwupp sended dein detector ein binäres 
signal an den µC bei Fund eines Musters.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
sid schrieb:
> n paar XOR gates und ne Hand voll flipflops und fertig.

Der STM32 hat eine CRC Hardware intern, die das in 2-3 Zyklen
erledigt.... dauert keine paar Mikrosekunden bei mir für das ganze Feld.
Das Polynom ist allerdings fix, mir aber auch egal. XOR taete es auch.

: Bearbeitet durch User
von sid (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Der STM32 hat eine CRC Einheit intern, die das in 2-3 Zyklen
> erledigt....

jo, aber er braucht ja keinen CRC sondern eine Mustererkennung ;)

von Wilhelm M. (wimalopaan)


Bewertung
0 lesenswert
nicht lesenswert
sid schrieb:
> Christian J. schrieb:
>> Der STM32 hat eine CRC Einheit intern, die das in 2-3 Zyklen
>> erledigt....
>
> jo, aber er braucht ja keinen CRC sondern eine Mustererkennung ;)

Genau: deswegen (s.o.): Autokorrelation

von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Stures Vergleichen ist nicht gerade das Ei des Kolumbus und etwas
> größere Zahlen und Arrays und schon potenziert sich das.

Was potenziert sich da? Der Aufwand ist O(n) (n = Länge des Arrays).
Besser als O(n) ist auch kein anderes Verfahren, da jedes Arrayelement
mindestens einmal gelesen werden muss.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Was potenziert sich da? Der Aufwand ist O(n) (n = Länge des Arrays).
> Besser als O(n) ist auch kein anderes Verfahren, da jedes Arrayelement
> mindestens einmal gelesen werden muss.

Ich widerspreche nicht, da ich weiss, dass Du ziemlich was auf dem 
Kasten hast in Sachen Software :-) Ok, ich baue es so ein......

von Christian J. (Firma: privat) (christianj)


Angehängte Dateien:

Bewertung
0 lesenswert
nicht lesenswert
Ist jetzt noch nicht ganz fertig aber geht das auch noch pfiffiger?
Habe versucht das alles in Schleifen zu erschlagen. 2er bis 5er 
Perioden.
compVal als HilfsVar zunächst mal, kann man auch weglassen.

Habe es im Debug Mode mit "Life View" mehrmals durchlaufen lassen, auf 
2er Perioden reagiert er jedenfalls sofort. Eine 2er wird allerdings 
durch den Vergleich auf 3er auch abgedeckt. D.h auf 2 bräuchte man gar 
nicht zu prüfen, 1,2,1,2,1,2,... wird auch mit Vergleich auf 1,2,1 
abgedeckt.

 Die Switch Case kann man sicherlich noch etwas eleganter formulieren 
aber das später. Da ich lokale Vars auf dem Stack nicht debuggen kann 
sind die erstmal global.

/* 15 x 32 Bit Checksummen als aufeinander folgende Abbilder der Matrix */
#define CRC32_MAX  15
volatile int WP_CRC32Stream = 0;    /* Write Pointer, rolierend, INT gesteuert */
volatile uint32_t CRC32Stream[CRC32_MAX+1];

#define MAX_COMP   5
uint32_t compVal[MAX_COMP];

static
int CheckForPeriod()
{
    int round = 2;
    int ptr = 0;

    while (round <= MAX_COMP) {
        /* Erste Werte als Vergleich speichern */
        for (int i = 0; i < round; i++)
            compVal[i] = CRC32Stream[i];

        ptr = round + 1;

        /* Vergleiche die n 32 Bit Werte schrittweise mit dem Rest des Arrays */
        _Bool treffer = false;
        while (ptr < CRC32_MAX) {

            switch (round)
            {
                case 2: if ((compVal[0] == CRC32Stream[ptr]) &&  \
                            (compVal[1] == CRC32Stream[ptr + 1]))
                            treffer = true;
                        break;
                case 3: if ((compVal[0] == CRC32Stream[ptr]) &&  \
                            (compVal[1] == CRC32Stream[ptr + 1]) && \
                            (compVal[2] == CRC32Stream[ptr + 2]))
                            treffer = true;
                        break;
                case 4: if ((compVal[0] == CRC32Stream[ptr]) &&  \
                            (compVal[1] == CRC32Stream[ptr + 1]) && \
                            (compVal[2] == CRC32Stream[ptr + 2]) && \
                            (compVal[3] == CRC32Stream[ptr + 3]))
                            treffer = true;
                        break;
                case 5: if ((compVal[0] == CRC32Stream[ptr]) &&  \
                            (compVal[1] == CRC32Stream[ptr + 1]) && \
                            (compVal[2] == CRC32Stream[ptr + 2]) && \
                            (compVal[3] == CRC32Stream[ptr + 3]) && \
                            (compVal[4] == CRC32Stream[ptr + 4]))
                            treffer = true;
                        break;
                default:
                        break;
            }

            /* Pointer n Bytes weiter setzen */
            ptr = ptr + round;
        }

        round++;
    }

    return 0;
}

: Bearbeitet durch User
von Yalu X. (yalu) (Moderator)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> ptr = round + 1;

Sollte da nicht

ptr = round + 1;

stehen?

Sollte das Verfahren statt bei Index 0 nicht bei Index WP_CRC32Stream,
d.h. nicht am Anfang des Array, sondern am Anfang des Ringpuffers
starten? Wenn round ein Teiler der Array-Länge ist, ist das egal. Aber
für round=2 und round=4 ist die letzte Periode im Array nicht
vollständig.

Es paarmal wird über das Array-Ende hinaus gelesen.

Die Variable treffer wird schon dann auf true gesetzt, wenn sich der
betrachtete Block einziges Mal wiederholt. Sollten die Daten nicht über
die gesamte Array-Länge periodisch sein?

Die Funktion CheckForPeriod liefert keine Information darüber zurück,
ob die Daten periodisch sind oder nicht (der Wert von treffer
verschwindet im Nirwana).

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Sollte das Verfahren statt bei Index 0 nicht bei Index WP_CRC32Stream,
> d.h. nicht am Anfang des Array, sondern am Anfang des Ringpuffers
> starten?

Ja, so ist das wenn man etwas postet und nachher noch weiter macht. 
Fehler ist korrigiert. Außerdem muss das Feld erst voll sein.
 /* Eintragen in BitStream */
    CRC32Stream[WP_CRC32Stream] = CRC32Bitstream;
    /* Zeiger rolieren */
    WP_CRC32Stream = (WP_CRC32Stream + 1) % CRC32_MAX;

    /* Feld muss voll sein für Auswertung */
    if (WP_CRC32Stream == 0)
        f_IsFull = true;

    if (!f_IsFull)
        return 0;

Aber wo man anfängt.... es ist egal ob das sofort oder erst später 
erkannt wird, Periode ist Periode und die bleibt so. Nur sind 2er 
Treffer auch zufällig möglich. 3er unwahrscheinlicher und ein 3er deckt 
den 2er mit ab.

von foobar (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nur mal als Hinweis: Game of Life ist deterministisch - auf einen 
bestimmten State X folgt immer der gleiche State X+1.   D.h., wenn ich 
zwei States gefunden habe, die gleich sind, brauch ich nicht mehr weiter 
zu vergleichen, da sie eh immer die gleichen Folgestates generieren. 
Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue 
State schon einmal vorgekommen ist.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue
> State schon einmal vorgekommen ist.

Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss 
nur schauen, ob ich bei N States schon einmal meinen gemerkten State 
hatte? Eben weil sich aus einem Muster immer die gleichen Folgemuster 
entwickeln. Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig 
beschrieben.

: Bearbeitet durch User
von MaWin (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Für meine ST32 Bastelei muss ich eine Funktion schreiben, die CRC32
> Perioden erkennt.

CRC32 ? Woher auch immer, Perioden sind Zahlenfolgen.

Der ZIP ZLW Ziv Lemoel Welsh  Algorithmus erkennt, ob eine Bytefolge 
früher schon mal vorlag, man kann einstellen wie viel früher und wie 
lang.

Compress von http://ftp.ntu.edu.tw/pub/cpatch/h/helpdeco/helpdc21.zip 
ist eine kurze Version.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
MaWin schrieb:
> RC32 ? Woher auch immer, Perioden sind Zahlenfolgen.

Jedes grafische 24x32 Muster wird bei mir durch einen CRC32 abgelegt, da 
ich nur so feststellen kann, ob es ein Muster schon mal gab.

Dieser Algorithmus funktioniert auch für Binärzahlen? Sieht eher nach 
Text Zippen aus.

von foobar (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>> Das Finden eines Zyklus' reduziert sich also auf die Suche, ob der neue
>> State schon einmal vorgekommen ist.
>
> Innerhalb welchen Zeitraumes? Bzw Periodenraumes hier... d.h. ich muss
> nur schauen, ob ich bei N States schon einmal meinen gemerkten State
> hatte?

Wenn du die letzten N States merkst, kannst du Zyklen bis Länge N 
erkennen.

von Theor (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> [...]

> Ein Muster wird durch eine einzige 32 Bit CRC32 eindeutig
> beschrieben.

Soweit ich den Sachverhalt CRC verstanden habe, gilt das nur und hängt 
auch von dem Polynom ab, falls die Menge der Eingangsdaten (bei CRC32) 
kleiner oder gleich 32 Bit sind.

Anders herum. Für 33 Bit Eingangsdatenlänge wird ein CRC32 verschiedene 
Eingangsdaten auf die gleich CRC-Summe abbilden.

Ich hoffe, ich habe nichts übersehen, was meinen Einwand überflüssig 
macht.

von MaWin (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Sieht eher nach Text Zippen aus

Text zippen besteht aus der Aufgabe, früher schon mal auftretende 
Bytefolgen schnell erkennen zu können.

Beim GoL sind aber sehr lange Perioden denkbar, über tausende von 
States, eine sichere Erkennung ab wann das Muster wiederholt wird (und 
ab dann das Spiel in eine Periodd läuft) ist also nicht möglich.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
MaWin schrieb:
> Beim GoL sind aber sehr lange Perioden denkbar, über tausende von
> States,

Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt 
bleibt früher oder später einfach stehen. Blinker und Stilleben. Ich 
habe es nur ganz selten gehabt, dass komplexe Blinker entstehen, die aus 
mehr als 5 Zyklen bestehen. Das Ding läuft Tag und Nacht bei mir, ca 1 x 
Woche entstehen Zustände, die noch nicht erfasst habe.

: Bearbeitet durch User
von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> Nur mal als Hinweis: Game of Life ist deterministisch - auf einen
> bestimmten State X folgt immer der gleiche State X+1.

Wollte nochmal Danke sagen für diesen Hinweis! Man muss wirklich keine 
Perioden durchsuchen, da eine einzige Wiederholung schon ausreicht um zu 
erkennen, dass es eine Periode mit ? Zyklen ist. Es kann keine 2 
gleichen Muster beginnend ab Start geben bis Ende. Ich hatte öfter mal 
einen Zustand mit zwei parallel fliegenden Gleitern, der unendlich war 
aber auch die kriege ich mit einer 100er Histrory erfasst, da das Feld 
ja "rund" ist, was obenr raus fliegt, fliegt unten wieder rein.

Schaue mir das heute abend mal an, nach ner Weile wird man eh etwas 
"gaga" vom Zuschauen ;-)
static
int CheckForPeriod()
{
    static int WP_CRC32 = 0;    /* Write Pointer, rolierend, INT gesteuert */
  static _Bool f_IsFull = false;

    /* Aktuelles Muster eintragen in BitStream */
    CRC32Stream[WP_CRC32] = CRC32Bitstream;
  uint32_t CRC32Now = CRC32Bitstream;
  
    /* Zeiger rolieren */
    WP_CRC32 = (WP_CRC32 + 1) % CRC32_MAX;
  
    /* Feld muss voll sein für Auswertung */
    if (WP_CRC32 == 0)
        f_IsFull = true;

    if (!f_IsFull)
        return 0;

  /* Werte vor Write Pointer bis direkt hinter ihm durchsuchen */
  int ReadPtr = WP_CRC32;
  do {
    /* Read Pointer auf nächstes Element */
    ReadPtr = (ReadPtr + 1) % CRC32_MAX;
    if (CRC32Now == CRC32Stream[ReadPtr])
      /* Muster schon vorgekommen! */
      return 1;
  } while (ReadPtr != WP_CRC32); /* RP holt WP ein */
  
    return 0;
}


: Bearbeitet durch User
von MaWin (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:
> Sind sie nicht

Doch.

Allerdings muss ich einschränken: nur in Toruswelten, wo also links und 
rechts, oben und unten verbunden sind. Aber das halte ich für die 
normale GoL Welt.

Es gibt Gleiter, die fliegen endlos wenn sie mit nicht mit was anderem 
kollidieren, Periodenlänge abhängig von Brettgrösse. Davon mehrere 
unterschiedlich fliegende nicht kollidierende, und der Zyklus ist das 
KGV davon.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
MaWin schrieb:
> Allerdings muss ich einschränken: nur in Toruswelten, wo also links und
> rechts, oben und unten verbunden sind. Aber das halte ich für die
> normale GoL Welt.

Ist bei mir auch so und ja, wenn ich 2 davon habe fliegen die auch 
endlos über das 32x24 Feld. Bzw bei STM32409 Disco Board mit seinen 
640px noch weiter, da kann es ewig dauernd bis 3 zusammen stossen. Somit 
wäre das richtig. Aber den Zustand erkenne ich schnell über die 
Zellzahl, da diese sich dann innerhalb fester Differenzen bewegt.

: Bearbeitet durch User
von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
PS: Habe hier grad ein recht komplexes Muster, was sich aber laufend in 
mehr als 50 Zyklen wiederholt.... faszinierend :-)

von c-hater (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Christian J. schrieb:

> Sind sie nicht. Oder nur bei konstruierten Welten. Jede Zufallswelt
> bleibt früher oder später einfach stehen.

Der Witz am Zufall ist ja gerade, dass er auch so extrem 
Unwahrscheinliches wie eine "konstruierte" Welt erschaffen kann. Er muss 
nur oft genug die Chance haben, wirksam zu werden.

Ich persönlich finde übrigens diese konstruierten Welten mit ihren 
Zyklen einigermaßen langweilig.

Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte 
Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in 
Statik oder einem Zyklus enden. Das sind für mich die spannendsten 
Welten. Vermutlich hat auch der TO genau dieses Ziel.

Er wird aber wahrscheinlich daran scheitern. Ein statistische Analyse 
zeigt, warum. Am besten fängt man mit sehr kleinen Toroiden an, da die 
Sache dann noch einfach beherschbar ist und der volle Suchraum 
durchexerziert werden kann. Bei schrittweiser Vergrößerung des Toroiden 
und Auswertung der jeweiligen Ergebnisse erkennt man dann schnell, wohin 
der Hase läuft...

OK, die dabei empirisch ermittelte "Gesetzmäßigkeit" ist mathematisch 
gesehen natürlich noch kein Beweis dafür, dass das bis zur unendlichen 
Ausdehnung der Toroide so weitergeht...

von foobar (Gast)


Bewertung
0 lesenswert
nicht lesenswert
> static int CheckForPeriod()
> ...

Ich denke, deine Routine ist .. verbesserungswürdig ;-)  Findet wohl 
immer den gerade neu eingetragenen State; das isFull erscheint mir 
unnötig (bei Programmstart wird ne CRC von 0 als Zyklus erkannt - who 
cares); den neuen State muß man nur eintragen, wenn er noch nicht drin 
ist; globale Variable als versteckter Funktionsparameter; ...

Btw, ich bin kein Fan von vielen Großbuchstaben in Identifiern, erst 
recht bei lokalen Variablen.  Insb sind komplett großgeschriebene 
immer defines.
#define MAX_CYCLE_LEN    16

/*
 * Add new state to history.  Returns true if 'state' really is new.
 */

static int
new_state(uint32_t state)
{
    static uint32_t history[MAX_CYCLE_LEN];
    static unsigned wp;

    for (unsigned i = 0; i < MAX_CYCLE_LEN; ++i)
        if (history[i] == state)
            return 0;  // not new - start of a cycle

    history[wp++] = state;
    wp %= MAX_CYCLE_LEN;
    return 1;
}

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
foobar schrieb:
> Ich denke, deine Routine ist .. verbesserungswürdig ;-)

Yupp! Deswegen habe ich mir das auch grad nochmal vorgenommen, eh 
besch.. Wetter draussen. Leider ist es so, dass sich CRC32 wiederholen. 
Nicht oft aber eben doch. Erst wenn man 3 Treffer als erfüllte Bed. 
einstuft passt es.

von Christian J. (Firma: privat) (christianj)


Bewertung
0 lesenswert
nicht lesenswert
c-hater schrieb:
> Wenn ich nach irgendwas suchen würde, wären das zufallsgenerierte
> Welten, die eine möglichst lange Phase "Chaos" haben, bevor sie in
> Statik oder einem Zyklus enden.

Das geht leider nur mit dem STm32F4xxx, da dieser einen Zufall hat, der 
von einer Rauschdiode erzeugt wird und zudem auch für Sicherheitssysteme 
geeignet ist. Was ich mache ist immer die gleiche Chose, die exakt so 
abläuft wie der Startwert es vorgibt.

Andere lösen Kreuzworträtsel oder gehen auf FFF Demos, mir ist das hier 
lieber...

: Bearbeitet durch User

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.