ASCII Mazes with A* search

# 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, astar=True):
    current = (0,) + init
    open = [current]
    closed = []
    action = [[ '' for col in range(len(grid[0]))] for row in range(len(grid))]
    resign = False

    if astar:
        heuristic = generate_heuristic(grid, goal)
    else:
        heuristic = [[0 for x in range(len(grid[0]))] for y in range(len(grid))]

    while current[1:] != goal:
        if not open: #no open nodes left
            resign = True
            current = (-1,) + current[1:]
            break
        #Find open node with smallest f = g + h
        current = min(open, key= lambda (g, y, x): g + heuristic[y][x])
        #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 and visited nodes
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == 1:
                roadmap[i][j] = 'H'
            if (i,j) in closed:
                roadmap[i][j] = '.'

    #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 for column in range(no_of_columns)] for row in range(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

def generate_heuristic(grid, goal):
    heuristic = [ [-1 for column in range(len(grid[0]))] for row in range(len(grid))]
    goal_y, goal_x = goal
    for y in range(len(grid)):
        for x in range(len(grid[0])):
            heuristic[y][x] = abs(y-goal_y) + abs(x-goal_x)
    return heuristic

grid, init, goal = generate_grid(20)

print "Without A*"
steps, path= search(grid, init, goal, cost, False)
for row in path:
    print row
print "cost: ", steps
print
print "With A*"
steps, path= search(grid, init, goal, cost, True)
for row in path:
    print row
print "cost:", steps