Skip to content

Instantly share code, notes, and snippets.

@serser
Created December 6, 2017 07:51
Show Gist options
  • Save serser/94f90cc9453efab6ef34bf77939a1b27 to your computer and use it in GitHub Desktop.
Save serser/94f90cc9453efab6ef34bf77939a1b27 to your computer and use it in GitHub Desktop.
# https://classroom.udacity.com/courses/cs373/lessons/48646841/concepts/486468390923
# -----------
# User Instructions:
#
# Modify the the search function so that it becomes
# an A* search algorithm as defined in the previous
# lectures.
#
# Your function should return the expanded grid
# which shows, for each element, the count when
# it was expanded or -1 if the element was never expanded.
#
# If there is no path from init to goal,
# the function should return the string 'fail'
# ----------
grid = [[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0]]
heuristic = [[9, 8, 7, 6, 5, 4],
[8, 7, 6, 5, 4, 3],
[7, 6, 5, 4, 3, 2],
[6, 5, 4, 3, 2, 1],
[5, 4, 3, 2, 1, 0]]
init = [0, 0]
goal = [len(grid)-1, len(grid[0])-1]
cost = 1
delta = [[-1, 0 ], # go up
[ 0, -1], # go left
[ 1, 0 ], # go down
[ 0, 1 ]] # go right
delta_name = ['^', '<', 'v', '>']
def search(grid,init,goal,cost,heuristic):
# ----------------------------------------
# modify the code below
# ----------------------------------------
closed = [[0 for col in range(len(grid[0]))] for row in range(len(grid))]
closed[init[0]][init[1]] = 1
expand = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))]
action = [[-1 for col in range(len(grid[0]))] for row in range(len(grid))]
x = init[0]
y = init[1]
g = 0
open = [[g, x, y]]
found = False # flag that is set when search is complete
resign = False # flag set if we can't find expand
count = 0
while not found and not resign:
if len(open) == 0:
resign = True
return "Fail"
else:
open.sort()
open.reverse()
next = open.pop()
x = next[1]
y = next[2]
g = next[0]
expand[x][y] = count
count += 1
if x == goal[0] and y == goal[1]:
found = True
else:
buf = []
for i in range(len(delta)):
x2 = x + delta[i][0]
y2 = y + delta[i][1]
if x2 >= 0 and x2 < len(grid) and y2 >=0 and y2 < len(grid[0]):
if closed[x2][y2] == 0 and grid[x2][y2] == 0:
g2 = g + cost
buf.append([g2, x2, y2])
#print 'buf',buf, 'found:', found
if len(buf):
buf_s = sorted(buf, key=lambda x:heuristic[x[1]][x[2]], reverse=False)
open.append(buf_s[0])
closed[buf_s[0][1]][buf_s[0][2]] = 1
return expand
print search(grid,init,goal,cost,heuristic)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment