Hallo,

Zitat:

p = MinenÜbrig / FelderÜbrig

ist natürlich eine feine Methode.

Mir stürzt das Programm ab, wenn ich ein Feld 300x38 mit "0" Minen ( böse das ) von dem rechten unteren Feld aus aufdecke.Ohne AutoFlag/Autosubtract.
Das sind dann wohl 300x38 = 11400 Einträge.
300x37 funktioniert.-> Mit TurboDelphi kompiliert-> Stackoverflow bei (Zeile 287 bei mir: Pick(i,j) )
Ich habe mal nur die Dateien angehängt, die man zum Kompilieren braucht. Mit den .dcu's kann ich nichts anfangen.

Wie kann man denn nun geschickt die Rekursionstiefe verringern?
Das erinnert doch stark an FloodFill und weiterhin an Tiefensuche.
Was, wenn man eine Breiten/ Umfangssuche macht, dann müsste man "nur" die Punkte der Wellenfront{-en wenn man irgendwo im Feld einen Punkt anklickt ) speichern.Das entspricht auch mehr dem Muster das üblicherweise entsteht.
Das Anzahl der Punkte wäre optimal der Umfang = sqrt(umgrenzter Fläche)*Konstant bei sternenförmiger Anordnung der Minen aber nicht.

Gruß Horst

Hallo Horst,

Horst_H hat folgendes geschrieben :

stürzt das Programm ab, wenn ich ein Feld 300x38 mit "0" Minen ( böse das ) von dem rechten unteren Feld aus aufdecke.Ohne AutoFlag/Autosubtract. Das sind dann wohl 300x38 = 11400 Einträge. 300x37 funktioniert.-> Mit TurboDelphi kompiliert-> Stackoverflow bei (Zeile 287 bei mir: Pick(i,j) )

Danke für's ausprobieren Ich hatte schon überlegt, dass das wahrscheinlich das nächste Limit ist. Wahrscheinlich sind längere Aufdeck-Zyklen möglich, wenn ich aus der Rekursivon Minensuche eine Schleife mache (wird glaube ich schwer, möglicherweise mit bösen GoTos). Oder sollte ich den Call-Stack hochstellen? Da gab's doch mal was, wie ging das gleich..

Grüße,
Daniel

Hidden hat folgendes geschrieben:

Sinspin hat folgendes geschrieben : €dith2: Warum Zoom? Ich habe es mal mit 50x50 probiert. Ich treffe die Felder kaum noch mit der Maus. Verstehe ich nicht Wenn du das Mausrad scrollst, zoomt es rein und die Felder werden größer. Das behandelt doch genau dein Problem? Als du von großen Feldern sprachst, hatte ich beim Coden mit 300x160, 9900 Minen getestet (siehe Anhang). Bei noch größeren Feldern treten dann aber Fehler auf, ich weiß noch nicht was ich als vernünftige Grenze festsetzen soll

War wohl doch etwas spät gestern Abend. Zoom und ziehen funktioniert astrein. Du könntest ja noch auf dem schwarzen Rand Rechts und Unten einen weißen Balken Strich), im Verhältnis zur Gesamtgröße, an der entsprechenden Position anzeigen so das man weis wo man sich befindet. Also eine Simulation der Scrollbalken.

Edit:
Delphi : Settings im Quelltext ändern : STRG+O+O. Dann kann man auch den Stack leichter erhöhen ohne immer in die Optionen zu gehen.
Ich fände es aber anspruchsvoller es anders zu lößen ZB. die Koordinaten in ein Array schreiben und nur den Index übergeben. In der Funktion die Anzahl der Variablen verringern, bzw. diese auch in dem Array ablegen. Schleifen mit bekannter länge ausimplementieren (Spaghetticode) um die Schleifenvariable weg zu bekommen.

Hallo,

Zitat:

Koordinaten in ein Array schreiben und nur den Index

Die Koordinate ist doch schon ein Index = ZeilenNr * SPALTENZAHL+SpaltenNr
Ich suche gerade nach einer Idee, die ich bei "Game of Life" gesehen hatte.
Dort wurde die Belegung der 8 umgebenden Felder in in einem Byte gespeichert.
Popcount für 1 Byte geht über Tabelle ja sehr schnell.
Ob das überhaupt hier was bringt?

Gruß Horst

Ich habe mir deinen Quelltext nicht angesehen. Aber ich meine ja nicht die Daten des Mienenfeldes, das die in einem Array sind ist klar. Wenn Du die Suche aufrufst, werden ja wohl Parameter übergeben und die rekursive Funktion hat Variablen. Die kann man auch in einem globalen Array ablegen. Dann braucht nur der Zeiger auf den Index übergeben zu werden. Das Array selber kann aber auch nicht auf dem Stack liegen sonst bleibt das Problem das gleiche. Das muss Speicher sein. am besten ein dynamisches Array dessen maximale Größe man großzügig festlegt um sie nicht dauernd ändern zu müssen.

Die Nachbarn kann man in einem Byte speichern. Indem man die 8 Bits einzeln verwendet. Das geht dann aber nur mit binären Informationen. Reinpacken und rauslesen kann dann aber wieder extra Zeit kosten.

Ich schau mir heute Abend mal die Quelltexte an. Wenn nicht gerade Sommer wäre, dann wären sicher auch die Profioptimierer schon aktiv

Sinspin hat folgendes geschrieben :

Ich schau mir heute Abend mal die Quelltexte an. Wenn nicht gerade Sommer wäre, dann wären sicher auch die Profioptimierer schon aktiv

Ein paar Änderungen habe ich noch im Kopf*, wenn du schon reinschauen und ändern möchtest, kannst du das Update ja reinmergen

*Ich werde noch die Zeichenmethode so anpassen, dass nur veränderte Abschnitte überzeichnet werden (und nicht immer der ganze sichtbare Bereich).

Hallo,

Es bringt alles nichts
die Funktion Pick ist ja der "Übeltäter"
Ich habe Autoflag und Autosubtract in proceduren ausgelagert.Damit werden deren Variablen nur kurzfristig auf dem Stack erzeugt und wieder gelöscht.Die Boolean habe ich global gemacht, weil sie innerhalb von Pick ja nicht in einer Rekursion gebraucht werden.
Das hilft aber nichts, da bei einer Klassen- Funktion/Prozedur ja immer verdeckt der Zeiger auf die Instanz und sonst was übergeben, was schon wieder 12 Byte belegt.So sind es nun 300 x50 statt 300 x37.Das ist nicht so berauschend.
Was auch schon ohne den Einsatz eines Feldes für die Koordinaten ging.


TiefeKoor[Tiefe] hätte ich mir sparen können.
Nur für die von mir so genannte procedure OpenFreeFields(x,y: Integer); werden die Variablen i,j gebraucht da dort rekursiv von einem leere Feld aus alle umliegenden Felder abgeklappert werden.
Mit einem Stack von 16 Mb kommt man erheblich weiter, bis zur Tiefe in der Gegend von 209408 ( also bis 457*457, da nur alle 512 die Tiefe angezeigt wird und keine Ausgabe in das Memofeld erfolgt dauert das nur Sekundenbruchteile ).Die Ausgabe dauert sehr lang.

Wie bewerkstelligt man nun eine Wellenfront, die entweder am Rand oder einem Mitglied der Wellenfront endet.

Gruß Horst

Moin,

da ich jetzt erstmal ins Büro muss, gibt es ein Update mit einem kleinen Fehler: Der Preview beim Reinzoomen wird falsch positioniert.
Ansonsten gibt es aber jede Menge neues, u.A.:

• Beim Aufdecken neuer Felder wird nur noch der veränderte Bereich neu gezeichnet, der Rest der Buffer-Bitmap wird weiter verwendet.
  
• Die Buffer-Bitmap ist nun doppelt so groß wie der sichtbare Bereich, damit sieht man in der Vorschau zu DragNDrop oder Zoom keine nicht bemalten Felder.
  
• Es wird jetzt sorgsamer ausgewählt, wann die Buffer-Bitmap neu bezeichnet werden muss; wenn ein DragNDrop beispielsweise negative Koordinaten erzeugen würde und nicht voll ausgeführt wird, reicht ein Repaint der Paintbox und verwerfen der temporären DragNDrop-Koordinaten.
  
• Das Feld hat einen schwarzen Rand bekommen, durch den es jetzt leichter zu erkennen sein sollte wenn man auf einem gezoomten Feld die Begrenzung erreicht (leider bin ich noch nicht dazu gekommen, die Zeichenroutine im maximal rausgezoomten Fall so zu überarbeiten, dass man ihn auch ganz sieht).
  
• Im Startup-Dialog gibt es der Einfachheit halber einige Buttons mit vorgeschlagenen Feldgrößen und Minenzahlen

Grüße,
Daniel

Hi,

Die Einstellungen können jetzt in eine Datei im Programmordner gespeichert werden.

Hidden hat folgendes geschrieben :

Horst_H hat folgendes geschrieben : Man kann ja zu Beginn das Startfeld und eventuell seine Umgebung ausklammern. Aktuell wird das Spielfeld genau einmal durchgegangen und in jedes Feld mit einer Wahrschienlichkeit von p = MinenÜbrig / FelderÜbrig eine Mine gesetzt. Ich werde das anpassen, sodass die 9 Felder um die Startposition dabei ausgelassen werden und FelderÜbig entsprechend vermindert wird.

Ist nun umgesetzt.

Wenn ich mehr Zeit in das Projekt stecke, sind die nächsten zwei Umsetzungen:

• Ein Problem an Minesweeper als Logik-Puzzle ist, dass es nicht immer eine eindeutige Lösung gibt. Ich will einen Solver einbauen, dann kann das Programm erkennen wenn der Nutzer zwischen gleichwahrscheinlichen Lösungen auswählt und wird die Wellenfunktion auf die Auswahl kollabieren.
  Das einzige Problem daran: Ich werde einen Indikator für die Laufzeit dieses Solvers brauchen, denn einfach starten und hoffen dass das Programm in diesem Jahrhundert noch terminiert, ist doof.
  
• Abspeichern und Laden der aktuellen Minemap, eventuell ein Editor-Modus zum Erstellen bestimmter, interessanter Situationen.

Download wie immer im ersten Post.

lg,
Daniel

Schönes Icon hast Du da jetzt drinne. Mehr leider auch nicht. Es war vorher mit etwas Ausdauer möglich den sichtbaren Ausschnitt zu verschieben, nun ist es unmöglich. Sobald ich die Maus bewege springt das ganze Spielfeld einfach wild herum. Halte ich sie still taucht das Spielfeld links nach einiger Zeit auf aber es geht weiter mit dem wilden rumspringen sobald ich die Maus wieder bewege.

Aus diesem wofür auf immer "log"

Zitat:

Painting (busy) .. Idle .. Painting (busy) .. Idle .. Painting (idle) .. Idle .. Painting (idle) .. Idle .. Painting (idle) .. Idle ..

und so weiter. Habe nach mehr als 30 Einträgen aufgegeben.
Habe dummerweise die letzte Version überschrieben, so das ich jetzt nicht mehr Spielen kann.

Hi,

Das klingt ganz als wäre die Funktion Autoscroll bei dir aktiviert (die Checkbox dafür ist eigentlich gar nicht sichtbar, aber offenbar ist die bei mir nur deshalb nicht aktiv weil ich die Einstellungen von der Platte lade.

Ich werde gleich ein Update hochladen, das diese Funkion sicher deaktiviert.
Das Log dient nur dazu, bei eventuellen Fehlern sagen zu können in welcher Funktion diese Auftreten. Painting (busy) ist das gewöhnliche Neu-Zeichnen, Painting (idle) das Neu-Zeichnen im Hintergrund während gezoomt oder gescrollt wird (mit ProcessMessages).

lg,
Daniel

Hallo,

Zitat:

gleichwahrscheinlichen Lösungen auswählt und wird die Wellenfunktion auf die Auswahl kollabieren.

Wie denn?Wo denn?Was denn?
Muss ich die neue Version herunterladen, um das zu verstehen?

Braucht ein Lösungalgo wirklich sehr lang?
Bombe oder Nicht-Bombe sind die beiden Zustände eines Feldes. 16 Felder eben 16 Bit = 65536 Brute-Force Möglichkeiten, das geht doch sicher Ratz-Fatz.

Ich stelle mir das so vor, dass man die angrenzenden nicht aufgedeckten Felder einfach fortlaufend in LinearFeld nummeriert, damit ist Summe auch immer die Summe aufeinanderfolgender Felder. Von einem Startfeld im Uhrzeigersinn zum Beispiel.
Feld x1,y1 hat laut autosubtract noch 2 Bomben zu Nachbarn und grenzt an Feldnummer 0,1,2
Feld x2,y1 hat laut autosubtract noch 1 Bombe zu Nachbarn und grenzt an Feldnummer 1,2,3
etc pp.
Man bestimmt die Lösungsmenge zu Feld1 011,101,110 ( 3 statt 8 )
kombiniert diese mit Feld 2 = 1/0 + Lösungen Feld 1 / ohne letztes Bit
1-01/1 -> Keine Lösung, denn 101 sind 2 gesetzte Bit
0-01/1 -> 001 = mögliche Lösung

1-10/1 -> Keine Lösung, denn 110 sind 2 gesetzte Bit
0-10/1 -> 010 = mögliche Lösung

1-11/0 -> Keine Lösung, denn 111 sind 3 gesetzte Bit
0-11/0 -> Keine Lösung, denn 011 sind 2 gesetzte Bit

Dummerweise müsste man jetzt irgendwie abfragen, dass bei den möglichen Lösungen , das Bit 0 des Feldes vorher hier immer 1 ist und damit die Bombe an Stelle 0 gewiss ist.
Aber man erkennt bei der Vorgehensweise, das man schon bei den hier skizzierten 4 Feldern= 16 Möglichkeiten nur 2 mögliche Lösungen hat, die man weiterverfolgen kann.

Gruß Horst

Moin Horst,

in den meißten Fällen, die durch Autosubstract nicht bereits abgedeckt werden, kann man wie du sagst wirklich durch Vergleichen benachbarter Zahlen schon weiterkommen. Wenn ich von Hand löse, habe ich dafür folgende weitere Heuristik, die allerdings ekelhaft zu implementieren ist:



(Wie für sets in Delphi sollen +, *, - für die Vereinigung, den Schnitt bzw die Differenz zweiter Mengen stehen. card bezeichnet die Anzahl der Elemente.)

In zwei benachbarten, aufgedeckten Feldern stehen Minenzahlen a,b (o.E. a <= b), die sich auf Feldmengen A,B beziehen.
Dann enthalten folgende Mengen mindestens folgende Minenzahlen:
B-A mindestens b - a = 1 (alles Minen, falls card(B-A) = b - a),
A*B mindestens b - card(B-A),
und damit A-B maximal a - ( b - card(B-A) ) = a + card(B-A) - b = 1 + 1 - 2 = 0 (alles frei, falls a + card(B-A) = b).

Das deckt leider nicht alle lösbaren Fälle ab, teilweise muss man wirklich annehmen dass Feld X eine Mine enthält und mit dieser Annahme das ganze Spielfeld durchknobeln, bis es zu einem Widerspruch führt (wenn ich dich richtig verstanden habe, wolltest du immer nur zwei Felder vergleichen?).

---

Eine Methode, die sicher jede Lösung findet und ansonsten Wahrscheinlichkeiten liefert, ist sich für jede freigedeckte Zahl alle möglichen Belegungen in folgender Weise aufzuschreiben,
Minen: (A, B), Keine Minen: (C, D, E)
Minen: (A, C), Keine Minen: (B, D, E)
usw,

und diese Belegungs-Listen X,Y für verschiedene Felder probeweise zusammenzufügen. Diese "Summe" zweier Belegungen ist dabei illegal, sobald ein Feld in beiden Listen enthalten ist (Mine und keine Mine gleichzeitig). Nach paarweisem Aufsummieren aller Belegungen aus X x Y und Filtern aller illegalen Belegungen kennt man die Wahrscheinlichkeit, hinter jedem dieser Felder eine Mine zu finden.

Das Problem nun ist die Auswahl, welche Listen man addiert; die Menge der möglichen Kombinationen ist sehr groß, und ich habe das Programm diese Woche darauf vorbereitet auf 300x160-Brettern zu spielen. Minesweeper ist np-vollständig, also wird es da relativ enge Grenzen geben.

Werde es trotzdem vielleicht bei Gelegeneheit implementieren.

Grüße,
Daniel

Hallo,

Die neue Version hat mal wieder viele kleine Änderungen. Sichtbar ist nur, dass Scrollen nun exakter funktioniert und das Game Results-Fenster ein paar mehr Infos ausgibt. Zusätzlich wird nun die Anzahl der nicht aufgedeckten Felder angezeigt, nicht nur die der verbleibenden Minen.

Edit: Ach ja, mit Rechtsklick-Drag könnt ihr jetzt einen Bereich auswählen und exakt auf diesen Zoomen.

Grüße,
Daniel

Die neue Version enthält einen Solver. Der hat noch ein besseres Interface verdient (speziell wenn weitergespielt wird während der Solver aktiv ist und nicht nur eine statische Stellung analysiert), aber das muss warten bis ich wieder mehr Zeit habe.

Damit sollte es nun machbar sein, folgenden Spielmodus einzuführen:

• Klickt der Spieler auf ein Feld und weiß nicht mit Sicherheit, dass es frei ist, so wird bestraft (dem Solver wird zufällig eine Lösung entnommen, in der dort eine Mine ist).
  
• Klickt der Spieler auf ein Feld und war dabei zum Raten gezwungen (unentscheidbar, Auswahl zwischen gleich wahrscheinlichen Lösungen), so wird eingegriffen (dem Solver wird zufällig eine Lösung entnommen, in der dort keine Mine ist).
  

Grüße,
Daniel