-
-
Save ximecediaz/c2178cf3ac36e2b84ddf9a1855def1eb 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)]: # 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 = [[1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]] | |
map2 = [[1,1,1,1,1,1,1,1,1,308,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], | |
[37,1,41,1,45,1,49,1,53,1,57,1,61,1,65,1,69,1,73,1,77,1,81,1,85,1,89,1,93,1,97,1,101,1,105,1,109,1,113,1,117,1,121,1,125,1,128,1,131,1,133,1,135,1,137,1], | |
[0,264,0,265,0,266,0,267,0,268,0,269,0,270,0,271,0,272,0,273,0,274,0,275,0,276,0,277,0,278,0,279,0,280,0,281,0,282,0,283,0,284,0,285,0,286,0,287,0,288,0,289,0,290,0,291], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,1,72,1,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,1,120,1,124,1,127,1,130,1,132,1,134,1,136,1], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,294,0,295,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,306,0,307,124,1,127,1,130,1,132,1,134,1,136,1], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,1,1,1,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,1,1,1,124,1,127,1,130,1,132,1,134,1,136,1], | |
[0,171,0,172,0,173,0,174,0,175,0,176,0,177,0,178,0,179,179,179,0,180,0,181,0,182,0,183,0,184,0,185,0,186,0,187,0,188,0,189,0,190,190,190,0,191,0,192,0,193,0,194,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,1,1,1,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,1,1,1,123,1,126,1,129,1,1,1,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,292,0,293,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,304,1,305,123,1,126,1,129,1,1,1,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,1,71,1,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,1,119,1,123,1,126,1,129,1,1,1,1,1,1,1], | |
[0,203,0,204,0,205,0,206,0,207,0,208,0,209,0,210,0,211,0,212,0,213,0,214,0,215,0,216,0,217,0,218,0,219,0,220,0,221,0,222,0,223,0,224,0,225,0,1,0,1,0,1,0,1,0,1], | |
[34,1,38,1,42,1,46,1,50,1,54,1,58,1,62,1,66,1,70,1,74,1,78,1,82,1,86,1,90,1,94,1,98,1,102,1,106,1,110,1,114,1,118,1,1,1,1,1,1,1,1,1,1,1,1,1], | |
[0,234,0,235,0,236,0,237,0,238,0,239,0,240,0,241,0,242,0,243,0,244,0,245,0,246,0,247,0,248,0,249,0,250,0,251,0,252,0,253,0,254,0,1,1,1,1,1,1,1,1,1,1,1,1,1]] | |
map3 = maze | |
start = (1, 0) | |
end = (10, 49) | |
path = astar(maze, start, end) | |
for x,y in path: | |
map3[x][y]= maze[x][y] | |
print(map3) | |
if __name__ == '__main__': | |
main() |
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)]: # 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 names(path, map): | |
# The xlsx archive containing the security info is imported | |
import xlrd | |
loc = ("SLP.xlsx") | |
# The workbook is open | |
wb = xlrd.open_workbook(loc) | |
sheet = wb.sheet_by_index(0) | |
# For each of the nodes in the route, the name of the square is printed | |
for x,y in path: | |
# If the node value is 0, the value is ommited | |
if map[x][y] == 0: | |
continue | |
# The name is recovered from the xlsx archive | |
print(sheet.cell_value(map[x][y], 1)) | |
def security(path, map): | |
# The xlsx archive containing the security info is imported | |
import xlrd | |
loc = ("SLP.xlsx") | |
# The workbook is open | |
wb = xlrd.open_workbook(loc) | |
sheet = wb.sheet_by_index(0) | |
# For each of the nodes in the route, we sum the security score to the total score | |
total = 0 | |
nodes = 0 | |
for x,y in path: | |
# If the node value is 0, the value is ommited | |
if map[x][y] == 0: | |
continue | |
# The security paramether is recovered from the xlsx archive | |
total += sheet.cell_value(map[x][y], 5) | |
# A node has been counted | |
nodes += 1 | |
# We get the mean for all the nodes considered | |
total /= nodes | |
# The path's security score is returned | |
return(total) | |
def main(): | |
maze = [[1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1], | |
[0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]] | |
map2 = [[1,1,1,1,1,1,1,1,1,308,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], | |
[37,1,41,1,45,1,49,1,53,1,57,1,61,1,65,1,69,1,73,1,77,1,81,1,85,1,89,1,93,1,97,1,101,1,105,1,109,1,113,1,117,1,121,1,125,1,128,1,131,1,133,1,135,1,137,1], | |
[0,264,0,265,0,266,0,267,0,268,0,269,0,270,0,271,0,272,0,273,0,274,0,275,0,276,0,277,0,278,0,279,0,280,0,281,0,282,0,283,0,284,0,285,0,286,0,287,0,288,0,289,0,290,0,291], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,1,72,1,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,1,120,1,124,1,127,1,130,1,132,1,134,1,136,1], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,294,0,295,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,306,0,307,124,1,127,1,130,1,132,1,134,1,136,1], | |
[36,1,40,1,44,1,48,1,52,1,56,1,60,1,64,1,68,1,1,1,76,1,80,1,84,1,88,1,92,1,96,1,100,1,104,1,108,1,112,1,116,1,1,1,124,1,127,1,130,1,132,1,134,1,136,1], | |
[0,171,0,172,0,173,0,174,0,175,0,176,0,177,0,178,0,179,179,179,0,180,0,181,0,182,0,183,0,184,0,185,0,186,0,187,0,188,0,189,0,190,190,190,0,191,0,192,0,193,0,194,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,1,1,1,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,1,1,1,123,1,126,1,129,1,1,1,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,292,0,293,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,304,1,305,123,1,126,1,129,1,1,1,1,1,1,1], | |
[35,1,39,1,43,1,47,1,51,1,55,1,59,1,63,1,67,1,71,1,75,1,79,1,83,1,87,1,91,1,95,1,99,1,103,1,107,1,111,1,115,1,119,1,123,1,126,1,129,1,1,1,1,1,1,1], | |
[0,203,0,204,0,205,0,206,0,207,0,208,0,209,0,210,0,211,0,212,0,213,0,214,0,215,0,216,0,217,0,218,0,219,0,220,0,221,0,222,0,223,0,224,0,225,0,1,0,1,0,1,0,1,0,1], | |
[34,1,38,1,42,1,46,1,50,1,54,1,58,1,62,1,66,1,70,1,74,1,78,1,82,1,86,1,90,1,94,1,98,1,102,1,106,1,110,1,114,1,118,1,1,1,1,1,1,1,1,1,1,1,1,1], | |
[0,234,0,235,0,236,0,237,0,238,0,239,0,240,0,241,0,242,0,243,0,244,0,245,0,246,0,247,0,248,0,249,0,250,0,251,0,252,0,253,0,254,0,1,1,1,1,1,1,1,1,1,1,1,1,1]] | |
map3 = maze | |
start = (1, 0) | |
end = (10, 45) | |
path = astar(maze, start, end) | |
for x,y in path: | |
map3[x][y]= map2[x][y] | |
print("Ruta") | |
print('\n'.join([''.join(['{:4}'.format(item) for item in row]) | |
for row in map3])) | |
print("Nodos visitados") | |
names(path, map2) | |
print("Puntuacion de Seguridad") | |
print(security(path, map2)) | |
if __name__ == '__main__': | |
main() |
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
{ | |
"CurrentProjectSetting": null | |
} |
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
{ | |
"python.pythonPath": "D:\\Users\\ximec\\AppData\\Local\\Programs\\python.exe" | |
} |
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
{ | |
"ExpandedNodes": [ | |
"" | |
], | |
"PreviewInSolutionExplorer": false | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment