# Freie Felder bei Minesweeper automatisch aufdecken



## Tobias K. (2. Februar 2005)

moin


Wenn man beim Originalen MInesweeper auf ein freies Feld (ohne Zahl und Miene) klickt, "öffnen" sich auch alle anliegenden freien und Zahlenfelder und bei allen dadurch geöffneten passiert wieder das selbe, ihr kennt das ja.

Wie berechne ich am das am besten, also wie berechne ich die anliegenden Felder?


mfg
umbrasaxum


----------



## fhr (2. Februar 2005)

Link zum Bild geht nicht


----------



## Tobias K. (2. Februar 2005)

moin


Ja hab ich schon gemerkt, muss mal eben gucken woran das liegt.

Edit:
Fehler behoben.


mfg
umbrasaxum


----------



## Java/CppProgrammer (2. Februar 2005)

Bei mir erscheint da so ein Bild mit einem Mann , der ein Schild mit der Aufschrift "externes Linken nicht erlaubt" trägt.


----------



## Tobias K. (2. Februar 2005)

moin


Mag sein jedoch liegt das nicht in deinem ermessen.
Aber eigentlich ist es erlaubt, wenn es auf etwas spezielles zeigt.

Außerdem kannst du dir solche Kommentare sparen (sammel deine Beiträge wo anders), dafür gibt es hier Leute.


mfg
umbrasaxum


----------



## MFC openGL (2. Februar 2005)

Wie hast du denn das Spielfeld aufgebaut ?

Per Array wo z.b. 0 = nicht aufgedeckt, 1 = aufgedeckt/ohne bombe, 2 = mit bombe markiert
heisst ?

Wenn ja brauchst du doch um deinen Arraypunkt nur abfragen ob die Felder  x+-1, y+-1 und y+-1/x+-1 markiert/schon aufgedeckt sind, dann setzt du einfach einen neuen Status und fragst ab ob in deiner Original Bomben Liste dort eine Bombe gewesen ist, wenn ja -> BOOOOOM, wenn nein, neuer Status mit aufgedeckt(1) und weiter im Text...

Wenn du das anders gemacht hast, scheib mal wie und dann kann man das evtl anpassen...

Gruss

MFC OpenGL


----------



## Tobias K. (2. Februar 2005)

moin


Ja die Attribute jedes einzelnen Feldes ist in einer Struktur gespeichert.
Das mit den Bomben ist auch kein Problem, ich poste einfach mal mein Programm.

http://umbrasaxum.um.funpic.de/Mienensuchen.exe

Zum vergleich könnt ihr/du ja mal das originale Spielen und sehen was passiert wenn ein leeres Feld geklickt wird, das sollte mein Problem deutlich machen.


mfg
umbrasaxum


----------



## Matthias Reitinger (2. Februar 2005)

Man könnte das ganze rekursiv angehen:

Pseudocode:

```
funktion deckeAuf(feld)
{
	if (feld is bombe) {
		boom();
		return;
	}

	markiereAlsAufgedeckt(feld);

	foreach (nachbarfeld) {
		if (nachbarfeld is bombe
			or nachbarfeld is aufgedeckt) continue;
		else deckeAuf(nachbarfeld);
	}
}
```
Eventuell muss man noch aufpassen, dass man in keine Endlosschleife gerät bei der Überprüfung der Nachbarfelder...


----------



## Tobias K. (2. Februar 2005)

moin


Hatte eine falsche Version meines Mienensuchens hochdeladen!
Falls ihr euch gewundert habt das keine Mienen zu sehen waren, jetzt werden sie angezeigt.
http://umbrasaxum.um.funpic.de/Mienensuchen.exe


mfg
umbrasaxum


----------



## Kachelator (3. Februar 2005)

umbrasaxum hat gesagt.:
			
		

> moin
> 
> 
> Mag sein jedoch liegt das nicht in deinem ermessen.
> ...


Kein Grund zum Schimpfen! Der Link ist tatsächlich nicht gut. Der Host deines Bildes erlaubt das externe Linken nicht; das hat nichts mit dem Forum zu tun. Sieh selbst:


----------



## Tobias K. (3. Februar 2005)

moin

OK, ok.
Hatte das falsch verstanden, da bei mir alles so funktioniert wie es soll.

Sorry.


mfg
umbrasaxum


----------



## Kachelator (3. Februar 2005)

Die Vorgehensweise beim Aufdecken und die oben genannten Vorschläge entsprechen übrigens dem, was ich als Floodfill-Algorithmus kenne. Ist ja eigentlich nichts anderes als z.B. der Farbeimer in einem Malprogramm.


----------



## MFC openGL (3. Februar 2005)

Matthias Reitinger hat gesagt.:
			
		

> Man könnte das ganze rekursiv angehen:
> 
> Pseudocode:
> 
> ...


 

Glaube ja mal nicht das das funktionieren kann, da du ja zumindest sagen musst, welches dein neues Nachbarfeld ist, und ich denke da wird dein Programm nicht rekursiv funktionieren können, da die Felder kreisförmig um den Klickpunkt aufgedeckt werden müssten... Du brächtest Globale/Statische Variablen, dann macht das rekursiv keinen Sinn mehr, der Vorteil wäre dann komplett weg...(Durch den Mehraufwand für Globale Variablen, start/end Checks usw.)


----------



## Tobias K. (3. Februar 2005)

moin


Ich denke mal das er damit nur einen denkanstoß geben wollte.
Und das hat es auch. Werde das jetzt mal probieren und mich dann wieder melden.


mfg
umbrasaxum


----------



## ngc (4. Februar 2005)

Hatte das gleiche Problem in einem ähnlichen Programm. (Auch Minesweeper aber unter DOS.)

 Die Aufdeckung mehrer Felder funktioniert meiner Meinung nach nur rekursiv, da sich das Zentrum deiner Betrachtung (beim Check der Felder in der Umgebung) jedesmal ändert und du nicht vorhersehen kannst, wie und wie oft. Kombiniert mit einem Globalen Array für die Felder könnte eventuell etwas wie folgendes funktionieren:


```
void aufdecken(int Y, int X)
   	{
   	if ((brett[Y][X]==0)&&(aufgedeckt[Y][X]!=1))
   		{
   		aufgedeckt[Y][X]=1;
 		if ((Y<9)&&(X<9)&&(aufgedeckt[Y+1][X+1]!=1)) aufdecken(Y+1,X+1);				 
   		if ((X<9)&&(aufgedeckt[Y][X+1]!=1)) aufdecken(Y,X+1);
 		if ((Y>0)&&(X<9)&&(aufgedeckt[Y-1][X+1]!=1)) aufdecken(Y-1,X+1);
   		if ((Y<9)&&(aufgedeckt[Y+1][X]!=1)) aufdecken(Y+1,X);
   		if ((Y>0)&&(aufgedeckt[Y-1][X]!=1)) aufdecken(Y-1,X);
 		if ((Y<9)&&(X>0)&&(aufgedeckt[Y+1][X-1]!=1)) aufdecken(Y+1,X-1);
   		if ((X>0)&&(aufgedeckt[Y][X-1]!=1)) aufdecken(Y,X-1);
 		if ((Y>0)&&(X>0)&&(aufgedeckt[Y-1][X-1]!=1)) aufdecken(Y-1,X-1);
   		}
   	else aufgedeckt[Y][X]=1;
   	}
```
 
  In meinem Fall ist das Feld 10x10 groß.
  im array brett[][] werden die minen gespeichert.
  1: ja
  0: nein
 Du müsstest das Ganze noch dahingehend modifizieren, dass dein Programm auch auf markierte Minen reagiert. Das machte bei meiner DOS Version keinen Sinn, weil es die Bedienung zu umständlich macht.
  regards, Alex


----------



## MFC openGL (4. Februar 2005)

ngc hat gesagt.:
			
		

> Hatte das gleiche Problem in einem ähnlichen Programm. (Auch Minesweeper aber unter DOS.)
> 
> Die Aufdeckung mehrer Felder funktioniert meiner Meinung nach nur rekursiv, da sich das Zentrum deiner Betrachtung (beim Check der Felder in der Umgebung) jedesmal ändert und du nicht vorhersehen kannst, wie und wie oft. Kombiniert mit einem Globalen Array für die Felder könnte eventuell etwas wie folgendes funktionieren:
> 
> ...


 

Beim besten Willen, mit Rekursiv hat das wirklich nur noch sehr wenig zu tun. Da kannst du direkt die Koordinaten um den jeweiligen Punkt fest definieren(haste ja im Grunde auch gemacht) und dann die testefeld Methode aufrufen.
Bei so vielen IF's ist das Rekursive vollkommen für den *****. (Meine persönliche Meinung)


----------



## Tobias K. (4. Februar 2005)

moin


Hatte das gestern abend mal probiert, war aber nur mäßig erfolgreich.

Und zwar bekam ich immer einen Stack überlauf.

Mir ist dann aufgefallen das ich nciht verhindert hab das schon aufgedeckte nochmal aufgedeckt werden, was natürlich zu problemen führt, werde das nachher nochmal anders versuchen.


mfg
umbrasaxum


----------



## ngc (4. Februar 2005)

MFC openGL hat gesagt.:
			
		

> Beim besten Willen, mit Rekursiv hat das wirklich nur noch sehr wenig zu tun. Da kannst du direkt die Koordinaten um den jeweiligen Punkt fest definieren(haste ja im Grunde auch gemacht) und dann die testefeld Methode aufrufen.
> Bei so vielen IF's ist das Rekursive vollkommen für den *****. (Meine persönliche Meinung)


 
 Das ist allein schon dadurch rekursiv, das sich die Funktion selbst aufruft.
 Die vielen IFs brauchst Du um sie mit jedem der benachbarten Punkte aufrufen zu können.
 Mag sein, dass das die Rekursionskurve verhunzt. Aber hier gings um ne Lösung für ein Problem, nicht um Kosmetik.

 Ich wäre an deiner Alternativ-Lösung interessiert, die Du ja sicherlich hast, nachdem Du ja nichts von meiner hälst.

 regards, Alex


----------



## MFC openGL (4. Februar 2005)

ngc hat gesagt.:
			
		

> Das ist allein schon dadurch rekursiv, das sich die Funktion selbst aufruft.


 

Danke ich brauche keine Nachhilfe in Rekursiven Aufrufen. 

Sagte ja auch das es nur "sehr wenig" mit Rekursivität zu tun hat, damit meinte ich den Selbstaufruf... Der Vorteil das du damit Code ersparst(z.b. durch Schleifen) ist bei dieser Lösung nicht mehr gegeben.

Auch wird dein Programm Laufzeitmäßig nicht schneller sein als eine direkte Abfrage aller Umgebungspunkte. Im gegenteil, durch die Ständigen IF's und die Rekursion wird es sogar noch um einiges lagsamer, da bei einer Rekursion die vorherige Routine gesichert und meist auf den Stack geschoben werden muss, das dauert Zeit...

Also mein Vorschlag(wie in vorherigen Posts schon gesagt) wäre einfach die Koordinaten x und y zu nehmen, und dann mit +/- 1 alle Umgebungsfelder abzufragen.

Wenn man jetzt noch so schlau ist/und genug Speicher hat kann man das Spielfeld um x+2 und y+2 erweitern. Dann spart man sich die lästige Abfrage ob es das Feld überhaupt gibt auch noch...


Beispiel

Spielfeld Ansicht 

 1111111111
 1111111111
 1111111111
 1111111111


Interne Verwaltung

00000000000
01111111110
01111111110
01111111110
01111111110
00000000000

Dann könnte man, wenn man z.b. das 1. Feld oben Links checken will sagen :
check(x-1,y-1);
check(x,y-1);
check(x+1,y-1);
check(x-1,y);
check(x+1,y);
check(x-1,y+1);
check(x,y+1);
check(x+1,y+1);


Dann wären alle Felder abgefragt, wenn eins dieser Felder dann BOOOM sagt, haste verloren, ansonsten markiere das Feld als aufgedeckt...


Vorteil gegenüber Rekursion :

- Übersichtlicher
- Keine IF's mehr
- Keine möglichen Speicherzugriffsfehler da du nicht mehr ausserhalb des Feldes kommen kannst
- Keine übermäßige Belastung des Stacks
- Schneller als die Rekursionvariante



@ngc
Und Alex, ich wollte dich nicht persönlich angreifen, falls du das so aufgefasst hast, SORRY...


Gruss

MFC OpenGL


----------



## Tobias K. (4. Februar 2005)

moin




> - Keine IF's mehr



Klar hast du dann in der check() noch IFs und ob du die so aufrufst oder in Funktionen gepackt.




> Dann wären alle Felder abgefragt, wenn eins dieser Felder dann BOOOM sagt, haste verloren, ansonsten markiere das Feld als aufgedeckt...



Was hat eine Miene mit einem freien Feld zu tun?
Eine Miene kann nicht neben einem freien Feld liegen. Und somit auch völlig uninteressant.


mfg
umbrasaxum


----------



## Matthias Reitinger (4. Februar 2005)

MFC openGL hat gesagt.:
			
		

> Glaube ja mal nicht das das funktionieren kann [...]


Wie sagt man so schön: glauben heißt nicht wissen   Natürlich funktioniert das, wenn man es richtig implementiert...

Beitrag #19 macht übrigens wenig Sinn, da du mit deinem Code nur zeigst, wie man alle Nachbarfelder abfragt. Was das mit Rekursion oder nicht Rekursion zu tun hat, erschließt sich mir da leider nicht so ganz. Außerdem müsstest du ja immer noch ggf. die Nachbarfelder der Nachbarfelder (der Nachbarfelder der Nachbarfelder...) abfragen. Und wenn du das iterativ lösen willst, dann bist du selber Schuld.


----------



## Tobias K. (4. Februar 2005)

moin


So es funktioniert jetzt erstmal mit folgendem Code:

```
void aufdecken(int x, int y)
{
	if(att[x][y].zahl != 0 || att[x][y].zustand == 1)
		return;

	if(att[x][y].geklickt == 0 )
	{	
		att[x][y].geklickt = 1;

		att[x+1][y].status = 0;
		aufdecken(x+1, y);
		att[x-1][y].status = 0;
		aufdecken(x-1, y);
		att[x][y+1].status = 0;
		aufdecken(x, y+1);
		att[x][y-1].status = 0;
		aufdecken(x, y-1);
		att[x-1][y-1].status = 0;
		att[x-1][y+1].status = 0;
		att[x+1][y-1].status = 0;
		att[x+1][y+1].status = 0;
	}		
}
```

Ich weiss noch nciht ob ich es so lasse, aber wie gesagt es funktioniert.


mfg
umbrasaxum


----------



## ngc (4. Februar 2005)

@MFC openGL:
  Ist Ok.
  Was machst Du bei deiner Lösung denn, wenn eines der umliegenden Felder auch leer ist.
 Du müsstest den ganzen Kram ja für dieses neue leere Feld auch wieder überprüfen und so weiter und so weiter. Und genau hier macht die Rekursion jede Menge Sinn. Ich wüsste jetzt nicht, wie es mit vertretbarem Aufwand iterativ klappen soll.




 @umbrasaxum
 Was machst Du, wenn deine Rekursion am Rand des Feldes ankommt?


   regards, Alex


----------



## Tobias K. (4. Februar 2005)

moin


Noch mach ich da nichts, es kommt zwar zu einem Fehler aber den behebe ich noch mit 4 IFs.


mfg
umbrasaxum


----------



## ngc (4. Februar 2005)

Es ginge auch ohne IFs, wenn du deine Felder um je 1 in jede Richtung größer machst und diesen "Rahmen" als schon geklickt und ohne Minen deklarierst.
 Dann wird die Aufdecken-Funktion nicht mehr mit den RandFeldern aufgerufen weil die schon geklickt sind und es ändert sich nichts an der Minen-in-der-Umgebung Berechnung.

 Kostet aber 2n+2m-4 Speicherplätze mehr. (n und m sollen die Kantenlänge sein)
 Je nachdem wie groß deine Felder sind, lohnt sich das vielleicht.


----------



## MFC openGL (5. Februar 2005)

ngc hat gesagt.:
			
		

> @MFC openGL:
> Ist Ok.
> Was machst Du bei deiner Lösung denn, wenn eines der umliegenden Felder auch leer ist.
> Du müsstest den ganzen Kram ja für dieses neue leere Feld auch wieder überprüfen und so weiter und so weiter. Und genau hier macht die Rekursion jede Menge Sinn. Ich wüsste jetzt nicht, wie es mit vertretbarem Aufwand iterativ klappen soll.
> ...


 

Genau da ist mein Denkfehler gewesen, sorry aber ein blindes Huhn findet auch mal ein Korn, bei mir hats nur ein wenig länger gedauert... SORRY....


----------



## uhu01 (5. Februar 2005)

Hy!

Ich weis die Idee kommt ein bisschen spät, aber was hältst du davon beim anlegen deines Arrays das Array wie einen Graphen durchzugehen, und allen benachbarten leeren Feldern ein Zahl z.B. größer als 10 gibst. Würde dann so aussehen:


```
221AA11111
xx2AA1x22x
23x33233x2
BB2xxx4x2C
BBB25xx2CC
BBBBB2x2CC
```

In dem Fall sind die
x      Miene
1,2   Die angezeigte Zahl
A,B  Zusammenhängende freie Felder

Ist vielleicht zu spät das so zu implementieren, weil ja bei so einem Array fast alle Prüfungen, wie viele Felder im Umkreis eines freien Feldes liegen auf das Initialisieren des Spielfeldes verschoben werden.

Wenn jetzt jemand auf ein Feld klickt, für das eine Zahl > 9 gespeichert ist müsstest du nur in zwei Schleifen das Array durchgehen, und alle mit derselben Zahl aufdecken.

Schreibt mal was ihr davon haltet, ich weiß das sich warsch. nicht mehr lohnt das ganze so zu implementieren, weil du schon sehr weit bist mit deinem Programm, ich soll nur für die Schule ein einfaches Spiel programmieren, und mein Minesweeper Ansatz sieht so aus.

mfg
uhu01


----------



## Tobias K. (5. Februar 2005)

moin

Wäre natürlich eine möglichkeit so etwas gleich zum Anfang zu machen, aber um erstmal solche zusammengehörigen Felder zu speichern muss ich sie erst erkennen und das wäre genau das selbe Verfahren, wie das das ich jetzt benutze.


mfg
umbrasaxum


----------

