Scribd
Upload
3 views1 page

A* Pathfinding Algorithm Explained

The document summarizes the A* search algorithm. It takes in a starting node and dictionary of nodes, and determines the best next step by comparing the distance between adjacent nodes to the starting node plus the remaining distance to the end node. It repeats this process of finding the lowest total distance node until it reaches the desired end node, outputting the path taken. Pseudocode provides more details on the algorithm's process.

Uploaded by

api-511394397
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views1 page

A* Pathfinding Algorithm Explained

The document summarizes the A* search algorithm. It takes in a starting node and dictionary of nodes, and determines the best next step by comparing the distance between adjacent nodes to the starting node plus the remaining distance to the end node. It repeats this process of finding the lowest total distance node until it reaches the desired end node, outputting the path taken. Pseudocode provides more details on the algorithm's process.

Uploaded by

api-511394397
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

1.

Background and Related Work


A* is a best-first search algorithm that works alongside a heuristic function to operate on
nodes in a graph or path. The nodes are defined by a method which takes in self, name of node,
and straight line heuristic as parameters. Our particular A* method uses parameters ‘start node’
and the dictionary of objects called ‘node’. The node data is stored in a list of tuples which are
assigned a key value and indexed into a python dictionary. A* determines which node is the
“best” next step by first taking the distance between the two nodes that would potentially be
traversed, and adding it to the remaining straight line distance between the end of the traversal
and the final node in the path. This distance cost is then compared to the distance costs produced
by other nodes in adjacency with the starting node. Adjacent node that results in least overall
distance cost becomes new current to be operated on. Rinse and repeat until the desired end node
is reached. Pseudocode is as follows:

DEF A* (nodes, starting node)


End node = node ‘Baruch’
Current node = starting node
Initialize list of previous nodes, begins as empty set
while adjacent nodes of current aren’t null:
if (current node = end node)
Terminate program
else
Initialize variable ‘initial’ as a large number
for node in ‘adjacent nodes’:
if node is not in previous nodes
if (straight line heuristic + weight of a certain node < initial )
Initial = straight line heuristic + weight of certain node
current node = certain node
Print straight line heuristic, weight

Previous node = current


Print current node
Print initial

You might also like