-
-
Save Nicholas-Swift/003e1932ef2804bebef2710527008f44 to your computer and use it in GitHub Desktop.
| 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() |
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!
@ryancollingwood glad I could help
Hey @ryancollingwood,
Where did you adjust the code? It looks identical to me.
Adding
#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.
FYI, found your code via google search "a* algorithm"
Howdy @bearcub my gist is here: https://gist.github.com/ryancollingwood/32446307e976a11a1185a5394d6657bc
I've used it in my silly 2d game here: https://github.com/ryancollingwood/arcade-rabbit-herder/blob/master/pathfinding/astar.py
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
Hi @ Nicholas-Swift, can I please use your code with slight modifications in my assignment?
@Thilac, feel free to use this in any of your projects :). Please do note the bugs pointed out in earlier comments.
Why aren't you using a PriorityQueue to keep open_list organized? Wouldn't that be more efficient?
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!
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.
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]]
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
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?
I've changed end to (1, 6) and the program is stuck.
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 .
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?
maze and implementation link: https://www.analytics-link.com/post/2018/09/14/applying-the-a-path-finding-algorithm-in-python-part-1-2d-square-Grid
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
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