ASCII mazes

# Grid format:
#   0 = Navigable space
#   1 = Occupied space

import random

deltas = [[-1, 0 ], # go up
        [ 0, -1], # go left
        [ 1, 0 ], # go down
        [ 0, 1 ]] # go right

delta_names = ['^', '<', 'v', '>']

cost = 1

def search(grid, init, goal, cost):
    current = [0] + init
    open = [current]
    closed = []
    action = [[ '' for col in range(len(grid[0]))] for row in range(len(grid))]
    resign = False
    while current[1:] != goal:
        if not open: #no open nodes left
            resign = True
            current[0] = -1
            break
        current = min(open, key= lambda pos: pos[0]) #Find open node with smallest g
        #first coordinate is y, not x
        gcur, ycur, xcur = current
        for d in zip(deltas, delta_names):
            (dy, dx), direction = d
            g, y, x = gcur + cost, ycur + dy, xcur + dx
            if x<0 or y<0 or y>=len(grid) or x>=len(grid[0]):
                continue
            elif [y,x] in closed or grid[y][x]==1: #already visited, or a wall
                continue
            elif [y,x] in map(lambda node: node[1:], open): #already planning to visit
                continue
            else:
                open.append([g, y, x])
                action[y][x] = direction

        open.remove([gcur,ycur,xcur])
        closed.append([ycur, xcur])

    current_g, _, _ = current #cost of getting to goal

    #ASCII art for path
    dir_dict = {}
    for d in zip(deltas, delta_names):
        delta, delta_name = d
        dir_dict[delta_name] = delta

    roadmap = [[' ' for col in range (len(grid[0]))] for row in range(len(grid))]

    #add walls
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                roadmap[i][j] = 'H'

    #add path
    path_y, path_x = ycur, xcur
    if resign: #nowhere left to go
        roadmap[path_y][path_x] = '?'
    goal_y, goal_x = goal
    roadmap[goal_y][goal_x] = '*'
    while [path_y, path_x] != init:
        motion = action[path_y][path_x]
        path_dy, path_dx = dir_dict[motion]
        path_y, path_x = path_y - path_dy, path_x - path_dx
        roadmap[path_y][path_x] = motion

    #beautify
    roadmap = map(lambda x: ' '.join(x), roadmap)
    roadmap = map(lambda x: '| '+ x + ' |', roadmap)
    roadmap = ['='*len(roadmap[0])] + roadmap + ['='*len(roadmap[0])]
    return current_g, roadmap

def generate_grid(maxsize):
    no_of_columns = random.randint(2, maxsize)
    no_of_rows = random.randint(2,maxsize)
    max_wall_percent = 25
    cells_per_wall = 100/max_wall_percent

    grid = [ [0] * no_of_columns ] * no_of_rows
    grid = map(lambda row: map(lambda entry: 1 if random.randint(1, cells_per_wall)%int(cells_per_wall)==0\
        else 0, row), grid)

    while True:
        init_y, init_x = random.randint(0, len(grid)-1), random.randint(0, len(grid[0])-1)
        if grid[init_y][init_x] == 0: #initial position isn't a wall
            break
    init = [init_y, init_x]
    while True:
        goal_y, goal_x = random.randint(0, len(grid)-1), random.randint(0, len(grid[0])-1)
        if grid[goal_y][goal_x] == 0 and [goal_y,goal_x] != init: #goal shouldn't be a wall, or same as start point
            break
    goal = [goal_y, goal_x]

    return grid, init, goal

grid, init, goal = generate_grid(20)
steps, path= search(grid, init, goal, cost)
for row in path:
    print row
print "cost:", steps