-
-
Save jamiees2/5531924 to your computer and use it in GitHub Desktop.
| # Enter your code here. Read input from STDIN. Print output to STDOUT | |
| class Node: | |
| def __init__(self,value,point): | |
| self.value = value | |
| self.point = point | |
| self.parent = None | |
| self.H = 0 | |
| self.G = 0 | |
| def move_cost(self,other): | |
| return 0 if self.value == '.' else 1 | |
| def children(point,grid): | |
| x,y = point.point | |
| links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]] | |
| return [link for link in links if link.value != '%'] | |
| def manhattan(point,point2): | |
| return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0]) | |
| def aStar(start, goal, grid): | |
| #The open and closed sets | |
| openset = set() | |
| closedset = set() | |
| #Current point is the starting point | |
| current = start | |
| #Add the starting point to the open set | |
| openset.add(current) | |
| #While the open set is not empty | |
| while openset: | |
| #Find the item in the open set with the lowest G + H score | |
| current = min(openset, key=lambda o:o.G + o.H) | |
| #If it is the item we want, retrace the path and return it | |
| if current == goal: | |
| path = [] | |
| while current.parent: | |
| path.append(current) | |
| current = current.parent | |
| path.append(current) | |
| return path[::-1] | |
| #Remove the item from the open set | |
| openset.remove(current) | |
| #Add it to the closed set | |
| closedset.add(current) | |
| #Loop through the node's children/siblings | |
| for node in children(current,grid): | |
| #If it is already in the closed set, skip it | |
| if node in closedset: | |
| continue | |
| #Otherwise if it is already in the open set | |
| if node in openset: | |
| #Check if we beat the G score | |
| new_g = current.G + current.move_cost(node) | |
| if node.G > new_g: | |
| #If so, update the node to have a new parent | |
| node.G = new_g | |
| node.parent = current | |
| else: | |
| #If it isn't in the open set, calculate the G and H score for the node | |
| node.G = current.G + current.move_cost(node) | |
| node.H = manhattan(node, goal) | |
| #Set the parent to our current item | |
| node.parent = current | |
| #Add it to the set | |
| openset.add(node) | |
| #Throw an exception if there is no path | |
| raise ValueError('No Path Found') | |
| def next_move(pacman,food,grid): | |
| #Convert all the points to instances of Node | |
| for x in xrange(len(grid)): | |
| for y in xrange(len(grid[x])): | |
| grid[x][y] = Node(grid[x][y],(x,y)) | |
| #Get the path | |
| path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid) | |
| #Output the path | |
| print len(path) - 1 | |
| for node in path: | |
| x, y = node.point | |
| print x, y | |
| pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ] | |
| food_x, food_y = [ int(i) for i in raw_input().strip().split() ] | |
| x,y = [ int(i) for i in raw_input().strip().split() ] | |
| grid = [] | |
| for i in xrange(0, x): | |
| grid.append(list(raw_input().strip())) | |
| next_move((pacman_x, pacman_y),(food_x, food_y), grid) |
In line 51, you are checking to see if there's a better path to reach the child node from tge current node. Just check the algorithm's Wikipedia page to understand.
In line 53 we are updating it. Node is just reference to data in memory, like C pointers. It is not a copy from the openset element, it is a reference to the element itself. Confusing, but yeah, it's python, it's implicit.
About your error.. don't know much without seeing the full code.
The reason of why I want to see your code is because you might have modified something, even if just a line or a variable, and it might have some impact over the full code. After all, as the old ones said: "In my PC at home the code works, not sure why on yours it doesn't".
Why the aStar function is calling four times in next_move function?
If you are referring to my version, not the author's one, the answer I should give you is: my bad. I can't remember what I was trying to do at the time, maybe I just clicked the ctrl+v shortcut a few times by mistake. I just can't see a reason for executing 4 times the same thing.
Getting error: TypeError: unhashable type: 'Node'
when trying to add start node to openset Set.
Any idea how to overcome this ?