WEBVTT

1
00:00:06.218 --> 00:00:09.802
Game Common
A* Understanding and implementing the algorithm of path finding

2
00:00:27.497 --> 00:00:29.013
Hello everyone

3
00:00:29.013 --> 00:00:31.344
This is Lee Deukwoo of Game Algorithm

4
00:00:31.344 --> 00:00:35.505
This lecture will be about 
A* understanding the path finding algorithm

5
00:00:35.505 --> 00:00:37.918
along with ways to implement it

6
00:00:37.918 --> 00:00:40.174
A*Pathfinding algorithm

7
00:00:40.174 --> 00:00:43.756
something you must've heard 
at least once as a game developer

8
00:00:43.756 --> 00:00:45.789
is a famous algorithm

9
00:00:45.789 --> 00:00:50.209
It is used often in game development since it is popular

10
00:00:50.209 --> 00:00:52.697
The lecture is structured into three categories

11
00:00:52.697 --> 00:00:56.769
The first lecture will introduce A* Pathfinding algorithm

12
00:00:56.769 --> 00:00:59.643
and explain the way it works

13
00:00:59.643 --> 00:01:01.058
And the second lecture

14
00:01:01.058 --> 00:01:05.529
explains the data structure to 
implement the A* pathfinding algorithm

15
00:01:05.529 --> 00:01:07.561
Due to the algorithm proceeding

16
00:01:07.561 --> 00:01:10.861
how the data inside the data structure changes

17
00:01:10.861 --> 00:01:13.600
Taking a look at the procedure one at a time

18
00:01:13.600 --> 00:01:16.209
The ways to implement A*algorithm

19
00:01:16.209 --> 00:01:18.242
will be taught

20
00:01:18.242 --> 00:01:20.997
Lastly, utilizing other data structure

21
00:01:20.997 --> 00:01:24.108
to optimize A*algorithm

22
00:01:24.108 --> 00:01:25.295
will be taught in the lecture

23
00:01:26.103 --> 00:01:30.885
A* Understanding and Implementing Pathfinding Algorithm

24
00:01:30.885 --> 00:01:32.800
A*Pathfinding algorithm is

25
00:01:32.800 --> 00:01:36.202
something you must've heard 
at least once as a game developer

26
00:01:36.202 --> 00:01:38.127
It is a famous algorithm

27
00:01:38.127 --> 00:01:43.012
Since it is famous, it's used often in game development

28
00:01:43.012 --> 00:01:46.417
However, this algorithm didn't start from game development

29
00:01:46.417 --> 00:01:50.206
it was found through research on artificial intelligence of robots

30
00:01:50.206 --> 00:01:53.194
About 55 years ago

31
00:01:53.194 --> 00:01:56.870
In 1968, at Stanford University

32
00:01:56.870 --> 00:02:00.231
There was a project called Shakey

33
00:02:00.231 --> 00:02:02.503
that researched on autonomy control

34
00:02:02.503 --> 00:02:08.608
The robot on the left is Shakey

35
00:02:08.608 --> 00:02:11.100
As you can see from the picture, Shakey

36
00:02:11.100 --> 00:02:16.345
mounted various sensors and personal mobility

37
00:02:16.345 --> 00:02:19.050
Researchers wanted to let Shakey move on its own

38
00:02:19.050 --> 00:02:21.316
so they researched on various functions

39
00:02:21.316 --> 00:02:25.511
When they working on Shakey avoiding obstacles on its own

40
00:02:25.511 --> 00:02:28.290
and getting to the destination

41
00:02:28.290 --> 00:02:31.255
the A*algorithm was coined

42
00:02:31.255 --> 00:02:35.897
The picture on the right shows that 
Shakey analyzes the area with grids

43
00:02:35.897 --> 00:02:38.525
and processes the situation with the obstacle

44
00:02:38.525 --> 00:02:40.902
Using the A*algorithm

45
00:02:40.902 --> 00:02:44.318
As you can see from the starting point to the target point

46
00:02:44.318 --> 00:02:48.112
it calculated ways to avoid the obstacle on its own

47
00:02:48.112 --> 00:02:51.275
and found its way out

48
00:02:51.275 --> 00:02:54.974
In fact, there were shortcut pathfinding

49
00:02:54.974 --> 00:02:56.684
algorithms in the past

50
00:02:56.684 --> 00:02:58.917
It's called Dijkstra algorithm

51
00:02:58.917 --> 00:03:04.592
It was found 10 years ago 
compared to this one which is 1959

52
00:03:04.592 --> 00:03:07.578
Compared to the Dijkstra algorithm, A* algorithm

53
00:03:07.578 --> 00:03:10.302
could be considered as an extended version of it

54
00:03:10.302 --> 00:03:12.339
First, to understand A*

55
00:03:12.339 --> 00:03:16.374
I will briefly go over Dijkstra algorithm

56
00:03:16.374 --> 00:03:19.074
In order to explain Dijkstra algorithm

57
00:03:19.074 --> 00:03:21.602
I have brought a graph as an example

58
00:03:21.602 --> 00:03:26.178
In the graph there is a vertex also called as node

59
00:03:26.178 --> 00:03:30.493
which is an information about the important point

60
00:03:30.493 --> 00:03:34.029
Connecting these points are paths 
called edges also known as links

61
00:03:34.029 --> 00:03:36.895
the paths are set

62
00:03:36.895 --> 00:03:40.958
The distance of each path has been calculated already

63
00:03:40.958 --> 00:03:45.606
As you can see, the numbers are calculated for each path

64
00:03:45.606 --> 00:03:47.805
and designated on the screen

65
00:03:47.805 --> 00:03:51.409
The circles are called Nodes

66
00:03:51.409 --> 00:03:54.335
and the lines are paths

67
00:03:54.335 --> 00:03:55.823
Dijkstra algorithm

68
00:03:55.823 --> 00:03:59.035
calculates the sum of every distance

69
00:03:59.035 --> 00:04:03.089
calculating the path from starting point A to destination G

70
00:04:03.089 --> 00:04:05.968
which is the minimum distance

71
00:04:05.968 --> 00:04:09.789
For example, there are two paths for destination G

72
00:04:09.789 --> 00:04:13.759
There's a path coming from E or F

73
00:04:13.759 --> 00:04:19.799
The sum of minimum distance coming from E is 5

74
00:04:19.799 --> 00:04:24.304
The sum of minimum distance coming from F is 5

75
00:04:24.304 --> 00:04:25.905
They are both 5s

76
00:04:25.905 --> 00:04:29.281
From F to G and E to G

77
00:04:29.281 --> 00:04:31.076
comparing these two

78
00:04:31.076 --> 00:04:34.175
From E which is situated on the right, to G

79
00:04:34.175 --> 00:04:35.802
becomes E

80
00:04:35.802 --> 00:04:38.738
This is 7 and this is 9

81
00:04:38.738 --> 00:04:41.906
Therefore, the minimum path to get to G is

82
00:04:41.906 --> 00:04:46.950
From E which has the path value of 7

83
00:04:46.950 --> 00:04:52.027
We can conclude that it's the right node

84
00:04:52.027 --> 00:04:56.125
Like so, every number of cases for the destination

85
00:04:56.125 --> 00:04:58.096
and its path value is calculated

86
00:04:58.096 --> 00:05:02.194
and finding the path with the minimum value

87
00:05:02.194 --> 00:05:07.429
is the fundamental mechanism of Dijkstra algorithm

88
00:05:07.429 --> 00:05:09.520
Dijkstra algorithm is accurate but

89
00:05:09.520 --> 00:05:12.551
it has to calculate for every node

90
00:05:12.551 --> 00:05:14.359
so if the structure of the graph becomes complicated

91
00:05:14.359 --> 00:05:17.891
the memory and computational complexity will increase

92
00:05:17.891 --> 00:05:21.799
A* algorithm has made improvements for this problem

93
00:05:21.799 --> 00:05:24.888
The Stanford Research Institute 
which implemented the Shakey project

94
00:05:24.888 --> 00:05:30.011
put a name on the A* algorithm so-called

95
00:05:30.011 --> 00:05:32.472
A New Heuristic Search Method

96
00:05:32.472 --> 00:05:35.776
In this case, 'Heuristic' means 
utilizing experiential knowledge

97
00:05:35.776 --> 00:05:37.868
in order to receive a solution to the problem

98
00:05:40.710 --> 00:05:42.735
A* algorithm is convenient

99
00:05:42.735 --> 00:05:44.701
and can be used efficiently

100
00:05:44.701 --> 00:05:48.043
So not only is it used in game development but

101
00:05:48.043 --> 00:05:51.799
Also used efficiently in fields such as 
car navigation and natural language parsing

102
00:05:54.037 --> 00:05:56.758
Through these mathematical expressions

103
00:05:56.758 --> 00:05:58.773
A* algorithm can be simply summarized

104
00:05:58.773 --> 00:06:02.550
The final value f(n) is a sum of

105
00:06:02.550 --> 00:06:07.165
path value g(n) and heuristic vale h(n)

106
00:06:07.165 --> 00:06:09.267
For the case of Dijkstra algorithm

107
00:06:09.267 --> 00:06:11.834
there was only the path value g(n)

108
00:06:11.834 --> 00:06:15.597
A* algorithm adds the heuristic value h(n)

109
00:06:15.597 --> 00:06:19.195
which is the formula it uses

110
00:06:19.195 --> 00:06:21.876
Then let's take a look at examples to

111
00:06:21.876 --> 00:06:25.888
learn the mechanism of A* algorithm

112
00:06:25.888 --> 00:06:29.368
I will use the same graph from the Dijkstra algorithm

113
00:06:29.368 --> 00:06:31.810
but I will utilize the A* algorithm

114
00:06:31.810 --> 00:06:36.155
in order to explain the path with minimum distance

115
00:06:36.155 --> 00:06:38.485
First, to use A* algorithm

116
00:06:38.485 --> 00:06:43.047
Ways to calculate heuristic values must be set

117
00:06:43.047 --> 00:06:45.006
Generally, heuristic value

118
00:06:45.006 --> 00:06:49.579
takes the minimum distance from the node to the destination

119
00:06:49.579 --> 00:06:53.542
but using different functions 
depending on the situation is also an option

120
00:06:53.542 --> 00:06:56.187
therefore, A* algorithm

121
00:06:56.187 --> 00:07:00.502
copes with the situation in a flexible manner

122
00:07:00.502 --> 00:07:05.740
For this example, we will use the minimum distance

123
00:07:05.740 --> 00:07:07.498
As you can see over here

124
00:07:07.498 --> 00:07:11.445
It calculates the minimum distance 
for each node unrelated to the path

125
00:07:11.445 --> 00:07:15.472
The final value can be seen like so

126
00:07:15.472 --> 00:07:21.399
The value of minimum distance 
from each node to the destination

127
00:07:21.399 --> 00:07:23.690
will be saved to this node

128
00:07:23.690 --> 00:07:27.749
It has already been calculated so, we're able to save it

129
00:07:27.749 --> 00:07:31.883
The value of node B is 4, node C is 4.5

130
00:07:31.883 --> 00:07:38.600
2 for D, 2 for E, and the heuristic value of F is 4

131
00:07:38.600 --> 00:07:41.660
The values have all been saved

132
00:07:41.660 --> 00:07:43.423
Just like the mathematical expression that I mentioned

133
00:07:43.423 --> 00:07:47.524
The sum of path value and heuristic value for each node

134
00:07:47.524 --> 00:07:51.017
which is the final value can be calculated

135
00:07:51.017 --> 00:07:56.126
Based on this, I will proceed with the A* algorithm

136
00:07:56.126 --> 00:07:59.931
The starting point A has two different paths

137
00:07:59.931 --> 00:08:03.175
Path to B and path to C

138
00:08:03.175 --> 00:08:05.997
I will calculate the value of these two cases

139
00:08:05.997 --> 00:08:09.145
The path value from A to B is 1.5

140
00:08:09.145 --> 00:08:11.801
The heuristic value of B is 4

141
00:08:11.801 --> 00:08:16.393
which makes the final value from A to B as 5.5

142
00:08:16.393 --> 00:08:19.761
Like so, the path value from A to C is 2

143
00:08:19.761 --> 00:08:23.192
the heuristic value of C is 4.5

144
00:08:23.192 --> 00:08:27.591
The final value from A to C will be 6.5

145
00:08:27.591 --> 00:08:30.627
Then we need to find a smaller value from the two cases

146
00:08:30.627 --> 00:08:33.967
in order to initiate

147
00:08:33.967 --> 00:08:37.145
The smaller value is path B

148
00:08:37.145 --> 00:08:40.415
Just because we chose path B with a final value of 5.5

149
00:08:40.415 --> 00:08:44.254
that is smaller than 6.5

150
00:08:44.254 --> 00:08:48.252
It doesn't mean that the value of 
6.5 with path C is unnecessary

151
00:08:48.252 --> 00:08:52.670
This value must be saved somewhere and memorized

152
00:08:52.670 --> 00:08:57.230
From now on, we will search for a path to B

153
00:08:57.230 --> 00:09:01.243
but if the measured value is bigger than 6.5

154
00:09:01.243 --> 00:09:04.443
we must stop and come back to the beginning

155
00:09:04.443 --> 00:09:06.410
Path B might not head to the destination

156
00:09:06.410 --> 00:09:10.205
and could be misdirected

157
00:09:10.205 --> 00:09:12.205
We will move on to the next step

158
00:09:15.443 --> 00:09:19.162
In path B, the value of the next node D is

159
00:09:19.162 --> 00:09:22.200
the path value is 1.5 + 1.5 = 3

160
00:09:22.200 --> 00:09:26.245
the heuristic value of D is 2 which is added up to 5

161
00:09:26.245 --> 00:09:30.901
this value is smaller than path C which was 6.5

162
00:09:30.901 --> 00:09:34.175
we can proceed the inquiry

163
00:09:34.175 --> 00:09:36.641
Let's move on to the next step

164
00:09:36.641 --> 00:09:40.548
Continuing with path B, the value of the next node F is

165
00:09:40.548 --> 00:09:46.373
1.5 + 1.5 + 2 which is added up to 5

166
00:09:46.373 --> 00:09:50.512
The heuristic value is 4, which makes the total value 9

167
00:09:50.512 --> 00:09:55.459
This value is bigger than the path value of C which was 6.5

168
00:09:55.459 --> 00:09:58.522
This means we should stop the inquiry of path B

169
00:09:58.522 --> 00:10:02.799
And let's hand this over to C

170
00:10:05.027 --> 00:10:07.849
The inquiry begins on path C

171
00:10:07.849 --> 00:10:10.655
The rules are same as before

172
00:10:10.655 --> 00:10:15.730
If path C's value is bigger than the value of 
path C which is 9, we will stop the inquiry

173
00:10:15.730 --> 00:10:20.037
and we will begin path finding 
in the final node of path B which is F

174
00:10:20.037 --> 00:10:23.383
We should set this beforehand

175
00:10:23.383 --> 00:10:27.202
The next node of path C is E, leading to 2+3

176
00:10:27.202 --> 00:10:29.690
The path value is 2+3 which is 5

177
00:10:29.690 --> 00:10:32.957
The heuristic value is 2 which makes the total value 7

178
00:10:32.957 --> 00:10:36.041
This is smaller than 9 which was the previous value

179
00:10:36.041 --> 00:10:40.383
We can proceed with the inquiry

180
00:10:40.383 --> 00:10:44.799
Moving on, we will arrive at the destination

181
00:10:44.799 --> 00:10:48.185
Arriving at the destination doesn't mean that it's over

182
00:10:48.185 --> 00:10:52.025
The path value until 
the destination point needs to be added up

183
00:10:52.025 --> 00:10:55.836
whether if it is the minimum value

184
00:10:55.836 --> 00:10:58.819
needs to be checked first

185
00:10:58.819 --> 00:11:01.304
Looking back at path C, which we have inquired

186
00:11:01.304 --> 00:11:04.975
the calculation of the path value is 2+3+2

187
00:11:04.975 --> 00:11:07.908
the total value is 7

188
00:11:07.908 --> 00:11:11.239
This is smaller than the value 
previously calculated which was 9

189
00:11:11.239 --> 00:11:15.849
Finally, the pathfinding node can be fixed

190
00:11:15.849 --> 00:11:20.452
Then what are the differences between the 2 algorithms?

191
00:11:20.452 --> 00:11:25.469
The advantages of A* algorithm 
compared to Dijkstra algorithm is

192
00:11:25.469 --> 00:11:28.401
the calculation of the node from F to G

193
00:11:28.401 --> 00:11:31.175
doesn't need to be done separately

194
00:11:31.175 --> 00:11:33.535
Therefore, A* algorithm

195
00:11:33.535 --> 00:11:35.962
decreases memory and computational complexity

196
00:11:35.962 --> 00:11:38.109
and is an efficient pathfinding algorithm

197
00:11:38.109 --> 00:11:43.264
It is useful for games that need real-time calculation

198
00:11:43.264 --> 00:11:47.165
Next, I have prepared another practical example

199
00:11:47.165 --> 00:11:50.540
Let's say a game is structured

200
00:11:50.540 --> 00:11:52.611
with a grid map like so

201
00:11:52.611 --> 00:11:56.324
The starting point is S and the target point is D

202
00:11:56.324 --> 00:12:02.116
In between S and D there is a purple obstacle blocking them

203
00:12:02.116 --> 00:12:05.674
Number of cases to get to 
target point D from starting point S

204
00:12:05.674 --> 00:12:08.175
can be countless

205
00:12:08.175 --> 00:12:11.287
So, using the A* algorithm

206
00:12:11.287 --> 00:12:13.403
I'll try to only calculate points that are necessary

207
00:12:13.403 --> 00:12:17.304
which is an efficient path finding

208
00:12:17.304 --> 00:12:21.868
First, the starting point S has 8 number of cases

209
00:12:21.868 --> 00:12:25.620
In the grid map, the straight line distance value is 1

210
00:12:25.620 --> 00:12:31.433
The diagonal distance value will be set to 1.414

211
00:12:31.433 --> 00:12:34.613
In the 8 different paths that are near the S

212
00:12:34.613 --> 00:12:39.334
The minimum value will be on the right

213
00:12:39.334 --> 00:12:42.242
The right node has path value 1 and

214
00:12:42.242 --> 00:12:45.423
the heuristic value 3 to the destination

215
00:12:45.423 --> 00:12:48.938
added into 4 in total

216
00:12:48.938 --> 00:12:50.699
In the 8 number of cases

217
00:12:50.699 --> 00:12:54.433
Let's check the second smallest value

218
00:12:54.433 --> 00:12:57.524
The node diagonally across the upper right

219
00:12:57.524 --> 00:13:01.393
will have the same value as the node 
diagonally across the lower right

220
00:13:01.393 --> 00:13:04.152
First, the path value is 1.414

221
00:13:04.152 --> 00:13:08.740
and the heuristic value is 
one diagonal line and two straight lines

222
00:13:08.740 --> 00:13:11.601
which is 3.414

223
00:13:11.601 --> 00:13:14.462
This adds up to a total value of 4.828

224
00:13:14.462 --> 00:13:18.845
The upper right and lower right has an equal value

225
00:13:18.845 --> 00:13:21.573
In this case of an even score

226
00:13:21.573 --> 00:13:26.146
There needs to be a rule on what should come first

227
00:13:26.146 --> 00:13:30.829
We will make a rule of choosing the lower side first

228
00:13:30.829 --> 00:13:35.007
Let's move on to the next step

229
00:13:35.007 --> 00:13:37.778
After choosing the right node

230
00:13:37.778 --> 00:13:40.595
in order to expand the path

231
00:13:40.595 --> 00:13:43.423
we need to search for every neighboring node once again

232
00:13:43.423 --> 00:13:47.433
The right node is blocked by 
the obstacle and has nowhere to go

233
00:13:47.433 --> 00:13:51.314
Then we should move up or down

234
00:13:51.314 --> 00:13:54.663
We said that the bottom side goes first

235
00:13:54.663 --> 00:13:56.104
Following the order of bottom priority

236
00:13:56.104 --> 00:14:00.759
We will choose the bottom node and expand it

237
00:14:00.759 --> 00:14:02.819
When proceeding with the bottom node

238
00:14:02.819 --> 00:14:05.403
Instead of going through right to get to the bottom

239
00:14:05.403 --> 00:14:09.037
Moving diagonally from the starting point 
will have a smaller value

240
00:14:09.037 --> 00:14:11.075
Crossing right to get to the bottom

241
00:14:11.075 --> 00:14:12.599
leads to a path value of 2

242
00:14:12.599 --> 00:14:16.096
But moving diagonally has the value of 1.414

243
00:14:17.680 --> 00:14:21.799
So we will chose the node on the lower right

244
00:14:21.799 --> 00:14:24.710
but the node to chose when the path is blocked

245
00:14:24.710 --> 00:14:28.056
will be kept in mind as well

246
00:14:28.056 --> 00:14:32.056
The right upper node that had an even score

247
00:14:32.056 --> 00:14:36.461
This upper node will be considered as next in order

248
00:14:36.461 --> 00:14:39.863
The value of this node is equal

249
00:14:39.863 --> 00:14:42.393
It has an even value of 4.828

250
00:14:42.393 --> 00:14:45.103
Therefore, we will move to the lower right

251
00:14:45.103 --> 00:14:48.542
but if the value is bigger than 4.828

252
00:14:48.542 --> 00:14:52.152
starting over at the upper right

253
00:14:52.152 --> 00:14:54.264
is the structure we will proceed the algorithm in

254
00:14:54.264 --> 00:14:56.254
Let's move to the bottom

255
00:14:58.165 --> 00:15:02.134
We moved to the bottom but it is still blocked

256
00:15:02.134 --> 00:15:06.868
These 2 nodes are the only ones that can be inquired

257
00:15:06.868 --> 00:15:09.680
So we need to move to the bottom once more

258
00:15:11.284 --> 00:15:15.227
But when the value of the bottom node is calculated

259
00:15:15.227 --> 00:15:20.086
it is added up to 6.242

260
00:15:20.086 --> 00:15:21.644
But compared to the previous value

261
00:15:21.644 --> 00:15:25.284
which was 4.828, it has increased

262
00:15:25.284 --> 00:15:28.034
this means starting over at the node we remembered

263
00:15:28.034 --> 00:15:30.967
and begin exploring from here

264
00:15:30.967 --> 00:15:34.422
And the 6.242 node that was previously calculated

265
00:15:34.422 --> 00:15:36.878
will be saved somewhere once again

266
00:15:40.195 --> 00:15:44.522
Let's start over from the upper right node

267
00:15:44.522 --> 00:15:46.132
These 3 nodes

268
00:15:46.132 --> 00:15:48.918
can be newly added to the top

269
00:15:48.918 --> 00:15:51.957
The upper right has the minimum value

270
00:15:51.957 --> 00:15:55.888
it can be calculated into 5.656

271
00:15:55.888 --> 00:15:57.972
2 diagonal path values and

272
00:15:57.972 --> 00:16:01.154
the heuristic value is 2 diagonal lines

273
00:16:01.154 --> 00:16:03.759
which is 5.656

274
00:16:03.759 --> 00:16:07.616
This is smaller than the previous minimum value, 6.242

275
00:16:07.616 --> 00:16:09.492
we can proceed the exploration

276
00:16:09.492 --> 00:16:10.977
Let's move on

277
00:16:12.571 --> 00:16:14.221
Exploring the next node

278
00:16:14.221 --> 00:16:16.991
lets us bring 5 neighboring nodes

279
00:16:16.991 --> 00:16:18.876
Out of these 5, the lower right

280
00:16:18.876 --> 00:16:22.799
diagonally situated node has a minimum value

281
00:16:22.799 --> 00:16:25.522
Calculating this node value

282
00:16:25.522 --> 00:16:27.429
the path value has 3 diagonal lines

283
00:16:27.429 --> 00:16:29.366
the heuristic value is 1 diagonal line

284
00:16:29.366 --> 00:16:35.344
leading to an equal value of 5.656

285
00:16:35.344 --> 00:16:37.920
This is still smaller than the previous value

286
00:16:37.920 --> 00:16:40.136
which means the exploration could go on

287
00:16:42.155 --> 00:16:45.886
Starting from this node 
and searching for its neighboring nodes

288
00:16:45.886 --> 00:16:49.799
We can finally find the destination

289
00:16:49.799 --> 00:16:52.839
Calculating the path value to the destination

290
00:16:52.839 --> 00:16:55.641
it is 5.656 which is an equal value

291
00:16:55.641 --> 00:16:59.388
This is the minimum value out of every number of cases

292
00:16:59.388 --> 00:17:02.482
which means it can be fixed as a minimum distance

293
00:17:02.482 --> 00:17:04.855
Like so, ways to use A* algorithm

294
00:17:04.855 --> 00:17:08.414
to find the minimum distance 
from the starting point until the target point

295
00:17:08.414 --> 00:17:12.057
efficiently, have been learned through out the lecture

296
00:17:12.057 --> 00:17:14.992
To implement the A* algorithm

297
00:17:14.992 --> 00:17:18.750
first, there needs to be 
two different containers to hold the data

298
00:17:18.750 --> 00:17:20.151
One is Open Set and

299
00:17:20.151 --> 00:17:23.800
the other is Closed Set

300
00:17:23.800 --> 00:17:26.419
Like the meaning of 'set'

301
00:17:26.419 --> 00:17:30.800
each container does not allow overlapping data

302
00:17:30.800 --> 00:17:32.721
The open set on the left is

303
00:17:32.721 --> 00:17:36.493
used to store the node that is used for path finding

304
00:17:36.493 --> 00:17:38.301
The closed set on the right is

305
00:17:38.301 --> 00:17:41.562
used to store nodes that are calculated

306
00:17:41.562 --> 00:17:43.816
Inserting data into open set

307
00:17:43.816 --> 00:17:45.781
and when the data calculation is finished

308
00:17:45.781 --> 00:17:48.648
it is moved to the closed set

309
00:17:48.648 --> 00:17:51.176
This is how the algorithm works

310
00:17:51.176 --> 00:17:53.610
Then, as the algorithm continues

311
00:17:53.610 --> 00:17:56.863
how the data of these 2 containers change

312
00:17:56.863 --> 00:17:58.642
will be checked out step by step

313
00:18:01.107 --> 00:18:04.048
First is the algorithm preparation step

314
00:18:04.048 --> 00:18:07.141
We will use the same example

315
00:18:07.141 --> 00:18:09.483
that we have used before

316
00:18:09.483 --> 00:18:12.950
Only the starting node and target node is informed

317
00:18:12.950 --> 00:18:16.661
2 containers both do not have data

318
00:18:16.661 --> 00:18:19.607
In this condition, to initiate the algorithm

319
00:18:19.607 --> 00:18:22.523
we will put the starting node into open set

320
00:18:22.523 --> 00:18:24.702
Like the picture

321
00:18:24.702 --> 00:18:26.275
the starting node will move into the open set

322
00:18:27.602 --> 00:18:31.612
Then let's begin the algorithm

323
00:18:31.612 --> 00:18:33.306
Out of the node in the open set

324
00:18:33.306 --> 00:18:38.186
Call out a node with the minimum value

325
00:18:38.186 --> 00:18:40.471
If the nodes in open set

326
00:18:40.471 --> 00:18:43.240
have an equal value

327
00:18:43.240 --> 00:18:48.582
We should designate a rule on what node to choose

328
00:18:48.582 --> 00:18:51.900
Let's say the heuristic value h(n)

329
00:18:51.900 --> 00:18:55.275
chooses the smaller node

330
00:18:55.275 --> 00:18:58.372
and if the h(n) value is equal as well

331
00:18:58.372 --> 00:19:01.509
The node that came in first, need to be a priority

332
00:19:01.509 --> 00:19:03.602
This will be our rule

333
00:19:03.602 --> 00:19:07.855
Next, which node should be put into the open set first

334
00:19:07.855 --> 00:19:09.780
is another rule we should designate

335
00:19:09.780 --> 00:19:11.825
Nodes situated on the lower side

336
00:19:11.825 --> 00:19:15.067
will be put into the open set first

337
00:19:15.067 --> 00:19:19.691
Take every neighboring node of 
the selected one into the open set

338
00:19:19.691 --> 00:19:22.969
When the neighboring node is in the closed set

339
00:19:22.969 --> 00:19:25.721
or if it is in the area where it can't move, it is excluded

340
00:19:27.414 --> 00:19:30.896
Near the starting node, there are a total of eight nodes

341
00:19:30.896 --> 00:19:34.800
calculate thee path value g(n) and heuristic value h(n)

342
00:19:34.800 --> 00:19:38.364
The newly added parent node will be the starting node

343
00:19:38.364 --> 00:19:41.384
It will be set as a starting node as previously decided

344
00:19:41.384 --> 00:19:44.787
Now, as you can see in the open set

345
00:19:44.787 --> 00:19:47.243
Starting node will be the parent

346
00:19:47.243 --> 00:19:51.255
of the newly added 8 nodes

347
00:19:51.255 --> 00:19:53.689
After wrapping up the process

348
00:19:53.689 --> 00:19:57.186
Go back to Step2 and repeat the same process again

349
00:19:57.186 --> 00:20:01.483
Get the node with the lowest value from the open set

350
00:20:01.483 --> 00:20:04.077
This node will be node number 1

351
00:20:07.651 --> 00:20:09.672
Like so, node number 1 will be

352
00:20:09.672 --> 00:20:12.325
placed on the right

353
00:20:12.325 --> 00:20:15.862
Compare node number 1 and the terminal node 
to see if they're equivalent

354
00:20:15.862 --> 00:20:18.899
If they are different, they will be moved to closed set

355
00:20:21.523 --> 00:20:26.503
This is the processed data structure

356
00:20:26.503 --> 00:20:30.366
Then, go back to node number 1 
and the neighboring node

357
00:20:30.366 --> 00:20:32.968
to check and add

358
00:20:32.968 --> 00:20:37.463
I mentioned before that nodes nearby are excluded

359
00:20:37.463 --> 00:20:45.800
Therefore, out of the neighboring nodes of node number one

360
00:20:45.800 --> 00:20:49.592
the new nodes on the right is completely blocked

361
00:20:49.592 --> 00:20:52.127
and it is in the area where it cannot move

362
00:20:52.127 --> 00:20:55.087
Theses are excluded from the list

363
00:20:55.087 --> 00:20:57.655
And the starting node that is

364
00:20:57.655 --> 00:21:00.493
already in the closed set must be excluded as well

365
00:21:00.493 --> 00:21:03.356
Next, the highlighted parts on the screen

366
00:21:03.356 --> 00:21:07.097
these nodes on the top and bottom need to be added

367
00:21:07.097 --> 00:21:10.949
These nodes are already inside the open set

368
00:21:10.949 --> 00:21:13.676
And their parents are the starting node

369
00:21:13.676 --> 00:21:16.503
which is the S

370
00:21:16.503 --> 00:21:18.846
In this case where the node is overlapped

371
00:21:18.846 --> 00:21:24.394
Replace it into the node with a smaller final value f(n)

372
00:21:24.394 --> 00:21:28.010
But these yellow nodes

373
00:21:28.010 --> 00:21:31.057
If node number one is set as a parent

374
00:21:31.057 --> 00:21:37.394
It doesn't head straight 
but instead adds a path value of 1

375
00:21:37.394 --> 00:21:41.622
For this case, it's 1+1.414, right?

376
00:21:41.622 --> 00:21:46.038
that's why the final value 
doesn't end up being better

377
00:21:46.038 --> 00:21:49.285
So, these must be excluded too

378
00:21:49.285 --> 00:21:51.703
Out of the neighboring node, none of them

379
00:21:51.703 --> 00:21:56.305
could be added to the open set

380
00:21:56.305 --> 00:22:00.184
Now let's go back to the starting node

381
00:22:00.184 --> 00:22:04.533
and select a node with 
the minimum value in the open set

382
00:22:04.533 --> 00:22:07.097
I will name this as node number 2

383
00:22:07.097 --> 00:22:08.615
According to the rule that was mentioned previously

384
00:22:08.615 --> 00:22:10.592
There's a priority to the bottom part

385
00:22:10.592 --> 00:22:12.642
I will select the bottom node first

386
00:22:14.701 --> 00:22:17.558
Same as before, if it's different 
after comparing to the terminal node

387
00:22:17.558 --> 00:22:22.354
Node number 2 can be moved to the closed set

388
00:22:22.354 --> 00:22:24.767
Moving on

389
00:22:24.767 --> 00:22:28.127
Out of the neighboring nodes 
that have node number 2 as the parent

390
00:22:28.127 --> 00:22:32.229
The node that satisfy what was explained before

391
00:22:32.229 --> 00:22:35.866
which are these two nodes situated on the bottom

392
00:22:35.866 --> 00:22:37.384
These can only be added to the open set, right?

393
00:22:37.384 --> 00:22:42.431
The node with a starting node 
as a parent has a smaller value

394
00:22:42.431 --> 00:22:45.671
and the node on the right is immovable

395
00:22:47.632 --> 00:22:52.364
Now, only these two nodes are added in the open set

396
00:22:52.364 --> 00:22:58.127
We have to select the node with 
a minimum value from the open set

397
00:22:58.127 --> 00:23:00.800
Let's name this as node number 3

398
00:23:00.800 --> 00:23:02.775
Then node number 3 is

399
00:23:02.775 --> 00:23:06.503
the node on the upper right side

400
00:23:06.503 --> 00:23:09.742
Same as before, it has to be compared to the terminal node

401
00:23:09.742 --> 00:23:11.540
Since it is not a terminal node

402
00:23:11.540 --> 00:23:14.800
It will be moved to the closed set

403
00:23:14.800 --> 00:23:18.538
And the nearby node of node number three on the upper part

404
00:23:18.538 --> 00:23:22.137
should be added into the open set

405
00:23:22.137 --> 00:23:26.492
The node with the minimum value

406
00:23:26.492 --> 00:23:30.147
will be the node on the upper right part

407
00:23:30.147 --> 00:23:33.909
This will be node number 4

408
00:23:33.909 --> 00:23:38.434
Node number 4 isn't a terminal node so, 
it goes into the closed set

409
00:23:38.434 --> 00:23:42.302
And the neighboring node with node number 4

410
00:23:42.302 --> 00:23:44.444
should be added into open set

411
00:23:44.444 --> 00:23:47.441
Then the open set with S as the parent

412
00:23:47.441 --> 00:23:49.978
Open set with number 2 as the parent

413
00:23:49.978 --> 00:23:53.650
Nodes with number 3 as the parent

414
00:23:53.650 --> 00:23:55.790
Nodes with number 4 as the parent

415
00:23:55.790 --> 00:23:59.958
All of these will move into openset

416
00:23:59.958 --> 00:24:05.632
Now the node with the minimum value has to be selected

417
00:24:05.632 --> 00:24:08.311
By repeating this process

418
00:24:08.311 --> 00:24:11.077
The node with the next small value

419
00:24:11.077 --> 00:24:14.335
will be node number 5 on the lower right part

420
00:24:16.414 --> 00:24:20.317
Adding node number 5

421
00:24:20.317 --> 00:24:24.141
New nodes that have number 5 as the parent

422
00:24:24.141 --> 00:24:27.186
should be added to the open set

423
00:24:27.186 --> 00:24:31.397
I have searched for the node with a minimum value

424
00:24:31.397 --> 00:24:34.444
and it has been selected as a terminal node

425
00:24:34.444 --> 00:24:39.406
Then whether the terminal node is actually

426
00:24:39.406 --> 00:24:41.690
the minimal value out of the nodes in the open set

427
00:24:41.690 --> 00:24:45.701
has to be compared

428
00:24:45.701 --> 00:24:47.800
I have selected from here

429
00:24:47.800 --> 00:24:50.167
Out of the open set, the terminal node

430
00:24:50.167 --> 00:24:54.067
has been selected as the node with a minimum value

431
00:24:54.067 --> 00:24:57.345
Now the algorithm can be terminated

432
00:24:58.800 --> 00:25:01.364
When the path finding ends

433
00:25:01.364 --> 00:25:05.741
each nodes that have been 
used in the path needs to be returned

434
00:25:05.741 --> 00:25:08.221
The parent of the terminal node is number 5

435
00:25:08.221 --> 00:25:10.046
The parent of node number 5 is number 4

436
00:25:10.046 --> 00:25:11.743
The parent of node number 4 is number 3

437
00:25:11.743 --> 00:25:13.501
The parent of node number 3 is S

438
00:25:13.501 --> 00:25:16.156
which is the starting node

439
00:25:16.156 --> 00:25:19.258
We can put it into a sequence

440
00:25:19.258 --> 00:25:24.701
and arranging it in reverse which is S, 3, 4, 5, D

441
00:25:24.701 --> 00:25:27.335
This is how the minimum distance can be set

442
00:25:28.691 --> 00:25:31.434
Until now the A* algorithm and

443
00:25:31.434 --> 00:25:34.028
ways to implement it has been taught

444
00:25:34.028 --> 00:25:35.418
Now we will begin

445
00:25:35.418 --> 00:25:39.001
Implementing A* algorithm in a game engine

446
00:25:39.001 --> 00:25:42.265
and ways to do it

447
00:25:42.265 --> 00:25:44.951
For the coding practice, a Unity based

448
00:25:44.951 --> 00:25:48.196
practice project has been prepared

449
00:25:48.196 --> 00:25:50.234
open this project

450
00:25:50.234 --> 00:25:52.380
In this Scenes folder

451
00:25:52.380 --> 00:25:56.632
we will open Scenes that says AStarPathfinding

452
00:25:56.632 --> 00:26:00.325
Then a screen like this will show

453
00:26:00.325 --> 00:26:03.604
If you move to the script folder of this project

454
00:26:03.604 --> 00:26:06.284
In order to implement A* algorithm

455
00:26:06.284 --> 00:26:10.464
3 scripts, grid and node, path finding

456
00:26:10.464 --> 00:26:13.097
3 scripts have been prepared

457
00:26:13.097 --> 00:26:19.196
Out of these 3, let's take a look at Node.cs script

458
00:26:19.196 --> 00:26:22.387
Double click and open up visual studio

459
00:26:22.387 --> 00:26:26.998
A basic grid unit that is needed for the path finding

460
00:26:26.998 --> 00:26:30.453
A scrip that defines node class

461
00:26:30.453 --> 00:26:35.039
This node class declares a variable for walking

462
00:26:35.039 --> 00:26:37.246
which is isWalkable

463
00:26:37.246 --> 00:26:42.961
For the sequence information of location and grid

464
00:26:42.961 --> 00:26:45.830
the variables have been set

465
00:26:45.830 --> 00:26:50.156
If related information is delivered through the constructor

466
00:26:50.156 --> 00:26:54.147
The constructor has been selected so they can be set

467
00:26:54.147 --> 00:26:57.779
And hcost and gcost

468
00:26:57.779 --> 00:27:01.602
They are used in implementing A* algorithm

469
00:27:01.602 --> 00:27:05.865
gcost which applies to the path value

470
00:27:05.865 --> 00:27:10.008
hcost which applies to heuristic value

471
00:27:10.008 --> 00:27:12.859
These are the variables that have been set

472
00:27:12.859 --> 00:27:16.428
The final calculation value that adds up these two

473
00:27:16.428 --> 00:27:20.950
Property that calculates the final value f(n)

474
00:27:20.950 --> 00:27:25.760
fcost has been declared in the class

475
00:27:27.869 --> 00:27:29.983
Let's go back to Unity

476
00:27:29.983 --> 00:27:33.345
The scene structure of Unity project will be explained

477
00:27:33.345 --> 00:27:38.533
Arrange ground plane game object in the background

478
00:27:38.533 --> 00:27:43.881
Extending the size of the plane by three times

479
00:27:43.881 --> 00:27:51.444
I will set a map with a total size of 30*30

480
00:27:51.444 --> 00:27:57.327
I will highlight the player through a capsule on the map

481
00:27:57.327 --> 00:28:03.246
I have set the target beforehand, using a cube

482
00:28:03.246 --> 00:28:08.135
And for empty game objects called Obstacles

483
00:28:08.135 --> 00:28:13.186
Like so, the cube can be arranged as a child

484
00:28:13.186 --> 00:28:15.006
These are the obstacles

485
00:28:15.006 --> 00:28:16.708
The player cannot move

486
00:28:16.708 --> 00:28:19.651
and it will become a obstacle game object

487
00:28:19.651 --> 00:28:24.043
To find out if they are actually immovable

488
00:28:24.043 --> 00:28:25.750
Looking at the upper right part

489
00:28:25.750 --> 00:28:28.012
There is a layer called Unwalkable

490
00:28:28.012 --> 00:28:31.691
which is set to the game objects

491
00:28:31.691 --> 00:28:36.375
So later on when the map is analyzed

492
00:28:36.375 --> 00:28:39.946
for areas that are covered by Unwalkable

493
00:28:39.946 --> 00:28:43.847
the information that they are immovable is delivered

494
00:28:43.847 --> 00:28:46.434
through this layer

495
00:28:46.434 --> 00:28:50.861
Now the important game object is

496
00:28:50.861 --> 00:28:53.295
The A* placed on the top part

497
00:28:53.295 --> 00:28:55.634
A* game object has

498
00:28:55.634 --> 00:28:58.645
Grid component and Pathfinding component

499
00:28:58.645 --> 00:29:01.048
These two are arranged

500
00:29:01.048 --> 00:29:04.368
The Grid component plays the role of

501
00:29:04.368 --> 00:29:08.651
dividing the background with 1m unit grids

502
00:29:08.651 --> 00:29:13.275
These designate the values

503
00:29:13.275 --> 00:29:16.609
And one thing to add on this part

504
00:29:16.609 --> 00:29:20.264
The layer name to detect immovable grid

505
00:29:20.264 --> 00:29:24.493
which was Unwalkable, it was structured to be set here

506
00:29:24.493 --> 00:29:27.881
Now let's take a look at

507
00:29:27.881 --> 00:29:30.671
the code of the Grid component

508
00:29:30.671 --> 00:29:32.900
Open up visual studio

509
00:29:32.900 --> 00:29:37.444
We'll look over the configuration of the Grid component

510
00:29:37.444 --> 00:29:42.916
First, in a Grid there is a 2D array of nodes

511
00:29:42.916 --> 00:29:45.394
it is a variable called Grid

512
00:29:45.394 --> 00:29:48.475
This 2D array of nodes, when starting

513
00:29:48.475 --> 00:29:51.719
it uses a function called CreateGrid

514
00:29:51.719 --> 00:29:54.533
to fill up the 2D array

515
00:29:54.533 --> 00:29:56.396
The amount that they fill up is

516
00:29:56.396 --> 00:29:59.497
Previously, we have set from the editor

517
00:29:59.497 --> 00:30:04.750
X value and Y value of Number of Grids

518
00:30:04.750 --> 00:30:07.325
and it analyzes the arrangement

519
00:30:07.325 --> 00:30:12.394
calculating the size of the whole 2D array

520
00:30:12.394 --> 00:30:18.698
Next, utilizing the size of the fixed node

521
00:30:18.698 --> 00:30:23.159
Run the loop twice in the Grid

522
00:30:23.159 --> 00:30:26.345
in order to calculate the complete node

523
00:30:26.345 --> 00:30:30.075
This is a size of 30*30

524
00:30:30.075 --> 00:30:32.661
A total of 900 Grids have been set

525
00:30:34.335 --> 00:30:37.070
Running the horizontal and vertical loop

526
00:30:37.070 --> 00:30:41.523
Add one in the Grid 2D array of node

527
00:30:41.523 --> 00:30:46.482
use the function from the physics engine to see if the Grid

528
00:30:46.482 --> 00:30:50.147
is an area where the player can walk through

529
00:30:50.147 --> 00:30:53.294
In this Physics.CheckSphere

530
00:30:53.294 --> 00:30:57.029
add the information of unwalkableMask to see

531
00:30:57.029 --> 00:30:59.557
if the Grid and node

532
00:30:59.557 --> 00:31:01.618
is an area where the player can walk through

533
00:31:01.618 --> 00:31:03.939
or an area where the player can't walk

534
00:31:03.939 --> 00:31:07.849
If the player isn't able to walk, 
the related information

535
00:31:07.849 --> 00:31:11.671
needs to be inserted into 
the first argument to create a node object

536
00:31:11.671 --> 00:31:14.513
and put it into the 2D array

537
00:31:14.513 --> 00:31:18.183
Like so, if the Grid is completely created

538
00:31:18.183 --> 00:31:20.775
the next important function is

539
00:31:20.775 --> 00:31:25.037
A function to bring 8 neighboring nodes that are

540
00:31:25.037 --> 00:31:28.546
nearby a specific node

541
00:31:28.546 --> 00:31:30.661
It is the GetNeighBours function

542
00:31:30.661 --> 00:31:33.375
Utilizing the GetNeighBours function

543
00:31:33.375 --> 00:31:37.028
information of nearby nodes can be retrieved

544
00:31:37.028 --> 00:31:39.735
Lastly, another important function is

545
00:31:39.735 --> 00:31:42.117
A function called OnDrawGizmos

546
00:31:42.117 --> 00:31:47.482
The Unity draws the current grids

547
00:31:47.482 --> 00:31:52.552
When the path is found, the minimum distance

548
00:31:52.552 --> 00:31:55.265
is drawn with a black coloring

549
00:31:56.711 --> 00:31:59.172
Then let's come back to Unity

550
00:31:59.172 --> 00:32:02.780
and execute the program

551
00:32:02.780 --> 00:32:05.181
Press the play button

552
00:32:05.181 --> 00:32:11.273
Switch to the scene view from the game view

553
00:32:11.273 --> 00:32:13.682
When you check the scene view

554
00:32:13.682 --> 00:32:18.097
You can see grids of scene view being displayed

555
00:32:18.097 --> 00:32:22.096
The most important part 
that executes the logic of path finding

556
00:32:22.096 --> 00:32:26.998
Let's look over the code of Pathfinding component

557
00:32:26.998 --> 00:32:32.294
Currently, the pathfinding function isn't available

558
00:32:32.294 --> 00:32:36.721
The current location of the player 
is marked with a black coloring

559
00:32:36.721 --> 00:32:40.736
Let's reactivate the pathfinding logic

560
00:32:40.736 --> 00:32:44.702
In realtime, from the starting point to the target point

561
00:32:44.702 --> 00:32:49.800
We will try to mark the path finding on screen

562
00:32:49.800 --> 00:32:52.963
Playing the role of path finding in this project

563
00:32:52.963 --> 00:32:55.374
It is called Pathfinding component

564
00:32:55.374 --> 00:32:57.757
In the pathfinding component

565
00:32:57.757 --> 00:33:01.414
a function called FindPath is declared

566
00:33:01.414 --> 00:33:06.968
So let's get to know this function called FindPath

567
00:33:06.968 --> 00:33:10.185
In order to implement this, as I mentioned

568
00:33:10.185 --> 00:33:12.287
Closed set and closed set

569
00:33:12.287 --> 00:33:15.741
These two data structure needs to be arranged

570
00:33:15.741 --> 00:33:17.929
From this code, in the open set

571
00:33:17.929 --> 00:33:20.345
The List data structure is designated

572
00:33:20.345 --> 00:33:24.127
The closed set selects HashSet

573
00:33:24.127 --> 00:33:27.625
The reason why the List data structure 
of the open set is designated is

574
00:33:27.625 --> 00:33:29.700
because it is easy to add the node

575
00:33:29.700 --> 00:33:33.444
and to make it efficient for sequential searching

576
00:33:33.444 --> 00:33:37.216
The reason why HashSet data structure 
was chosen from closed set is

577
00:33:37.216 --> 00:33:39.744
because the node in the closed set that will be used

578
00:33:39.744 --> 00:33:41.932
don't need sequential searching

579
00:33:41.932 --> 00:33:46.206
but instead, only need to find the designated node quickly

580
00:33:46.206 --> 00:33:48.595
Now the first node of open set

581
00:33:48.595 --> 00:33:50.646
The starting node needs to be put

582
00:33:50.646 --> 00:33:54.909
the actual algorithm is proceeded through a while loop

583
00:33:54.909 --> 00:33:56.978
Looking at the condition of this while loop

584
00:33:56.978 --> 00:33:59.472
It needs to continue until

585
00:33:59.472 --> 00:34:02.691
there is a data of the open set

586
00:34:02.691 --> 00:34:06.038
Then, since the starting node was already put in

587
00:34:06.038 --> 00:34:08.612
It will proceed by the while node participating as well

588
00:34:08.612 --> 00:34:12.661
Let's open the logic of the first area

589
00:34:12.661 --> 00:34:15.063
Out of the open set

590
00:34:15.063 --> 00:34:17.769
the node with a minimum value

591
00:34:17.769 --> 00:34:20.246
needs to be selected in this logic

592
00:34:20.246 --> 00:34:24.417
Take currentNode

593
00:34:24.417 --> 00:34:29.236
which is the first element of the node

594
00:34:29.236 --> 00:34:33.937
Run the loop so that the next element

595
00:34:33.937 --> 00:34:37.565
will have a smaller fcost compared to the current element

596
00:34:37.565 --> 00:34:40.909
check if the final value is small

597
00:34:40.909 --> 00:34:43.493
If the final value is equal

598
00:34:43.493 --> 00:34:48.450
the hcost selects a smaller element

599
00:34:48.450 --> 00:34:53.057
and designates as a currentNode, 
which is a logic implemented

600
00:34:53.057 --> 00:34:56.907
If the hcost is small

601
00:34:56.907 --> 00:35:00.859
The node that was already selected has to be prioritized

602
00:35:00.859 --> 00:35:04.478
For the node that was selected beforehand

603
00:35:04.478 --> 00:35:10.050
When the neighboring node from the open set is added

604
00:35:10.050 --> 00:35:12.255
the order is set

605
00:35:12.255 --> 00:35:15.570
As you can see from the Grid

606
00:35:15.570 --> 00:35:19.830
When we bring neighboring nodes

607
00:35:19.830 --> 00:35:21.429
We have an order of going from bottom to top

608
00:35:21.429 --> 00:35:24.879
and from left to right

609
00:35:24.879 --> 00:35:28.616
If the fcost and the hcost is equal

610
00:35:28.616 --> 00:35:31.781
the node on the bottom part will be prioritized

611
00:35:31.781 --> 00:35:32.929
That's how you should understand it

612
00:35:34.345 --> 00:35:36.800
Let's open up the next area

613
00:35:36.800 --> 00:35:39.582
The next area is currentNode

614
00:35:39.582 --> 00:35:43.499
If the minimum value

615
00:35:43.499 --> 00:35:47.295
which is the currentNode is equal to the terminal node

616
00:35:47.295 --> 00:35:48.956
the exploration can be executed

617
00:35:48.956 --> 00:35:53.087
and a function called RetracePath can be invoked

618
00:35:53.087 --> 00:35:55.501
This RetracePath function will be

619
00:35:55.501 --> 00:35:57.137
explained further on later

620
00:35:59.483 --> 00:36:01.800
Next, the third field

621
00:36:01.800 --> 00:36:06.859
The third area has a logic of 
dislocating the currentNode from open set

622
00:36:06.859 --> 00:36:09.800
and moving it into the closed set

623
00:36:09.800 --> 00:36:11.384
This is simple so

624
00:36:11.384 --> 00:36:14.562
We will move on to the next part

625
00:36:14.562 --> 00:36:19.593
The fourth area has the logic of

626
00:36:19.593 --> 00:36:21.925
bringing every neighboring nodes in currentNode

627
00:36:21.925 --> 00:36:24.859
and putting it into the open set

628
00:36:24.859 --> 00:36:26.230
When I previously explained it

629
00:36:26.230 --> 00:36:30.377
I used the function of bringing neighboring nodes

630
00:36:30.377 --> 00:36:32.028
to put it into the open set

631
00:36:32.028 --> 00:36:36.952
The condition is that 
when the neighboring node is in closed set

632
00:36:36.952 --> 00:36:39.741
or if it is immovable

633
00:36:39.741 --> 00:36:42.850
The node has to be skipped and can't be put into open set

634
00:36:44.543 --> 00:36:47.341
So if it has passed this condition

635
00:36:47.341 --> 00:36:49.680
it can fit into the open set

636
00:36:49.680 --> 00:36:51.988
and becoming a valid node

637
00:36:51.988 --> 00:36:56.127
The algorithm value for this node has to be calculated

638
00:36:56.127 --> 00:37:01.453
The value of gcost is the current node's gcost and

639
00:37:01.453 --> 00:37:05.381
the neighboring node next to the current one

640
00:37:05.381 --> 00:37:07.675
What we're currently calculating

641
00:37:07.675 --> 00:37:11.156
the distance of the neighboring node all added up

642
00:37:11.156 --> 00:37:14.879
leads to the path value gcost

643
00:37:14.879 --> 00:37:17.829
and the heuristic, h value

644
00:37:17.829 --> 00:37:21.424
The node we will now add to the open set

645
00:37:21.424 --> 00:37:25.810
and the target node's minimum distance has to be calculated

646
00:37:25.810 --> 00:37:29.156
the f value adds these two values together

647
00:37:29.156 --> 00:37:32.278
When a neighboring node is made like so

648
00:37:32.278 --> 00:37:33.572
There are two cases

649
00:37:33.572 --> 00:37:37.968
One case which includes a node 
that is overlapped in the open set

650
00:37:37.968 --> 00:37:41.919
and the second case which is a new node

651
00:37:41.919 --> 00:37:46.434
For the case of an overlapped node in the open set

652
00:37:46.434 --> 00:37:51.780
The gcost in the open set has to be replaced

653
00:37:51.780 --> 00:37:54.072
Because the heuristic value of the node

654
00:37:54.072 --> 00:37:56.978
does not change the location of the node

655
00:37:56.978 --> 00:37:59.542
so maintain the heuristic value of the node

656
00:37:59.542 --> 00:38:01.592
and alter the gcost

657
00:38:01.592 --> 00:38:03.651
Then the parent information has to be replaced

658
00:38:03.651 --> 00:38:08.226
If there is an equivalent node currently

659
00:38:08.226 --> 00:38:11.927
the previous parent will be different from the current node

660
00:38:11.927 --> 00:38:13.869
It will be different from currentNode

661
00:38:13.869 --> 00:38:17.453
Alter the parent node to currentNode

662
00:38:17.453 --> 00:38:22.196
If there isn't a node to add to the open set

663
00:38:22.196 --> 00:38:26.602
Add new information of gcost, hcost, and the parent

664
00:38:26.602 --> 00:38:29.582
and add it to the open set

665
00:38:29.582 --> 00:38:33.909
Now I will explain the rest of the functions

666
00:38:33.909 --> 00:38:38.800
Let's take a look at RetracePath 
which is activated when the path is found

667
00:38:38.800 --> 00:38:43.493
This will be the last node

668
00:38:43.493 --> 00:38:47.800
Continuously analyzing the final node and the current node

669
00:38:47.800 --> 00:38:51.949
The code which finds the parent in reverse

670
00:38:51.949 --> 00:38:54.434
is implemented

671
00:38:54.434 --> 00:38:57.931
Like so, in the List data structure

672
00:38:57.931 --> 00:39:01.364
The nodes which are related to pathfinding have all fit in

673
00:39:01.364 --> 00:39:03.899
Use the Reverse function to flip it upside down

674
00:39:03.899 --> 00:39:07.458
Then it is able to find every array of nodes

675
00:39:07.458 --> 00:39:11.721
that are needed in minimum distance path finding

676
00:39:11.721 --> 00:39:15.523
The last function to be explained 
is the GetDistance function

677
00:39:15.523 --> 00:39:19.899
This GetDistance function calculates the distance

678
00:39:19.899 --> 00:39:25.800
It calculates the number of diagonal or vertical arrangement

679
00:39:25.800 --> 00:39:30.231
The diagonal arrangement is assigned with a weight of 14

680
00:39:30.231 --> 00:39:33.295
and the straight line is assigned with a weight of 10

681
00:39:33.295 --> 00:39:37.750
The function to calculate the total distance 
could be assigned like this

682
00:39:37.750 --> 00:39:39.669
currentNode == targetNode

683
00:39:39.669 --> 00:39:41.285
until the target point

684
00:39:41.285 --> 00:39:46.000
or until every node from the open set

685
00:39:46.000 --> 00:39:48.305
isn't left there

686
00:39:48.305 --> 00:39:51.552
It has to be repeated on and on

687
00:39:51.552 --> 00:39:57.628
The FindPath function is used to repeat it

688
00:39:57.628 --> 00:40:02.958
Place it in the update query and uncomment

689
00:40:02.958 --> 00:40:05.721
Now I will execute this again

690
00:40:10.275 --> 00:40:14.800
Compile the altered code and press the execute button

691
00:40:14.800 --> 00:40:17.166
If we take a look at the Unity result screen

692
00:40:17.166 --> 00:40:20.018
The path is found as you can see

693
00:40:20.018 --> 00:40:23.215
The nodes taking place in the path

694
00:40:23.215 --> 00:40:25.968
can be seen marked with a black coloring

695
00:40:25.968 --> 00:40:29.378
If the selected game object is moved

696
00:40:29.378 --> 00:40:31.087
or if the target is moved

697
00:40:31.087 --> 00:40:34.800
the minimum distance path could be found like so

698
00:40:34.800 --> 00:40:38.023
The execution of path finding could be seen real time

699
00:40:38.023 --> 00:40:39.790
and can be checked out

700
00:40:42.265 --> 00:40:45.680
We have implemented the A* pathfinding algorithm

701
00:40:45.680 --> 00:40:48.265
through the Unity engine

702
00:40:48.506 --> 00:40:53.642
A* Pathfinding Algorithm Optimization

703
00:40:53.642 --> 00:40:57.800
As the A* algorithm proceeds, in the open set

704
00:40:57.800 --> 00:41:00.988
A function to search for the minimum value

705
00:41:00.988 --> 00:41:03.770
A function to eliminate from the data structure

706
00:41:03.770 --> 00:41:06.602
and a function to check the overlapped node

707
00:41:06.602 --> 00:41:08.899
A function to add a new node

708
00:41:08.899 --> 00:41:10.755
And a function to replace the overlapped node

709
00:41:10.755 --> 00:41:13.473
into a new node

710
00:41:13.473 --> 00:41:16.048
There five functions are often used

711
00:41:18.493 --> 00:41:20.612
Out of theses 5 functions, the first

712
00:41:20.612 --> 00:41:25.453
The logic to find the minimum value 
in the open set will be explained

713
00:41:25.453 --> 00:41:27.702
In previous examples

714
00:41:27.702 --> 00:41:30.552
to find the minimum value node in the open set

715
00:41:30.552 --> 00:41:34.285
We had to explore every node from the open set

716
00:41:34.285 --> 00:41:37.352
However as the pathfinding became complex

717
00:41:37.352 --> 00:41:40.572
The size of the open set List had gotten bigger

718
00:41:40.572 --> 00:41:42.549
The process to search every node

719
00:41:42.549 --> 00:41:45.394
had to be overwhelming

720
00:41:45.394 --> 00:41:48.312
When exploring every element

721
00:41:48.312 --> 00:41:52.899
the complexity of the algorithm is called ON

722
00:41:52.899 --> 00:41:54.903
As you can see from the picture

723
00:41:54.903 --> 00:41:56.433
in the open set data structure

724
00:41:56.433 --> 00:41:58.780
there are three items

725
00:41:58.780 --> 00:42:01.661
In order to find the minimum value of 3

726
00:42:01.661 --> 00:42:03.562
The node has to be explored 3 times

727
00:42:03.562 --> 00:42:07.697
Therefore the search complexity of the algorithm

728
00:42:07.697 --> 00:42:09.533
is called by the expression ON

729
00:42:11.463 --> 00:42:14.760
But what if this could be searched at once?

730
00:42:14.760 --> 00:42:18.295
This would mean the quality of the algorithm has increased

731
00:42:18.295 --> 00:42:20.595
Out of the numerous item list

732
00:42:20.595 --> 00:42:24.404
there is a data structure made 
to find the minimum value at once

733
00:42:24.404 --> 00:42:27.820
Priority Queue is commonly used

734
00:42:27.820 --> 00:42:31.671
Priority Queue is a data structure 
that implements reserve gear

735
00:42:31.671 --> 00:42:34.807
It puts the minimum value in front of everything else

736
00:42:34.807 --> 00:42:37.057
which is a unique trait

737
00:42:37.057 --> 00:42:39.412
When we implement A* algorithm

738
00:42:39.412 --> 00:42:42.671
we only have to earn the minimum value

739
00:42:42.671 --> 00:42:44.241
Using Priority Queue

740
00:42:44.241 --> 00:42:47.840
could develop the search quality

741
00:42:47.840 --> 00:42:50.800
The search for the minimum value in a priority queue

742
00:42:50.800 --> 00:42:53.394
could be executed at once

743
00:42:53.394 --> 00:42:56.543
so it has a complexity of O1

744
00:42:56.543 --> 00:43:00.905
From this picture, when the previously seen

745
00:43:00.905 --> 00:43:03.968
data structure is replaced through a priority queue

746
00:43:03.968 --> 00:43:06.061
The minimal element 3 will

747
00:43:06.061 --> 00:43:08.741
always be situated in the front

748
00:43:08.741 --> 00:43:11.097
it can be found through one search

749
00:43:13.602 --> 00:43:16.002
Then let's take a look at

750
00:43:16.002 --> 00:43:19.840
implementing A* algorithm using the priority queue

751
00:43:19.840 --> 00:43:23.741
In order to do this, we have to 
make a priority queue ourselves

752
00:43:23.741 --> 00:43:26.873
Priority queue is a data structure that

753
00:43:26.873 --> 00:43:30.335
ensures minimal or maximal value as a superior element

754
00:43:30.335 --> 00:43:33.949
In this case, we must use minimal value

755
00:43:33.949 --> 00:43:36.113
As you can see from the word priority queue

756
00:43:36.113 --> 00:43:39.850
it only has to guarantee the superior element

757
00:43:39.850 --> 00:43:42.663
It is different from structures that

758
00:43:42.663 --> 00:43:44.008
arrange every element in order

759
00:43:45.879 --> 00:43:48.066
When implementing priority queue

760
00:43:48.066 --> 00:43:51.859
normally, a structure called binary heap is likely to be used

761
00:43:51.859 --> 00:43:54.335
Let's find out

762
00:43:54.335 --> 00:43:57.308
Binary heap is divided into two branches

763
00:43:57.308 --> 00:43:59.483
and it is in a tree structure

764
00:43:59.483 --> 00:44:01.978
It is implemented from an array

765
00:44:01.978 --> 00:44:05.023
It starts from number 0 index which is the root

766
00:44:05.023 --> 00:44:07.127
and it branches out

767
00:44:07.127 --> 00:44:11.364
If we put the previous examples into a binary heap

768
00:44:11.364 --> 00:44:16.287
From node 3 which is the root, 3,15,8

769
00:44:16.287 --> 00:44:19.576
branches out to left and right

770
00:44:19.576 --> 00:44:22.533
consisting 15 and 8

771
00:44:22.533 --> 00:44:24.794
It has the structure of

772
00:44:24.794 --> 00:44:26.384
being lined up

773
00:44:32.315 --> 00:44:35.600
In this binary heap structure, the location of the node

774
00:44:35.600 --> 00:44:39.404
is usually set with fixed rules

775
00:44:39.404 --> 00:44:43.632
When the binary heap structure is arranged as the picture

776
00:44:43.632 --> 00:44:46.978
Let's say these data are lined up this way

777
00:44:46.978 --> 00:44:49.329
each of them as a distinct index

778
00:44:49.329 --> 00:44:51.691
from the array like so

779
00:44:51.691 --> 00:44:55.929
The root index will have index number 0

780
00:44:55.929 --> 00:44:58.968
Ad the child of the second root

781
00:44:58.968 --> 00:45:01.820
will always have index number 1 and 2

782
00:45:01.820 --> 00:45:06.746
The first child nodes as you can see

783
00:45:06.746 --> 00:45:09.226
will have index number 3 and 4

784
00:45:09.226 --> 00:45:13.615
the second child nodes are 10 and 27

785
00:45:13.615 --> 00:45:17.394
In other words, they will have index number 5 and 6

786
00:45:21.453 --> 00:45:25.147
If a random index is given

787
00:45:25.147 --> 00:45:28.729
It is easy to find the parent index right away

788
00:45:28.729 --> 00:45:31.741
which is a trait of the binary heap structure

789
00:45:31.741 --> 00:45:35.424
The formula to find the parent index 
from a distinct index is

790
00:45:35.424 --> 00:45:38.262
Child index ci-1

791
00:45:38.262 --> 00:45:41.830
subtract 1 from the ci and divide it into 2

792
00:45:41.830 --> 00:45:45.226
In this case, integer operation is necessary

793
00:45:45.226 --> 00:45:48.650
If it is not divisible into ci

794
00:45:48.650 --> 00:45:51.414
the decimal point will be eliminated

795
00:45:51.414 --> 00:45:53.748
the index to eliminate it

796
00:45:53.748 --> 00:45:56.236
will be the parent index

797
00:45:56.236 --> 00:46:00.701
If the previous open set structure 
is implemented into a binary heap

798
00:46:00.701 --> 00:46:03.651
Let's select a random element

799
00:46:03.651 --> 00:46:06.602
If an element of 10 is chosen

800
00:46:06.602 --> 00:46:10.117
10 will take index number 5

801
00:46:10.117 --> 00:46:12.251
The parent of index number 5 will be

802
00:46:12.251 --> 00:46:15.364
(5-1)/2 which is number 2

803
00:46:15.364 --> 00:46:21.345
number 2 will be the second child index of the root

804
00:46:21.345 --> 00:46:27.038
And in case of 8, it takes index number 2

805
00:46:27.038 --> 00:46:28.948
The parent of 8 will be

806
00:46:28.948 --> 00:46:35.137
(2-1)/2 which is 0.5

807
00:46:35.137 --> 00:46:38.754
The decimal points have to be eliminated

808
00:46:38.754 --> 00:46:40.434
so the parent index will be 0

809
00:46:40.434 --> 00:46:42.939
This stands for the root index

810
00:46:42.939 --> 00:46:47.107
Using the formula above, any index or

811
00:46:47.107 --> 00:46:48.888
where the parent index is

812
00:46:48.888 --> 00:46:50.731
can be found right away

813
00:46:53.137 --> 00:46:55.338
In this binary heap structure

814
00:46:55.338 --> 00:46:58.265
We will add an item at a time

815
00:46:58.265 --> 00:47:02.840
to see how the data structure is created

816
00:47:02.840 --> 00:47:10.226
For example, 6 data which are 23, 10, 8, 9, 3, 5

817
00:47:10.226 --> 00:47:13.444
will be put into the binary heap structure

818
00:47:13.444 --> 00:47:16.094
The first element, 23

819
00:47:16.094 --> 00:47:18.750
will be the last and the root

820
00:47:18.750 --> 00:47:21.196
It will go into index number 0

821
00:47:21.196 --> 00:47:22.909
The array data will be like so

822
00:47:22.909 --> 00:47:27.592
which results in 23 being put into index number 0

823
00:47:29.711 --> 00:47:32.750
Next, it's time for 10

824
00:47:32.750 --> 00:47:35.335
10 will be added into the last element as well

825
00:47:35.335 --> 00:47:39.008
which means it will take index number 1

826
00:47:39.008 --> 00:47:40.794
it doesn't end here

827
00:47:40.794 --> 00:47:43.800
10 will be added into the last element

828
00:47:43.800 --> 00:47:45.434
and we have to find the parent

829
00:47:45.434 --> 00:47:48.548
If the number is smaller than the parent

830
00:47:48.548 --> 00:47:51.339
It has to go through the process of 
replacing itself and the parent

831
00:47:51.339 --> 00:47:53.077
which is an additional step

832
00:47:53.077 --> 00:47:55.741
This is before the alteration

833
00:47:55.741 --> 00:47:59.255
First, when the 10 is added in the last element

834
00:47:59.255 --> 00:48:02.129
as you can see 23 and 10 is

835
00:48:02.129 --> 00:48:05.048
lined up side by side

836
00:48:06.305 --> 00:48:10.919
So the root node which has a value of 23 
is compared with itself

837
00:48:10.919 --> 00:48:12.493
but 10 is smaller

838
00:48:12.493 --> 00:48:14.929
leading to an alteration between the two

839
00:48:14.929 --> 00:48:17.458
When it is altered, the data of the array

840
00:48:17.458 --> 00:48:19.721
will be replaced like so

841
00:48:19.721 --> 00:48:21.513
10 goes into the root

842
00:48:21.513 --> 00:48:24.444
and the 23 will be set as a child

843
00:48:26.265 --> 00:48:29.968
Now, I will add 8 which is a third element

844
00:48:29.968 --> 00:48:31.987
Put 8 in the last part

845
00:48:31.987 --> 00:48:33.937
And before the replacement

846
00:48:33.937 --> 00:48:36.285
I will take a look at the index of the parent

847
00:48:36.285 --> 00:48:39.233
Parent of the 8 will be 2-1

848
00:48:39.233 --> 00:48:41.701
and divided by 2 equals 0

849
00:48:41.701 --> 00:48:44.394
We can tell that it is the root index

850
00:48:46.186 --> 00:48:49.176
Comparing itself to the root index

851
00:48:49.176 --> 00:48:50.897
8 is clearly smaller

852
00:48:50.897 --> 00:48:53.513
It has to replace itself with the root index

853
00:48:53.513 --> 00:48:56.618
and the 8 goes as a root

854
00:48:56.618 --> 00:49:01.255
and 10 goes back to the original index of 8, number 2

855
00:49:01.255 --> 00:49:04.592
The following arrangement is the array structure

856
00:49:04.592 --> 00:49:07.335
Next, let's add 9

857
00:49:07.335 --> 00:49:08.486
In the case of adding 9

858
00:49:08.486 --> 00:49:12.315
It will be added in the last part making 3 as the index

859
00:49:12.315 --> 00:49:17.117
the parent of 9 will be 23 from the index number 1

860
00:49:17.117 --> 00:49:21.988
This is calculated by (3-1)/2

861
00:49:21.988 --> 00:49:26.457
Then the 23 from index number 1

862
00:49:26.457 --> 00:49:27.607
should be replaced, right?

863
00:49:27.607 --> 00:49:29.275
since 9 is smaller

864
00:49:29.275 --> 00:49:30.946
The data that is replaced

865
00:49:30.946 --> 00:49:34.949
can be formed like so

866
00:49:34.949 --> 00:49:37.146
It doesn't end here

867
00:49:37.146 --> 00:49:41.354
Let's compare with the root index

868
00:49:41.354 --> 00:49:44.391
(1-2)/2 which is the root index

869
00:49:44.391 --> 00:49:46.919
let's take it

870
00:49:46.919 --> 00:49:48.963
and compare it

871
00:49:48.963 --> 00:49:51.850
9 is bigger than 8, so it should stop

872
00:49:54.008 --> 00:49:56.368
Then, I will add 3

873
00:49:56.368 --> 00:49:59.424
The index of 3 will be 4

874
00:49:59.424 --> 00:50:01.683
The parent which has the index of 4 is

875
00:50:01.683 --> 00:50:06.424
(4-2)/2 which equals 1

876
00:50:06.424 --> 00:50:10.941
Comparing the numbers between 9 and 3

877
00:50:10.941 --> 00:50:13.612
which obviously shows that 3 is smaller

878
00:50:13.612 --> 00:50:15.583
9 and 3 has to be swapped

879
00:50:15.583 --> 00:50:18.010
So the index of 3 is 1

880
00:50:18.010 --> 00:50:20.592
and the index of 9 is 4

881
00:50:20.592 --> 00:50:22.484
Let's not stop here

882
00:50:22.484 --> 00:50:25.067
We should find the parent of 3

883
00:50:25.067 --> 00:50:26.982
If we find out the parent of 3

884
00:50:26.982 --> 00:50:29.800
we can tell that it is the root index

885
00:50:29.800 --> 00:50:33.295
Comparing 3 and 8, 3 is smaller

886
00:50:33.295 --> 00:50:36.384
which means a swap is necessary

887
00:50:36.384 --> 00:50:39.589
So as a result of this replacement

888
00:50:39.589 --> 00:50:42.580
it has showed how the data of array can be set

889
00:50:42.580 --> 00:50:43.869
like the following setting on the screen

890
00:50:46.424 --> 00:50:49.315
Lastly, I will add 5

891
00:50:49.315 --> 00:50:52.372
The index of 5 will be 5

892
00:50:52.372 --> 00:50:54.721
And the parent of 5 will be 10 which is index number 2

893
00:50:56.483 --> 00:50:59.465
Of course, 5 is smaller than 10

894
00:50:59.465 --> 00:51:01.721
so we can swap with the parent

895
00:51:01.721 --> 00:51:03.528
We won't stoop here and

896
00:51:03.528 --> 00:51:07.632
go back to the root to compare with it

897
00:51:07.632 --> 00:51:11.281
5 is bigger than 3 which is a root

898
00:51:11.281 --> 00:51:13.642
so we must stop

899
00:51:13.642 --> 00:51:15.915
This is the case of binary heap

900
00:51:15.915 --> 00:51:19.860
23, 10, 8, 9, 3, 5

901
00:51:19.860 --> 00:51:23.275
when these six data are added to it in order

902
00:51:23.275 --> 00:51:26.223
how the array of data will change

903
00:51:26.223 --> 00:51:29.523
was checked out by us

904
00:51:29.523 --> 00:51:33.217
Now this act of implementing priority queue

905
00:51:33.217 --> 00:51:36.651
will be checked out in the Unity engine through a screen

906
00:51:36.651 --> 00:51:40.434
and whether the result of simulation done by us

907
00:51:40.434 --> 00:51:45.028
is an accurate act will be checked out as well

908
00:51:45.028 --> 00:51:50.779
Move to the Scene folder 
from the example project that is prepared

909
00:51:50.779 --> 00:51:55.592
Open a scene called PriorityQueueTest

910
00:51:55.592 --> 00:51:59.900
Then select A* game object

911
00:51:59.900 --> 00:52:03.147
and a script called PriorityQueueTest

912
00:52:03.147 --> 00:52:06.176
will be attached to the component

913
00:52:06.176 --> 00:52:08.491
If you press the execution button

914
00:52:11.303 --> 00:52:16.255
The data structure list of the component

915
00:52:16.255 --> 00:52:19.109
shows the simulations as we did in our heads

916
00:52:19.109 --> 00:52:23.346
3, 8, 5, 23, 9, 10, these datas

917
00:52:23.346 --> 00:52:26.800
are lined up in order

918
00:52:26.800 --> 00:52:29.988
How these codes were made

919
00:52:29.988 --> 00:52:32.315
will be looked through a script

920
00:52:34.830 --> 00:52:40.325
If you see over here, create a priority queue data structure

921
00:52:40.325 --> 00:52:42.411
following the order of this data structure

922
00:52:42.411 --> 00:52:45.666
as we practiced with the example

923
00:52:45.666 --> 00:52:49.092
the 23, 10, 8, 9, 3, 5

924
00:52:49.092 --> 00:52:52.968
will be invoked through the Enqueue function in order

925
00:52:52.968 --> 00:52:56.602
Let's see how this Enqueue function is consisted

926
00:52:56.602 --> 00:53:00.999
The Enqueue function is in Priority Queue

927
00:53:00.999 --> 00:53:05.285
The newest item will be at the end

928
00:53:05.285 --> 00:53:07.800
the data will be added at last

929
00:53:07.800 --> 00:53:10.899
Invoking the function called BubbleUp

930
00:53:10.899 --> 00:53:14.230
The minimum value will be in front of everything else

931
00:53:14.230 --> 00:53:16.186
This is how the logic was structured

932
00:53:16.186 --> 00:53:21.273
As we saw previously, current ci Count

933
00:53:21.273 --> 00:53:23.860
current Count that is in the last part

934
00:53:25.513 --> 00:53:28.117
Calculate the index in the last element

935
00:53:28.117 --> 00:53:30.907
until this index becomes a 0

936
00:53:30.907 --> 00:53:34.176
In other words, it goes up until it becomes a root

937
00:53:34.176 --> 00:53:37.560
It goes up, but in order to go up

938
00:53:37.560 --> 00:53:39.035
the parent index needs to be calculated

939
00:53:39.035 --> 00:53:41.978
The formula that was previously mentioned should be used

940
00:53:41.978 --> 00:53:47.061
And the current child and parent data

941
00:53:47.061 --> 00:53:53.703
should be compared, if the child is bigger

942
00:53:53.703 --> 00:53:56.939
the pool should stop

943
00:53:56.939 --> 00:54:00.710
and if it's smaller the parent and child should swap

944
00:54:00.710 --> 00:54:04.899
The child index should be replaced with a parent index

945
00:54:04.899 --> 00:54:06.809
Once again going back to the loop

946
00:54:06.809 --> 00:54:09.255
This is how the logic is consisted

947
00:54:11.493 --> 00:54:13.034
And as I mentioned

948
00:54:13.034 --> 00:54:16.172
The code used to implement 
adding items in the priority queue data

949
00:54:16.172 --> 00:54:18.968
was what we took a look at

950
00:54:18.968 --> 00:54:22.977
Next, the superior root in binary heap

951
00:54:22.977 --> 00:54:24.719
In other words, eliminating minimum value

952
00:54:24.719 --> 00:54:27.612
Let's take a look at the process

953
00:54:27.612 --> 00:54:30.677
Due to the structure of priority queue

954
00:54:30.677 --> 00:54:33.292
If the value in the front is read

955
00:54:33.292 --> 00:54:35.750
the item has to be eliminated right away

956
00:54:35.750 --> 00:54:40.112
If it is taken out right away, the value at the top

957
00:54:40.112 --> 00:54:43.394
needs to be maintained as the minimum value

958
00:54:43.394 --> 00:54:47.434
I will explain how to implement this in a binary heap

959
00:54:47.434 --> 00:54:49.579
In this current data, first

960
00:54:49.579 --> 00:54:51.793
This is the root value of index number 0

961
00:54:51.793 --> 00:54:52.642
Let's eliminate it

962
00:54:52.642 --> 00:54:54.840
This gets rid of the root

963
00:54:54.840 --> 00:54:57.176
leading to an invalid binary heap

964
00:54:57.176 --> 00:54:59.560
Therefore, temporarily

965
00:54:59.560 --> 00:55:02.259
Move the last element in the current array

966
00:55:02.259 --> 00:55:04.691
which is 10 into the root

967
00:55:04.691 --> 00:55:09.434
Then the data will change like so

968
00:55:09.434 --> 00:55:11.782
This temporarily set root

969
00:55:11.782 --> 00:55:13.960
allows reverse comparison with the child

970
00:55:13.960 --> 00:55:18.156
and if it is bigger than the child,
it can be set to go downwards

971
00:55:18.156 --> 00:55:19.758
However, there are two child nodes

972
00:55:19.758 --> 00:55:23.234
So, out of the left and right child nodes

973
00:55:23.234 --> 00:55:26.067
the smaller one has to be compared

974
00:55:26.067 --> 00:55:29.343
And the smaller child out of these two should be compared

975
00:55:29.343 --> 00:55:32.760
making the smaller one go downwards

976
00:55:32.760 --> 00:55:35.894
In the current data, the 8 on the left is

977
00:55:35.894 --> 00:55:38.022
bigger than the 5 on the right

978
00:55:38.022 --> 00:55:40.681
We can compare with the 5 on the right

979
00:55:42.018 --> 00:55:45.418
So, the child on the right 
and the root should be compared

980
00:55:45.418 --> 00:55:47.811
The root is smaller than the right

981
00:55:47.811 --> 00:55:50.800
which means it should be swapped and headed downwards

982
00:55:50.800 --> 00:55:54.949
Now, the data will be altered like so

983
00:55:54.949 --> 00:55:57.017
The 10 that has headed downwards as a child

984
00:55:57.017 --> 00:56:00.770
doesn't have a child to be compared to, so it should stop

985
00:56:00.770 --> 00:56:02.122
Through this process

986
00:56:02.122 --> 00:56:05.239
The root node will be set to a minimum value

987
00:56:05.239 --> 00:56:07.003
The rule that binary tree had

988
00:56:07.003 --> 00:56:09.651
can be kept well

989
00:56:13.632 --> 00:56:16.949
The process to eliminate items

990
00:56:16.949 --> 00:56:21.021
coming back to Unity 
and getting rid of root items on the top

991
00:56:21.021 --> 00:56:24.074
We will execute functions and

992
00:56:24.074 --> 00:56:25.572
check if the operation works

993
00:56:27.602 --> 00:56:33.847
From the Unity code and the test of the script

994
00:56:33.847 --> 00:56:38.194
The pq.Dequeue function which is commented out

995
00:56:38.194 --> 00:56:40.176
We will uncomment the code and execute it

996
00:56:40.176 --> 00:56:44.328
And the element in the front

997
00:56:44.328 --> 00:56:47.320
Excluding the 3 in the front

998
00:56:47.320 --> 00:56:50.097
It will make a priority queue once again

999
00:56:50.097 --> 00:56:53.204
Taking a look while it is executing

1000
00:56:53.204 --> 00:56:56.643
The data of 5, 8, 20, 23, 9 are

1001
00:56:56.643 --> 00:56:59.968
being lined up in order

1002
00:56:59.968 --> 00:57:03.532
This is equivalent to the simulation result

1003
00:57:03.532 --> 00:57:06.186
that we had in our heads

1004
00:57:06.186 --> 00:57:08.986
Then let's see how this Dequeue function is

1005
00:57:08.986 --> 00:57:10.246
being implemented

1006
00:57:11.830 --> 00:57:15.275
In the case of Dequeue function, first

1007
00:57:15.275 --> 00:57:18.236
return the data of head

1008
00:57:18.236 --> 00:57:22.424
And relocate the last element to the top

1009
00:57:22.424 --> 00:57:24.965
Calculate the last index and

1010
00:57:24.965 --> 00:57:29.127
move it to the front

1011
00:57:29.127 --> 00:57:33.343
Then, at the top

1012
00:57:33.343 --> 00:57:36.935
Item placed on the top which was moved to the last item

1013
00:57:36.935 --> 00:57:39.354
It is being brought down by the SinkDown function

1014
00:57:39.354 --> 00:57:44.851
It is similar to the BubbleUp that was previously mentioned

1015
00:57:44.851 --> 00:57:46.315
It just brings it down

1016
00:57:46.315 --> 00:57:48.020
keeps on bringing it down

1017
00:57:48.020 --> 00:57:51.176
First, compare the child on the left and right

1018
00:57:51.176 --> 00:57:55.704
After bringing the child on the left and right

1019
00:57:55.704 --> 00:57:57.506
Compare these two and

1020
00:57:57.506 --> 00:58:01.750
when the index of left and right changes

1021
00:58:01.750 --> 00:58:06.003
In other words, if the value of the right index is smaller

1022
00:58:06.003 --> 00:58:08.711
Choose the right index as a target index

1023
00:58:08.711 --> 00:58:10.835
If the left index is smaller

1024
00:58:10.835 --> 00:58:13.949
Maintain the left index value and

1025
00:58:13.949 --> 00:58:17.047
compare it to the current parent index

1026
00:58:17.047 --> 00:58:19.784
If the child is smaller than the parent

1027
00:58:19.784 --> 00:58:21.972
It brings the parent down

1028
00:58:21.972 --> 00:58:24.166
This is the logic it has

1029
00:58:26.147 --> 00:58:28.363
Utilizing the list data structure

1030
00:58:28.363 --> 00:58:30.261
implementing open set and

1031
00:58:30.261 --> 00:58:32.001
using binary heap data structure to

1032
00:58:32.001 --> 00:58:34.107
implement openset

1033
00:58:34.107 --> 00:58:38.463
This is the comparison of 
algorithm complexity between the two

1034
00:58:38.463 --> 00:58:40.603
First, the node with a minimum value

1035
00:58:40.603 --> 00:58:42.644
For the function to search for it

1036
00:58:42.644 --> 00:58:47.018
the binary heap can bring it without a sequential search

1037
00:58:47.018 --> 00:58:49.126
Compared to the List, binary heap has a

1038
00:58:49.126 --> 00:58:51.444
faster search speed

1039
00:58:51.444 --> 00:58:54.525
However when executing elimination or insertion

1040
00:58:54.525 --> 00:58:58.453
and processes to substitute

1041
00:58:58.453 --> 00:59:01.995
It has to go through the tree structure 
between parent and child

1042
00:59:01.995 --> 00:59:05.578
which means processes of going up or downwards

1043
00:59:05.578 --> 00:59:07.661
The binary heap is slower in those cases

1044
00:59:07.661 --> 00:59:09.721
It doesn't mean extremely slow

1045
00:59:09.721 --> 00:59:12.067
The complexity of the algorithm

1046
00:59:12.067 --> 00:59:16.325
will decrease to a log which is 
an opposite of tree exponentiation

1047
00:59:16.325 --> 00:59:18.169
So this complexity of algorithm

1048
00:59:18.169 --> 00:59:20.780
is named as OlogN

1049
00:59:20.780 --> 00:59:24.493
Binary heap is considered slower than the List

1050
00:59:26.592 --> 00:59:29.331
And when finding out overlapping

1051
00:59:29.331 --> 00:59:32.462
Both has to go through numerous nodes

1052
00:59:32.462 --> 00:59:33.894
to find out

1053
00:59:33.894 --> 00:59:36.384
So the value for this case is equivalent

1054
00:59:36.384 --> 00:59:38.926
When implementing open set

1055
00:59:38.926 --> 00:59:42.207
the data structure that List and binary heap structure has

1056
00:59:42.207 --> 00:59:44.265
the advantages and disadvantages have been compared

1057
00:59:44.265 --> 00:59:47.362
This is strictly a theoretical comparison

1058
00:59:47.362 --> 00:59:49.730
Actual bench marking is necessary

1059
00:59:49.730 --> 00:59:52.394
to prove the quality

1060
00:59:52.394 --> 00:59:54.426
The differences between list and binary heap is

1061
00:59:54.426 --> 00:59:57.675
For list structure, the memory can be distributed

1062
00:59:57.675 --> 01:00:01.622
and binary heap is able to use fixed array

1063
01:00:01.622 --> 01:00:04.370
The cache effect that can't be 
identified from the algorithm

1064
01:00:04.370 --> 01:00:07.701
can be increased, which is a benefit

1065
01:00:07.701 --> 01:00:09.855
From the code that I have implemented

1066
01:00:09.855 --> 01:00:11.651
I did not use a fixed array

1067
01:00:11.651 --> 01:00:13.950
which is why the effect that binary heap has

1068
01:00:13.950 --> 01:00:16.048
doesn't show well

1069
01:00:16.048 --> 01:00:18.824
Therefore, for the optimization

1070
01:00:18.824 --> 01:00:21.572
theoretical points can't be the judge

1071
01:00:21.572 --> 01:00:25.370
A situation that could happen in real life 
needs to be prepared

1072
01:00:25.370 --> 01:00:29.255
and the quality should be proven through benchmarking

1073
01:00:30.949 --> 01:00:33.304
Until now we have used binary heap structure to

1074
01:00:33.304 --> 01:00:35.322
find out ways to optimize

1075
01:00:35.322 --> 01:00:38.434
A* algorithm

1076
01:00:38.434 --> 01:00:40.406
This is the end of today's lecture

1077
01:00:40.406 --> 01:00:42.450
I appreciate your participation

1078
01:00:42.450 --> 01:00:43.325
Thank you

1079
01:00:44.390 --> 01:00:46.672
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

1080
01:00:46.672 --> 01:00:48.986
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)

1081
01:00:48.986 --> 01:00:51.380
The setting of heuristic
Generally, set as minimum distance to get to the destination
Flexible responding is available in different situations through heuristic

1082
01:00:51.380 --> 01:00:53.103
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

1083
01:00:53.103 --> 01:00:54.875
Implementation of A* algorithm
two types of containers for open set and closed set

1084
01:00:54.875 --> 01:00:56.221
Open set controls nodes to calculate weight
Closed set collects nodes that don't need calculation

1085
01:00:56.221 --> 01:00:57.381
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

1086
01:00:57.381 --> 01:00:59.311
Optimization of A*pathfinding algorithm
Priority Queue container
Priority Queue container places the minimum or maximum value in the front

1087
01:00:59.311 --> 01:01:00.975
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

1088
01:01:00.975 --> 01:01:02.668
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

1089
01:01:02.668 --> 01:01:04.341
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