Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/python
#TrendJP CTF Prog300 - maze solving
#@mrexcessive @WHA
import sys
import copy
import math
from itertools import permutations
debug = True
debugLots = False
#useful
logfname="logTries.txt"
def Log(s,alwaysLog = False):
if logfname <> None:
f=open(logfname,"a")
f.write("%s\n" % s)
f.close
if debug and (alwaysLog or debugLots):
print s
walkingFname = "walking.txt"
def Walk(s,logIt = True):
Log("Walking [%s]" % s,True)
if walkingFname <> None:
f = open(walkingFname,"a")
f.write("%s\n" % s)
f.close()
def NewWalk(): # start a new walk
Walk("\n\n\nNEW WALK\n\n")
#A* solving
def GenerateMoves(m):
board = {}
bw = len(m[0]) # YYY all walls have been removed at this point
bh = len(m)
print "Board width,height = %i,%i" % (bw,bh) # I is row number, J is minor index and column
player = None
exitGoals = [] # list of possible goals - will need to compute best energy for each possible goal...
food = {}
walls = {}
checkpoints = [] # have to visit these - so they are sub-goals sigh
for i in xrange(0,bh): # first row is label
d = m[i]
for j in xrange(0,bw):
key = (j,i)
board[key] = None # create cell on map
cell = d[j]
if cell == ".": # empty cell
pass
elif cell == "E":
food[(j,i)] = 1 # good thing food - if not too far to go...
elif cell == "C":
checkpoints.append((j,i)) # gotta visit these before goals
elif cell == "S": # player start
player = (j,i)
elif cell == "G": # player exit
exitGoals.append((j,i)) # YYY note that j is X coord and i is Y coord...
elif cell == "#": # wall
walls[(j,i)] = 1
else:
print "Failed to parse board, what is [%s]" % cell
exit()
assert(player <> None)
assert(len(exitGoals) > 0)
def hestimate(posa,posb):
ax,ay = posa
bx,by = posb
d = math.sqrt( (ax - bx) * (ax - bx) + (ay - by) * (ay - by) )
return d # note this is a float
def NeighbourList(posa):
result = []
x,y = posa
for (dx,dy) in [(-1,0),(1,0),(0,-1),(0,1)]: # no diagonal moves
tx = x + dx # tentative
ty = y + dy
if tx >= 0 and tx <= bw and ty >= 0 and ty <= bh: # check within bounds
result.append((tx,ty))
return result
# need to generate an enumeration of checkpoints and goals, but only for checkpoints first in any order then goals
# then generate a complete path from start, through each sequence of checkpoints, ending at each goal
# then pick the lowest scored
# XXX ideally need to track health accurately... so when walk over already covered point is -1
best_score = 8888 # less than one wall...
best_path = None
for checkpointSequence in permutations(checkpoints): # try all sequences through mandatory checkpoints
for oneExitGoal in list(exitGoals): # and each checkpoint sequence with each possible exit point
print "x"
goalsRunningOrder = list(checkpointSequence) + [oneExitGoal]
# OK so now calculate total path and score from start to first goal, first goal to second goal etc...
this_score = 0
this_path = ""
already_visited = {} # temporary list of places already visited this sequence run
goalsRunningOrder = [player] + goalsRunningOrder # now can strip them off in pairs, player is first start location
for i in xrange(0,len(goalsRunningOrder)-1): # minimum seq is (start, end)
closedset = {} #A* algo see http://en.wikipedia.org/wiki/A*_search_algorithm
openset = {}
gscore = {} # known route scores to end
fscore = {} # estimated total cost from start to goal through here
start = goalsRunningOrder[i]
goal = goalsRunningOrder[i+1]
print "seq %i start %s end %s" % (i,start,goal)
openset[ start ] = 1
came_from = copy.deepcopy(board) # YYY need to deepcopy each time or we'll mess with algo...
gscore[start] = 0 # yes, yes - I am copying the wiki algo, not using my own map data entirely ...
fscore[start] = gscore[start] + hestimate(start,goal)
failedAstar = True
while len(openset.keys()) > 0:
minscore = 9999
minkey = None
for k in openset.keys():
v = fscore[k]
if v < minscore:
minscore = v
minkey = k
assert(minkey <> None)
current = minkey
if current == goal:
failedAstar = False
break # exit while()
del openset[current]
closedset[current] = minscore # that's what the score was ^^^
neighbours = NeighbourList(current)
for n in neighbours:
if closedset.has_key(n):
continue
if walls.has_key(n):
tentative_gscore = 9999 # can't go this way
elif food.has_key(n):
tentative_gscore = -20 # reward eating food
elif already_visited.has_key(n):
tentative_gscore = 1 # punishment
else:
tentative_gscore = gscore[current] + hestimate(current,n)
if not openset.has_key(n) or tentative_gscore < gscore[n]:
came_from[n] = current
gscore[n] = tentative_gscore
fscore[n] = gscore[n] + hestimate(n,goal)
if not openset.has_key(n):
openset[n] = 1
#end while()
if failedAstar:
print "bad failed... ?"
exit() # should never happen
# Derive path from scores generated
total_path = [current] # current == goal at this point
while current in came_from.keys():
current = came_from[current]
total_path = [current] + total_path
Log("Total path = %s" % total_path)
# Here we have a path through points, turn it into directions
nowx,nowy = total_path[1] # first is always None, second is start point of playerone at start... skip that
path = total_path[2:] #
movestring = ""
for p in path:
already_visited[p] = 1 # only count midpoints as already visited
(nx,ny) = p
if nx > nowx: # implement a WASD controller... can only be one of these each time 'cos no diagonal moves
ch = "R"
elif nx < nowx:
ch = "L"
elif ny < nowy:
ch = "U"
elif ny > nowy:
ch = "D"
else:
print "SOMETHING WENT HORRIBLY wrong %i,%i move to %i,%i" % (nowx,nowy,nx,ny)
exit()
movestring += ch
nowx = nx
nowy = ny
# add moves to current attempt, also add the score
this_path += movestring
this_score += fscore[goal]
#end for all the sequences
if this_score < best_score: # lower is better
best_score = this_score
best_path = this_path
Log("GenerateMoves says [%s]" % best_path)
return best_path
if __name__ == "__main__":
fnamemaze = "maze.txt"
f = open(fnamemaze,"rb")
raw = f.read()
f.close()
NewWalk()
rows = raw.split("\n")
state = 0 # 0=> expecting numbers defining size new maze
mazesSolved = 0
for onerow in rows:
if onerow == "":
break # all done
if state == 0:
nums = onerow.split(" ")
width = int(nums[0])
height = int(nums[1])
food = int(nums[2])
print "New maze %i * %i with %i food" % (width,height,food)
state = 1
onemaze = []
elif state == 1: # reading blank ######## at head of this maze
countrows = height - 2 # actual rows ignoring the boundaries
state = 2 # next read data
elif state == 2: # reading maze rows
rowbit = onerow[1:-1] # skip first and last chars (which are boundary walls)
onemaze.append(rowbit)
countrows -= 1
if countrows == 0:
state = 3
elif state == 3: # skip final blank row and solve maze
Log( "So go solve maze %i\n%s" % (mazesSolved+1,"\n".join(onemaze)) )
moves = GenerateMoves(onemaze)
Walk(moves)
mazesSolved += 1
state = 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.