Freie Felder bei Minesweeper automatisch aufdecken

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.
 
Matthias Reitinger hat gesagt.:
Man könnte das ganze rekursiv angehen:

Pseudocode:
Code: 
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...
Zum Vergrößern anklicken....


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

Code: 
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
 
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:

Code: 
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
Zum Vergrößern anklicken....


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)
 
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
 
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)
Zum Vergrößern anklicken....

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
 
ngc hat gesagt.:
Das ist allein schon dadurch rekursiv, das sich die Funktion selbst aufruft.
Zum Vergrößern anklicken....


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
 
moin


- Keine IF's mehr
Zum Vergrößern anklicken....

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...
Zum Vergrößern anklicken....

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
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück