#!/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)