Sokoban Cheater

CDW

0
Mitarbeiter
Das berühmte Spiel mit den Kisten/Diamanten/Kugeln.
(wer er nicht kennt: ab in die Ecke und schämt euch!)
http://en.wikipedia.org/wiki/Sokoban

Die Levels liegen üblicherweise in diesem Format vor:
http://www.sokobano.de/wiki/index.php?title=Level_format

Schreibe ein Programm, welches ein Level lösen kann.
Idealerweise kann das Programm ein Level in dem Format einlesen und die Lösung als Schrittabfolge (up,right,down oder ^ > v usw. ) der Figur präsentieren.

Als Testlevels können die Beispiele aus
http://www.sokobano.de/wiki/index.php?title=How_to_play_Sokoban
genommen werden. Richtig "schöne" Levels sollten z.B im Nabokosmos
http://www.sokobano.de/de/levels.php Packet enthalten sein ;)
 
Eine recht simple Implementierung habe ich mal geschrieben. Da sie total unoptimiert ist kann sie m.E. noch nicht als vollwertige Lösung angesehen werden. Wer will kann gerne auf meinem Source-Code aufbauen.
Das Programm sucht in jedem Schritt die Positionen, bei denen es sich lohnt, sie zu besuchen, also die, von denen aus man einen Stein verschieben kann. Dann geht es per A*-Algorithmus an die entsprechende Position und verschiebt den Stein. Die ganzen Möglichkeiten werden dann per Breitensuche durchkämmt. Es wird also immer die optimale Lösung gefunden.
Da ich noch keine Optimierungen (Heuristiken) eingebaut habe kann man nur sehr kleine Level lösen, da es sonst einfach zu lange dauert. Bei einem Level mit drei Steinen, das mehr als 40 Schritte braucht, kann man das Programm quasi nicht mehr benutzen.
Code:
#!/usr/bin/python
import time
import sys
sokofield = []
f = open(sys.argv[1])
for line in f:
    l = []
    for c in line[:-1]:
        l.append(c)
    sokofield.append(l)
f.close()

def printField(field):
    for line in field:
        for cell in line:
            print(cell, sep="", end="")
        print()

'''def isWalkable(field, x, y):
    if y < len(field) and x < len(field[0]) and field[y][x] != '#':
        return True
    else:
        return False'''
    
def isFree(field, x, y):
    if y < len(field) and x < len(field[0]) and (field[y][x] == ' ' or field[y][x] == '.' or field[y][x] == '@'):
        return True
    else:
        return False

def isWallFree(field, x, y):
    if y < len(field) and x < len(field[0]) and (field[y][x] == ' ' or field[y][x] == '.' or field[y][x] == '@' or field[y][x] == '$'):
        return True
    else:
        return False

def isTarget(field, x, y):
    if y < len(field) and x < len(field[0]) and field[y][x] == '.':
        return True
    else:
        return False
        
def getValidPos(field, lastPos):
    validPos = []
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if cell == '$':
                if isFree(field, x, y-1) and isFree(field, x, y+1):
                    if isTarget(field, x, y+1) or not isBlocked(field, x, y+1):
                        validPos.append(((x, y-1), (x, y)))
                    if isTarget(field, x, y-1) or not isBlocked(field, x, y-1):
                        validPos.append(((x, y+1), (x, y)))
                if isFree(field, x-1, y) and isFree(field, x+1, y):
                    if isTarget(field, x+1, y) or not isBlocked(field, x+1, y):
                        validPos.append(((x-1, y), (x, y)))
                    if isTarget(field, x-1, y) or not isBlocked(field, x-1, y):
                        validPos.append(((x+1, y), (x, y)))
    return validPos

def isBlocked(field, x, y):
    return False
    if ((isWallFree(field, x-1, y) and isWallFree(field, x+1, y)) or
        (isWallFree(field, x, y-1) and isWallFree(field, x, y+1))):
        print(x, y, "free")
        return False
    else:
        print(x, y, "not free")
        return True

def getNeighbors(field, x, y):
    nb = []
    if isFree(field, x-1, y):
        nb.append((x-1, y))
    if isFree(field, x, y-1):
        nb.append((x, y-1))
    if isFree(field, x+1, y):
        nb.append((x+1, y))
    if isFree(field, x, y+1):
        nb.append((x, y+1))
    return nb

def aStar(field, startPos, targetPos):
    openlist = [startPos]
    ratings = {startPos: 0}
    pre = {startPos: None}
    closedlist = []
    while len(openlist) > 0:
        b = dict(map(lambda item: (item[1],item[0]),ratings.items()))
        currentNode = b[min(b.keys())]
        currentRating = ratings[currentNode]
        openlist.remove(currentNode)
        ratings.pop(currentNode)
        if (currentNode == targetPos):
            break
        for nb in getNeighbors(field, currentNode[0], currentNode[1]):
            if nb in closedlist:
                continue
            f = currentRating + abs(currentNode[0] - nb[0]) + abs(currentNode[1] - nb[1])
            if nb in openlist:
                if ratings[nb] <= f:
                    continue
            else:
                openlist.append(nb)
            ratings[nb] = f
            pre[nb] = currentNode
        closedlist.append(currentNode)
        
    currentNode = targetPos
    path = [currentNode]
    try:
        while (currentNode != startPos):
            currentNode = pre[currentNode]
            path.append(currentNode)
        path.reverse()
        return path
    except KeyError:
        return None

def doMove(myField, f, t):
    (x, y) = f
    (nx, ny) = t
    if (sokofield[y][x] != '@' and sokofield[y][x] != '$'):
        myField[y][x] = sokofield[y][x]
    else:
        myField[y][x] = ' '
    if (myField[ny][nx] == '$'):
        myField[ny + (ny - y)][nx + (nx - x)] = '$'
    myField[ny][nx] = '@'
    return myField

def getPlayerPos(field):
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if (cell == '@'):
                return (x, y)
    return None

def getNumTargets(field):
    numTargets = 0 
    for y in range(len(field)):
        for x in range(len(field[y])):
            cell = field[y][x]
            if (cell == '.'):
                numTargets += 1
            elif (cell == '@' and sokofield[y][x] == '.'):
                numTargets += 1
    return numTargets
    
def positionsToPath(pos):
    path = ''
    for i in range(len(pos)-1):
        (fx, fy) = pos[i]
        (tx, ty) = pos[i+1]
        if (tx < fx): path += 'l'
        elif (tx > fx): path += 'r'
        elif (ty < fy): path += 'u'
        elif (ty > fy): path += 'd'
    return path

def breitensuche(field):
    moves = [(0, getPlayerPos(field), field, [])]
    minMoves = 0
    while (len(moves) > 0):
        minMove = min(moves)
        moves.remove(minMove)
        if minMove[0] > minMoves:
            print("Kein Weg unter %s Schritten" % minMove[0])
            minMoves = minMove[0]
        #print(minMove[0], minMove[3])
        #printField(minMove[2])
        if getNumTargets(minMove[2]) == 0:
            print("Loesung gefunden:")
            printField(minMove[2])
            print("Weg:", positionsToPath(minMove[3]))
            break

        pos = getValidPos(minMove[2], 0)
        for pt in pos:
            (p, t) = pt
            #print(p)
            path = aStar(minMove[2], minMove[1], p)
            if (path == None): continue
            path.append(t)
            myField = [[a for a in b] for b in minMove[2]]
            for pid in range(len(path)-1):
                myField = doMove(myField, path[pid], path[pid+1])
            newMove = (minMove[0] + len(path), t, myField, minMove[3] + path)
            #print(newMove)
            #printField(myField)
            #printField(minMove[2])
            moves.append(newMove)
        #time.sleep(1)
            
print("Ausgangslage:")
printField(sokofield)
print("Suche Loesung...")
breitensuche(sokofield)
Code:
Ausgangslage:
########
#  #.  #
# $#   #
#  # @##
#  # $##
#    .##
########
Suche Loesung...
Kein Weg unter 2 Schritten
Kein Weg unter 6 Schritten
Kein Weg unter 8 Schritten
Kein Weg unter 9 Schritten
[...]
Kein Weg unter 40 Schritten
Loesung gefunden:
########
#  #$@ #
#  #   #
#  #  ##
#  #  ##
#    $##
########
Weg: lddrudllluuluurdddldrrruruurul
 
Zurück
Oben