Game Common A* Understanding and implementing the algorithm of path finding
Hello everyone
This is Lee Deukwoo of Game Algorithm
This lecture will be about A* understanding the path finding algorithm
along with ways to implement it
A*Pathfinding algorithm
something you must've heard at least once as a game developer
is a famous algorithm
It is used often in game development since it is popular
The lecture is structured into three categories
The first lecture will introduce A* Pathfinding algorithm
and explain the way it works
And the second lecture
explains the data structure to implement the A* pathfinding algorithm
Due to the algorithm proceeding
how the data inside the data structure changes
Taking a look at the procedure one at a time
The ways to implement A*algorithm
will be taught
Lastly, utilizing other data structure
to optimize A*algorithm
will be taught in the lecture
A* Understanding and Implementing Pathfinding Algorithm
A*Pathfinding algorithm is
something you must've heard at least once as a game developer
It is a famous algorithm
Since it is famous, it's used often in game development
However, this algorithm didn't start from game development
it was found through research on artificial intelligence of robots
About 55 years ago
In 1968, at Stanford University
There was a project called Shakey
that researched on autonomy control
The robot on the left is Shakey
As you can see from the picture, Shakey
mounted various sensors and personal mobility
Researchers wanted to let Shakey move on its own
so they researched on various functions
When they working on Shakey avoiding obstacles on its own
and getting to the destination
the A*algorithm was coined
The picture on the right shows that Shakey analyzes the area with grids
and processes the situation with the obstacle
Using the A*algorithm
As you can see from the starting point to the target point
it calculated ways to avoid the obstacle on its own
and found its way out
In fact, there were shortcut pathfinding
algorithms in the past
It's called Dijkstra algorithm
It was found 10 years ago compared to this one which is 1959
Compared to the Dijkstra algorithm, A* algorithm
could be considered as an extended version of it
First, to understand A*
I will briefly go over Dijkstra algorithm
In order to explain Dijkstra algorithm
I have brought a graph as an example
In the graph there is a vertex also called as node
which is an information about the important point
Connecting these points are paths called edges also known as links
the paths are set
The distance of each path has been calculated already
As you can see, the numbers are calculated for each path
and designated on the screen
The circles are called Nodes
and the lines are paths
Dijkstra algorithm
calculates the sum of every distance
calculating the path from starting point A to destination G
which is the minimum distance
For example, there are two paths for destination G
There's a path coming from E or F
The sum of minimum distance coming from E is 5
The sum of minimum distance coming from F is 5
They are both 5s
From F to G and E to G
comparing these two
From E which is situated on the right, to G
becomes E
This is 7 and this is 9
Therefore, the minimum path to get to G is
From E which has the path value of 7
We can conclude that it's the right node
Like so, every number of cases for the destination
and its path value is calculated
and finding the path with the minimum value
is the fundamental mechanism of Dijkstra algorithm
Dijkstra algorithm is accurate but
it has to calculate for every node
so if the structure of the graph becomes complicated
the memory and computational complexity will increase
A* algorithm has made improvements for this problem
The Stanford Research Institute which implemented the Shakey project
put a name on the A* algorithm so-called
A New Heuristic Search Method
In this case, 'Heuristic' means utilizing experiential knowledge
in order to receive a solution to the problem
A* algorithm is convenient
and can be used efficiently
So not only is it used in game development but
Also used efficiently in fields such as car navigation and natural language parsing
Through these mathematical expressions
A* algorithm can be simply summarized
The final value f(n) is a sum of
path value g(n) and heuristic vale h(n)
For the case of Dijkstra algorithm
there was only the path value g(n)
A* algorithm adds the heuristic value h(n)
which is the formula it uses
Then let's take a look at examples to
learn the mechanism of A* algorithm
I will use the same graph from the Dijkstra algorithm
but I will utilize the A* algorithm
in order to explain the path with minimum distance
First, to use A* algorithm
Ways to calculate heuristic values must be set
Generally, heuristic value
takes the minimum distance from the node to the destination
but using different functions depending on the situation is also an option
therefore, A* algorithm
copes with the situation in a flexible manner
For this example, we will use the minimum distance
As you can see over here
It calculates the minimum distance for each node unrelated to the path
The final value can be seen like so
The value of minimum distance from each node to the destination
will be saved to this node
It has already been calculated so, we're able to save it
The value of node B is 4, node C is 4.5
2 for D, 2 for E, and the heuristic value of F is 4
The values have all been saved
Just like the mathematical expression that I mentioned
The sum of path value and heuristic value for each node
which is the final value can be calculated
Based on this, I will proceed with the A* algorithm
The starting point A has two different paths
Path to B and path to C
I will calculate the value of these two cases
The path value from A to B is 1.5
The heuristic value of B is 4
which makes the final value from A to B as 5.5
Like so, the path value from A to C is 2
the heuristic value of C is 4.5
The final value from A to C will be 6.5
Then we need to find a smaller value from the two cases
in order to initiate
The smaller value is path B
Just because we chose path B with a final value of 5.5
that is smaller than 6.5
It doesn't mean that the value of 6.5 with path C is unnecessary
This value must be saved somewhere and memorized
From now on, we will search for a path to B
but if the measured value is bigger than 6.5
we must stop and come back to the beginning
Path B might not head to the destination
and could be misdirected
We will move on to the next step
In path B, the value of the next node D is
the path value is 1.5 + 1.5 = 3
the heuristic value of D is 2 which is added up to 5
this value is smaller than path C which was 6.5
we can proceed the inquiry
Let's move on to the next step
Continuing with path B, the value of the next node F is
1.5 + 1.5 + 2 which is added up to 5
The heuristic value is 4, which makes the total value 9
This value is bigger than the path value of C which was 6.5
This means we should stop the inquiry of path B
And let's hand this over to C
The inquiry begins on path C
The rules are same as before
If path C's value is bigger than the value of path C which is 9, we will stop the inquiry
and we will begin path finding in the final node of path B which is F
We should set this beforehand
The next node of path C is E, leading to 2+3
The path value is 2+3 which is 5
The heuristic value is 2 which makes the total value 7
This is smaller than 9 which was the previous value
We can proceed with the inquiry
Moving on, we will arrive at the destination
Arriving at the destination doesn't mean that it's over
The path value until the destination point needs to be added up
whether if it is the minimum value
needs to be checked first
Looking back at path C, which we have inquired
the calculation of the path value is 2+3+2
the total value is 7
This is smaller than the value previously calculated which was 9
Finally, the pathfinding node can be fixed
Then what are the differences between the 2 algorithms?
The advantages of A* algorithm compared to Dijkstra algorithm is
the calculation of the node from F to G
doesn't need to be done separately
Therefore, A* algorithm
decreases memory and computational complexity
and is an efficient pathfinding algorithm
It is useful for games that need real-time calculation
Next, I have prepared another practical example
Let's say a game is structured
with a grid map like so
The starting point is S and the target point is D
In between S and D there is a purple obstacle blocking them
Number of cases to get to target point D from starting point S
can be countless
So, using the A* algorithm
I'll try to only calculate points that are necessary
which is an efficient path finding
First, the starting point S has 8 number of cases
In the grid map, the straight line distance value is 1
The diagonal distance value will be set to 1.414
In the 8 different paths that are near the S
The minimum value will be on the right
The right node has path value 1 and
the heuristic value 3 to the destination
added into 4 in total
In the 8 number of cases
Let's check the second smallest value
The node diagonally across the upper right
will have the same value as the node diagonally across the lower right
First, the path value is 1.414
and the heuristic value is one diagonal line and two straight lines
which is 3.414
This adds up to a total value of 4.828
The upper right and lower right has an equal value
In this case of an even score
There needs to be a rule on what should come first
We will make a rule of choosing the lower side first
Let's move on to the next step
After choosing the right node
in order to expand the path
we need to search for every neighboring node once again
The right node is blocked by the obstacle and has nowhere to go
Then we should move up or down
We said that the bottom side goes first
Following the order of bottom priority
We will choose the bottom node and expand it
When proceeding with the bottom node
Instead of going through right to get to the bottom
Moving diagonally from the starting point will have a smaller value
Crossing right to get to the bottom
leads to a path value of 2
But moving diagonally has the value of 1.414
So we will chose the node on the lower right
but the node to chose when the path is blocked
will be kept in mind as well
The right upper node that had an even score
This upper node will be considered as next in order
The value of this node is equal
It has an even value of 4.828
Therefore, we will move to the lower right
but if the value is bigger than 4.828
starting over at the upper right
is the structure we will proceed the algorithm in
Let's move to the bottom
We moved to the bottom but it is still blocked
These 2 nodes are the only ones that can be inquired
So we need to move to the bottom once more
But when the value of the bottom node is calculated
it is added up to 6.242
But compared to the previous value
which was 4.828, it has increased
this means starting over at the node we remembered
and begin exploring from here
And the 6.242 node that was previously calculated
will be saved somewhere once again
Let's start over from the upper right node
These 3 nodes
can be newly added to the top
The upper right has the minimum value
it can be calculated into 5.656
2 diagonal path values and
the heuristic value is 2 diagonal lines
which is 5.656
This is smaller than the previous minimum value, 6.242
we can proceed the exploration
Let's move on
Exploring the next node
lets us bring 5 neighboring nodes
Out of these 5, the lower right
diagonally situated node has a minimum value
Calculating this node value
the path value has 3 diagonal lines
the heuristic value is 1 diagonal line
leading to an equal value of 5.656
This is still smaller than the previous value
which means the exploration could go on
Starting from this node and searching for its neighboring nodes
We can finally find the destination
Calculating the path value to the destination
it is 5.656 which is an equal value
This is the minimum value out of every number of cases
which means it can be fixed as a minimum distance
Like so, ways to use A* algorithm
to find the minimum distance from the starting point until the target point
efficiently, have been learned through out the lecture
To implement the A* algorithm
first, there needs to be two different containers to hold the data
One is Open Set and
the other is Closed Set
Like the meaning of 'set'
each container does not allow overlapping data
The open set on the left is
used to store the node that is used for path finding
The closed set on the right is
used to store nodes that are calculated
Inserting data into open set
and when the data calculation is finished
it is moved to the closed set
This is how the algorithm works
Then, as the algorithm continues
how the data of these 2 containers change
will be checked out step by step
First is the algorithm preparation step
We will use the same example
that we have used before
Only the starting node and target node is informed
2 containers both do not have data
In this condition, to initiate the algorithm
we will put the starting node into open set
Like the picture
the starting node will move into the open set
Then let's begin the algorithm
Out of the node in the open set
Call out a node with the minimum value
If the nodes in open set
have an equal value
We should designate a rule on what node to choose
Let's say the heuristic value h(n)
chooses the smaller node
and if the h(n) value is equal as well
The node that came in first, need to be a priority
This will be our rule
Next, which node should be put into the open set first
is another rule we should designate
Nodes situated on the lower side
will be put into the open set first
Take every neighboring node of the selected one into the open set
When the neighboring node is in the closed set
or if it is in the area where it can't move, it is excluded
Near the starting node, there are a total of eight nodes
calculate thee path value g(n) and heuristic value h(n)
The newly added parent node will be the starting node
It will be set as a starting node as previously decided
Now, as you can see in the open set
Starting node will be the parent
of the newly added 8 nodes
After wrapping up the process
Go back to Step2 and repeat the same process again
Get the node with the lowest value from the open set
This node will be node number 1
Like so, node number 1 will be
placed on the right
Compare node number 1 and the terminal node to see if they're equivalent
If they are different, they will be moved to closed set
This is the processed data structure
Then, go back to node number 1 and the neighboring node
to check and add
I mentioned before that nodes nearby are excluded
Therefore, out of the neighboring nodes of node number one
the new nodes on the right is completely blocked
and it is in the area where it cannot move
Theses are excluded from the list
And the starting node that is
already in the closed set must be excluded as well
Next, the highlighted parts on the screen
these nodes on the top and bottom need to be added
These nodes are already inside the open set
And their parents are the starting node
which is the S
In this case where the node is overlapped
Replace it into the node with a smaller final value f(n)
But these yellow nodes
If node number one is set as a parent
It doesn't head straight but instead adds a path value of 1
For this case, it's 1+1.414, right?
that's why the final value doesn't end up being better
So, these must be excluded too
Out of the neighboring node, none of them
could be added to the open set
Now let's go back to the starting node
and select a node with the minimum value in the open set
I will name this as node number 2
According to the rule that was mentioned previously
There's a priority to the bottom part
I will select the bottom node first
Same as before, if it's different after comparing to the terminal node
Node number 2 can be moved to the closed set
Moving on
Out of the neighboring nodes that have node number 2 as the parent
The node that satisfy what was explained before
which are these two nodes situated on the bottom
These can only be added to the open set, right?
The node with a starting node as a parent has a smaller value
and the node on the right is immovable
Now, only these two nodes are added in the open set
We have to select the node with a minimum value from the open set
Let's name this as node number 3
Then node number 3 is
the node on the upper right side
Same as before, it has to be compared to the terminal node
Since it is not a terminal node
It will be moved to the closed set
And the nearby node of node number three on the upper part
should be added into the open set
The node with the minimum value
will be the node on the upper right part
This will be node number 4
Node number 4 isn't a terminal node so, it goes into the closed set
And the neighboring node with node number 4
should be added into open set
Then the open set with S as the parent
Open set with number 2 as the parent
Nodes with number 3 as the parent
Nodes with number 4 as the parent
All of these will move into openset
Now the node with the minimum value has to be selected
By repeating this process
The node with the next small value
will be node number 5 on the lower right part
Adding node number 5
New nodes that have number 5 as the parent
should be added to the open set
I have searched for the node with a minimum value
and it has been selected as a terminal node
Then whether the terminal node is actually
the minimal value out of the nodes in the open set
has to be compared
I have selected from here
Out of the open set, the terminal node
has been selected as the node with a minimum value
Now the algorithm can be terminated
When the path finding ends
each nodes that have been used in the path needs to be returned
The parent of the terminal node is number 5
The parent of node number 5 is number 4
The parent of node number 4 is number 3
The parent of node number 3 is S
which is the starting node
We can put it into a sequence
and arranging it in reverse which is S, 3, 4, 5, D
This is how the minimum distance can be set
Until now the A* algorithm and
ways to implement it has been taught
Now we will begin
Implementing A* algorithm in a game engine
and ways to do it
For the coding practice, a Unity based
practice project has been prepared
open this project
In this Scenes folder
we will open Scenes that says AStarPathfinding
Then a screen like this will show
If you move to the script folder of this project
In order to implement A* algorithm
3 scripts, grid and node, path finding
3 scripts have been prepared
Out of these 3, let's take a look at Node.cs script
Double click and open up visual studio
A basic grid unit that is needed for the path finding
A scrip that defines node class
This node class declares a variable for walking
which is isWalkable
For the sequence information of location and grid
the variables have been set
If related information is delivered through the constructor
The constructor has been selected so they can be set
And hcost and gcost
They are used in implementing A* algorithm
gcost which applies to the path value
hcost which applies to heuristic value
These are the variables that have been set
The final calculation value that adds up these two
Property that calculates the final value f(n)
fcost has been declared in the class
Let's go back to Unity
The scene structure of Unity project will be explained
Arrange ground plane game object in the background
Extending the size of the plane by three times
I will set a map with a total size of 30*30
I will highlight the player through a capsule on the map
I have set the target beforehand, using a cube
And for empty game objects called Obstacles
Like so, the cube can be arranged as a child
These are the obstacles
The player cannot move
and it will become a obstacle game object
To find out if they are actually immovable
Looking at the upper right part
There is a layer called Unwalkable
which is set to the game objects
So later on when the map is analyzed
for areas that are covered by Unwalkable
the information that they are immovable is delivered
through this layer
Now the important game object is
The A* placed on the top part
A* game object has
Grid component and Pathfinding component
These two are arranged
The Grid component plays the role of
dividing the background with 1m unit grids
These designate the values
And one thing to add on this part
The layer name to detect immovable grid
which was Unwalkable, it was structured to be set here
Now let's take a look at
the code of the Grid component
Open up visual studio
We'll look over the configuration of the Grid component
First, in a Grid there is a 2D array of nodes
it is a variable called Grid
This 2D array of nodes, when starting
it uses a function called CreateGrid
to fill up the 2D array
The amount that they fill up is
Previously, we have set from the editor
X value and Y value of Number of Grids
and it analyzes the arrangement
calculating the size of the whole 2D array
Next, utilizing the size of the fixed node
Run the loop twice in the Grid
in order to calculate the complete node
This is a size of 30*30
A total of 900 Grids have been set
Running the horizontal and vertical loop
Add one in the Grid 2D array of node
use the function from the physics engine to see if the Grid
is an area where the player can walk through
In this Physics.CheckSphere
add the information of unwalkableMask to see
if the Grid and node
is an area where the player can walk through
or an area where the player can't walk
If the player isn't able to walk, the related information
needs to be inserted into the first argument to create a node object
and put it into the 2D array
Like so, if the Grid is completely created
the next important function is
A function to bring 8 neighboring nodes that are
nearby a specific node
It is the GetNeighBours function
Utilizing the GetNeighBours function
information of nearby nodes can be retrieved
Lastly, another important function is
A function called OnDrawGizmos
The Unity draws the current grids
When the path is found, the minimum distance
is drawn with a black coloring
Then let's come back to Unity
and execute the program
Press the play button
Switch to the scene view from the game view
When you check the scene view
You can see grids of scene view being displayed
The most important part that executes the logic of path finding
Let's look over the code of Pathfinding component
Currently, the pathfinding function isn't available
The current location of the player is marked with a black coloring
Let's reactivate the pathfinding logic
In realtime, from the starting point to the target point
We will try to mark the path finding on screen
Playing the role of path finding in this project
It is called Pathfinding component
In the pathfinding component
a function called FindPath is declared
So let's get to know this function called FindPath
In order to implement this, as I mentioned
Closed set and closed set
These two data structure needs to be arranged
From this code, in the open set
The List data structure is designated
The closed set selects HashSet
The reason why the List data structure of the open set is designated is
because it is easy to add the node
and to make it efficient for sequential searching
The reason why HashSet data structure was chosen from closed set is
because the node in the closed set that will be used
don't need sequential searching
but instead, only need to find the designated node quickly
Now the first node of open set
The starting node needs to be put
the actual algorithm is proceeded through a while loop
Looking at the condition of this while loop
It needs to continue until
there is a data of the open set
Then, since the starting node was already put in
It will proceed by the while node participating as well
Let's open the logic of the first area
Out of the open set
the node with a minimum value
needs to be selected in this logic
Take currentNode
which is the first element of the node
Run the loop so that the next element
will have a smaller fcost compared to the current element
check if the final value is small
If the final value is equal
the hcost selects a smaller element
and designates as a currentNode, which is a logic implemented
If the hcost is small
The node that was already selected has to be prioritized
For the node that was selected beforehand
When the neighboring node from the open set is added
the order is set
As you can see from the Grid
When we bring neighboring nodes
We have an order of going from bottom to top
and from left to right
If the fcost and the hcost is equal
the node on the bottom part will be prioritized
That's how you should understand it
Let's open up the next area
The next area is currentNode
If the minimum value
which is the currentNode is equal to the terminal node
the exploration can be executed
and a function called RetracePath can be invoked
This RetracePath function will be
explained further on later
Next, the third field
The third area has a logic of dislocating the currentNode from open set
and moving it into the closed set
This is simple so
We will move on to the next part
The fourth area has the logic of
bringing every neighboring nodes in currentNode
and putting it into the open set
When I previously explained it
I used the function of bringing neighboring nodes
to put it into the open set
The condition is that when the neighboring node is in closed set
or if it is immovable
The node has to be skipped and can't be put into open set
So if it has passed this condition
it can fit into the open set
and becoming a valid node
The algorithm value for this node has to be calculated
The value of gcost is the current node's gcost and
the neighboring node next to the current one
What we're currently calculating
the distance of the neighboring node all added up
leads to the path value gcost
and the heuristic, h value
The node we will now add to the open set
and the target node's minimum distance has to be calculated
the f value adds these two values together
When a neighboring node is made like so
There are two cases
One case which includes a node that is overlapped in the open set
and the second case which is a new node
For the case of an overlapped node in the open set
The gcost in the open set has to be replaced
Because the heuristic value of the node
does not change the location of the node
so maintain the heuristic value of the node
and alter the gcost
Then the parent information has to be replaced
If there is an equivalent node currently
the previous parent will be different from the current node
It will be different from currentNode
Alter the parent node to currentNode
If there isn't a node to add to the open set
Add new information of gcost, hcost, and the parent
and add it to the open set
Now I will explain the rest of the functions
Let's take a look at RetracePath which is activated when the path is found
This will be the last node
Continuously analyzing the final node and the current node
The code which finds the parent in reverse
is implemented
Like so, in the List data structure
The nodes which are related to pathfinding have all fit in
Use the Reverse function to flip it upside down
Then it is able to find every array of nodes
that are needed in minimum distance path finding
The last function to be explained is the GetDistance function
This GetDistance function calculates the distance
It calculates the number of diagonal or vertical arrangement
The diagonal arrangement is assigned with a weight of 14
and the straight line is assigned with a weight of 10
The function to calculate the total distance could be assigned like this
currentNode == targetNode
until the target point
or until every node from the open set
isn't left there
It has to be repeated on and on
The FindPath function is used to repeat it
Place it in the update query and uncomment
Now I will execute this again
Compile the altered code and press the execute button
If we take a look at the Unity result screen
The path is found as you can see
The nodes taking place in the path
can be seen marked with a black coloring
If the selected game object is moved
or if the target is moved
the minimum distance path could be found like so
The execution of path finding could be seen real time
and can be checked out
We have implemented the A* pathfinding algorithm
through the Unity engine
A* Pathfinding Algorithm Optimization
As the A* algorithm proceeds, in the open set
A function to search for the minimum value
A function to eliminate from the data structure
and a function to check the overlapped node
A function to add a new node
And a function to replace the overlapped node
into a new node
There five functions are often used
Out of theses 5 functions, the first
The logic to find the minimum value in the open set will be explained
In previous examples
to find the minimum value node in the open set
We had to explore every node from the open set
However as the pathfinding became complex
The size of the open set List had gotten bigger
The process to search every node
had to be overwhelming
When exploring every element
the complexity of the algorithm is called ON
As you can see from the picture
in the open set data structure
there are three items
In order to find the minimum value of 3
The node has to be explored 3 times
Therefore the search complexity of the algorithm
is called by the expression ON
But what if this could be searched at once?
This would mean the quality of the algorithm has increased
Out of the numerous item list
there is a data structure made to find the minimum value at once
Priority Queue is commonly used
Priority Queue is a data structure that implements reserve gear
It puts the minimum value in front of everything else
which is a unique trait
When we implement A* algorithm
we only have to earn the minimum value
Using Priority Queue
could develop the search quality
The search for the minimum value in a priority queue
could be executed at once
so it has a complexity of O1
From this picture, when the previously seen
data structure is replaced through a priority queue
The minimal element 3 will
always be situated in the front
it can be found through one search
Then let's take a look at
implementing A* algorithm using the priority queue
In order to do this, we have to make a priority queue ourselves
Priority queue is a data structure that
ensures minimal or maximal value as a superior element
In this case, we must use minimal value
As you can see from the word priority queue
it only has to guarantee the superior element
It is different from structures that
arrange every element in order
When implementing priority queue
normally, a structure called binary heap is likely to be used
Let's find out
Binary heap is divided into two branches
and it is in a tree structure
It is implemented from an array
It starts from number 0 index which is the root
and it branches out
If we put the previous examples into a binary heap
From node 3 which is the root, 3,15,8
branches out to left and right
consisting 15 and 8
It has the structure of
being lined up
In this binary heap structure, the location of the node
is usually set with fixed rules
When the binary heap structure is arranged as the picture
Let's say these data are lined up this way
each of them as a distinct index
from the array like so
The root index will have index number 0
Ad the child of the second root
will always have index number 1 and 2
The first child nodes as you can see
will have index number 3 and 4
the second child nodes are 10 and 27
In other words, they will have index number 5 and 6
If a random index is given
It is easy to find the parent index right away
which is a trait of the binary heap structure
The formula to find the parent index from a distinct index is
Child index ci-1
subtract 1 from the ci and divide it into 2
In this case, integer operation is necessary
If it is not divisible into ci
the decimal point will be eliminated
the index to eliminate it
will be the parent index
If the previous open set structure is implemented into a binary heap
Let's select a random element
If an element of 10 is chosen
10 will take index number 5
The parent of index number 5 will be
(5-1)/2 which is number 2
number 2 will be the second child index of the root
And in case of 8, it takes index number 2
The parent of 8 will be
(2-1)/2 which is 0.5
The decimal points have to be eliminated
so the parent index will be 0
This stands for the root index
Using the formula above, any index or
where the parent index is
can be found right away
In this binary heap structure
We will add an item at a time
to see how the data structure is created
For example, 6 data which are 23, 10, 8, 9, 3, 5
will be put into the binary heap structure
The first element, 23
will be the last and the root
It will go into index number 0
The array data will be like so
which results in 23 being put into index number 0
Next, it's time for 10
10 will be added into the last element as well
which means it will take index number 1
it doesn't end here
10 will be added into the last element
and we have to find the parent
If the number is smaller than the parent
It has to go through the process of replacing itself and the parent
which is an additional step
This is before the alteration
First, when the 10 is added in the last element
as you can see 23 and 10 is
lined up side by side
So the root node which has a value of 23 is compared with itself
but 10 is smaller
leading to an alteration between the two
When it is altered, the data of the array
will be replaced like so
10 goes into the root
and the 23 will be set as a child
Now, I will add 8 which is a third element
Put 8 in the last part
And before the replacement
I will take a look at the index of the parent
Parent of the 8 will be 2-1
and divided by 2 equals 0
We can tell that it is the root index
Comparing itself to the root index
8 is clearly smaller
It has to replace itself with the root index
and the 8 goes as a root
and 10 goes back to the original index of 8, number 2
The following arrangement is the array structure
Next, let's add 9
In the case of adding 9
It will be added in the last part making 3 as the index
the parent of 9 will be 23 from the index number 1
This is calculated by (3-1)/2
Then the 23 from index number 1
should be replaced, right?
since 9 is smaller
The data that is replaced
can be formed like so
It doesn't end here
Let's compare with the root index
(1-2)/2 which is the root index
let's take it
and compare it
9 is bigger than 8, so it should stop
Then, I will add 3
The index of 3 will be 4
The parent which has the index of 4 is
(4-2)/2 which equals 1
Comparing the numbers between 9 and 3
which obviously shows that 3 is smaller
9 and 3 has to be swapped
So the index of 3 is 1
and the index of 9 is 4
Let's not stop here
We should find the parent of 3
If we find out the parent of 3
we can tell that it is the root index
Comparing 3 and 8, 3 is smaller
which means a swap is necessary
So as a result of this replacement
it has showed how the data of array can be set
like the following setting on the screen
Lastly, I will add 5
The index of 5 will be 5
And the parent of 5 will be 10 which is index number 2
Of course, 5 is smaller than 10
so we can swap with the parent
We won't stoop here and
go back to the root to compare with it
5 is bigger than 3 which is a root
so we must stop
This is the case of binary heap
23, 10, 8, 9, 3, 5
when these six data are added to it in order
how the array of data will change
was checked out by us
Now this act of implementing priority queue
will be checked out in the Unity engine through a screen
and whether the result of simulation done by us
is an accurate act will be checked out as well
Move to the Scene folder from the example project that is prepared
Open a scene called PriorityQueueTest
Then select A* game object
and a script called PriorityQueueTest
will be attached to the component
If you press the execution button
The data structure list of the component
shows the simulations as we did in our heads
3, 8, 5, 23, 9, 10, these datas
are lined up in order
How these codes were made
will be looked through a script
If you see over here, create a priority queue data structure
following the order of this data structure
as we practiced with the example
the 23, 10, 8, 9, 3, 5
will be invoked through the Enqueue function in order
Let's see how this Enqueue function is consisted
The Enqueue function is in Priority Queue
The newest item will be at the end
the data will be added at last
Invoking the function called BubbleUp
The minimum value will be in front of everything else
This is how the logic was structured
As we saw previously, current ci Count
current Count that is in the last part
Calculate the index in the last element
until this index becomes a 0
In other words, it goes up until it becomes a root
It goes up, but in order to go up
the parent index needs to be calculated
The formula that was previously mentioned should be used
And the current child and parent data
should be compared, if the child is bigger
the pool should stop
and if it's smaller the parent and child should swap
The child index should be replaced with a parent index
Once again going back to the loop
This is how the logic is consisted
And as I mentioned
The code used to implement adding items in the priority queue data
was what we took a look at
Next, the superior root in binary heap
In other words, eliminating minimum value
Let's take a look at the process
Due to the structure of priority queue
If the value in the front is read
the item has to be eliminated right away
If it is taken out right away, the value at the top
needs to be maintained as the minimum value
I will explain how to implement this in a binary heap
In this current data, first
This is the root value of index number 0
Let's eliminate it
This gets rid of the root
leading to an invalid binary heap
Therefore, temporarily
Move the last element in the current array
which is 10 into the root
Then the data will change like so
This temporarily set root
allows reverse comparison with the child
and if it is bigger than the child, it can be set to go downwards
However, there are two child nodes
So, out of the left and right child nodes
the smaller one has to be compared
And the smaller child out of these two should be compared
making the smaller one go downwards
In the current data, the 8 on the left is
bigger than the 5 on the right
We can compare with the 5 on the right
So, the child on the right and the root should be compared
The root is smaller than the right
which means it should be swapped and headed downwards
Now, the data will be altered like so
The 10 that has headed downwards as a child
doesn't have a child to be compared to, so it should stop
Through this process
The root node will be set to a minimum value
The rule that binary tree had
can be kept well
The process to eliminate items
coming back to Unity and getting rid of root items on the top
We will execute functions and
check if the operation works
From the Unity code and the test of the script
The pq.Dequeue function which is commented out
We will uncomment the code and execute it
And the element in the front
Excluding the 3 in the front
It will make a priority queue once again
Taking a look while it is executing
The data of 5, 8, 20, 23, 9 are
being lined up in order
This is equivalent to the simulation result
that we had in our heads
Then let's see how this Dequeue function is
being implemented
In the case of Dequeue function, first
return the data of head
And relocate the last element to the top
Calculate the last index and
move it to the front
Then, at the top
Item placed on the top which was moved to the last item
It is being brought down by the SinkDown function
It is similar to the BubbleUp that was previously mentioned
It just brings it down
keeps on bringing it down
First, compare the child on the left and right
After bringing the child on the left and right
Compare these two and
when the index of left and right changes
In other words, if the value of the right index is smaller
Choose the right index as a target index
If the left index is smaller
Maintain the left index value and
compare it to the current parent index
If the child is smaller than the parent
It brings the parent down
This is the logic it has
Utilizing the list data structure
implementing open set and
using binary heap data structure to
implement openset
This is the comparison of algorithm complexity between the two
First, the node with a minimum value
For the function to search for it
the binary heap can bring it without a sequential search
Compared to the List, binary heap has a
faster search speed
However when executing elimination or insertion
and processes to substitute
It has to go through the tree structure between parent and child
which means processes of going up or downwards
The binary heap is slower in those cases
It doesn't mean extremely slow
The complexity of the algorithm
will decrease to a log which is an opposite of tree exponentiation
So this complexity of algorithm
is named as OlogN
Binary heap is considered slower than the List
And when finding out overlapping
Both has to go through numerous nodes
to find out
So the value for this case is equivalent
When implementing open set
the data structure that List and binary heap structure has
the advantages and disadvantages have been compared
This is strictly a theoretical comparison
Actual bench marking is necessary
to prove the quality
The differences between list and binary heap is
For list structure, the memory can be distributed
and binary heap is able to use fixed array
The cache effect that can't be identified from the algorithm
can be increased, which is a benefit
From the code that I have implemented
I did not use a fixed array
which is why the effect that binary heap has
doesn't show well
Therefore, for the optimization
theoretical points can't be the judge
A situation that could happen in real life needs to be prepared
and the quality should be proven through benchmarking
Until now we have used binary heap structure to
find out ways to optimize
A* algorithm
This is the end of today's lecture
I appreciate your participation
Thank you
Understanding and implementing the A* pathfinding algorithm A* pathfinding algorithm An algorithm that improves memory usage and search speed by utilizing heuristics in Dijkstra's algorithm
Heuristics: A method of finding answers using empirical knowledge Applications: Computer games, car navigation, natural language parsing How it works: f(n)=g(n)+h(n)
The setting of heuristic Generally, set as minimum distance to get to the destination Flexible responding is available in different situations through heuristic
How the A* algorithm works Selects the path with the lowest score by summing the distance and heuristic values Can reduce memory and computational costs Useful for games that require real-time computation
Implementation of A* algorithm two types of containers for open set and closed set
Open set controls nodes to calculate weight Closed set collects nodes that don't need calculation
Open set's activity to implement A*algorithm: Search for minimum value, elimination of minimum value, check for overlapping nodes, adding new nodes, replacement of overlapping nodes
Optimization of A*pathfinding algorithm Priority Queue container Priority Queue container places the minimum or maximum value in the front
So, the minimum value can be found at once The complexity of minimum value searching is 01 The structure is different from sorting in descending or ascending order
Implementation of priority queue It is implemented in binary heap in a tree structure consisting two branches Internal data of binary heap is consisted in arrays Rules of binary heap
The location of nodes in binary heap is always fixed The parent can only have two child nodes leading to rule setting Formula to find the index of a parent in a particular index pi=(ci-1)/2