Instantly share code, notes, and snippets.

# Nicholas-Swift/astar.py

Last active May 12, 2024 18:34
Show Gist options
• Save Nicholas-Swift/003e1932ef2804bebef2710527008f44 to your computer and use it in GitHub Desktop.
A* pathfinding algorithm. Please see comments below for a fork of this gist that includes bug fixes!
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
 class Node(): """A node class for A* Pathfinding""" def __init__(self, parent=None, position=None): self.parent = parent self.position = position self.g = 0 self.h = 0 self.f = 0 def __eq__(self, other): return self.position == other.position def astar(maze, start, end): """Returns a list of tuples as a path from the given start to the given end in the given maze""" # Create start and end node start_node = Node(None, start) start_node.g = start_node.h = start_node.f = 0 end_node = Node(None, end) end_node.g = end_node.h = end_node.f = 0 # Initialize both open and closed list open_list = [] closed_list = [] # Add the start node open_list.append(start_node) # Loop until you find the end while len(open_list) > 0: # Get the current node current_node = open_list[0] current_index = 0 for index, item in enumerate(open_list): if item.f < current_node.f: current_node = item current_index = index # Pop current off open list, add to closed list open_list.pop(current_index) closed_list.append(current_node) # Found the goal if current_node == end_node: path = [] current = current_node while current is not None: path.append(current.position) current = current.parent return path[::-1] # Return reversed path # Generate children children = [] for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0), (-1, -1), (-1, 1), (1, -1), (1, 1)]: # Adjacent squares # Get node position node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1]) # Make sure within range if node_position[0] > (len(maze) - 1) or node_position[0] < 0 or node_position[1] > (len(maze[len(maze)-1]) -1) or node_position[1] < 0: continue # Make sure walkable terrain if maze[node_position[0]][node_position[1]] != 0: continue # Create new node new_node = Node(current_node, node_position) # Append children.append(new_node) # Loop through children for child in children: # Child is on the closed list for closed_child in closed_list: if child == closed_child: continue # Create the f, g, and h values child.g = current_node.g + 1 child.h = ((child.position[0] - end_node.position[0]) ** 2) + ((child.position[1] - end_node.position[1]) ** 2) child.f = child.g + child.h # Child is already in the open list for open_node in open_list: if child == open_node and child.g > open_node.g: continue # Add the child to the open list open_list.append(child) def main(): maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]] start = (0, 0) end = (7, 6) path = astar(maze, start, end) print(path) if __name__ == '__main__': main()

### BryceBeagle commented Sep 23, 2018

Lines 84 and 94 don't do what you think they should. They're going to continue only their innermost for loops, and not the surrounding one at line 79

### ryancollingwood commented Nov 15, 2018

Lines 84 and 94 don't do what you think they should. They're going to continue only their innermost for loops, and not the surrounding one at line 79

Cheers for this. Saved me a bunch of time debugging!

### allisonmcampbell commented Oct 23, 2019

Hey @ryancollingwood,

Where did you adjust the code? It looks identical to me.

#set the current position as blocked for future use
maze[current_node.position[0]][current_node.position[1]] = 1

at line 47 fixed the problem of getting stuck in a "trap" for me.

### allisonmcampbell commented Oct 23, 2019

Thanks @ryancollingwood !

Hi
just thinking how the line 81-84 and 91-94 works

` for closed_child in closed_list:`
` if child == closed_child:`
` continue`
this `continue` will just select another point from `for closed_child in closed_list:` rather than from line 79 `for child in children:`
so even tough the child already in close_list. it will bee add to open list
` for open_node in open_list:`
` if child == open_node and child.g > open_node.g:`
` continue`
and i think the code above is going to replace the old point in new h g f number? but seems the code didn't replace. just adding a new one.

anyway, i might be wrong.
with regards

### Thilac commented May 17, 2020

Hi @ Nicholas-Swift, can I please use your code with slight modifications in my assignment?

### Nicholas-Swift commented May 29, 2020

@Thilac, feel free to use this in any of your projects :). Please do note the bugs pointed out in earlier comments.

### JeremiasThun commented Jun 1, 2020

Why aren't you using a PriorityQueue to keep open_list organized? Wouldn't that be more efficient?

### ximecediaz commented Jun 5, 2020

I've tested this algorithm with another map. This algorithm works amazing and peculiar in my opinion. I'd tried to configure the possibility of move only in 4 ways: up, down, left, right; excluding the diagonal between those directions. The modification at the line 59:
`for new_position in [(0, -1), (0, 1), (-1, 0), (1, 0)]`.
Thanks for your works @Nicholas-Swift you help us a lot in our Artificial Intelligence project!

### shashwata27 commented Jun 17, 2020

how is the End node coming 1st in path=[] ?
because of that we need to use [::-1]

but I cant understand why is it getting 1st into the list,by dry running.

### AlpoGIT commented Oct 10, 2020

Hi, I tried
end = (9, 9)
with the following maze, and the algorithm seems to be stuck. I don't know why. But for example, when I change the 1 at (6,8) to 0, it works.

``````    maze = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 1, 1, 1, 0, 0, 1],
[0, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 0, 1, 1, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
``````

### rommelrmarquez commented Nov 8, 2020

Hi @Nicholas-Swift, thank you for this.
@AlpoGIT I tried updating this and it worked. You can check https://github.com/rommelrmarquez/pathfinding/blob/master/astar.py

### bismanugraha commented Dec 27, 2020

Hi @Nicholas-Swift, thank you for this.
@AlpoGIT I tried updating this and it worked. You can check https://github.com/rommelrmarquez/pathfinding/blob/master/astar.py

Hello, i tried your code and expand the maze, but the program seems stuck. How can I solve this problem?

### Hakej commented May 9, 2021

I've changed end to (1, 6) and the program is stuck.

### sourav-sharma7 commented Jan 23, 2022

Hi @ Nicholas-Swift, can I please use your code with some modifications in my a research project ? if u want i can also provide citation .

### jpvincent1980 commented May 10, 2022

Lines 84 and 94 don't do what you think they should. They're going to continue only their innermost for loops, and not the surrounding one at line 79

Shouldn't "continue" be replaced with "break" on both lines then ?

Here is a little change for the "stuck" problem on line 81.

``````            # Child is on the closed list
is_closed = False
for closed_child in closed_list:
if child == closed_child:
is_closed = True
if is_closed : continue
``````

This is taking way too many iterations. For example when start = (0, 0) and goal = (0, 19) in the following maze, number of iterations = 2465. The following implementation solved in 322 iterations. What could be the reason?

### dfour commented Nov 8, 2023

Hi,
you're checking to see if the child is in the open list in a for loop when you could just use "in" and then use the index which quite a bit faster

``````# Child is already in the open list
if child in open_list:
childIndex = open_list.index(child)
if child.g > open_list[childIndex].g:
continue
``````