import random import pygame import sys random.seed (63) def solveMaze (maze, edges): mazeSizeY = len (maze[0]) mazeSizeX = len (maze) xAt = 0; yAt = 0 # Find the start for yy in xrange (0, mazeSizeY): for xx in xrange (0, mazeSizeX): if maze[xx][yy] == 'S': xAt = xx; yAt = yy solveMazeH (maze, edges, xAt, yAt, mazeSizeX, mazeSizeY) def solveMazeH (maze, edges, xAt, yAt, mazeSizeX, mazeSizeY): if maze[xAt][yAt] == 'F': return True maze[xAt][yAt] = '.' drawMaze (maze, edges) # need to take into account edges if edges[xAt][yAt][0] == ' ' and yAt < mazeSizeY - 1 and (maze[xAt][yAt + 1] == ' ' or maze[xAt][yAt + 1] == 'F'): if solveMazeH (maze, edges, xAt, yAt + 1, mazeSizeX, mazeSizeY): return True if edges[xAt][yAt][1] == ' ' and xAt < mazeSizeX - 1 and (maze[xAt + 1][yAt] == ' ' or maze[xAt + 1][yAt] == 'F'): if solveMazeH (maze, edges, xAt + 1, yAt, mazeSizeX, mazeSizeY): return True if yAt > 0 and edges[xAt][yAt - 1][0] == ' ' and (maze[xAt][yAt - 1] == ' ' or maze[xAt][yAt - 1] == 'F'): if solveMazeH (maze, edges, xAt, yAt - 1, mazeSizeX, mazeSizeY): return True if xAt > 0 and edges[xAt - 1][yAt][1] == ' ' and (maze[xAt - 1][yAt] == ' ' or maze[xAt - 1][yAt] == 'F'): if solveMazeH (maze, edges, xAt - 1, yAt, mazeSizeX, mazeSizeY): return True maze[xAt][yAt] = ' ' drawMaze (maze, edges) def makeMaze (mazeSizeX, mazeSizeY, patternFile): maze = [] edges = [] allset = [] for x in xrange (mazeSizeX): maze.append ([]) edges.append ([]) for y in range (mazeSizeY): maze[x].append ('X') # below and to the right edges[x].append (['_', '|']) for x in xrange (1, mazeSizeX - 1): for y in range (1, mazeSizeY - 1): allset.append ([x, y]) startX = 1; startY = 1; finishX = mazeSizeX - 2; finishY = mazeSizeY - 2 zcounter = -1 for a in patternFile: zcounter = zcounter + 1 for i in xrange (len (a) - 1): if a[i] == 'O': maze[zcounter][i] = 'O' edges[zcounter][i][0] = ' ' edges[zcounter][i][1] = ' ' if a[i] == '|': maze[zcounter][i] = 'O' edges[zcounter][i][1] = ' ' if a[i] == '_': maze[zcounter][i] = 'O' edges[zcounter][i][0] = ' ' if a[i] == 'J': maze[zcounter][i] = 'O' if a[i] == '>': edges[zcounter][i][0] = ' ' maze[zcounter][i] = ' ' if a[i] == 'v': edges[zcounter][i][1] = ' ' maze[zcounter][i] = ' ' if a[i] == '<': edges[zcounter][i - 1][0] = ' ' maze[zcounter][i] = ' ' if a[i] == '^': edges[zcounter - 1][i][1] = ' ' maze[zcounter][i] = ' ' if a[i] == 'S': # Start! startX = zcounter startY = i if a[i] == 'F': # Finish! finishX = zcounter finishY = i # Make the maze numOpen = 10 while numOpen > 0: random.shuffle (allset) numOpen = 0 for point in allset: x = point[0] y = point[1] if maze[x][y] == 'X': sum1 = 0 open = [] if maze[x + 1][y] == ' ': open.append ([x, y, 1]) if maze[x - 1][y] == ' ': open.append ([x - 1, y, 1]) if maze[x][y + 1] == ' ': open.append ([x, y, 0]) if maze[x][y - 1] == ' ': open.append ([x, y - 1, 0]) if len (open) > 0: edge = random.choice (open) edges[edge[0]][edge[1]][edge[2]] = ' ' maze[x][y] = ' ' numOpen = numOpen + 1 drawMaze (maze, edges) maze[startX][startY] = 'S' maze[finishX][finishY] = 'F' return [maze, edges] # X_|X_|X_| # X_|X_|X_| # X_| |X_| def printMaze (maze, edges): h = '_' for xx in xrange (1, len (maze) - 1): h = h + '__' print h for yy in xrange (1, len (maze[0]) - 1): h = '|' for xx in xrange (1, len (maze) - 1): # h = h + maze[xx][yy] if yy == len (maze) - 2 and edges[xx][yy][1] == ' ': h = h + '_' else: h = h + edges[xx][yy][0] if edges[xx][yy][1] == ' ' and edges[xx][yy][0] == '_': h = h + '_' else: h = h + edges[xx][yy][1] print h print def drawMaze (maze, edges): mazeSizeY = len (maze[0]) mazeSizeX = len (maze) lw = 1 b = pygame.draw.rect (marcsurf, [0, 0, 0], [0, 0, mazeSizeY * scale, mazeSizeX * scale]) b = pygame.draw.line (marcsurf, [0, 255, 0], [scale, scale], [(mazeSizeY - 1) * scale, scale], lw) b = pygame.draw.line (marcsurf, [0, 255, 0], [scale, scale], [scale, (mazeSizeX - 1) * scale], lw) for yy in xrange (1, mazeSizeY - 1): for xx in xrange (1, mazeSizeX - 1): if (edges[xx][yy][0] == '_'): b = pygame.draw.line (marcsurf, [0, 255, 0], [(yy + 1) * scale, xx * scale], [(yy + 1) * scale, (xx + 1) * scale], lw) if (edges[xx][yy][1] == '|'): b = pygame.draw.line (marcsurf, [0, 255, 0], [yy * scale, (xx + 1) * scale], [(yy + 1) * scale, (xx + 1) * scale], lw) for yy in xrange (0, mazeSizeY): for xx in xrange (0, mazeSizeX): if maze[xx][yy] == 'S': b = pygame.draw.circle (marcsurf, [255, 0, 0], [int ((yy + .5) * scale), int ((xx + .5) * scale)], int (.5 * scale) - 1, 0) if maze[xx][yy] == '.': b = pygame.draw.circle (marcsurf, [255, 255, 255], [int ((yy + .5) * scale), int ((xx + .5) * scale)], int (.5 * scale) - 1, 0) if maze[xx][yy] == 'F': b = pygame.draw.circle (marcsurf, [255, 255, 0], [int ((yy + .5) * scale), int ((xx + .5) * scale)], int (.5 * scale) - 2, 0) pygame.display.update () def generatePostscript (maze, edges, newfile): mazeSizeY = len (maze[0]) mazeSizeX = len (maze) lw = 2 newfile.write ('%!\n') newfile.write (str (lw + .05) + ' setlinewidth\n') newfile.write ('0 0 0 setrgbcolor\n') newfile.write ('20 20 translate\n') # newfile.write ('90 rotate\n') # newfile.write ('200 -150 moveto\n') # newfile.write ('90 rotate\n') #newpath #0 1 0 setrgbcolor #331.316 369.816 moveto #331.315 369.816 lineto #331.316 369.815 lineto #331.316 369.816 lineto #331.316 369.816 lineto #fill newfile.write ('newpath ' + str (scale) + ' ' + str (scale - lw/2.0) + ' moveto ' + str (scale) + ' ' + str ((mazeSizeY - 1) * scale + lw/2.0) + ' lineto stroke\n') # newfile.write ('newpath ' + str (scale * 2 - lw/2.0) + ' ' + str (scale) + ' moveto ' + str ((mazeSizeX - 1) * scale + lw/2.0) + ' ' + str (scale) + ' lineto stroke\n') newfile.write ('newpath ' + str (scale * 1 - lw/2.0) + ' ' + str (scale) + ' moveto ' + str ((mazeSizeX - 2) * scale + lw/2.0) + ' ' + str (scale) + ' lineto stroke\n') for yy in xrange (1, mazeSizeY - 1): for xx in xrange (1, mazeSizeX - 1): if (edges[xx][yy][0] == '_') and (yy != mazeSizeY - 2 or xx != mazeSizeX - 2): newfile.write ('newpath ' + str (xx * scale - lw/2.0) + ' ' + str ((yy + 1) * scale) + ' moveto ' + str ((xx + 1) * scale + lw/2.0) + ' ' + str ((yy + 1) * scale) + ' lineto stroke\n') if (edges[xx][yy][1] == '|'): newfile.write ('newpath ' + str ((xx + 1) * scale) + ' ' + str (yy * scale - lw/2.0) + ' moveto ' + str ((xx + 1) * scale) + ' ' + str ((yy + 1) * scale + lw/2.0) + ' lineto stroke\n') newfile.write ('showpage\n') newfile.flush () def countMaze (maze, mazeSizeX, mazeSizeY): sum = 0 for yy in range (mazeSizeY): for xx in range (mazeSizeX): if maze[xx][yy] == '.': sum = sum + 1 return sum filename = sys.argv[1] # Get the sizes mazeSizeX = 0 mazeSizeY = 0 zcounter = -1 patternFile = open (filename) for a in patternFile: zcounter = zcounter + 1 for i in xrange (len (a) - 1): if a[i] != ' ' and a[i] != '\n': if i > mazeSizeY: mazeSizeY = i if zcounter > mazeSizeX: mazeSizeX = zcounter mazeSizeX = mazeSizeX + 2 mazeSizeY = mazeSizeY + 2 # scale = 15 scale = 10 top = 0 marcsurf = pygame.display.set_mode ([mazeSizeY * scale, mazeSizeX * scale]) patternFile = open (filename) [maze, edges] = makeMaze (mazeSizeX, mazeSizeY, patternFile) drawMaze (maze, edges) newfile = open (filename + '.ps', 'w') generatePostscript (maze, edges, newfile) # printMaze (maze, edges) solveMaze (maze, edges) drawMaze (maze, edges) input () ##for i in range (20000): ## random.seed (i) ## maze = makeMaze (mazeSizeX, mazeSizeY) ## solveMaze (maze, xAt, 1, mazeSizeX, mazeSizeY) ## # printMaze (maze, mazeSizeX, mazeSizeY) ## sum = countMaze (maze, mazeSizeX, mazeSizeY) ## if sum > top: ## top = sum ## print i, top ## printMaze (maze, mazeSizeX, mazeSizeY)