{{ message }}

Instantly share code, notes, and snippets.

# jamiees2/astar.py

Created May 7, 2013
A* Algorithm implementation in python.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 # 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)

### rickhenderson commented May 5, 2016

Mind if I play with this and see what I can do? I'm interested in trying it on OpenAI Gym. You should check out that project if you are interested.

### rickhenderson commented May 5, 2016

Dear God why would request input that way! 👎

### Domiii commented Oct 11, 2016

Thanks, this really helped my studies.

Manhattan distance is currently:
def manhattan(point,point2): return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])

Shouldn't it be like this?:
def manhattan(point,point2): return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[1])

Saw that this was uploaded quite a while ago but I'm commenting this anyway.

Sincerely, Oliver.

### raulvillora commented Nov 30, 2016

Hi everyone. I am a bit lost. What do you mean by '# Enter your code here. Read input from STDIN. Print output to STDOUT' ?

We don´t know how to run the code. Can anybody help us?

Thanks so much.

My understanding is that the grid that next_move takes is two nested lists, the higher level one being the blocks/nodes in X and each and every one of these X-blocks contains a list with Y blocks beneath it. Can someone confirm this or clarify?

### rimonece commented Mar 16, 2017

Hi everyone, can anyone please explain how to set up data in this algorithm code?

### Isha8 commented Aug 12, 2017

Hi, what does the astar method return? I don't see a return statement, so what exactly is stored in path and how?
Thanks.

### hemantgupta2442 commented Jan 15, 2018

It says invalid syntax for line 73
print len(path) - 1
Don't know how to solve that.

### jbarsce commented Feb 8, 2018

@hemantgupta2442

Try "print(len(path) - 1)", because it sounds like you are using python 3.

### Mehadisa18 commented May 16, 2018

How would you give input to this code

@Domiii 's code works better

### VultureInAtom05 commented Sep 21, 2018

Where is raw_input defined?

### sukeshrachapalli commented Mar 25, 2019

can anyone suggest input for the above code

### SanjeevKumarPandey commented Apr 15, 2019

@sukeshrachapalli Try fileinput or sys module: Example:

import fileinput

for line in fileinput.input():
pass

### AshwiniAhire15 commented Nov 7, 2019

There is name error for pacman_x how to solve it

### carlHR commented Mar 7, 2020

Ok, so for everyone struggling with the cmd line input, here is how it is done, after a few hours of staring at it:

From your cmd line, you must type something like this:

\$ python a_star.py
0 0
3 3
4 4
..%.
..%.
%...
....

What did I just do?

Simple:

1. I said that the player or the pacman is located at the (0, 0) coordinates.
2. The food (or destination) is located at the right bottom (3, 3) coordinates.
3. The grid has a size of (4x4) tiles.

The walkable path is basically a dot '.'
The walls are these characters '%'
(idk if this is a bug, but...) If you put another character, it is treated as a walkable path but with a cost of 1. Just take a look at the line 9.

To write the map, pass each row's tiles of the grid without spaces:

......
......
......
......

This is a (4x6) grid, for example, where: 4 = rows or lines, and 6 = cols or characters in each line.

That's it.

Also, if you have problems putting the food at one of the corners (right or bottom), try to overwrite the line 14 of the code with this:

for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:

This way you can put your food at (3,3) in a (4x4) grid without problems.
You can use 1-line code here. It's just not my style.

Also, if you block all the possible paths with walls, creating a result that you can't reach the destination, the code results in an error. But that's ok, bc it really raises an error exception at the line 64.

PS: I'm using python 2.7 to run this code. Didn't tried with 3.6.

Bye.

### carlHR commented Mar 7, 2020

Thanks, this really helped my studies.

Manhattan distance is currently:
def manhattan(point,point2): return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[0])

Shouldn't it be like this?:
def manhattan(point,point2): return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[1])

Saw that this was uploaded quite a while ago but I'm commenting this anyway.

Sincerely, Oliver.

Also, yes, don't forget to change that. According to this site, this guy is right: https://www.redblobgames.com/pathfinding/a-star/introduction.html

Just search for the keyword "Manhattan", and you will find the reference code.

Bye.

### anshika99 commented Nov 26, 2020

Can someone tell me what could be the STDIN ? If someone knows please reply

### carlHR commented Nov 26, 2020

Ok i see you dont know what the 1st line means.

Stdin means standard input. It is the file where you want to speak with the running app.

Stdout is the standard output, which is the file where the app is going to print data.

By default if you execute this code as it is (and follow this small tutorial above that i made a while ago) into your terminal, the program will start running at the lines 77.

As you can see these lines have the function raw_input, which when it is called the code gets stuck until you type data in the terminal (which is the stdin by default) and press enter to confirm.

For each time it calls raw_input() you must provide the data and press enter to confirm.

That's why i've written that comment above. It tells which kind of data you should write once the code starts running. It is confusing as there is no tutorial to this :D

### anshika99 commented Nov 26, 2020

I know wat stdin and stdout means 😅 , I was asking what input should be provided to run the program in the stdin part !

For the code above i.e. astar.py

### carlHR commented Nov 26, 2020

Oh ok.. sorry, i interpreted your question wrong.

So as i commented here:

\$ python a_star.py
0 0
3 3
4 4
..%.
..%.
%...
....

All that comes after python a_star.py is the data you must write to make the code work.

Type without the "":
"0 0" is the start cell. It is a position.
"3 3" is the goal. Also a position / coordinate
"4 4" means the grid size.

From now on the code will ask for the grid layout. Each line must be passed in the terminal, where you must provide the right quantity of lines and character per lines. Each char corresponds to a single cell inside the grid, which is basically a string.

"..%." says that at (0,0), (1,0), (3,0) there are floors, and at (2,0) there is a wall.
The same for each line.
Dots (.) are floors or walkable cells and (%) are walls which the player cannot walk througth it.

### anshika99 commented Nov 26, 2020

Ohk, well it is now showing invalid syntax on line 72

Ok, so, I tried to execute the code above (ctrl+c, ctrl+v), and boom. Error. But not at this line. It was at line 14:

Traceback (most recent call last):
File "a_star.py", line 85, in <module>
next_move((pacman_x, pacman_y),(food_x, food_y), grid)
File "a_star.py", line 71, in next_move
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
File "a_star.py", line 43, in aStar
for node in children(current,grid):
File "a_star.py", line 14, in children
links = [grid[d[0]][d[1]] for d in [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]]
IndexError: list index out of range

But why is that? Bc if you read this comment:

Ok, so for everyone struggling with the cmd line input, here is how it is done, after a few hours of staring at it:

From your cmd line, you must type something like this:

\$ python a_star.py
0 0
3 3
4 4
..%.
..%.
%...
....

What did I just do?

Simple:

1. I said that the player or the pacman is located at the (0, 0) coordinates.

2. The food (or destination) is located at the right bottom (3, 3) coordinates.

3. The grid has a size of (4x4) tiles.

The walkable path is basically a dot '.'
The walls are these characters '%'
(idk if this is a bug, but...) If you put another character, it is treated as a walkable path but with a cost of 1. Just take a look at the line 9.

To write the map, pass each row's tiles of the grid without spaces:

......
......
......
......

This is a (4x6) grid, for example, where: 4 = rows or lines, and 6 = cols or characters in each line.

That's it.

Also, if you have problems putting the food at one of the corners (right or bottom), try to overwrite the line 14 of the code with this:

for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:

This way you can put your food at (3,3) in a (4x4) grid without problems.
You can use 1-line code here. It's just not my style.

Also, if you block all the possible paths with walls, creating a result that you can't reach the destination, the code results in an error. But that's ok, bc it really raises an error exception at the line 64.

PS: I'm using python 2.7 to run this code. Didn't tried with 3.6.

Bye.

It says that if you put the food (goal) on the corners, such as (3,3), the code results in an error. So you have to overwrite that piece of code on line 14. Then it should work.

Now, about your error at line 72, it didn't happened here. Did you really freshly copy pasted the entire code? Did you overwrite the 4 spaces as tab characters? Sometimes this can be the cause for the error as python uses tabs to manage blocks of code.

There is a difference in doing this:

var = 1

and this

var = 1

Also, the cause might be the version of python you are using. I've tested this using python 2.7. Maybe if the version you are using is different, it may cause some trouble.

### anshika99 commented Nov 26, 2020

I've tried and tested everything on python 2.7, but it is still not executing..

Ok, can I see the error log and source code (literally the file you are using)?

Also, on which OS are you on? I'm on Linux. The reason I ask this is bc I'm trying to replicate the error so I can understand what is happening ok.

### anshika99 commented Nov 26, 2020

I'm on Windows . And below is the source code

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)]]
for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
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
#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
#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
#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)

Stdin: 0 0
3 3
4 4
..%.
..%.
%...
....

Error after executing the above code:
Traceback (most recent call last):
File "main.py", line 15, in
for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
NameError: name 'x' is not defined

### carlHR commented Nov 26, 2020

Ok.. so.. just to clarify bc this gave such a headache when I looked at it (no kidding). You do indent your code right?

### carlHR commented Nov 26, 2020

Which kind of program are you using to compile the code? Is it really native python from command line, or some kind of framework?

You see, (from the code you gave me), you define x and y at the line 12 like this:

x,y = point.point

The variable point is a tuple, holding data like (0,1). So this operation should just define x as 0, and y as 1.

Try to change this line to:

x = point.point[0]
y = point.point[1]

Maybe it's your compiler's fault this time, because it should be working.

Now, other than this, be careful about indentation. One single tab placed in the wrong line can basically break the code.

In case of trouble, here's the author's code (with a few modifications of my part). I tested it right now, and it is working (at least on my pc :D)

# Enter your code here. Read input from STDIN. Print output to STDOUT
class Node (object):
def __init__(self,value,point):
self.value = value
self.point = point
self.refresh()

def refresh(self):
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

# for d in [(max(0, x-1), y),(x,max(0, y - 1)),(x,min(len(grid[0])-1, y + 1)),(min(len(grid)-1, x+1),y)]:
for i in [x-1, x, x+1]:
for j in [y-1, y, y+1]:
if i != x or j != y:
if (i >= 0 and j >= 0 and i < len(grid) and j < len(grid[0])):

return ret

def manhattan(point,point2):
return abs(point.point[0] - point2.point[0]) + abs(point.point[1]-point2.point[1])

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
#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
#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
#return empty list, as there is not path leading to destination
return []
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)
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
path = aStar(grid[pacman[0]][pacman[1]],grid[food[0]][food[1]],grid)
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)

### anshika99 commented Nov 26, 2020

Damn! Now this was srsly a headache and after so much efforts (yours obviously) it did worked !! Thank you so much 🤝

@anshika99 @carlHR Isn't Line 51 a bug? if node.G > new_g:
Here, node is an element from children.
Now, in line 53: node.G = new_g when you update the G value, it is updating the G value of an element of children, not of the desired element in openset
The aim was to update the G value of node in openset, in case the node was already present in the openset. For this update process, we should get to point the element in openset. But this is not happening. For all getting the output, this is because your example didn't hit such case where an update was needed.

Moreover, you cannot update any element of a set. (referring to openset)

Getting error: TypeError: unhashable type: 'Node'
when trying to add start node to openset Set.
Any idea how to overcome this ?

### carlHR commented Mar 19, 2021

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.

### carlHR commented Mar 19, 2021

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".

### Miltonbhowmick commented Sep 8, 2021

Why the aStar function is calling four times in next_move function?