You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Node:
"""
A node class for A* Pathfinding
parent is parent of the current Node
position is current position of the Node in the maze1
g is cost from start to current Node
h is heuristic based estimated cost for current Node to end Node
f is total cost of present node i.e. : f = g + h
"""
#This function return the path of the search
def return_path(current_node,maze1):
path = []
no_rows, no_columns = np.shape(maze1)
# here we create the initialized result maze1 with -1 in every position
result = [[-1 for i in range(no_columns)] for j in range(no_rows)]
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
# Return reversed path as we need to show from start to end path
path = path[::-1]
start_value = 0
# we update the path of start to end found by A-star serch with every step incremented by 1
for i in range(len(path)):
result[path[i][0]][path[i][1]] = start_value
start_value += 1
return result
def search(maze1, cost, start, end):
"""
Returns a list of tuples as a path from the given start to the given end in the given maze1
:param maze1:
:param cost
:param start:
:param end:
:return:
"""
# Create start and end node with initized values for g, h and f
start_node = Node(None, tuple(start))
start_node.g = start_node.h = start_node.f = 0
end_node = Node(None, tuple(end))
end_node.g = end_node.h = end_node.f = 0
# Initialize both yet_to_visit and visited list
# in this list we will put all node that are yet_to_visit for exploration.
# From here we will find the lowest cost node to expand next
yet_to_visit_list = []
# in this list we will put all node those already explored so that we don't explore it again
visited_list = []
# Add the start node
yet_to_visit_list.append(start_node)
# Adding a stop condition. This is to avoid any infinite loop and stop
# execution after some reasonable number of steps
outer_iterations = 0
max_iterations = (len(maze1) // 2) ** 10
# what squares do we search . serarch movement is left-right-top-bottom
#(4 movements) from every positon
move = [[-1, 0 ], # go up
[ 0, -1], # go left
[ 1, 0 ], # go down
[ 0, 1 ]] # go right
"""
1) We first get the current node by comparing all f cost and selecting the lowest cost node for further expansion
2) Check max iteration reached or not . Set a message and stop execution
3) Remove the selected node from yet_to_visit list and add this node to visited list
4) Perofmr Goal test and return the path else perform below steps
5) For selected node find out all children (use move to find children)
a) get the current postion for the selected node (this becomes parent node for the children)
b) check if a valid position exist (boundary will make few nodes invalid)
c) if any node is a wall then ignore that
d) add to valid children node list for the selected parent
For all the children node
a) if child in visited list then ignore it and try next node
b) calculate child node g, h and f values
c) if child in yet_to_visit list then ignore it
d) else move the child to yet_to_visit list
"""
#find maze1 has got how many rows and columns
no_rows, no_columns = np.shape(maze1)
# Loop until you find the end
while len(yet_to_visit_list) > 0:
# Every time any node is referred from yet_to_visit list, counter of limit operation incremented
outer_iterations += 1
# Get the current node
current_node = yet_to_visit_list[0]
current_index = 0
for index, item in enumerate(yet_to_visit_list):
if item.f < current_node.f:
current_node = item
current_index = index
# if we hit this point return the path such as it may be no solution or
# computation cost is too high
if outer_iterations > max_iterations:
print ("giving up on pathfinding too many iterations")
return return_path(current_node,maze1)
# Pop current node out off yet_to_visit list, add to visited list
yet_to_visit_list.pop(current_index)
visited_list.append(current_node)
# test if goal is reached or not, if yes then return the path
if current_node == end_node:
return return_path(current_node,maze1)
# Generate children from all adjacent squares
children = []
for new_position in move:
# Get node position
node_position = (current_node.position[0] + new_position[0], current_node.position[1] + new_position[1])
# Make sure within range (check if within maze1 boundary)
if (node_position[0] > (no_rows - 1) or
node_position[0] < 0 or
node_position[1] > (no_columns -1) or
node_position[1] < 0):
continue
# Make sure walkable terrain
if maze1[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 visited list (search entire visited list)
if len([visited_child for visited_child in visited_list if visited_child == child]) > 0:
continue
# Create the f, g, and h values
child.g = current_node.g + cost
## Heuristic costs calculated here, this is using eucledian distance
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 yet_to_visit list and g cost is already lower
if len([i for i in yet_to_visit_list if child == i and child.g > i.g]) > 0:
continue
# Add the child to the yet_to_visit list
yet_to_visit_list.append(child)
import numpy as np
class Node:
"""
A node class for A* Pathfinding
parent is parent of the current Node
position is current position of the Node in the maze1
g is cost from start to current Node
h is heuristic based estimated cost for current Node to end Node
f is total cost of present node i.e. : f = g + h
"""
#This function return the path of the search
def return_path(current_node,maze1):
path = []
no_rows, no_columns = np.shape(maze1)
# here we create the initialized result maze1 with -1 in every position
result = [[-1 for i in range(no_columns)] for j in range(no_rows)]
current = current_node
while current is not None:
path.append(current.position)
current = current.parent
# Return reversed path as we need to show from start to end path
path = path[::-1]
start_value = 0
# we update the path of start to end found by A-star serch with every step incremented by 1
for i in range(len(path)):
result[path[i][0]][path[i][1]] = start_value
start_value += 1
return result
def search(maze1, cost, start, end):
"""
Returns a list of tuples as a path from the given start to the given end in the given maze1
:param maze1:
:param cost
:param start:
:param end:
:return:
"""
if name == 'main':
The text was updated successfully, but these errors were encountered: