Was ist der Algorithmus hinter Minesweeper Generation

Question

Nun, ich habe durch viele Seiten erfahren, wie man es lösen kann, aber fragte sich, wie man es erstellt. Ich interessiere mich nicht sehr für die Codierungsaspekte, sondern wollte mehr über die Algorithmen dahinter wissen. Wenn das Gitter zum Beispiel mit 10 Minen erzeugt wird, würde ich jede zufällige Funktion verwenden, um sich über das Gitter zu verteilen, aber dann wieder, wie setze ich die zugehörigen Nummern und entscheide, welche Box geöffnet werden soll? Ich konnte keinen generischen Algorithmus festlegen, wie ich das machen würde.

Answer 1

Vielleicht etwas in den Zeilen:

grid = [n,m] // initialize all cells to 0 
for k = 1 to number_of_mines 
    get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine 
    for x = -1 to 1 
     for y = -1 to 1 
     if x = 0 and y = 0 then 
      grid[mine_x, mine_y] = -number_of_mines // negative value = mine 
     else 
      increment grid[mine_x + x, mine_y + y] by 1 

so ziemlich ist es ...

** EDIT **

Da dieser Algorithmus konnte führen in eine Schaffung board mit einigen Minen zu viel zusammen gruppiert, oder noch schlimmer verteilt (also langweilig zu lösen), können Sie dann zusätzliche Validierung hinzufügen, wenn mine_x generiert wird und mine_y Nummer. Zum Beispiel, um sicherzustellen, dass mindestens drei benachbarte Zellen nicht Minen sind, oder vielleicht sogar begünstigen die Anzahl der Minen zu begrenzen, die sich voneinander zu weit sind, usw.

** UPDATE **

I Habe mir die Freiheit genommen ein bisschen mit JS Bin zu spielen hier kam ein funktionierendes Minesweeper game demo. Dies dient lediglich dazu, den in dieser Antwort beschriebenen Algorithmus zu demonstrieren. Ich habe die Zufälligkeit der generierten Minenposition nicht optimiert, daher könnten manche Spiele unmöglich oder zu einfach sein. Es gibt auch keine Bestätigung, wie viele Minen es im Grid gibt, also könnt ihr tatsächlich ein 2 mal 2 Grid mit 1000 Minen erstellen ... aber das wird nur zu einer Endlosschleife führen :) Viel Spaß!

Answer 2

Sie säen einfach die Minen und danach durchqueren Sie jede Zelle und zählen die benachbarten Minen.

Oder Sie setzen jeden Zähler auf 0 und mit jeder gesetzten Mine erhöhen Sie alle Zähler der benachbarten Zellen.

Answer 3

Wenn Sie m Minen auf N Quadrate platzieren möchten, und Sie Zugriff auf einen Zufallsgenerator haben, gehen Sie einfach durch die verbleibenden Quadrate und für jedes Quadrat rechnen (# Minen übrig)/(# Quadrate übrig) und platzieren eine Mine, wenn Ihre Zufallszahl gleich oder niedriger als dieser Wert ist.

Nun, wenn Sie jedes Quadrat mit der Anzahl benachbarter Minen beschriften möchten, können Sie es einfach direkt:

count(x,y) = sum(
    for i = -1 to 1 
    for j = -1 to 1 
     1 if (x+i,y+j) contains a mine 
     0 otherwise 
) 

oder wenn Sie es vorziehen, können Sie mit einer Reihe von Nullen beginnen und jeder Zuwachs um eins auf dem 3x3 Quadrat, das in der Mitte eine Mine hat. (Es tut nicht weh, die Felder mit Minen zu nummerieren.)

Dies erzeugt ein rein zufälliges und korrekt kommentiertes Minesweeper-Spiel. Einige zufällige Spiele mögen jedoch keine lustigen Spiele sein; zufällige, aber lustige Spiele zu wählen, ist eine viel größere Herausforderung.