A* Algorithm implementation in python.

astar.py

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

There is name error for pacman_x how to solve it

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.

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.

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

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

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

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.

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:

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.

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.

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

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

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)

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 ?

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.