Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A* Algorithm implementation in python.
# 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
Copy link

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.

Loading

@rickhenderson
Copy link

rickhenderson commented May 5, 2016

Dear God why would request input that way! 👎

Loading

@Domiii
Copy link

Domiii commented Oct 11, 2016

Loading

@OliverEdholm
Copy link

OliverEdholm commented Nov 26, 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.

Loading

@raulvillora
Copy link

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.

Loading

@ZinoKader
Copy link

ZinoKader commented Dec 2, 2016

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?

Loading

@rimonece
Copy link

rimonece commented Mar 16, 2017

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

Loading

@Isha8
Copy link

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.

Loading

@hemantgupta2442
Copy link

hemantgupta2442 commented Jan 15, 2018

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

Loading

@jbarsce
Copy link

jbarsce commented Feb 8, 2018

@hemantgupta2442

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

Loading

@Mehadisa18
Copy link

Mehadisa18 commented May 16, 2018

How would you give input to this code

Loading

@FranchuFranchu
Copy link

FranchuFranchu commented May 22, 2018

@Domiii 's code works better

Loading

@VultureInAtom05
Copy link

VultureInAtom05 commented Sep 21, 2018

Where is raw_input defined?

Loading

@sukeshrachapalli
Copy link

sukeshrachapalli commented Mar 25, 2019

can anyone suggest input for the above code

Loading

@SanjeevKumarPandey
Copy link

SanjeevKumarPandey commented Apr 15, 2019

@sukeshrachapalli Try fileinput or sys module: Example:

import fileinput

for line in fileinput.input():
    pass

Loading

@AshwiniAhire15
Copy link

AshwiniAhire15 commented Nov 7, 2019

There is name error for pacman_x how to solve it

Loading

@carlHR
Copy link

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:

links = []
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)]:
    links.append(grid[d[0]][d[1]])

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.

Loading

@carlHR
Copy link

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.

Loading

@anshika99
Copy link

anshika99 commented Nov 26, 2020

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

Loading

@carlHR
Copy link

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

Loading

@anshika99
Copy link

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 !

Loading

@anshika99
Copy link

anshika99 commented Nov 26, 2020

For the code above i.e. astar.py

Loading

@carlHR
Copy link

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.

Loading

@anshika99
Copy link

anshika99 commented Nov 26, 2020

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

Loading

@carlHR
Copy link

carlHR commented Nov 26, 2020

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:

links = []
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)]:
    links.append(grid[d[0]][d[1]])

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.

Loading

@anshika99
Copy link

anshika99 commented Nov 26, 2020

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

Loading

@carlHR
Copy link

carlHR commented Nov 26, 2020

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.

Loading

@anshika99
Copy link

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)]]
links = []
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)]:
links.append(grid[d[0]][d[1]])
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)

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

Loading

@carlHR
Copy link

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?

Loading

@carlHR
Copy link

carlHR commented Nov 26, 2020

About this error log, (which is not a syntax error anymore), x is not defined. Ok.

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

	links = []
	# 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])):
					links.append(grid[i][j])

	ret = [link for link in links if (link.value != '%')]

	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
	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)
	#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)

Loading

@anshika99
Copy link

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 🤝

Loading

Copy link

ghost commented Mar 18, 2021

@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)

Loading

Copy link

ghost commented Mar 18, 2021

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

Loading

@carlHR
Copy link

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.

About your error.. don't know much without seeing the full code.

Loading

@carlHR
Copy link

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

Loading

@Miltonbhowmick
Copy link

Miltonbhowmick commented Sep 8, 2021

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

Loading

@carlHR
Copy link

carlHR commented Sep 8, 2021

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.

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment