Aufdeckalgorithmus Minesweeper

Hallihallöle,

jeder kennt es wahrscheinlich und hat es ab und hat es mindestens einmal gespielt. Ich rede vom Klassiker Minesweeper.
Ich habe mir überlegt dieses in Java umzusetzen und habe auch schon eine graphische Oberfläche und die Möglichkeit Zellen anzuklicken erschaffen. Hierbei wird dann die Zahl der Nachbarzellen mit Bomben angezeigt.
Zu den Spielregeln siehe hier: https://de.wikipedia.org/wiki/Minesweeper#Spielverlauf

Bei mir scheitert es nun an einer Sache. Nicht an der Programmierung sondern an der Logik. Ich finde dazu einfach nichts gescheites im Netz.
Hat jemand von euch eine Ahnung wie das mit dem automatischen Aufdecken funktioniert? Also wenn ich eine Zelle anklicke deckt das Spiel ja immer schon in alle Möglichen Richtungen wo keine Bomben sind leere Zellen auf.
Zu sehen zum Beispiel, wenn man es hier spielt: Minesweeper Online - Play Free Online Minesweeper (falls es jemand nicht installiert hat)

Ich sehe dahinter aktuell kein Muster, nach welchem Muster ich die aufdecken sollte.
Hat jemand eine Ahnung wie das intern so funktioniert oder kann sich das vorstellen?

Mein aktuelles Projekt hab ich hier als GitHubRepository: https://github.com/Dabendorf/Java-Minesweeper
Es beeinhaltet vier Klassen. MinesweeperMain startet das ganze, Minesweeper steuert die Generierung und die Spielzüge, Zelle sind die Einzelnen Zellen und die Instanzen von Bombe sind die Bomben.

Das Spielfeld ist ein GridLayout: public Zelle[][] spielfeld = new Zelle[x][y];
Das heißt man kann die Zellen mit x, y ansteuern.

Sodass man beispielsweise mit for-Schleifen ausgehend von der Zelle [5][3] solange nach Links gehen könnte, bis man auf eine Bombe trifft:

		int y = 3;
		do {
			spielfeld[x][y].setAktiviert(0);
			x--;
		} while(spielfeld[x][y].isBombe()==false);```

Ich habe alles mit Java-Doc kombiniert, damit man durchsieht.
mit setAktiviert(0) setze ich die Zelle als benutzt, also angeklickt.


Hat jemand einen brillant genialen Einfall wegen des Algorithmus des Aufdeckens?
Es muss auch kein Quellcode sein, mir geht es erstmal um die pure Logik dahinter, die ich noch nicht gesichtet habe.

Vielen Dank im Voraus.
Gruß
Lukas

In Minesweeper werden immer alle angrenzenden Teile aufgedeckt, alle Teile die keine Nummer haben decken dabei wiederum alle Teile um sich herum auf.
Minesweeper soll immer lösbar sein, wenn die Teile ohne Nummer nicht automatisch sich aufdecken würde wenn man sie entdeckt könnte es passieren das man nur ein Haufen von leeren Feldern hat und man zufällig im Feld herumstochert bis man wieder ein Teil mit einer Nummer (also einen Anhaltspunkt) findet oder eine Mine.
Das ist die Logik und der Grund dahinter.

Hui, hatte ich vor Jaaahren mal implementiert. War eigentlich recht übersichtlich, rekursiv wohl am einfachsten, grob war es sowas wie

void openFields(int x, int y)
{
    if (!validPosition(x,y)) return;

    int n = numberOfNeighborsWithMinesOf(field[x][y])
    field[x][y].setText(n);

    if (n == 0) {
        openFields(x+1, y  );
        openFields(x-1, y  );
        openFields(x  , y+1);
        openFields(x  , y-1);
    }
}

Hallihallo,

ich danke euch beiden für eure Antworten.
@Marco13
Ich habe es tatsächlich ähnlich wie Du in Gedanken gehabt, es scheitert aber so ein bisschen an einer Sache.
Schau Dir mal die aktuelle Konstellation an, die durch einen Algorithmus wie Deinen geschaffen wurde:

Es geht mir hier um die Ecken. Da ich ja nur die direkten vier Nachbaren auf weiter schalte, werden hier Zahlen ausgelassen auf Position (0,4).
Wenn ich jedoch einfach die Diagonalen mit machen würde, würde das einen Kreislauf ergeben und über diese Diagonalen Nachbaren hinweg würde er am Ende nahezu das gesamte Spielfeld, um die Bomben herum aufdecken.

Ich hoffe ich habe das nicht zu unlogisch formuliert. :slight_smile:

*** Edit ***

Jetzt muss ich doch nochmal in den Quellcode gehen. Also ich habe jetzt sehr lange gebastelt und für dieses Schrägproblem noch kein Ergebnis gefunden.
So sieht ein aktueller funktionierender Code aus, ohne das Problem behoben zu haben.

		int posx = z.getPosx();
		int posy = z.getPosy();
		if(!z.isBombe() && z.getAktiviert()==1) {
			z.setGeklickt(true);
			z.setAktiviert(0);
			z.repaint();
			try {
				if(z.getAnznachbaren()==0) {
					spielzug(spielfeld[posx+1][posy]);
					spielzug(spielfeld[posx-1][posy]);
					spielzug(spielfeld[posx][posy+1]);
					spielzug(spielfeld[posx][posy-1]);
				}
			} catch(ArrayIndexOutOfBoundsException e) {}
		}
	}```

Also hierzu ist folgendes zu sagen:
ich catche OutOfBoundsExceptions einfach komplett weg, wenn der Algorithmus über den Rand hinweg versucht zu arbeiten. Dadurch spare ich mir lästige große Abfragen, wie groß x und y sind. Ich erbitte mir, falls jemand das nicht gut findet keinerlei Kommentare dazu. Nehmt es hin. :D
So und dann gibt es noch ein paar Werte:
`getAnznachbaren()` ist die Anzahl der Bomben um die Zelle herum von 0 bis maximal 8.
`z.isBombe()` gibt einen boolean zurück, bei true ist das Feld vermint.
`z.getAktiviert()` ist eine Variable die 2, 1 oder 0 ist. Zwei ist der Startwert, wenn das Feld generiert ist, wird sie automatisch 1 (damit die paintMethode sich nicht ∞ paintet). Wenn der Wert also 1 ist, ist sie noch unbenutzt, bei 0 ist sie verbraucht.
`z.setGeklickt(true);` setzt geklickt auf true, dann ist die Zelle nicht mehr neu anklickbar.

Mit diesem getAktiviert==1 erreiche ist, dass es nicht zu einem stackoverflow-Error kommt. Sonst würde der Algorithmus rekursiv das Feld immer und immer wieder abarbeiten.

Nun zurück zum eigentlichen Problem: Hat jemand eine gute Idee für das Diagonale Problem?


Schönes Wochenende
Lukas

Zeige doch einfach mal alle Bomben, auch wenn Sie noch zugedeckt sind an. Das macht das ganze nachvollziehbarer.

Wenn auf dem Feld nur wenige Bomben vorhanden sind, dann ist es halt meist so, dass mit einem Klick auch schon fast alles oder manchmal auch alles aufgedeckt wird.

Nur Felder mit null Angrenzenden Nachbarn decken alle (8) Nachbarn auf. Felder mit mindestens einer angrenzenden Miene decken keine Nachbarn mit auf.

Das ist mir bekannt. Jedoch müssen trotzdem auch die Diagonalen Felder aufgedeckt werden. Wenn ich die aber mit aufdecke deckt die Rekursion logischerweise fast das ganze Feld auf.

[QUOTE=FranzFerdinand]Hallihallo,

                  	try {
				if(z.getAnznachbaren()==0) {
					spielzug(spielfeld[posx+1][posy]);
					spielzug(spielfeld[posx-1][posy]);
					spielzug(spielfeld[posx][posy+1]);
					spielzug(spielfeld[posx][posy-1]);
				}
			} catch(ArrayIndexOutOfBoundsException e) {}
		}
	}

ich catche OutOfBoundsExceptions einfach komplett weg, wenn der Algorithmus über den Rand hinweg versucht zu arbeiten. Dadurch spare ich mir lästige große Abfragen, wie groß x und y sind. Ich erbitte mir, falls jemand das nicht gut findet keinerlei Kommentare dazu. Nehmt es hin. :D[/QUOTE]

Nein, nehme ich nicht. Es KÖNNTE sein, dass genau DAS die Ursache für das beobachtete Problem ist. Eigentlich sollten die 4 Hauptrichtungen reichen, und die Diagonalen sollten NICHT nötig sein. Aber überleg’ mal ganz, ganz scharf, was passiert, wenn bei deinen 4 spielzug-Zeilen dort schon die ERSTE eine Exception wirft… Ja, die anderen werden nicht mehr ausgeführt, und es bleiben Felder unbearbeitet. Versuch’ es mal so, wie ich angedeutet hatte: (x,y) übergeben, am Anfang auf Gültigkeit prüfen, und (wenn sie ungültig sind) einfach NUR das aktuelle (ungültige) Feld ignorieren.

Hallöle,

der Quelltext sieht nun so aus:

        int posx = z.getPosx();
        int posy = z.getPosy();
        if(!z.isBombe() && z.getAktiviert()==1) {
            z.setGeklickt(true);
            z.setAktiviert(0);
            z.repaint();
            if(z.getAnznachbaren()==0) {
            	if(posx+1>-1 && posx+1<breite && posy>-1 && posy<hoehe) {
            		spielzug(spielfeld[posx+1][posy]);
            	}
            	if(posx-1>-1 && posx-1<breite && posy>-1 && posy<hoehe) {
            		spielzug(spielfeld[posx-1][posy]);
            	}
            	if(posx>-1 && posx<breite && posy+1>-1 && posy+1<hoehe) {
            		spielzug(spielfeld[posx][posy+1]);
            	}
				if(posx>-1 && posx<breite && posy-1>-1 && posy-1<hoehe) {
					spielzug(spielfeld[posx][posy-1]);
				}
            }
        }
    }```
Ich catche nun auf Dein Anraten alles manuell weg. Auf jeden Fall hat es den Fehler nicht bereinigt, zum Beispiel hier am Beispiel zu erkennen:

Er müsste zum Beispiel das Feld (1,7) noch mit aufdecken.



> Ja, die anderen werden nicht mehr ausgeführt, und es bleiben Felder unbearbeitet. Versuch' es mal so, wie ich angedeutet hatte: (x,y) übergeben, am Anfang auf Gültigkeit prüfen, und (wenn sie ungültig sind) einfach NUR das aktuelle (ungültige) Feld ignorieren.

Sorry wenn ich mich etwas doof anstelle, aber das verstehe ich gerade nicht.
Weil ich mache doch genau das, was Du auch machst.
```if (n == 0) {
        openFields(x+1, y  );
        openFields(x-1, y  );
        openFields(x  , y+1);
        openFields(x  , y-1);
    }```
-->`if(z.getAnznachbaren()==0) {`

Oder nicht?

Edit: Auf jeden Fall schon einmal danke für Deine bisherigen Beispiele und die benutzte Zeit! :)

Auch wenn ich hier wieder allen den Spaß verderbe, aber hier ist meine objektorientierte Lösung (im Sinne von, die Zellen sind selbst für’s Aufdecken verantwortlich) …public void uncover() { if (isBomb) { JOptionPane.showConfirmDialog(null, "you hit a bomb", "Looser!", JOptionPane.ERROR_MESSAGE); throw new RuntimeException("Game Over"); } else { isUncovered = true; defaultTableModel.fireTableDataChanged(); if (0 == neigbourBombCount) { for (Cell cell : neigbours) { cell.uncoverByNeigbour(); } } } } private void uncoverByNeigbour() { if (!isUncovered) { uncover(); } } public void addNeigbour(Cell cell) { neigbours.add(cell); neigbourBombCount += cell.isBomb ? 1 : 0; }

KSKB
[spoiler]Die Buttons in der Zelle habe ich kopiert, die funktionieren nicht so richtig, man muss auf eine zweite Zelle klicken, damit was passiert…```package minesweeper;

import java.awt.Component;
import java.awt.Dimension;
import java.util.Collection;
import java.util.EventObject;
import java.util.HashSet;
import java.util.Random;

import javax.swing.AbstractCellEditor;
import javax.swing.JButton;
import javax.swing.JOptionPane;
import javax.swing.JTable;
import javax.swing.table.DefaultTableModel;
import javax.swing.table.TableCellEditor;
import javax.swing.table.TableCellRenderer;

public class MinesweeperTest {
private static final int MAX_I = 20;
private static final int MAX_J = 20;
int bombChanceInPercent = 10;

private static class Cell {
	private final boolean isBomb;
	int neigbourBombCount;
	private boolean isUncovered = false;
	private final Collection<Cell> neigbours = new HashSet<MinesweeperTest.Cell>();
	private DefaultTableModel defaultTableModel;

	public Cell(boolean isBomb, int i, int j, DefaultTableModel defaultTableModel) {
		super();
		this.isBomb = isBomb;
		this.defaultTableModel = defaultTableModel;
	}

	public String getDisplay() {
		return isUncovered ? (isBomb ? "B" : 0 == neigbourBombCount ? " " : String.valueOf(neigbourBombCount))
				: "*";
	}

	public void uncover() {
		if (isBomb) {
			String title = "Looser!";
			Object message = "you hit a bomb";
			JOptionPane.showConfirmDialog(null, message, title, JOptionPane.ERROR_MESSAGE);
			throw new RuntimeException("Game Over");
		} else {
			isUncovered = true;
			defaultTableModel.fireTableDataChanged();
			if (0 == neigbourBombCount) {
				for (Cell cell : neigbours) {
					cell.uncoverByNeigbour();
				}
			}
		}
	}

	private void uncoverByNeigbour() {
		if (!isUncovered) {
			uncover();
		}
	}

	public void addNeigbour(Cell cell) {
		neigbours.add(cell);
		neigbourBombCount += cell.isBomb ? 1 : 0;
	}
}

public static void main(String[] args) {
	new MinesweeperTest().start();
}

@SuppressWarnings("serial")
private void start() {
	Cell[][] cells = new Cell[MAX_I][MAX_J];
	DefaultTableModel defaultTableModel = new DefaultTableModelExtension(cells);
	Random random = new Random();
	for (int i = 0; i < MAX_I; i++) {
		for (int j = 0; j < MAX_J; j++) {
			cells**[j] = new Cell(bombChanceInPercent > random.nextInt(100), i, j, defaultTableModel);
		}
	}
	for (int i = 0; i < MAX_I; i++) {
		for (int j = 0; j < MAX_J; j++) {
			if (0 < j)
				cells**[j].addNeigbour(cells**[j - 1]);
			if (j < MAX_J - 1)
				cells**[j].addNeigbour(cells**[j + 1]);
			if (0 < i)
				cells**[j].addNeigbour(cells[i - 1][j]);
			if (i < MAX_I - 1)
				cells**[j].addNeigbour(cells[i + 1][j]);
			if (0 < i)
				if (0 < j)
					cells**[j].addNeigbour(cells[i - 1][j - 1]);
			if (0 < i)
				if (j < MAX_J - 1)
					cells**[j].addNeigbour(cells[i - 1][j + 1]);
			if (i < MAX_I - 1)
				if (0 < j)
					cells**[j].addNeigbour(cells[i + 1][j - 1]);
			if (i < MAX_I - 1)
				if (j < MAX_J - 1)
					cells**[j].addNeigbour(cells[i + 1][j + 1]);
		}
	}
	JTable jTable = new JTable(defaultTableModel);
	EditorAndRenderer editorAndRenderer = new EditorAndRenderer();
	jTable.setDefaultRenderer(String.class, editorAndRenderer);
	jTable.setDefaultEditor(String.class, editorAndRenderer);
	jTable.setMaximumSize(new Dimension(10 * MAX_I, 10 * MAX_J));
	JOptionPane.showMessageDialog(null, jTable);

}

@SuppressWarnings("serial")
class EditorAndRenderer extends AbstractCellEditor implements TableCellEditor, TableCellRenderer {

	private final JButton renderer = new JButton();
	private final JButton editor = new JButton();

	@Override
	public Component getTableCellRendererComponent(JTable table, Object value, boolean isSelected, boolean hasFocus,
			int row, int column) {
		renderer.setText((String) value);
		renderer.setMaximumSize(new Dimension(10, 10));
		return renderer;
	}

	@Override
	public Component getTableCellEditorComponent(JTable table, Object value, boolean isSelected, int row,
			int column) {
		editor.setText((String) value);
		editor.setMinimumSize(new Dimension(10, 10));
		return editor;
	}

	@Override
	public Object getCellEditorValue() {
		return editor.getText();
	}

	@Override
	public boolean isCellEditable(EventObject ev) {
		return true;
	}

	@Override
	public boolean shouldSelectCell(EventObject ev) {
		return false;
	}
}

private final class DefaultTableModelExtension extends DefaultTableModel {
	private Cell[][] cells;

	public DefaultTableModelExtension(Cell[][] cells) {
		this.cells = cells;
		// TODO Auto-generated constructor stub
	}

	@Override
	public int getRowCount() {
		return MAX_I;
	}

	@Override
	public int getColumnCount() {
		return MAX_J;
	}

	@Override
	public String getColumnName(int columnIndex) {
		return null;
	}

	@Override
	public Class<?> getColumnClass(int columnIndex) {
		return String.class;
	}

	@Override
	public boolean isCellEditable(int rowIndex, int columnIndex) {
		return !cells[rowIndex][columnIndex].isUncovered;
	}

	@Override
	public Object getValueAt(int rowIndex, int columnIndex) {
		return cells[rowIndex][columnIndex].getDisplay();
	}

	@Override
	public void setValueAt(Object aValue, int rowIndex, int columnIndex) {
		cells[rowIndex][columnIndex].uncover();
	}
}

}```[/spoiler]
bye
TT

Hab’ gerade nochmal MineSweeper gestartet: Ja, er deckt auch über Diagonalen hinweg auf (entgegen dessen, was ich oben angedeutet hatte), d.h. man wird wohl doch auch die Diagonalen testen müssen.

Noch 4 rekursive Aufrufe. Mit if-Abfragen. Ja, diese if-Abfragen sind lästig, und durch das wiederholte Berechnen der Nachbarn auch fehleranfällig. Deswegen bietet es sich an, sie nur EINmal zu machen. Z.B. am Anfang der Methode. Wenn man unbedingt ein “Zelle”-Objekt übergeben will, könnte man sich ein Helferlein machen

public void spielzug(int x, int y) {
    if(x>=0 && x<breite && y>=0 && y<hoehe) {
        spielzug(spielfeld[x][y]);
    }
}

Dann kann man die Aufrufe schreiben als

if (...)
{
    spielzug(posx-1, posy-1);
    spielzug(posx-1, posy  );
    spielzug(posx-1, posy+1);
    spielzug(posx  , posy-1);
    //spielzug(posx  , posy  );
    spielzug(posx  , posy+1);
    spielzug(posx+1, posy-1);
    spielzug(posx+1, posy  );
    spielzug(posx+1, posy+1);
}

Hallihallo ihr beiden,
@Timothy_Truckle
Eine sehr unterhaltsame Lösung muss ich sagen. Da hast Du Dir aber Mühe gegeben. Ich danke auch Dir für die geopferte Zeit für dieses Thema. Ich muss sagen, ursprünglich habe ich das ähnlich gehabt, dass die Zelle das selbst macht. Ich habe eine klick-Methode in der Zelle eingebaut, die das da machen sollte. Aber irgendwie hat das bei mir zu Problemen geführt, weshalb die Klickmethode nun in meine Hauptklasse weiterleitet. Aber nun geht es auch so. :slight_smile:
@Marco13
Auch Dir vielen Dank für Deine Hilfe. Mit den Diagonalen mit eingebaut klappt es nun auch perfekt. Habe irgendwie den ganzen Tag um diese vier Zeilen herum umhergeeiert, finde ich schon seltsam. Vielleicht war ich etwas neben der Spur.
Vielen Dank Dir für alle Beiträge! :slight_smile:

Schöne Grüße
Lukas

[quote=FranzFerdinand]Aber nun geht es auch so.[/quote]Ich sag mal so:
wenn jemand ein Hexagonales Minesweeper Bauen möchte, oder eine 3D-Variante, dann wäre bei meiner Lösung der Algorithmus schon komplett fertig, nur die Bestimmung der Nachbarn (Zeilen 81 bis 107) müsste angepasst werden, und natürlich die Darstellung…

Was ist mit Deiner Lösung?

bye
TT

Hmmmm… :coding:

Ansonsten stimmt das natürlich, aber… manche würde schon bei einem Cell[][]-Array(!) die Krätze kriegen, und … man kann beliebig weit gehen :wink:

[quote=Marco13]manche würde schon bei einem Cell[][]-Array(!) die Krätze kriegen,[/quote]Ich ja eigentlich auch, aber ich wollte nicht schon wieder darüber streiten…:grampa:

bye
TT

:smiley: Danke dafür!

Warum? Weil in diesem Fall die Datenbank von der Logik getrennt wäre? Sehe ich erstmal kein Problem mit, ganz im Gegenteil. Dann wird für die Logik halt ein Objekt Schiedsrichter oder Spiellogik angelegt.
Aber ich bin auch kein OO-Experte, mich nerven schon meine Kollegen die letztes Jahr noch etwas behaupteten was die einzig richtige Lösung für ein Problem ist und was dieses Jahr magischerweise plötzlich falsch ist, hauptsache es ist populär und man bekommt damit auf Stackoverflow viele Upvotes hab ich das Gefühl.
Jedes Jahr auf ein neues :scheiterhaufen:

Hallo,

tl;dr

der Algorithmus muss feststellen:

definitiv keine Mine,
definitiv eine Mine,
definitiv vielleicht eine Mine (unbestimmt),

dafür muss er sich die benachbarten Felder angucken, und am Besten mit solchen beginnen, die eine hohe Zahl von Minen in der Umgebung habn, das wiederholt sich immer.

Ist das, wonach du gefragt hattest?

vlg

[OT][quote=TMII]mich nerven schon meine Kollegen die letztes Jahr noch etwas behaupteten was die einzig richtige Lösung für ein Problem ist und was dieses Jahr magischerweise plötzlich falsch ist,[/quote]OOP hat ein paar einfache Grundregeln. Allen voran sind da Information hiding, Single Responsibility, Law of Demeter (don’t talk to stranger) und das Liskov-Prinzip (wenn etwas wie eine Ente aussieht und wie eine Ente quakt, dann ist es wohl eine Ente). Mag sein dass manche mangels besserem Wissen bestimte Entwurfsmuster als Universallösung ansehen. Das ist natürlich immer unsinnig…[/OT]bye
TT

Hmm ja das habe ich danach auch erkannt, aber man kann leider seinen Beitrag hier nicht editieren… so ganz habe ich das System hier im Forum noch nicht raus.
Hatte mich nähmlich eher auf die Aussage fokusiert das durch deine Methodik nur die Nachbardependencies angepasst werden müssten, aber es gibt viel mehr Faktoren mit Fürs und Gegens beider Möglichkeiten.

Aber danke das du das nochmals so sachlich erläutert hattest.

[OT][quote=TMII]aber man kann leider seinen Beitrag hier nicht editieren…[/quote]Doch, aber nur maximal eine Stunde nach dem Post.[/OT]

bye
TT