Minesweeper ohne GUI -> Rekursions-Error

Code-Stücke können hier veröffentlicht werden.
Antworten
Üpsilon
User
Beiträge: 189
Registriert: Samstag 15. September 2012, 19:23
Wohnort: Altschauerberg 8 in 91448 Emskirchen

Donnerstag 10. September 2015, 11:44

Hey Leute. Ich habe letztens ein Minesweeper programmiert, was man in der Python-Shell spieln kann. Funktioniert auch eigentlich ganz gut. Aber beim echten Minesweeper werden, wenn man ein Feld ohne Minen auf den Nachbarn anklickt, die Nachbarn automatisch freigeklickt und da klemmt es bei mir (wenn ich es einkommentiere, versteht sich :D): Aus mir nicht bekannten Gründen geht die Rekursion zu tief. Könnt ihr mir helfen? (Für weitere Vorschläge bin ich selbstverständlich offen.)

Code: Alles auswählen

from random import randint
from itertools import product as kartesisches_produkt

class SpielVerloren(Exception):
    pass

class Minenfeld:
    def __init__(self, breite=10, hoehe=10, anz_minen=10):
        self.breite = breite
        self.hoehe = hoehe
        self.freigeklickt = []
        self.flaggen = []
        self.init_minen(anz_minen)
        
    def init_minen(self, anz_minen):
        self.minen = []
        while len(self.minen) < anz_minen:
            # Vorsicht: Nullbasiert zählen!!
            mine = randint(0,self.breite-1), randint(0,self.hoehe-1)
            if mine not in self.minen:
                self.minen.append(mine)
                
    def klick(self, z, s, out=True):
        if not (0<=z<self.hoehe and 0<=s<self.breite):
            raise IndexError("Dieses Feld gibts nicht! (%i,%i)"%(z,s))
        if (z,s) in self.minen:
            raise SpielVerloren("Mine bei (%i,%i) BOOOOOOM!!!!!!!!"%(z,s))
        self.freigeklickt.append((z,s))
        # Nachbarn errechnen
        nachbarn = list(kartesisches_produkt((z-1, z, z+1),
                                             (s-1, s, s+1)))
        nachbarn.remove((z, s))
        nachbarn = [koords for koords in nachbarn
                    if 0<=koords[0]<self.breite and 0<=koords[1]<self.hoehe]
        # Verminte Nachbarn zählen
        anz_nachbarminen = len([nachbar for nachbar in nachbarn if nachbar in self.minen])
        # 0er automatisch freiklicken (und hier klemmts)
        """if anz_nachbarn == 0:
            self.mehrfachklick(nachbarn)"""
        if out: print(self)
        return anz_nachbarminen
    
    def mehrfachklick(self, felderliste, out=True):
        erg = [self.klick(z,s,out=False) for z,s in felderliste]
        if out: print(self)
        return erg
    
    def __str__(self):
        zeilen = [[self.feldinfo(z,s) for s in range(self.breite)] for z in range(self.hoehe)]
        zeilen_str = ["|"+"|".join(zeile)+"|\n" for zeile in zeilen]
        trennzeile = "+"+"+".join(["-"]*self.breite)+"+\n"
        darstellung = trennzeile + trennzeile.join(zeilen_str) + trennzeile
        return darstellung
    
    def feldinfo(self, z, s):
        if not (0<=z<self.hoehe and 0<=s<self.breite):
            raise IndexError("Dieses Feld gibts nicht! (%i,%i)"%(z,s))
        if (z,s) in self.flaggen:
            return "Y"
        if (z,s) not in self.freigeklickt:
            return " "
        return str(self.klick(z,s,out=False))
    
    def setze_flagge(self, z, s):
        if not (0<=z<self.hoehe and 0<=s<self.breite):
            raise IndexError("Dieses Feld gibts nicht! (%i,%i)"%(z,s))
        self.flaggen.append((z,s))

m = Minenfeld()
PS: Die angebotene Summe ist beachtlich.
BlackJack

Donnerstag 10. September 2015, 12:01

@Üpsilon: Wenn man das wieder einkommentiert bekommt man einen `NameError` weil `anz_nachbarn` nicht definiert ist. Ohne zu wissen wie dieser Wert zustande kommt, kann man auch nicht sagen warum der bei Dir nicht 0 wird, obwohl er das sollte damit die Rekursion abbricht. Und Du musst natürlich auch `nachbarn` noch so einschränken, dass beim automatischen freiklicken nicht auch auf minen geklickt wird. Und auch bereits freigeklickte Felder sollte man noch einmal freiklicken wollen, damit könnte man sich sonst nämlich ewig aufhalten — oder zumindest bis zum Rekursionslimit.
Üpsilon
User
Beiträge: 189
Registriert: Samstag 15. September 2012, 19:23
Wohnort: Altschauerberg 8 in 91448 Emskirchen

Donnerstag 10. September 2015, 15:11

Wenn man das wieder einkommentiert bekommt man einen `NameError` weil `anz_nachbarn` nicht definiert ist. Ohne zu wissen wie dieser Wert zustande kommt, kann man auch nicht sagen warum der bei Dir nicht 0 wird
Jaaa sorry. Gemeint war anz_nachbarminen. Der Fehler war das Resultat wilden Rauslöschens und Wieder-hin-schreibens, aber naja, ist jetzt ja auch egal.
Und Du musst natürlich auch `nachbarn` noch so einschränken, dass beim automatischen Freiklicken nicht auch auf Minen geklickt wird.
Nee, das ist von vornherein ausgeschlossen: Es werden ja nur die Nachbarn von Feldern ohne Nachbarminen freigeklickt.
Und auch bereits freigeklickte Felder sollte man noch einmal freiklicken wollen, damit könnte man sich sonst nämlich ewig aufhalten — oder zumindest bis zum Rekursionslimit.
(Kann es sein, dass in diesem Satz ein "nicht" fehlt?) Meinst du sowas: Wenn Feld (0,0) angeklickt wird und keine Nachbarminen hat, dann wird (0,1) aufgedeckt, und wenn das auch keine Nachbarminen hat, wird (0,0) wieder angeklickt usw. Man muss die bereits angeklickten Felder also rausfiltern.. Danke für den Hinweis. :D

Lg Y.
PS: Die angebotene Summe ist beachtlich.
BlackJack

Donnerstag 10. September 2015, 16:06

@Üpsilon: Ja da fehlte ein „nicht“ in dem Satz. :oops:
Üpsilon
User
Beiträge: 189
Registriert: Samstag 15. September 2012, 19:23
Wohnort: Altschauerberg 8 in 91448 Emskirchen

Donnerstag 10. September 2015, 19:24

Soo, habe diesen Bug jetzt ausgebessert und den Code auch sonst überhaupt verschönert. Das Endergebnis darf man hier bestaunen :lol:. Wenn ihr noch Tipps für mich habt, dann her damit.
Lg Y.
PS: Die angebotene Summe ist beachtlich.
BlackJack

Freitag 11. September 2015, 00:12

@Üpsilon: Die ”magischen” Methoden werden üblicherweise am Anfang einer Klasse definiert. Mit dem `__str__()` so weit unten in der Klassendefinition rechnet niemand.

Abkürzungen bei Namen sollte man vermeiden, einbuchstabige Namen nur wenn die wirklich eindeutig sind, oder nur einen *sehr* begrenzten Gültigkeitsbereich haben („list comprehensions“ (LCs), Generator- und ``lambda``-Ausdrücke). Das `z` und `s` überall ist nicht schön. `x` und `y` wäre gegangen, aber `z` und `s` sind unüblich für Koordinaten.

Anstelle von `randint()` könnte man `randrange()` verwenden, dann braucht man weder den Startwert angeben noch den Endwert um 1 nach unten korrigieren.

Ob die Minenposition schon in `self.minen` enthalten ist braucht man nicht testen. Das kostet nur unnötig Rechenzeit.

In `berechne_nachbarn()` werden für meinen Geschmack zu viele Listen erstellt. `nachbarn` kann man in einer LC erstellen, ohne Listen als Zwischenergebnisse. Das `z` und `s` innerhalb der Methode an verschiedenen Stellen verschiedene Bedeutungen haben ist äusserst unschön. Auch für die Berechnung der Anzahl der Nachbarminen braucht man keine Liste erstellen.

Beim Methodennamen `pruefe_existenz()` würde ich einen Wahrheitswert als Rückgabewert erwarten und nicht das die Methode eine Ausnahme auslöst oder nicht.

Die Liste beim Aufruf von `mehrfachklick()` könnte man sich auch sparen und dort einen Generator übergeben. Deswegen ist der Argumentname `felderliste` auch zu einschränkend.

Weder bei `klick()` noch bei `mehrfachklick()` wird der Rückgabewert irgendwo verwendet.

Irgendwie wird bei der Ausgabe gar nicht zwischen freigeklickten Feldern und nicht freigeklickten Feldern unterschieden, nur bei Flaggen und Feldern die nicht freigeklickt sind und die Bomben als Nachbarn haben gibt es eine andere Ausgabe als das Leerzeichen.

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf8
from __future__ import absolute_import, division, print_function
from itertools import product as kartesisches_produkt
from random import randrange

try:
    range = xrange
except NameError:
    pass 


class SpielVerloren(Exception):
    pass


class Minenfeld(object):

    def __init__(self, breite=10, hoehe=10, minenanzahl=10):
        self.breite = breite
        self.hoehe = hoehe
        self.freigeklickt = set()
        self.flaggen = set()
        self.minen = set()
        while len(self.minen) < minenanzahl:
            self.minen.add((randrange(self.breite), randrange(self.hoehe)))
               
    def __str__(self):
        zeilen = (
            (
                '|'
                + '|'.join(self.feldinfo(z, s) for s in range(self.breite))
                + '|\n'
            )
            for z in range(self.hoehe)
        )
        trennzeile = '+-' * self.breite + '+\n'
        return trennzeile + trennzeile.join(zeilen) + trennzeile
   
    @property
    def ist_gewonnen(self):
        return self.flaggen == self.minen
       
    def berechne_nachbarn(self, zeile, spalte):
        nachbarn = [
            (z, s)
            for z, s in kartesisches_produkt(
                (zeile - 1, zeile, zeile + 1), (spalte - 1, spalte, spalte + 1)
            )
            if (
                (z, s) != (zeile, spalte)
                and 0 <= s < self.breite
                and 0 <= z < self.hoehe
            )
        ]
        nachbarminenanzahl = sum(1 for n in nachbarn if n in self.minen)
        return nachbarn, nachbarminenanzahl
       
    def pruefe_existenz(self, zeile, spalte):
        if not (0 <= zeile < self.hoehe and 0 <= spalte < self.breite):
            raise IndexError(
                'Dieses Feld gibts nicht! {0!r}'.format((zeile, spalte))
            )
   
    def feldinfo(self, zeile, spalte):
        self.pruefe_existenz(zeile, spalte)
        if (zeile, spalte) in self.flaggen:
            return '⚑'
        elif (zeile, spalte) not in self.freigeklickt:
            return '#'
        else:
            nachbarminenanzahl = self.berechne_nachbarn(zeile, spalte)[1]
            return str(nachbarminenanzahl) if nachbarminenanzahl else ' '
       
    # === Methoden, die vom Benutzer aufgerufen sollen ===
   
    def klick(self, zeile, spalte, out=True):
        # 
        # TODO `out` durch vernünftiges `logging` ersetzen.
        # 
        self.pruefe_existenz(zeile, spalte)
        if (zeile, spalte) in self.minen:
            raise SpielVerloren(
                'BOOOOOOM!!!!!!!! Mine bei {0!r}'.format((zeile, spalte))
            )
        self.freigeklickt.add((zeile, spalte))
        nachbarn, nachbarminenanzahl = self.berechne_nachbarn(zeile, spalte)
        if nachbarminenanzahl == 0:
            self.mehrfachklick(
                (n for n in nachbarn if n not in self.freigeklickt), False
            )
        if out:
            print(self)
   
    def mehrfachklick(self, felder, out=True):
        # 
        # TODO `out` durch vernünftiges `logging` ersetzen.
        # 
        for zeile, spalte in felder:
            self.klick(zeile, spalte)
        if out:
            print(self)
   
    def setze_flagge(self, zeile, spalte):
        self.pruefe_existenz(zeile, spalte)
        self.flaggen.add((zeile, spalte))
 

def main():
    minenfeld = Minenfeld()
    print(minenfeld)
    minenfeld.klick(5, 5)


if __name__ == '__main__':
    main()
Man könnte auch mal überlegen ob man Zeile und Spalte nicht günstiger als Tupel in der Gegend herum reichen kann, denn aus den beiden Werten wird ziemlich oft ein Tupel erstellt.
Üpsilon
User
Beiträge: 189
Registriert: Samstag 15. September 2012, 19:23
Wohnort: Altschauerberg 8 in 91448 Emskirchen

Freitag 11. September 2015, 08:24

Danke für die umfangreiche Antwort!
BlackJack hat geschrieben:@Üpsilon: Die ”magischen” Methoden werden üblicherweise am Anfang einer Klasse definiert. Mit dem `__str__()` so weit unten in der Klassendefinition rechnet niemand.

Abkürzungen bei Namen sollte man vermeiden, einbuchstabige Namen nur wenn die wirklich eindeutig sind, oder nur einen *sehr* begrenzten Gültigkeitsbereich haben („list comprehensions“ (LCs), Generator- und ``lambda``-Ausdrücke). Das `z` und `s` überall ist nicht schön. `x` und `y` wäre gegangen, aber `z` und `s` sind unüblich für Koordinaten.
Na wenn du das sagst...
Anstelle von `randint()` könnte man `randrange()` verwenden, dann braucht man weder den Startwert angeben noch den Endwert um 1 nach unten korrigieren.
Cool, das kannte ich noch nicht.
Ob die Minenposition schon in `self.minen` enthalten ist braucht man nicht testen. Das kostet nur unnötig Rechenzeit.
Äh, ja, stimmt. Das war noch ein Relikt aus der Zeit, als ich die Minen in einer Liste gespeichert habe.
In `berechne_nachbarn()` werden für meinen Geschmack zu viele Listen erstellt. `nachbarn` kann man in einer LC erstellen, ohne Listen als Zwischenergebnisse.
Und in deiner berechne_nachbarn steht für meinen Geschmack zu viel in einer LC :wink: Naja, Geschmack halt.
Das `z` und `s` innerhalb der Methode an verschiedenen Stellen verschiedene Bedeutungen haben ist äusserst unschön. Auch für die Berechnung der Anzahl der Nachbarminen braucht man keine Liste erstellen.
Das hab ich mir auch schon gedacht, aber aus Faulheit so gelassen.
Beim Methodennamen `pruefe_existenz()` würde ich einen Wahrheitswert als Rückgabewert erwarten und nicht das die Methode eine Ausnahme auslöst oder nicht.
Wenn es nicht mein Programm wäre, würde ich das auch erwarten :wink: . Aber früher hatte ich am Anfang jeder Methode, die Koordinaten übergeben bekommt, den Code, der jetzt in pruefe_existenz steht, und diese Methode war dann dazu da, diese Redundanz zu eliminieren.
Die Liste beim Aufruf von `mehrfachklick()` könnte man sich auch sparen und dort einen Generator übergeben. Deswegen ist der Argumentname `felderliste` auch zu einschränkend.
Ok.
Weder bei `klick()` noch bei `mehrfachklick()` wird der Rückgabewert irgendwo verwendet.
Ich habe gedacht, dass das mal praktisch wäre, wenn man auf dieses Programm aufbauend eine Minesweeper-KI bastelt.
Irgendwie wird bei der Ausgabe gar nicht zwischen freigeklickten Feldern und nicht freigeklickten Feldern unterschieden, nur bei Flaggen und Feldern die nicht freigeklickt sind und die Bomben als Nachbarn haben gibt es eine andere Ausgabe als das Leerzeichen.
Hier kann ich dir nicht folgen. Bei mir werden Leerzeichen für unangeklickte Felder benutzt und Nullen für ... Nullen.
Bei dir sinds Rauten für unangeklickte Felder und Leerzeichen für Nullen.
Man könnte auch mal überlegen ob man Zeile und Spalte nicht günstiger als Tupel in der Gegend herum reichen kann, denn aus den beiden Werten wird ziemlich oft ein Tupel erstellt.
Dann bräuchte man aber so viele Klammern, wenn man das Spiel einfach nur in der Python-Shell zocken wollte.

Naja, jetzt muss ich aber auch wirklich los, tschüssi und liebe Grüße.
PS: Die angebotene Summe ist beachtlich.
Sirius3
User
Beiträge: 8798
Registriert: Sonntag 21. Oktober 2012, 17:20

Freitag 11. September 2015, 09:15

ich bin ja für die direkte Methode ohne LCs:

Code: Alles auswählen

    def berechne_nachbarn(self, zeile, spalte):
        nachbarn = set(kartesisches_produkt(
            range(max(zeile-1, 0), min(self.hoehe, zeile+2)),
            range(max(spalte-1, 0), min(self.breite, spalte+2))
        )) - {(zeile,spalte)}
        nachbarminenanzahl = len(nachbarn.intersection(self.minen))
        return nachbarn, nachbarminenanzahl
BlackJack

Freitag 11. September 2015, 20:20

@Üpsilon: Bei der Ausgabe hatte ich wohl schon zuviel verändert so dass die 0en bei mir nicht ausgegeben wurden. :oops:
Antworten