Entwickler-Ecke :: Thema anzeigen - [Sweeper] (Minesweeper-Klon)

Hidden - So 30.06.13 09:24
Titel: [Sweeper] (Minesweeper-Klon)

Hallo mal wieder :wave: :wave:

Sweeper ist ein Klon des Windows-Spiels Minesweeper [http://de.wikipedia.org/wiki/Minesweeper]. Viel zu erklären gibt es nicht, bis auf einige 'Comfort'-Optionen:

Autoflag isolated mines, mit der Minen markiert werden wenn sie die einzigen verdeckten Felder um ein aufgedecktes Feld sind
und Autosubstract flagged Mines: Eine der Hauptaufgaben des Spielers ist es, die bereits gefundenen Minen im Kopf von den Zahlen in Feldern abzuziehen. Diese Option veranschaulicht die Wirkung dieses Prozesses.

Für große Spielfelder kann mit dem Mausrad und DragNDrop gezoomt bzw. gescrollt werden. Zum exakteren Zoom kann mit gehaltener rechter Maustaste ein Bereich ausgewählt werden.
Seit Rev 12 gibt es auch einen Solver, der aber noch ein besseres Interface braucht.

Programm (exe, 1000.5 KB)
Quelltext (rar, 31.88 KB)

Screenshot

Bugs:

Zu dem Modal-Dialog bei Programmstart gibt es leider keinen Taskleisten-Eintrag. (klick) [http://www.entwickler-ecke.de/viewtopic.php?t=111830] :(
Der Preview beim Rauszoomen srimmr nicht.

ich wünsche viel Spaß beim ausprobieren :)

Hidden - So 30.06.13 13:22

Marc. hat folgendes geschrieben :

Mathematiker hat folgendes geschrieben :

und dann kommt eine Fehlermeldung (5), was das auch sein mag.

Dein Windows 8 ist komisch. Bei mir funktioniert die Rev1 einwandfrei. :D

Hmm, ok. Habe schon meinen Mitbewohner überredet, dass ich das gleich mal bei ihm testen kann.

Marc. hat folgendes geschrieben :

Allerdings sollte das Spiel doch enden, wenn ich eine Mine aufdecke, oder nicht? Das ist nämlich nicht mehr Fall. :idea:

Japp, ist so gewollt :) Die rote Mine wirst du nicht mehr los, ansonsten wirkt sie auf das Spiel wie eine geflaggte.

Hidden - So 30.06.13 17:06

BenBE hat folgendes geschrieben :

Unter Wine gibt es zahlreiche grafische Artefakte.

Die beobachte ich unter Windows auch, wenn ich das Programm nicht in den Vollbildmodus schalte. Was relativ seltsam ist, alles was passiert ist ein artefaktfreies Bild per StretchDraw auf eine Paintbox zu packen :gruebel: Und StretchDraw scheint runterskalieren nicht zu mögen :?

BenBE hat folgendes geschrieben :

Zusätzlich ist dein Hit-Test falsch, so dass es insbesondere beim Zoomen des Feldes dazu kommen kann, dass er das Feld rechts daneben anklickt.

War lokal schon gefixt, beim hit-Test empfiehlt es sich wohl ausnahmsweise mal mit / zu arbeiten statt div wie im Rest des Programms :P

BenBE hat folgendes geschrieben :

Ferner ist deine Aufdeck-Methode derart langsam, dass man entweder auf dem Spielfeld den Fortschritt animieren sollte ODER aber aber das Aufdecken durch BeginUpdate/EndUpdate instantan gestalten sollte.

Ist eigentlich bereits instantan, d.h. alles was geändert wurde wird auf einmal eingezeichnet. Ich vermute das Application.ProcessMessages zwecks Log-Update zeichnet die Paintbox zwischenzeitlich mehrfach neu. Da könnte BeginUpdate helfen, du hast Recht :idea: [Edit] ggf hilft es auch schon, die extra angelegte Buffer-Bitmap nicht bei JEDEM Paintbox-Repaint komplett neu zu zeichnen :autsch::autsch: [/Edit]. (Problem bei der Aufdeck-Methode ist, dass mit beiden 'Comfort'-Hilfen eigentlich nur noch eine Heuristik zum komplett-Lösen fehlt. Und das ist dann Turing-Vollständig, also weiß ich nicht wie viel sich da noch optimieren lässt. :()

BenBE hat folgendes geschrieben :

Auch sollte die farbliche Hervorhebung von Mienen, explodierten Feldern, ... besser gestaltet werden.

Du meinst ohne Autosubstract? Da gefällt es mir eigentlich schon ganz gut, mit Autosubstract treten gefundene Minen absichtlich ein bisschen in den Hintergrund.

lg,
Daniel

Martok - So 30.06.13 19:09

Hidden hat folgendes geschrieben :

BenBE hat folgendes geschrieben :

Unter Wine gibt es zahlreiche grafische Artefakte.

Ja, in den Standardeinstellungen macht das nur Nearest Neighbor, das sieht bescheiden aus ;-)
HALFTONE fixt das ein wenig (ist nicht wirklich AntiAliased, aber geht schon). StretchDraw verleiert da einiges wieder, also direkt StretchBlt aufrufen:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:

  SetStretchBltMode(PaintBox1.Canvas.Handle, HALFTONE);
  StretchBlt(PaintBox1.Canvas.Handle,
             0, 0, PaintBox1.ClientWidth, PaintBox1.ClientHeight,
             FBuffer.Canvas.Handle,
             0, 0, FBuffer.Width, FBuffer.Height, SRCCOPY);
//  PaintBox1.Canvas.StretchDraw(PaintBox1.ClientRect, FBuffer);

Hidden - So 30.06.13 22:34

Hi,

Revision 2 und nun auch schon 3 ist online. In [2] ist die Grafik sehr viel runder geworden und eine weitere 'Comfort'-Option ist hinzugekommen (Autosubstract-Heuristik bei unveränderter Spielfeldoptik). [3] ist ein Hotfix: wurden zu viele Minen markiert, so ist der Minenzähler nicht ins negative gegangen sondern bei Null nach unten übergelaufen.

Das Programm startet nun im (fast)-Vollbildmodus, das heißt mit voller Breite; die Fensterhöhe wird nach wie vor so festgelegt, dass das Minenfeld ein Format von 30:16 hat. Wenn das Fenster übermäßig klein gezogen wird, gehen die Minensymbole und Zahlen über die Kästchengröße hinaus, gegebenenfalls könnte ich das Fenster vielleicht auf eine Mindestgröße beschränken.

Zu dem Modal-Dialog bei Programmstart gibt es leider keinen Taskleisten-Eintrag. :(

Sinspin - Sa 06.07.13 15:10

Als bekennender Minesweeper Fan musste ich mir Dein Spiel mal reinziehen. Nach einer Runde habe ich es aber wegen unüberwindlicher Differenzen wieder gelöscht.
Wenn ich am Fensterrand ziehe dann wird mir der Rand aus der "Hand" gerissen umd flackert wild rum. Warum legst Du die Feldgröße nicht via Option fest und packst alles in eine Scrollbox? So wäre es dann auch möglich endlich mal Spiele mit utopischen Abmessungen also, hunderten Feldern, zu erzeugen.

Was ich sehr gut finde, das man nach einer Miene die man kassiert weiter machen kann. Den Timer hätte ich gerne optional, also zu abschalten. Sowas finde ich bei Knobelspielen mehr als überflüssig. Es ist doch interessanter ob man es schafft zu lösen ohne eine Miene zu kassieren.

Hidden - Sa 06.07.13 15:55

Hallo

Sinspin,

Hidden hat folgendes geschrieben :

Bugs:

Die Methode zum Anpassen der Spielfeldgröße auf 30:16 (für quadratische Minenfelder) verhindert das Vergrößern des Formulars am Rand (an der Ecke funktioniert es, also wenn Höhe und Breite gleichzeitg verändert werden).

Sinspin hat folgendes geschrieben :

Wenn ich am Fensterrand ziehe dann wird mir der Rand aus der "Hand" gerissen umd flackert wild rum. Warum legst Du die Feldgröße nicht via Option fest und packst alles in eine Scrollbox? So wäre es dann auch möglich endlich mal Spiele mit utopischen Abmessungen also, hunderten Feldern, zu erzeugen.

Hmm, das ist eine Idee. Ich implementiere das mal schnell in der Art.
Größere Spielfelder sind aber mit Vorsicht zu genießen: Das Aufdecken ist Turing-vollständig, also recht Zeitintensiv. Wenn Comfort-Optionen zum Aufdecken und Markieren aktiviert sind, kann das ggf auch mal 2-3 Minuten dauern.

Sinspin hat folgendes geschrieben :

Was ich sehr gut finde, das man nach einer Miene die man kassiert weiter machen kann. Den Timer hätte ich gerne optional, also zu abschalten. Sowas finde ich bei Knobelspielen mehr als überflüssig. Es ist doch interessanter ob man es schafft zu lösen ohne eine Miene zu kassieren.

Hmm, das ist ja nicht viel Aufwand. Wenn mich ein Timer nicht interessiert, ignoriere ich ihn meißt aber einfach :)

lg,
Daniel

Horst_H - So 07.07.13 07:41

Hallo,

der Effekt tritt bei autosubtract auf.
Wenn ich ein Feld als Miene markiere, das defintiv keine ist, dann entstehen Summen <0 und die richtigen Mienen werden aufgedeckt.
BenBe hat eben erwartet , dass das Programm dann stille schweigt.
Aber dann funktioniert das mit den Summen auch nicht mehr, weil, wie Du schon schriebst, man einfach mal probehalber markiert werden kann und autosubtract liefert einem die Mienen.

Diese Flackerei, schon bei Mausbewegungen, ist ja sehr nervig, wenn ich es mit TurboDelphi kompiliere.
In Lazarus 1.0.6 gibt es form.doublebuffered = true in der dfm nicht und es flackert trotzdem nichts ( GTK2, uuuh wie alt ).
Diese merkwürdigen Farben clWebDarkred habe ich mit Tcolor($000080) oder ähnlichem ersetzt.Ebenso Roundrect durch rectangle.
Zum Glück hat das Feld eine angenehme Größe für meine geschwächten Augen....

Gruß Horst

Hidden - So 07.07.13 08:12

Horst_H hat folgendes geschrieben :

Hallo,

Hi :)

Horst_H hat folgendes geschrieben :

Zum Glück hat das Feld eine angenehme Größe für meine geschwächten Augen....

Ich spiele auch ausschließlich mit maximiertem Fenster, sonst klickt man viel zu schnell mal daneben ;)

Horst_H hat folgendes geschrieben :

Diese Flackerei, schon bei Mausbewegungen, ist ja sehr nervig, wenn ich es mit TurboDelphi kompiliere.

Die gibt es lokal schon nicht mehr, dafür kann man jetzt mit dem Mausrad zoomen. Sowenn ich es denn noch schaffe, dass das Spielfeld auf die Mausposition zoomt statt auf (0;0) :lol:

Hidden - So 07.07.13 19:52

So, jetzt gibt es was kaputtzutesten :)

Bekanntlich dauert Programmieren ja immer länger als geplant, vor allem dann wenn dem Entwickler ständig neue Dinge einfallen, die man einbauen könnte :P

Änderungen:

Die Fenstergröße wird nicht länger angepasst, statt dessen kann mit dem Mausrad gezoomt und per DragNDrop in diesem Zoom navigiert werden.
Die Schriftgröße in den Kästchen kann die Kästchengröße nicht länger überschreiten, auch wenn extrem weit herausgezoomt wird.

Das Formular blinkt jetzt nach jedem Feld-Aufdecken in der Taskleiste, da dies mit Comfort-Optionen / Aufdeck-Heuristik schonmal länger dauern kann ( -> [Alt][Tab]bing ).

Weiß jemand eine Alternative zu den auskommentierten, nicht funktionierenden, Methoden um festzustellen wann dies nötig ist?

1:
2:

if not false {self.Showing}{self.focused}{self.Active} then
  FlashWindow(Handle, true);

Horst_H hat folgendes geschrieben :

Diese Flackerei, schon bei Mausbewegungen, ist ja sehr nervig, wenn ich es mit TurboDelphi kompiliere.

Du meintest aber schon beim Vergrößern / Verkleinern des Formulars, oder? Anstonsten hatte bei mir nichts geflackert, ich habe aber auch kein Turbo Delphi zur Hand.

Sinspin - So 07.07.13 23:23

Dann mal,...
der Tragödie zweiter Teil. :roll: Feldgröße, Mienenanzahl, Timer, Größe ändern. Fein, Absolut!
Nur, zu was nochmal, ist dieses permanente blinken des Fensterrahmens und Taskbuttons da? Um den Nutzer zu verwirren? Das schafft es. Selbst wenn das halbe Spielfeld mit einem Schlag aufgedeckt wird dauert das nichtmal eine Sekunde und ich habe wahrlich keinen schnellen Rechner. Wenn Du den Output rechts schreibst, da frage ich mich ob da nen ProcessMessages dranhängt denn ich kann sehen wie die Zeilen kommen. Das wäre dann kein Wunder wenn das was Lahm wird.
Wenn man da was drehen wollen würde könnte man ja den Aufdeckvorgang an sich animieren. Aber darum geht es ja nicht. Sondern nur darum, so Klever zu sein die Felder zu umschiffen hinter denen sich eine Überraschung versteckt. Aber nichts Süßes und auch kein Bunny.

€dith:
Als Vorschlag, miss doch die Zeit die vergeht von Start bis Ende der Aktion und lass es nur blinken wenn es länger als 1 1/2 Sekunden gedauert hat.
€dith2:
Warum Zoom? Ich habe es mal mit 50x50 probiert. Ich treffe die Felder kaum noch mit der Maus. Was spricht gegen die Eingabe einer Rastergröße und die Verwendung einer Scrollbox? So das ich den für mich aktuell interessanten Ausschnitt betrachten kann egal wie groß das Spielfeld ist.

Hidden - Mo 08.07.13 06:59

Hi,

Sinspin hat folgendes geschrieben :

Nur, zu was nochmal, ist dieses permanente blinken des Fensterrahmens und Taskbuttons da?
€dith: Als Vorschlag, miss doch die Zeit die vergeht von Start bis Ende der Aktion und lass es nur blinken wenn es länger als 1 1/2 Sekunden gedauert hat.

Daran hatte ich auch schon gedacht, als Notlösung oder zusätzliche Bedingung wann das Fenster blinkt.
War so nicht vorgesehen, ich hoffte relativ schnell auf eine Antwort hierauf:

Hidden hat folgendes geschrieben :

Weiß jemand eine Alternative zu diesen auskommentierten, nicht funktionierenden, Methoden um festzustellen wann dies nötig ist?

1:
2:

if not false {self.Showing}{self.focused}{self.Active} then
  FlashWindow(Handle, true);

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

Sinspin hat folgendes geschrieben :

Was spricht gegen die Eingabe einer Rastergröße und die Verwendung einer Scrollbox? So das ich den für mich aktuell interessanten Ausschnitt betrachten kann egal wie groß das Spielfeld ist.

Als nächsten Schritt könnte man noch überlegen, ob man die h/v-Position des Ausschnitts auf dem Feld irgendwie anzeigt (abgesehen von den Koordinaten unten rechts).
Einfach die bestehende Paintbox auf eine Scrollbox zu packen, funtioniert leider nicht: Man muss schon auswählen, was gezeichnet wird, sonst wird es langsam. Wenn du die Rastergröße eingeben willst statt mit dem Mausrad zu scrollen, wirst du wahrscheinlich mehrmals probieren müssen bis es stimmt. Was ist da der Vorteil? :gruebel:

Sinspin hat folgendes geschrieben :

Wenn Du den Output rechts schreibst, da frage ich mich ob da nen ProcessMessages dranhängt denn ich kann sehen wie die Zeilen kommen. Das wäre dann kein Wunder wenn das was Lahm wird.

Nein, kein ProcessMessages. Memo1.Lines.BeginUpdate verhindert den Effekt, aber dann fühlt sich die Oberfläche "eingefroren" an (das ist sie auch so, aber man bekommt nicht mehr mit dass etwas passiert).
Hauptgründe für lange Aufdeckzeiten sind:

Stark minengesättigte Felder: Aktuell wird so lange ein neues Spiel gestartet, bis am Anfang etwas aufgedeckt wird -- ohne Rücksicht darauf, wie unwahrscheinlich dieses Ereignis bei einem 100x100 Feld mit 9998 Minen ist.
große Felder mit wenig Minen, besonders wenn Autosubstract + Autoflag aktiviert sind.

Horst_H - Mo 08.07.13 07:26

Hallo,

Zitat:

Stark minengesättigte Felder: Aktuell wird so lange ein neues Spiel gestartet, bis am Anfang etwas aufgedeckt wird -- ohne Rücksicht darauf, wie unwahrscheinlich dieses Ereignis bei einem 100x100 Feld mit 9998 Minen ist.

Man kann ja zu Beginn das Startfeld und eventuell seine Umgebung ausklammern.
Oder ganz simpel eine Umkehrung machen.
Alle Felder sind zu Beginn Minen-> Startfeld befreien und dann per Zufall die restliche Anzahl.
Wer zu viele Prüfungen dabei hasst, kann ja einfach eine Liste aller möglichen Feldkoordinaten machen, das Startfeld aber nicht einfügen, diese Liste mischen und die ersten ((N-1) - Anzahl Minen ) von Minen befreien.

Gruß Horst

Horst_H - Mo 08.07.13 09:33

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

Hidden - Mo 08.07.13 09:55

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

Grüße,
Daniel

Sinspin - Mo 08.07.13 11:10

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.

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.

Sinspin - Mo 08.07.13 15:14

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 ;-)

Horst_H - Mo 08.07.13 20:21

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.

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

0045E740 8BF8             mov edi,eax      
0045E742 33C0             xor eax,eax
//Hier werden 12 Byte belegt
0045E744 55               push ebp          
0045E745 6895E84500       push $0045e895
0045E74A 64FF30           push dword ptr fs:[eax]

0045E74D 648920           mov fs:[eax],esp

uSweeper.pas.379: with TiefeKoor[Tiefe] do
0045E750 A11C764600       mov eax,[$0046761c]
0045E755 8B1520764600     mov edx,[$00467620]
0045E75B 8D34D0           lea esi,[eax+edx*8] // TKoor -> ESI
uSweeper.pas.381: result := getPick(t_x,t_y);
0045E75E 8B4E04           mov ecx,[esi+$04]
0045E761 8B16             mov edx,[esi]
0045E763 8BC7             mov eax,edi
0045E765 E87EF1FFFF       call TSpielfeld.getPick
0045E76A 8BD8             mov ebx,eax

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

Hidden - Di 09.07.13 11:40

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

Hidden - Sa 13.07.13 23:04

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

Sinspin - Sa 13.07.13 23:46

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.

Hidden - Sa 13.07.13 23:56

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

Horst_H - So 14.07.13 14:28

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

Hidden - So 14.07.13 18:39

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:

Minesweeper_with_sets

(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

Hidden - Do 01.08.13 10:16

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

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!