1
00:00:06,955 --> 00:00:08,846
Hi, welcome to this new lesson.

2
00:00:08,846 --> 00:00:12,933
We're going to continue working
with our pathfinding algorithm, and

3
00:00:12,933 --> 00:00:15,646
we're going to jump
straight into the code.

4
00:00:15,646 --> 00:00:19,334
In the past video, we actually understood
how the Astar algorithm actually operates.

5
00:00:19,334 --> 00:00:23,822
So let's just jump into code and
start seeing how to work with it.

6
00:00:23,822 --> 00:00:28,554
I'm going to continue working
with the same script that we have

7
00:00:28,554 --> 00:00:33,285
from the last session,
where we have been building the flood

8
00:00:33,285 --> 00:00:37,834
field algorithm that has
a optimal path solution.

9
00:00:37,834 --> 00:00:40,834
This is the algorithm
that we're working with.

10
00:00:40,834 --> 00:00:44,766
And what we're going to be doing here
if we just jump into the environment,

11
00:00:44,766 --> 00:00:47,786
as you can see here,
we are using still the flatfield.

12
00:00:47,786 --> 00:00:49,442
I'm going to comment that out.

13
00:00:49,442 --> 00:00:52,624
This is going to be our first
neighborhood calculation.

14
00:00:52,624 --> 00:00:57,505
We're going to use a different one this
time, which is going to be our a star,

15
00:00:57,505 --> 00:00:58,073
right?

16
00:00:58,073 --> 00:01:01,816
So let's just,
maybe we can call it out here already.

17
00:01:01,816 --> 00:01:06,467
So self.a_star_search, right?

18
00:01:06,467 --> 00:01:14,032
And we don't have that function yet,
we're going to construct that.

19
00:01:14,032 --> 00:01:19,084
So let's just go ahead just above
the flood fill because we know that's

20
00:01:19,084 --> 00:01:25,604
the area where we actually worked on
the tower search algorithm, the flatfill.

21
00:01:25,604 --> 00:01:28,684
So we're going to use a different one.

22
00:01:28,684 --> 00:01:32,273
It's going to be borrowing
a lot from the flat field, but

23
00:01:32,273 --> 00:01:36,813
it would be fundamentally different
in many other domains, right?

24
00:01:36,813 --> 00:01:40,173
So there's a few things
that we want to change or

25
00:01:40,173 --> 00:01:43,508
data that we might want to
have available to us.

26
00:01:43,508 --> 00:01:49,401
So we have already an open list, let's say
a list that it's called a stack, which we

27
00:01:49,401 --> 00:01:54,973
use as the frontier, the kind of searching
nodes that keep on growing, right?

28
00:01:54,973 --> 00:01:59,789
So we're going to keep this,
traditionally in the a star algorithm,

29
00:01:59,789 --> 00:02:03,094
this is usually called the open list,
right?

30
00:02:03,094 --> 00:02:06,072
So we're going to keep it called stack.

31
00:02:06,072 --> 00:02:10,946
But if you see this algorithm online or
you find reference to it,

32
00:02:10,946 --> 00:02:14,602
I'm going to remain maintain this name,
right?

33
00:02:14,602 --> 00:02:19,074
So let's create another
list called the closed.

34
00:02:19,074 --> 00:02:23,372
And I'm going to close
the closed_stack just for

35
00:02:23,372 --> 00:02:28,794
the sake of having some reference
to this one here, right?

36
00:02:28,794 --> 00:02:31,377
So you can refactor those things,
these two,

37
00:02:31,377 --> 00:02:35,749
if you want to be, have this algorithm
kind of more accurately connected to how

38
00:02:35,749 --> 00:02:38,146
you might find it in a textbook, right?

39
00:02:38,146 --> 00:02:40,999
So we have the stack and
the closed stack, so

40
00:02:40,999 --> 00:02:45,710
basically one will represent the areas
that we have already searched.

41
00:02:45,710 --> 00:02:49,714
The closed and the open stack would be
the areas that we're still evaluating.

42
00:02:51,574 --> 00:02:52,438
So that's great.

43
00:02:52,438 --> 00:02:55,107
We actually doing the same thing,

44
00:02:55,107 --> 00:02:59,766
adding the start node to the open,
to the stack basically.

45
00:02:59,766 --> 00:03:04,594
And we're kind of ready to go to start
writing the algorithm as we have it here.

46
00:03:05,834 --> 00:03:12,554
So we're going to do the same thing
that we've done before if running.

47
00:03:12,554 --> 00:03:17,514
So we're going to be
checking if we are running.

48
00:03:17,514 --> 00:03:20,978
If the stack is not bigger than zero,
this is also going to be the same.

49
00:03:20,978 --> 00:03:25,574
I'm going to copy paste the things that
are exactly the same from our flood fill.

50
00:03:28,594 --> 00:03:30,426
If the stack is bigger than zero here,

51
00:03:30,426 --> 00:03:33,114
we're going to be doing
something different.

52
00:03:33,114 --> 00:03:40,144
If you think about it, the current
cell here, it's going to be equal.

53
00:03:41,604 --> 00:03:46,519
Once we grow the algorithm, let's say to
its neighbors, the selection of which cell

54
00:03:46,519 --> 00:03:51,171
we're going to be growing towards, it's
going to be a specific selection, right?

55
00:03:51,171 --> 00:03:55,588
Previously we were just saying, hey,
from the stack, pick the first one

56
00:03:55,588 --> 00:03:59,664
in the order that they came,
just goes through all of them, right?

57
00:03:59,664 --> 00:04:02,914
So here,
there's going to be a major difference.

58
00:04:02,914 --> 00:04:04,390
I'm going to make a comment here, and

59
00:04:04,390 --> 00:04:07,130
I know this is going to end up in
an error if we would write it this way.

60
00:04:07,130 --> 00:04:15,274
But we're going to find the closest f,
right.

61
00:04:15,274 --> 00:04:20,117
If you remember from the past video, the f
value, which is a summation of h and g,

62
00:04:20,117 --> 00:04:24,826
meaning the cost of the path plus the
distance of the path that is remaining.

63
00:04:24,826 --> 00:04:29,935
So we're going to evaluate those values
and find the, the smallest one or

64
00:04:29,935 --> 00:04:34,072
the, or the closest one to
continue the search, right?

65
00:04:34,072 --> 00:04:36,224
So we have to pick one specific cell.

66
00:04:36,224 --> 00:04:38,016
So we're going to write a function for
that.

67
00:04:38,016 --> 00:04:40,144
Let's go to the tile.

68
00:04:40,144 --> 00:04:44,885
And in the tile I would like to add after
the parent a few attributes that we

69
00:04:44,885 --> 00:04:45,752
will need.

70
00:04:45,752 --> 00:04:51,038
So self.g,
all of them will start with zero,

71
00:04:51,038 --> 00:04:58,556
self.h, and by all means just
create comments to this, right?

72
00:04:58,556 --> 00:05:02,750
The g being the cost of the path,
h is the heuristic function,

73
00:05:02,750 --> 00:05:06,164
which in this case is
going to be distance.

74
00:05:06,164 --> 00:05:08,476
So distance to reach the goal.

75
00:05:08,476 --> 00:05:13,420
And finally f,
which is going to be also zero.

76
00:05:13,420 --> 00:05:18,604
But you can write a comment that
is the summation of g and h.

77
00:05:18,604 --> 00:05:23,264
So now a tile should have these
properties that we can use, right?

78
00:05:23,264 --> 00:05:24,896
Why do we want to use these properties?

79
00:05:24,896 --> 00:05:26,656
Because we will need a function.

80
00:05:26,656 --> 00:05:31,281
Let's just create that
function right away,

81
00:05:31,281 --> 00:05:36,224
which is going to be find closes f, right.

82
00:05:36,224 --> 00:05:39,667
So define closest f, right?

83
00:05:39,667 --> 00:05:45,643
We'll assume first of
all that we have a self,

84
00:05:45,643 --> 00:05:49,484
and we're going to pass a list.

85
00:05:51,304 --> 00:05:55,620
So if we provide a list of nodes,
we will need to

86
00:05:55,620 --> 00:06:00,816
calculate which is the smallest
f available, right?

87
00:06:00,816 --> 00:06:07,044
So we're going to create lowest f,
let's start with a very big number.

88
00:06:09,584 --> 00:06:13,092
Lowest f node, it's going to be none.

89
00:06:13,092 --> 00:06:17,180
And we've done this calculation before.

90
00:06:17,180 --> 00:06:23,843
We've done it for other things, finding
the closest particle, things of that sort.

91
00:06:23,843 --> 00:06:26,610
But in a similar fashion,
we're going to just loop through the list.

92
00:06:36,616 --> 00:06:41,800
So I'm looking through the list,

93
00:06:41,800 --> 00:06:48,413
if the node.f is smaller
than the lowest f,

94
00:06:48,413 --> 00:06:53,239
right, then the lowest f equals

95
00:06:53,239 --> 00:06:57,365
the f of that node, right?

96
00:07:06,750 --> 00:07:13,696
So here and the node would be the node
we're currently evaluating, right?

97
00:07:13,696 --> 00:07:17,178
So we're saying if the distance
is smaller than, or

98
00:07:17,178 --> 00:07:21,849
the f number is smaller than this
large number, then at that point that

99
00:07:21,849 --> 00:07:27,000
becomes the smallest number and that
becomes the node that we should check.

100
00:07:27,000 --> 00:07:28,656
But we loop through all of them.

101
00:07:28,656 --> 00:07:34,048
And this would allow us to pick out of a
list of many nodes which has the lowest f,

102
00:07:34,048 --> 00:07:34,766
right?

103
00:07:34,766 --> 00:07:42,034
So then at this point we
can return the lowest node.

104
00:07:43,254 --> 00:07:45,815
So what we're really looking for

105
00:07:45,815 --> 00:07:50,174
is the specific node that
has the lowest f, right?

106
00:07:50,174 --> 00:07:54,587
So out of having many nodes, we would end
up with one, the one with the lowest f.

107
00:07:54,587 --> 00:07:59,435
So this calculation here, which before,
if you look at the flat field,

108
00:07:59,435 --> 00:08:04,694
was selecting the first item, now it's
going to be fulfilled by this function.

109
00:08:04,694 --> 00:08:07,648
Out of a list make sure you
pick the one with the lowest.

110
00:08:07,648 --> 00:08:12,129
We haven't really yet
assigned a g score or

111
00:08:12,129 --> 00:08:15,498
an f score to our nodes, right?

112
00:08:15,498 --> 00:08:19,812
So for now it's kind of going to work
similar in the sense that the value would

113
00:08:19,812 --> 00:08:20,520
be zero.

114
00:08:20,520 --> 00:08:24,904
But we will do that in
the rest of the algorithms.

115
00:08:24,904 --> 00:08:27,596
So let's just do this for now.

116
00:08:27,596 --> 00:08:32,691
We're going to find the closest,
and we're searching for

117
00:08:32,691 --> 00:08:36,205
the closest within the stack, right?

118
00:08:36,205 --> 00:08:42,828
The stack is kind of the open list and
there we go, right?

119
00:08:42,828 --> 00:08:43,858
So the next part,

120
00:08:43,858 --> 00:08:47,915
it's going to remain relatively similar
to the flood fill is this part of

121
00:08:47,915 --> 00:08:52,333
the algorithm where we're actually
checking how we reach the end, right?

122
00:08:52,333 --> 00:08:54,284
Let's just copy paste,
paste this for a moment.

123
00:08:55,464 --> 00:08:59,468
And what we're saying here is that if

124
00:08:59,468 --> 00:09:04,246
the current cell is
equal to the final node,

125
00:09:04,246 --> 00:09:09,928
we reach the goal,
we stop running the algorithm and

126
00:09:09,928 --> 00:09:14,080
we can reconstruct the path, right?

127
00:09:14,080 --> 00:09:17,529
Let's do the following,

128
00:09:17,529 --> 00:09:23,171
which is we're going to,
from the open set,

129
00:09:23,171 --> 00:09:29,114
we're going to remove the cell self.stack.

130
00:09:29,114 --> 00:09:33,655
So from the stack,
let's just remove, you see,

131
00:09:33,655 --> 00:09:38,089
because here we're not
using the pop function,

132
00:09:38,089 --> 00:09:43,218
which automatically removes
the entry from the list.

133
00:09:43,218 --> 00:09:46,225
We're going to remove the current cell so

134
00:09:46,225 --> 00:09:50,822
that we don't end up with always
some nodes that are there.

135
00:09:50,822 --> 00:09:56,542
We need to make sure that
list starts becoming smaller,

136
00:09:56,542 --> 00:10:01,286
and we're going to add
that to the closed stack,

137
00:10:01,286 --> 00:10:06,530
which is equivalent to the visited nodes,
right?

138
00:10:06,530 --> 00:10:13,848
So for the closed stack, we're going to
append the current cell, right?

139
00:10:13,848 --> 00:10:17,989
So we're transferring the cell out
of the openstack to the closed

140
00:10:17,989 --> 00:10:20,184
stack if we evaluate it, right?

141
00:10:20,184 --> 00:10:23,001
And this is only happening if
we haven't reached the end goal,

142
00:10:23,001 --> 00:10:26,424
which is the moment where
the algorithm actually stops.

143
00:10:26,424 --> 00:10:30,223
So let's go through now
the neighborhood calculation again,

144
00:10:30,223 --> 00:10:33,848
very similar to what we've
done here in the flood field.

145
00:10:33,848 --> 00:10:41,186
Let's just go through for a neighbor

146
00:10:41,186 --> 00:10:50,664
in current_cell.get_neighbors, right.

147
00:10:52,804 --> 00:10:56,947
So the first thing we want to do,
similarly,

148
00:10:56,947 --> 00:11:02,289
as we have done before,
we're going to say if the neighbor,

149
00:11:02,289 --> 00:11:06,213
in this case, in, if we're going to check,

150
00:11:06,213 --> 00:11:11,154
is it in the closest tag or
is it an obstacle, right?

151
00:11:11,154 --> 00:11:15,186
In that case, continue,
just like skip this one.

152
00:11:15,186 --> 00:11:20,654
So we're going to say self.closed_stack or

153
00:11:20,654 --> 00:11:25,634
sorry, in close_stack, right.

154
00:11:25,634 --> 00:11:30,674
Or neighbor.is, I believe that

155
00:11:30,674 --> 00:11:37,874
is obstacle was written
a little bit like this.

156
00:11:39,454 --> 00:11:42,502
Let's double check how
we did the obstacle.

157
00:11:42,502 --> 00:11:45,254
Yeah, this is a function.

158
00:11:45,254 --> 00:11:47,246
There we go.

159
00:11:47,246 --> 00:11:52,325
So we're saying if this particular
neighbor is in fact within

160
00:11:52,325 --> 00:11:57,514
the closed stack or is an obstacle,
let's just say continue.

161
00:11:59,144 --> 00:12:03,079
And continue is a keyword that maybe we
haven't used too much, but it's a way of

162
00:12:03,079 --> 00:12:07,400
like breaking from this for loop, meaning
that the for loop can continue otherwise.

163
00:12:07,400 --> 00:12:10,786
But if it reaches any of these conditions,

164
00:12:10,786 --> 00:12:16,064
it would skip this,
this particular iteration, right?

165
00:12:16,064 --> 00:12:22,881
So let's write a variable
called tentative g and

166
00:12:22,881 --> 00:12:28,374
the tentative g is this cellscurrent.

167
00:12:30,234 --> 00:12:35,423
Cells g, meaning that the cell that we're
currently evaluating has probably like,

168
00:12:35,423 --> 00:12:38,714
let's start with g,
which is a cost of zero.

169
00:12:38,714 --> 00:12:40,986
We're going to add one to that.

170
00:12:40,986 --> 00:12:44,764
So as we kind of grow the search,
we're going to be adding,

171
00:12:44,764 --> 00:12:48,323
this is the way in which we
keep growing the value of g.

172
00:12:48,323 --> 00:12:50,545
So every step we're
going to be adding one.

173
00:13:00,521 --> 00:13:06,137
And we're going to create a variable,
say new path equals false,

174
00:13:06,137 --> 00:13:10,122
which we're going to be
using within the loop.

175
00:13:10,122 --> 00:13:13,130
So let's just wait a moment and
we're going to be using this.

176
00:13:13,130 --> 00:13:18,125
This is something that is
going to just allow us

177
00:13:18,125 --> 00:13:23,260
to signal if we have found a new path,
right?

178
00:13:23,260 --> 00:13:26,934
So if the neighbor in self.stack.

179
00:13:31,674 --> 00:13:36,522
So if the neighbor that we're
currently evaluating, right,

180
00:13:36,522 --> 00:13:40,644
is part of the stack,
we're going to do the following.

181
00:13:40,644 --> 00:13:44,174
We're going to do neighbor.g
equals ten to tg,

182
00:13:53,723 --> 00:13:58,975
Right, so we're assigning to that neighbor
the tentative g and new path equal true.

183
00:14:04,551 --> 00:14:06,294
Right.

184
00:14:06,294 --> 00:14:13,583
And else, meaning that the, if the
neighbor is not in the OpenStack right,

185
00:14:21,558 --> 00:14:25,910
We will actually append it to the stack.

186
00:14:25,910 --> 00:14:29,599
So we're doing the same thing for both
of them, but we want to make sure that

187
00:14:29,599 --> 00:14:32,456
if we're evaluating a neighbor
that is not in the stack,

188
00:14:32,456 --> 00:14:34,442
we're adding it to the stack, right.

189
00:14:34,442 --> 00:14:44,020
So we would say the same thing here, Plus,

190
00:14:53,680 --> 00:14:54,320
Right.

191
00:14:54,320 --> 00:14:57,987
And finally now,
if we have found a new path, so

192
00:14:57,987 --> 00:15:02,392
only in the case that if we
have that path that we marked.

193
00:15:02,392 --> 00:15:08,835
So if new path has been found,
let's assign some of the values that

194
00:15:08,835 --> 00:15:15,036
we've been discussing, the h and
the calculation of g plus h.

195
00:15:15,036 --> 00:15:21,472
So neighbor.h, which if you remember
the h is the distance, or the heuristic,

196
00:15:21,472 --> 00:15:26,924
it's going to be the distance from
that neighbor to the end node.

197
00:15:26,924 --> 00:15:29,708
So we want to say distance.

198
00:15:29,708 --> 00:15:33,572
And a lot of algorithms actually use
different distance calculations that could

199
00:15:33,572 --> 00:15:34,676
be more efficient.

200
00:15:34,676 --> 00:15:38,344
We're going to use the inbuilt
distance that processing offer us.

201
00:15:40,324 --> 00:15:49,174
Neighbor.position.x, neighbor.position.y,

202
00:15:49,174 --> 00:15:55,139
self.end_node.position.x and

203
00:15:55,139 --> 00:16:02,934
feel free to just break
this into two lines.

204
00:16:02,934 --> 00:16:04,474
Find necessary.

205
00:16:05,854 --> 00:16:11,204
So the distance between the neighbor,
which is the current

206
00:16:11,204 --> 00:16:16,294
cell we're evaluating,
and the end node, right.

207
00:16:16,294 --> 00:16:19,054
So that is the h, the distance, right.

208
00:16:19,054 --> 00:16:24,485
And the neighbor.f

209
00:16:24,485 --> 00:16:30,237
would be neighbor.g

210
00:16:30,237 --> 00:16:35,674
plus neighbor.h.

211
00:16:37,854 --> 00:16:42,669
So this is the part where we
have already calculated the g,

212
00:16:42,669 --> 00:16:47,726
which is the cost of the path,
how many steps have we taken?

213
00:16:47,726 --> 00:16:52,748
At this point we also calculate the h,
which is the distance remaining and

214
00:16:52,748 --> 00:16:56,222
the f would be the addition of those two,
right.

215
00:16:56,222 --> 00:16:57,394
G plus h.

216
00:16:58,774 --> 00:17:03,382
And then at this point we could say
that the parent is the current cell.

217
00:17:03,382 --> 00:17:08,031
So neighbor parent

218
00:17:08,031 --> 00:17:13,554
equals current cell.

219
00:17:15,854 --> 00:17:20,405
Well, there's one final else that
we might want to include, and

220
00:17:20,405 --> 00:17:22,154
this is maybe optional.

221
00:17:23,194 --> 00:17:24,722
I'm going to think it's here.

222
00:17:24,722 --> 00:17:25,814
Let's just see.

223
00:17:28,554 --> 00:17:33,411
We're going to say print

224
00:17:33,411 --> 00:17:37,756
line No solution and

225
00:17:37,756 --> 00:17:43,894
self running equals false.

226
00:17:45,194 --> 00:17:46,746
Yeah, so basically this is it.

227
00:17:46,746 --> 00:17:47,906
We have two new functions.

228
00:17:47,906 --> 00:17:52,438
The start, the a star search,
and the find closest,

229
00:17:52,438 --> 00:17:56,656
which is used within the a star search,
right.

230
00:17:56,656 --> 00:18:01,295
And there's a particular point where
we actually calculate the distance and

231
00:18:01,295 --> 00:18:03,444
mainly this equation is used here.

232
00:18:04,864 --> 00:18:09,778
But more importantly, when we
are selecting which is the next cell to

233
00:18:09,778 --> 00:18:15,648
evaluate, we have to do it by searching
the smallest f or the closest f, right.

234
00:18:15,648 --> 00:18:18,944
Let's see what errors do we have?

235
00:18:21,140 --> 00:18:21,733
Well.
So

236
00:18:21,733 --> 00:18:24,396
it's actually working already very well.

237
00:18:24,396 --> 00:18:28,623
So as you can see,
the path reconstruction,

238
00:18:28,623 --> 00:18:33,297
because we're using
the same parenting system,

239
00:18:33,297 --> 00:18:38,364
the parent, it's achieved here,
it still works.

240
00:18:38,364 --> 00:18:43,292
The obstacle detection, it's also working
because we're including that here.

241
00:18:43,292 --> 00:18:49,181
We're avoiding cells
that contain obstacles.

242
00:18:49,181 --> 00:18:54,352
What we are not visualizing currently,

243
00:18:54,352 --> 00:18:59,368
like if you think about it, we have been

244
00:18:59,368 --> 00:19:06,667
visualizing the stack which
remains being the open set,

245
00:19:06,667 --> 00:19:11,858
which is demonstrated with CN, right?

246
00:19:11,858 --> 00:19:13,896
With the CN color we have the open set.

247
00:19:13,896 --> 00:19:18,066
So there was search going in this
direction and then it changed its mind and

248
00:19:18,066 --> 00:19:19,084
it went this way.

249
00:19:21,304 --> 00:19:24,105
And that's all good, but
we would like to visit,

250
00:19:24,105 --> 00:19:28,455
probably these cells here were visited,
so they were part of the closed tag.

251
00:19:28,455 --> 00:19:32,085
So we're actually going to spend
a bit more time really understanding

252
00:19:32,085 --> 00:19:35,664
the algorithm in the next few
videos through some visualization.

253
00:19:35,664 --> 00:19:38,960
Like adding some of the text
on the algorithm, but

254
00:19:38,960 --> 00:19:44,582
also being able to paint the cells that
are being evaluated with what data, right?

255
00:19:44,582 --> 00:19:47,174
So I'll see you in the next video.

256
00:19:47,174 --> 00:19:49,510
Yeah, we're going to continue
looking at that data then.

257
00:19:49,510 --> 00:19:50,010
See you then.