# -*- coding: utf-8 -*-
import random

random.seed( )

# w - width
# h - height
def print_maze( mz, w, h ):
  for y in range( h ):
    for x in range( w ):
      print mz[ x ][ y ],
    print

def is_even( num ):
  return num % 2 == 0

#---------------------------------------------------------------- mark_frontier
# x,y - grid positions
# w - width
# h - height
# status - 2D list of the prim status of each maze position
# front - list that contains the squares that are on the frontier
# returns a list of surrounding 'in' status squares 
# note: not the actual squares, but the wall between them, to make the carving easier
def mark_frontier( x, y, w, h, status, front ):
  inlist = [ ]
  if x >= 2:
    if status[ x-2 ][ y ] == "o":
      status[ x-2 ][ y ] = "f"
      front.append( ( x-2, y ) )
    elif status[ x-2 ][ y ] == "i":
      inlist.append( ( x-1, y ) )
  if x <= w-3:
    if status[ x+2 ][ y ] == "o":
      status[ x+2 ][ y ] = "f"
      front.append( ( x+2, y ) )
    elif status[ x+2 ][ y ] == "i":
      inlist.append( ( x+1, y ) )
  if y >= 2:
    if status[ x ][ y-2 ] == "o":
      status[ x ][ y-2 ] = "f"
      front.append( ( x, y-2 ) )
    elif status[ x ][ y-2 ] == "i":
      inlist.append( ( x, y-1 ) )
  if y <= h-3:
    if status[ x ][ y+2 ] == "o":
      status[ x ][ y+2 ] = "f" 
      front.append( ( x, y+2 ) )
    elif status[ x ][ y+2 ] == "i":
      inlist.append( ( x, y+1 ) )
  return inlist
#------------------------------------------------------------------ end mark_frontier


#-------------------------------------------------------------gen_maze_prim
# a function that generates a maze based on Prim's algorithm
def gen_maze_prim( width, height ):

  # subtract width and height so Prim can operate on entire space
  # at the end, add in the border walls, entrance, and exit
  width = width - 2
  height = height - 2

  # create a maze for Prim to operate on
  mazestats = [ ]
  for i in range( width ):
    mazestats.append( [ "o" ]*height )

  # create start point
  # they *must* be even numbers for an odd x odd maze or results are a bit funky 
  # (similar reason why even x even is not used at all)
  # this is because of our odd maze representation where walls are cells
  # prim's really operates where walls aren't part of the maze
  currentx = random.randint( 1, width-1 )
  while not is_even( currentx ):
    currentx = random.randint( 1, width-1 )
  currenty = random.randint( 1, height-1 )
  while not is_even( currenty ):
    currenty = random.randint( 1, height-1 )
  mazestats[ currentx ][ currenty ] = "i"

  # start the digging
  frontier = [ ] # keep track of which cells on the frontier
  mark_frontier( currentx, currenty, width, height, mazestats, frontier )
  #print
  #print_maze( mazestats, width, height )
  while frontier:
    # shuffle frontier and take the first one to get a random frontier cell
    random.shuffle( frontier )
    currentx, currenty = frontier.pop( )
    # mark current cell as in
    mazestats[ currentx ][ currenty ] = "i"
    # mark its surrounding cells as frontier and get list of walls to in neighbors
    ins = mark_frontier( currentx, currenty, width, height, mazestats, frontier )
    # shuffle and take first to get a random wall
    random.shuffle( ins )
    wall = ins[ 0 ] 
    # tear down the wall to join with the in neighbor
    mazestats[ wall[ 0 ] ][ wall[ 1 ] ] = "i"    
    #print
    #print_maze( mazestats, width, height )

  # fill maze with walls
  maze = [ ]
  for i in range( width ):
    maze.append( [ "*" ]*( height ) )

  # update the maze to reflect Prim's results
  for x in range( width ):
    for y in range( height ):
      # edges must be walls so test for this first
      #if x == 0 or y == 0 or x == width-1 or y == height-1:
      #  maze[ x ][ y ] == "*"
      #else:
        foo = mazestats[ x ][ y ]
        if foo == "i":
          maze[ x ][ y ] = " "
        elif foo == "o":
          maze[ x ][ y ] = "*"
        else: # this is for debugging, maze should never have an @
          maze[ x ][ y ] = "@"
  

  # add the outside vertical edges
  maze.insert( 0, [ "*" ]*height )
  maze.append( [ "*" ]*height )
  
  # change width and height back to original values
  width = width + 2
  height = height + 2
  
  # add the horizontal edges
  for x in range( width ):
    maze[ x ].insert( 0, "*" )
    maze[ x ].append( "*" )

  # find an entrance and exit
  start = random.randint( 0, height )
  while maze[ 1 ][ start ] != " ":
    start = random.randint( 0, height )
  maze[ 0 ][ start ] = " " 
  end = random.randint( 0, height )
  while maze[ width-2 ][ end ] != " ":
    end = random.randint( 0, height )
  maze[ width-1 ][ end ] = " " 
  
  return maze, start, end
  
#----------------------------------------------------------- end maze_gen_prim

w = input( "Width (odd numbers only)? " )
while is_even( w ):
  w = input( "Width (odd numbers only)? " )
h = input( "Height (odd numbers only)? " )
while is_even( h ):
  h = input( "Height (odd numbers only)? " )
generated, s, e = gen_maze_prim( w, h )
print "Start is at ( 0,", s, ") and end is ( ", w-1, ",", e, ")"
print_maze( generated, w, h )