Ich möchte ein altes Minesweeper-Spieleprogramm von mir vom PC zu einem Mikrocontroller portieren.
Das ganze funktioniert auch gut, hat aber einen gewaltigen Schönheitsfehler. Ich verwende zum Suchen freier benachbarter Mienenfelder einen rekursiven Floodfillalgorithmus, prinzipiell genau so, wie ich auch eine umrandete Grafik mit einem Farbwert fülle.
Code hier und nicht als Anhang eingefügt, da ich denke dass das kein wirklich großes Listing ist:
Das Mienenfeld ist nur in einem eindimensionalen Array mfeld[] abgelegt und eine x,y Koordinate berechnet sich dann aus einer Startposition aktpos relativ zu den Konstanten mfeldx und mfeldy. Im Array selbst ist ein Zahlenwert 0x10 für eine vorhandene Miene eingetragen, die Füllfunktion selbst legt im Array selbst den Zahlenwert 0x09 ab, wenn dieses als Leerfeld markiert wird.
Grenzt an ein Element eine oder mehrere Mienen, trägt mark8nb die Anzahl umliegender Mienen ins Array ein.
Wie gesagt funktioniert das ganze gut, allerdings ist der Rambedarf für einen Controller groß: Für ein 18x18 großes Feld benötigt mein Programm für die ungünstigste Konstellation (getestet mit nur einer einzigen eingetragenen Miene) einen Controller mit mindestens 7 kbyte Ram um das gesamte Feld auszufüllen. Hat der Controller weniger Ram, kommt es logischerweise zu einem Stack-Overflow.
Wie kann ich die Funktion fill4 iterativ definieren? Irgendwie stehe ich hier auf dem Schlauch.
Wie kann ich die Funktion fill4 iterativ definieren?
Gar nicht. Der Ansatz muss schon anders gewählt werden.
Du hast genug Speicherplatz, um die Zahl für jedes Feld zu speichern, und und kannst die Zahl einfach durch einen einzelnen Durchlauf durch alle Felder ermitteln.
Sprich: Du durchläufst alle Felder und zählst zusammen, wobei logischerweise die Felder, die noch nicht dran waren, noch nicht berücksichtigt werden. Wenn sich durch ein späteres Feld der Wert in einem vorhergegangenen Feld erhöht, wird das nachgetragen. Das können ja maximal 4 Felder sein.
Trittst Du auf eine Mine, ist es zu spät, noch gute Miene zum bösen Spiel zu machen.
Nachtrag: Eigentlich brauchst Du die Zahl ja noch nicht einmal. Für das automatische Aufdecken reicht es ja aus zu wissen, ob überhaupt ein Nachbar mit Mine existiert.
Der obige Algorithmus kann aber sowohl die Anzeige der Anzahl als auch das automatische aufdecken, das Du bisher mit floodfill gelöst hast, realisieren.
Ich verwende zum Suchen freier benachbarter
Mienenfelder einen rekursiven Floodfillalgorithmus, prinzipiell genau
so, wie ich auch eine umrandete Grafik mit einem Farbwert fülle.
Was ist ein Mienenfeld?
Eine blöde Miene macht der Spieler gewöhnlich erst, wenn er auf eine Mine tritt, d.h. es gibt genau eine Miene von jedem Spieler, wieso ein Array?
Was ist ein Mienenfeld?
Eine blöde Miene macht der Spieler gewöhnlich erst, wenn er auf eine
Mine tritt, d.h. es gibt genau eine Miene von jedem Spieler, wieso ein
Array?
scnr
:-) okay: Ich schreibe Mine nie mehr mit "ie", auch wenn ich gute Mine zum bösen (Mienen)Spiel mache... :-)
( irgendwie war da jetzt wieder etwas falsch, oder ? :-) )
Die Strafarbeit:
1
for (int i= 0; i< 100; i++) { printf("\n\rMine"); }
:-) okay: Ich schreibe Mine nie mehr mit "ie", auch wenn ich gute Mine
zum bösen (Mienen)Spiel mache... :-)
Das war nur der eine Aspekt ;-)
Ein Minenfeld bezeichnet im gewöhnlichen Sprachgebrauch eine verminte Fläche, nicht das einzelne Flächenelement (auf dem eine Mine liegen kann). Ein "benachbartes" Minenfeld wäre also ein weiteres Array, in dem es ebenfalls "Planstellen" für Minen gibt.
Verständnisfrage: wird der Rand richtig berücksichtigt?
bei z.B. 18*18 Feldern folgende Feldanordnung:
1
0 1 2 ... 17
2
18 19 20 ... 35
3
36 37 ...
4
...
bptr z.B. auf 18 prüft Felder 36,0,17,19. 17 ist doch kein Nachbar?
Bei Feldern in der obersten und untersten Reihe wird ausserhalb des arrays geprüft? z.B. 1 prüft 19,-17,0,2.
Da scheinen auch noch bound checks zu fehlen. Wenn du z.B. am linken Rand bist, und eins weiter Links gehst, kommst du eins weiter oben rechts raus. Und wenn du bei Position 0 warst, und eins links gehst, bist du im nirgendwo.
Das Mienenfeld ist nur in einem eindimensionalen Array mfeld[] abgelegt
und eine x,y Koordinate berechnet sich dann aus einer Startposition
aktpos relativ zu den Konstanten mfeldx und mfeldy.
Wie kann ich die Funktion fill4 iterativ definieren? Irgendwie stehe
ich hier auf dem Schlauch.
Naja, du must halt nebeneinander liegende Felder in einer Schleife markieren. z.B. alle links vom Momentanen, dann die nächste Zeile, usw. Dann auf die andere Richtung. Aber ganz ohne Stack geht das so halt auch nicht, wenn es um ne Mauer rum muss, muss man sich dann merken, da wieder zurück zu kommen. In welcher Reihenfolge man die markiert, da gibt es viele Möglichkeiten.
Ein Minenfeld bezeichnet im gewöhnlichen Sprachgebrauch eine verminte
Fläche, nicht das einzelne Flächenelement (auf dem eine Mine liegen
kann).
Ein Feld mit einer Mine ist ein Minenfeld. Ein Feld mit vielen Minen ist auch ein Minenfeld. Ein Spielfeld mit vielen Feldern mit jeweils keiner oder einer Mine ist auch ein Minenfeld.
Und wer schon einmal im ehemaligen Jugoslawien war weiß: Ein Feld, von dem man nicht weiß, ob da eine Mine ist, ist auch ein Minenfeld. Sicher ist sicher.
Da scheinen auch noch bound checks zu fehlen. Wenn du z.B. am linken
Rand bist, und eins weiter Links gehst, kommst du eins weiter oben
rechts raus. Und wenn du bei Position 0 warst, und eins links gehst,
bist du im nirgendwo.
Das 18x18 Array beherbergt ein 16x16 Minenfeld. Der Rand oben, unten, links und rechts wird mit einem Wert belegt, bei dem der Floodfill garantiert anhält.
Für ein 18x18 großes Feld benötigt mein Programm
für die ungünstigste Konstellation (getestet mit nur einer einzigen
eingetragenen Miene) einen Controller mit mindestens 7 kbyte Ram um das
gesamte Feld auszufüllen. Hat der Controller weniger Ram, kommt es
logischerweise zu einem Stack-Overflow.
Im schlimmsten Fall braucht der Algorithmus eine Rekursionsebene pro
Feld, das sind 16·16=256. Bei jedem Aufruf werden die beiden
Funktionsargumente, die Rücksprungadresse und Zwischenergebnisse auf den
Stack geschoben. Da du offensichtlich eine 32-Bit-MCU verwendest, wo
Adressen und int-Werte 4 Bytes groß sind, kommen da schnell mehrere KB
an Stack-Daten zusammen.
Du kannst versuchen, ein paar Variablen vom Stack fernzuhalten:
ovalue: entfernen, weil ungenutzt
value: als static deklarieren, da sein Inhalt in den rekursiven
Aufrufen problemlos überschrieben werden darf
bptr: aus der Argumentliste entfernen und global machen, da sich der
Inhalt sowieso nie ändert
Es kann aber gut sein, dass der Compiler das alles schon vorweggenommen
hat, so dass du damit keine (oder nur eine marginale) Verbesserung
erreichst.
Der einfachste Weg, das Ganze ohne Rekursion zu machen, ist hier
beschrieben:
Statt des riesigen Programmstacks, auf den alles Mögliche geschoben
wird, gibt es hier einen dedizierten Daten-Stack, der nur die relevanten
Dinge, nämlich die Indizes der noch zu bearbeitenden Feldelemente,
enthält. Dieser Stack kann nicht größer als die Anzahl der Feldelemente
(256) werden. Bei der Verwendung von 16-Bit-Integers sind das gerade mal
512 Bytes.
Nimmst du statt des Stacks (FIFO) eine Queue (LIFO), kommst du evtl. mit
noch weniger Speicherplatz aus. Vermutlich reichen 61 Queue-Elemente,
also 122 Bytes.
Sowohl den Stack als auch die Queue kannst du auch einfache Weise als
Array plus einer (Stack) bzw. zwei (Queue) Indexvariablen, über die das
Array gelesen und beschrieben wird, implementieren.
Ich bin mir aber noch nicht ganz sicher, ob der Algorithmus immer geht, und wie gross das Spielfeld da maximal sein dürfte.
Die Idee ist jedenfalls, erst mal alle zusammenhängenden Bereiche zu finden, jedem eine eigene ID zu geben, und dann später einfach alle Felder mit der ID zu ersetzen.
Die Idee ist jedenfalls, erst mal alle zusammenhängenden Bereiche zu
finden, jedem eine eigene ID zu geben, und dann später einfach alle
Felder mit der ID zu ersetzen.
... genau daran werkel ich im Moment und lustigerweise hantiere ich auch mit Bit 7 eines Chars als Kennung für ein Leerfeld. Komplett funktioniert es aber leider noch nicht.
Im schlimmsten Fall braucht der Algorithmus eine Rekursionsebene pro
Feld, das sind 16·16=256. Bei jedem Aufruf werden die beiden
Funktionsargumente, die Rücksprungadresse und Zwischenergebnisse auf den
Stack geschoben. Da du offensichtlich eine 32-Bit-MCU verwendest, wo
Adressen und int-Werte 4 Bytes groß sind, kommen da schnell mehrere KB
an Stack-Daten zusammen.
... das ganze habe ich so auch "gesehen" gehabt und hier grundsätzlich überlegt: 2 Argumente zu 4 Bytes plus den 4 Bytes für die Rücksprungadresse plus 4 Bytes für Funktionsergebnis machen für den Kopf 16 Bytes aus.
value: als static deklarieren, da sein Inhalt in den rekursiven
Aufrufen problemlos überschrieben werden darf
bptr: aus der Argumentliste entfernen und global machen, da sich der
Inhalt sowieso nie ändert
ovalue habe ich schlicht vergessen zu entfernen und war in einer frühen Version verwendet (wie gesagt fällt das auf einem PC so gar nicht auf, weil für so eine kleines Feld bei einem PC der Speicherbedarf lächerlich ist, obgleich das nicht die Schlampigkeit des Nichtentfernens entschuldigt).
Value als static und bptr global werde ich machen und sehen wie sich der Speicherbedarf ändert.
Vielen Dank für die Hinweise. Vielleicht ist es dann doch nicht notwendig, große Klimmzüge zu machen um das auf kleineren Controllern zum Laufen zu bringen.
Vielleicht ist es dann doch nicht notwendig, große Klimmzüge zu machen
um das auf kleineren Controllern zum Laufen zu bringen.
Große Klimmzüge sind für einen anderen Algorithmus ja auch nicht
erforderlich. Hier ist die primitivste Variante, die ohne Rekursion
auskommt:
1
voidfill4(intcpos,uint8_t*bptr){
2
staticuint16_tstack[407];
3
intssize=0;
4
5
stack[ssize++]=cpos;
6
while(ssize){
7
cpos=stack[--ssize];
8
if(!bptr[cpos]){
9
mark8nb(cpos,bptr);
10
bptr[cpos]=9;// als Leerfeld markieren
11
12
stack[ssize++]=cpos-1;// x-1, y
13
stack[ssize++]=cpos+mfeldx;// x, y+1
14
stack[ssize++]=cpos-mfeldx;// x, y-1
15
stack[ssize++]=cpos+1;// x+1, y
16
}
17
}
18
}
Streng genommen ist das kein anderer Algorithmus, sondern nur eine
andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
Algorithmus.
Er arbeitet mit einem Daten-Stack für die noch zu bearbeitenden Felder.
Die Rekursion wird dadurch eliminiert, dass
die rekursiven Funktionsaufrufe mit den Feldern als Argument durch
Pushes der Felder auf den Stack ersetzt werden,
das jeweils als nächstes zu bearbeitende Feld nicht als
Funktionsargument empfangen, sondern vom Stack gepoppt wird und
das Ganze in eine Schleife eingebettet wird, die so lange iteriert,
bis der Stack leer ist, d.h. keine weiteren Felder mehr bearbeitet
werden müssen.
Ich bin mir etwas unsicher bzgl. der maximalen Stack-Größe. Sie wird
vermutlich dann benötigt, wenn das Spielbrett komplett leer ist. Aus
dieser Ausgangssituation heraus habe ich den Algorithmus für alle 256
möglichen Startfelder durchlaufen lassen und und das Maximum von ssize
(der jeweils aktuellen Stack-Größe) bestimmt. Das Ergebnis ist 407, d.h.
so groß sollte das Stack-Array mindestens dimensioniert werden.
Die Reihenfolge der Push-Operationen in den Zeilen 12-15 habe ich
gegenüber deinem Programm etwas geändert, da sich dies leicht positiv
auf die erforderliche maximale Stack-Größe auswirkt.
Außerdem habe ich deine
1
*(bptr+cpos)
mit etwas syntaktischem Zucker versüßt und durch das äquivalente
Hey, vielen Dank Yalu... leider komme ich nicht dazu das alles auszupropieren, weil ich leider wieder einmal mit der doofen COPD im Krankenhaus liege. Das letzte mal konnte ich das planen und hatte meine Spielzeuge mit im Krankenhaus, dieses mal leider nicht.
... so, das war jetzt mal Denksportaufgabe für mich und ich denke ich habe das in Trockenübung verstanden.
Umsonst hast du dein Array nicht Stack getauft, ausgehend davon, dass alles von der Position 0 ausgeht und ssize (was hier dann der Stackpointer ist) eben entsprechend inkrementiert / dekrementiert wird.
Smile, ein "gespieltes" HRMPF, weil hier wohl alle meine Bemühungen davor abosolet werden, da mir das hier als eleganteste Lösung erscheint
Streng genommen ist das kein anderer Algorithmus, sondern nur eine
andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
Algorithmus
.. und warum? Hier ist ein technisches Forum gegeben und kein Forum für "Deutsch Leistungskurs"! Solange alle wissen um was es geht ist doch niemandem geschadet (außer den Deutsch-Pedanten denen ein unkorrektes Deutsch Tränen in die Augen treibt).
Grundsätzlich finde ich das Herumreiten auf Schreibfehlern oder grammatikalischen Schwächen sogar für eine "Schlechtigkeit", zeigt es doch meistens (nicht immer) auf, dass sich jemand nur aufgrund der Deutschfähigkeiten über jemand anderen stellen mag.
Lustig darauf hinweisen geht, aber "Erst mal ein bischen Grammatik lernen?!!" ist schon der Oberlehrerzeigefinger
Streng genommen ist das kein anderer Algorithmus, sondern nur eine
andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
Algorithmus.
Er arbeitet mit einem Daten-Stack für die noch zu bearbeitenden Felder.
Die Rekursion wird dadurch eliminiert, dass
die rekursiven Funktionsaufrufe mit den Feldern als Argument durch
Pushes der Felder auf den Stack ersetzt werden,
das jeweils als nächstes zu bearbeitende Feld nicht als
Funktionsargument empfangen, sondern vom Stack gepoppt wird und
das Ganze in eine Schleife eingebettet wird, die so lange iteriert,
bis der Stack leer ist, d.h. keine weiteren Felder mehr bearbeitet
werden müssen.
Weil mich das ganze auch im Krankenhaus nicht in Ruhe lässt, hat mir meine Frau ihr (Windows) Notebook mitgebracht und ich habe mir hier dann kurzerhand in einer Virtualbox mein Linux-Livesystem installiert und mir von meinem Server die Dateien des Minesweeper gezogen, :-) nur um Yalu's Verbesserungen auszuprobieren.
Jetzt bin ich am Spielen und wie es ausschaut funktioniert das ganze. Herzlichen Dank. Schade, dass ich meinen Mikrocontrollerboards nicht hier habe. Theoretisch müßte das jetzt auch auf einem CH32V003 laufen.
Streng genommen ist das kein anderer Algorithmus, sondern nur eine
andere (rekursionsfreie) Implementierung des von dir bereits verwendeten
Algorithmus
Eben, daher Unsinn.
Kein Unsinn, sondern Lösung des vorliegenden Problems.
Für ein 18x18 großes Feld benötigt mein Programm für die ungünstigste
Konstellation (getestet mit nur einer einzigen eingetragenen Miene)
einen Controller mit mindestens 7 kbyte Ram um das gesamte Feld
auszufüllen. Hat der Controller weniger Ram, kommt es logischerweise
zu einem Stack-Overflow.
Die Verwendung eines reinen Datenstacks ohne Rekursion spart fast 90%
des RAM-Bedarfs. Dabei bleibt die Laufzeitkomplexität unverändert O(n)
(n ist die Anzahl der Felder), und die Laufzeit selber ist sogar
deutlich kürzer, da der Overhead für die Funktionsaufrufe wegfällt.
Bei nur 16×16 Feldern läuft natürlich auch eine Hauruckmehtode mit O(n²)
(wie sie dir vermutlich vorschwebt) ausreichend schnell. Dass Ralph das
Spiel aber auf einem Mikrocontroller implementiert, legt die Vermutung
nahe, dass er daraus irgendwann ein batteriebetriebenes Gimmick für
unterwegs machen will, und für die Batterielaufzeit spielen die
verbrauchten Taktzyklen eine wesentliche Rolle.
Natürlich kann man die Sache sowohl bzgl. der Geschwindigkeit als auch
des Speicherbedarfs weiter optimieren. Der Hinweis auf mögliche Ansätze
wurde ja bereits gegeben:
Dass Ralph das
Spiel aber auf einem Mikrocontroller implementiert, legt die Vermutung
nahe, dass er daraus irgendwann ein batteriebetriebenes Gimmick für
unterwegs machen will
genau das.
Allerdings geschieht das Aufdecken der Leerfelder ja relativ selten und später wird mit gaaanz weitem Abstand die Beleuchtung des Displays deutlich mehr Strom fressen, von daher ist ein weiteres Nachdenken darüber nicht wirklich zwingend.
Wie das immer so ist, mit dem was man machen will: An meiner eigenen Spielekonsole bastel ich ja schon lange und momentan sieht es so aus, als ob es ein STM32F4 werden wird, mit einem 160x128 Display (ob das überhaupt jemals etwas wird laß ich mal so stehen). ... :-) grundsätzlich mag ich das für - kein Scheiß jetzt - die Sauna haben um dann dort das spielen zu können was ich mag. Die kaufbaren (billig)Konsollen haben da bis zu 500 Spiele drauf... und keines ist wirklich gut. Entweder das Display oder die Steuerung zu schlecht. Außerdem: es ist immer wieder schön, was eigenes zu sehen ( neben den Dingen, die man dienstlich machen muß ).
Minesweeper hatte ich lange nicht gespielt ... und bin jetzt wieder "angesteckt". Grundsätzlich wird das zu meinem STM32F4 dazugesellt werden und ich habe dann doch glatt schon 7 Spiele in dem Flash-Ram untergebracht. Der F4 hätte genügend Ram auch ohne deine Stack-Version, allerdings reizt es mich immer, was auch mit einem CH32V003 geht und wie das ausschaut, wird das darauf auch laufen.
Für alle die, die immer mal was gucken möchten, habe ich jetzt hier einmal das Gesamtprogramm für MineSweeper in der Linuxkonsole hier eingestellt, :-) mit nur einer einzigen Datei.
@Ralph: Auch ich wünsche dir eine schnelle Genesung!
vielen Dank... richtig gut wird es nie mehr werden, dafür habe ich in meinem Leben zu lange geraucht. Verrückt ist, dass ich wegen der Lunge und der COPD ins Krankenhaus gekommen bin, und jetzt wegen einer Schleimbeutelentzündung am Ellenbogen das Krankenhaus nicht verlassen darf / soll ....
:-) werde ich halt weiter mit den - begrenzten - Spielzeugen spielen || Platine für Konsole routen
