1
00:00:00,000 --> 00:00:05,509
Hi, welcome to this third video

2
00:00:05,509 --> 00:00:10,413
in our pathfinding series.

3
00:00:10,413 --> 00:00:12,323
This is our project four,
and in this video,

4
00:00:12,323 --> 00:00:14,650
we're going to be looking at
how do we access neighbors?

5
00:00:14,650 --> 00:00:17,055
This is, again, a recurring topic,

6
00:00:17,055 --> 00:00:21,652
something that we covered in different
places throughout this course.

7
00:00:21,652 --> 00:00:26,398
But we're going to revisit it because it's
a kind of fundamental computation that we

8
00:00:26,398 --> 00:00:30,284
need to undo in order to kind of
do the pathfinding project, right?

9
00:00:30,284 --> 00:00:34,548
So finding neighbors in this case is
going to be when we have a start node or

10
00:00:34,548 --> 00:00:35,792
a particular node.

11
00:00:35,792 --> 00:00:38,580
We're going to start with the mouse so
to make sure that actually it works.

12
00:00:38,580 --> 00:00:41,253
For every location in the grid,

13
00:00:41,253 --> 00:00:46,504
each cell should have information
of adjacent cells, right?

14
00:00:46,504 --> 00:00:48,818
So if you think of this as a graph,

15
00:00:48,818 --> 00:00:54,386
each cell should have a connecting kind
of information to other cells, right?

16
00:00:54,386 --> 00:00:58,052
So that means that the cell
needs to understand

17
00:00:58,052 --> 00:01:00,782
its own position in a collection.

18
00:01:00,782 --> 00:01:04,616
So we're going to be passing information
to the cell itself to be able to

19
00:01:04,616 --> 00:01:06,874
understand this information, right?

20
00:01:08,654 --> 00:01:11,284
The kind of equation that
we want to calculate,

21
00:01:11,284 --> 00:01:15,102
especially when we're looking at
this nested list configuration,

22
00:01:15,102 --> 00:01:18,534
is that your neighbor above you,
it's going to be a y-1.

23
00:01:18,534 --> 00:01:24,975
On the left is going to be x-1, below is
going to be y+1, and on the right, x+1.

24
00:01:24,975 --> 00:01:28,557
Understanding that the x and
y is the coordinate that we're sampling,

25
00:01:28,557 --> 00:01:31,853
meaning the point,
let's say in this case, the mouse, right?

26
00:01:31,853 --> 00:01:35,948
So whenever we have those
neighbors available to us,

27
00:01:35,948 --> 00:01:40,862
we will append them to a list of
neighbors, and we want to be able to

28
00:01:40,862 --> 00:01:45,694
have each cell in the system
have this information,, right?

29
00:01:45,694 --> 00:01:49,349
What I was mentioning is that
we could start thinking and

30
00:01:49,349 --> 00:01:54,327
reflecting on how the system could be
extrapolated also to other kind of data

31
00:01:54,327 --> 00:01:59,018
structures, or think of not necessarily
a grid, but perhaps a graph.

32
00:01:59,018 --> 00:02:03,955
We are looking at a grid as a graph,
and how those neighbors are kind of

33
00:02:03,955 --> 00:02:08,553
connected to each other,
which are the edges on a graph system,

34
00:02:08,553 --> 00:02:14,022
is the way in which you can access
this neighborhood relationship, right?

35
00:02:14,022 --> 00:02:16,849
But you could have a graph
that is much more arbitrary,

36
00:02:16,849 --> 00:02:19,439
that doesn't have
necessarily four neighbors.

37
00:02:19,439 --> 00:02:21,100
There could be more neighbors,
there could be less neighbors.

38
00:02:21,100 --> 00:02:24,267
There could be no neighbors on some nodes,
right?

39
00:02:24,267 --> 00:02:28,950
So I wanted you to start thinking of
how this algorithm could be used in

40
00:02:28,950 --> 00:02:30,500
different contexts.

41
00:02:30,500 --> 00:02:32,615
And many times when you
kind of research pathfinding,

42
00:02:32,615 --> 00:02:35,020
you'll see that it's actually
explained through graphs.

43
00:02:35,020 --> 00:02:38,157
In our case,
it's going to be a bit more graphing and

44
00:02:38,157 --> 00:02:41,457
straightforward to do it within this grid,
right?

45
00:02:41,457 --> 00:02:44,824
But let's start writing this kind
of neighborhood calculation,

46
00:02:44,824 --> 00:02:48,745
especially looking at how a tile would
actually get the information we need.

47
00:02:48,745 --> 00:02:50,899
So we're going to jump into the code.

48
00:02:50,899 --> 00:02:54,207
We are continuing with
the code that we have started,

49
00:02:54,207 --> 00:02:57,075
which is we have
a customizable environment,

50
00:02:57,075 --> 00:03:01,884
something that we can paint with our
left mouse and also delete walls.

51
00:03:01,884 --> 00:03:04,724
And I wanns go back all
the way to the tile here.

52
00:03:04,724 --> 00:03:07,300
Currently, the tile knows
very little about the world.

53
00:03:07,300 --> 00:03:08,620
It knows its own position.

54
00:03:08,620 --> 00:03:12,670
It knows which size it has and
its own type.

55
00:03:12,670 --> 00:03:15,892
But let's expand the information
that the tile has.

56
00:03:15,892 --> 00:03:19,374
Because if you think about it,
a neighbor for

57
00:03:19,374 --> 00:03:23,680
a tile first needs to be in
awareness that, hey, well,

58
00:03:23,680 --> 00:03:28,629
maybe I need to know how many columns and
rows are in the world, or

59
00:03:28,629 --> 00:03:32,685
maybe, which is my position in that world,
right?

60
00:03:32,685 --> 00:03:35,100
And also what is the total
collection of tiles, right?

61
00:03:35,100 --> 00:03:36,988
So let's just provide this information.

62
00:03:36,988 --> 00:03:39,756
If we realize that some of that
information is not necessary,

63
00:03:39,756 --> 00:03:41,356
we can backtrack and delete that.

64
00:03:41,356 --> 00:03:45,838
But let's think that we want to
provide the information of columns,

65
00:03:47,254 --> 00:03:52,281
The information of rows, right?

66
00:03:52,281 --> 00:03:54,056
I'm going to call x and y.

67
00:03:54,056 --> 00:03:58,913
It's going to be the current
index of the tile, so

68
00:03:58,913 --> 00:04:05,238
the tile should know its own index,
and all_cells, right?

69
00:04:05,238 --> 00:04:09,041
So the constructor of our tile
has changed quite drastically,

70
00:04:09,041 --> 00:04:10,774
has a lot more information.

71
00:04:10,774 --> 00:04:15,894
Let's just create

72
00:04:15,894 --> 00:04:23,577
local variables for those.

73
00:04:38,264 --> 00:04:40,769
Right, so we have cells,
columns, rows, ,x and y, right?

74
00:04:40,769 --> 00:04:42,730
So these are all the new
pieces of information.

75
00:04:42,730 --> 00:04:47,813
If we would try to run this, we're
going to run into an error because our

76
00:04:47,813 --> 00:04:53,174
environment, it constructs the cells
right here, new_tile = tile.

77
00:04:53,174 --> 00:04:54,636
It just provides three arguments.

78
00:04:54,636 --> 00:04:58,380
So let's provide the arguments
that were missing, right?

79
00:04:58,380 --> 00:05:02,232
So we do have self.columns,

80
00:05:02,232 --> 00:05:08,713
self.rows as the columns and
rows of the system.

81
00:05:08,713 --> 00:05:14,243
We also have, in the loop,
we know that i and

82
00:05:14,243 --> 00:05:20,684
j refer to the index of that
cell in the collection.

83
00:05:20,684 --> 00:05:29,442
And finally, self.cells are basically
all the other cells, right?

84
00:05:29,442 --> 00:05:32,485
So in order to access the list,

85
00:05:32,485 --> 00:05:38,454
a tile would have to go through
this collection, right?

86
00:05:38,454 --> 00:05:43,214
So knowing your index, most importantly,
knowing your index and

87
00:05:43,214 --> 00:05:48,784
the cells, you could kind of derive
your index plus 1, minus 1, and so on.

88
00:05:48,784 --> 00:05:49,810
So we can actually
calculate the neighbors.

89
00:05:49,810 --> 00:05:53,981
These columns and
rows is just to know that we are within

90
00:05:53,981 --> 00:05:57,887
the bounds of the world or
kind of how big the grid is.

91
00:05:57,887 --> 00:06:02,276
So let's go back into the tile.

92
00:06:02,276 --> 00:06:05,557
I mean, and
here you could have thought, well,

93
00:06:05,557 --> 00:06:09,011
could I do this calculation
from the environment?

94
00:06:09,011 --> 00:06:12,051
It could be done, but I like thinking
from the perspective of the cell,

95
00:06:12,051 --> 00:06:13,684
really kind of thinking bottom-up.

96
00:06:13,684 --> 00:06:20,305
Like, what would be the capacity of
one cell to identify its neighbors?

97
00:06:20,305 --> 00:06:26,162
So let's write a get_neighbors

98
00:06:26,162 --> 00:06:32,021
function, so get_neighbors.

99
00:06:33,069 --> 00:06:39,074
And in the get_neighbors, we're going to
create an empty list of neighbors.

100
00:06:39,074 --> 00:06:44,597
And we are going to first review

101
00:06:44,597 --> 00:06:52,037
if the self.x is bigger than 0, right?

102
00:06:52,037 --> 00:06:57,159
Because we want to make sure that
the index, we're checking these indices

103
00:06:57,159 --> 00:07:02,130
against the size of the world,
zero being the lowest there is, right?

104
00:07:02,130 --> 00:07:07,491
So let's just basically want to

105
00:07:07,491 --> 00:07:12,240
append to this empty list.

106
00:07:12,240 --> 00:07:12,892
What do we want to append?

107
00:07:12,892 --> 00:07:16,566
We want to append one entry, another node,

108
00:07:16,566 --> 00:07:21,374
basically self.all_cells,
which is from the list.

109
00:07:21,374 --> 00:07:23,778
So we access the list now
that we have access to.

110
00:07:23,778 --> 00:07:29,544
And if we would say x, or sorry,

111
00:07:29,544 --> 00:07:35,098
[self.x], [self.y],

112
00:07:35,098 --> 00:07:42,744
that index is who we are as a cell, right?

113
00:07:42,744 --> 00:07:49,924
So the neighbor in x needs to be
a -1 in this direction, right?

114
00:07:52,404 --> 00:07:57,245
Because by definition,
the cell in which we are working, right,

115
00:07:57,245 --> 00:08:02,963
its own index is defined by x and y,
and the collection is all_cells, right?

116
00:08:02,963 --> 00:08:07,275
So the x and y index would
represent who we are as a cell.

117
00:08:07,275 --> 00:08:10,224
The -1 would represent
our adjacent neighbor.

118
00:08:10,224 --> 00:08:14,667
So let's copy this line and
let's go one by one checking the four

119
00:08:14,667 --> 00:08:19,129
neighbors that we want to evaluate for
this situation, right?

120
00:08:19,129 --> 00:08:23,668
So the x in the second one needs
to be smaller than the columns,

121
00:08:23,668 --> 00:08:26,650
the number of columns, so self.cols.

122
00:08:26,650 --> 00:08:31,572
And we're going to do -1 here
because we want to make sure

123
00:08:31,572 --> 00:08:34,828
that it's not the size of the world.

124
00:08:34,828 --> 00:08:37,829
As you can see here,
we're doing bigger than 0.

125
00:08:37,829 --> 00:08:40,498
In the size of the world,

126
00:08:40,498 --> 00:08:46,613
we want to do smaller than
the number of columns minus 1.

127
00:08:46,613 --> 00:08:50,650
And here the neighbor in this
case would be a plus 1, right?

128
00:08:50,650 --> 00:08:54,379
Because this plus 1,
we need to stop one short and ask for

129
00:08:54,379 --> 00:08:59,136
a neighbor to the right, and
that could give us our rightmost neighbor.

130
00:08:59,136 --> 00:09:04,595
Understanding that the last cell on
the row would not have a neighbor

131
00:09:04,595 --> 00:09:10,554
to the right, right, because we ran
out of neighbors in that direction.

132
00:09:10,554 --> 00:09:12,029
Let's copy the first one,

133
00:09:12,029 --> 00:09:15,504
which is a little bit more closer
to what we're going to write now.

134
00:09:15,504 --> 00:09:17,509
The next one has to do with y.

135
00:09:17,509 --> 00:09:22,590
So if self.y is bigger than 0,

136
00:09:22,590 --> 00:09:25,233
we will append,

137
00:09:27,636 --> 00:09:32,047
The y-1 neighbor, right?

138
00:09:32,047 --> 00:09:34,534
So this is the neighbor above us.

139
00:09:34,534 --> 00:09:38,100
And then finally,
I'm going to copy the second line,

140
00:09:38,100 --> 00:09:42,326
which is closer to what we're
going to write for the final line.

141
00:09:44,765 --> 00:09:48,786
If the y is smaller than

142
00:09:48,786 --> 00:09:53,866
the number of rows minus 1,

143
00:09:53,866 --> 00:09:58,735
let's append the neighbor

144
00:09:58,735 --> 00:10:03,194
that has y+1, right?

145
00:10:03,194 --> 00:10:07,952
So again, the diagram here suggests
that we have four neighbors.

146
00:10:07,952 --> 00:10:10,298
All of them are based on their indices,
right?

147
00:10:10,298 --> 00:10:14,209
So the neighbors are defined
by their index numbers.

148
00:10:14,209 --> 00:10:19,436
So let's return, This new list,

149
00:10:24,545 --> 00:10:27,309
Of neighbors, right?

150
00:10:27,309 --> 00:10:27,843
Yeah, so this is great.

151
00:10:27,843 --> 00:10:33,587
Now, each cell can calculate some
neighbors based on indices, right,

152
00:10:33,587 --> 00:10:38,684
and we should be able to draw them
somehow in the screen, right?

153
00:10:38,684 --> 00:10:42,282
So how would we access the neighbors?

154
00:10:42,282 --> 00:10:46,564
Well, let's create a function from
the environment that we can call.

155
00:10:46,564 --> 00:10:51,412
So similarly to how we were painting
a cell, we can do a function that

156
00:10:51,412 --> 00:10:56,275
would be like, let's draw,
let's paint the neighbors, right?

157
00:10:56,275 --> 00:11:00,048
Collect the neighbors and

158
00:11:00,048 --> 00:11:06,055
draw them in the screen somehow, right?

159
00:11:06,055 --> 00:11:09,086
We could do them up here as well.

160
00:11:09,086 --> 00:11:11,713
I think that we are leaving
behind this calculation.

161
00:11:11,713 --> 00:11:15,288
So let's just do here a function
that we're going to be

162
00:11:15,288 --> 00:11:17,247
able to call from the mouse.

163
00:11:17,247 --> 00:11:20,822
So draw_neighbors,

164
00:11:24,803 --> 00:11:28,270
(self.x,y).

165
00:11:28,270 --> 00:11:33,615
So this is going to be testing with
the mouse position, first of all.

166
00:11:33,615 --> 00:11:37,857
So, What we

167
00:11:37,857 --> 00:11:42,764
want here is first collect the cell,
right?

168
00:11:42,764 --> 00:11:46,591
Let's collect the cell,

169
00:11:49,618 --> 00:11:54,944
self.get_cell.

170
00:11:55,987 --> 00:12:01,458
So this is going to be the, The cell
that we are kind of highlighting, right?

171
00:12:01,458 --> 00:12:06,102
And it would be nice to
have a way of drawing

172
00:12:06,102 --> 00:12:11,031
the cells with a particular color, right?

173
00:12:11,031 --> 00:12:16,366
Like what if the cells would
have a method that would draw

174
00:12:16,366 --> 00:12:21,823
themselves in a way but
similar to the display function?

175
00:12:21,823 --> 00:12:26,057
So something like display, but maybe
when we want to highlight them, right?

176
00:12:26,057 --> 00:12:27,608
So let's do that.

177
00:12:27,608 --> 00:12:31,659
It's kind of a very simple function, but

178
00:12:31,659 --> 00:12:36,291
I realized that it's
actually pretty useful,

179
00:12:36,291 --> 00:12:41,406
which I'm going to call
define display_highlight.

180
00:12:41,406 --> 00:12:45,963
And with this function,
we can provide a color.

181
00:12:45,963 --> 00:12:49,037
How do you want to highlight this cell?

182
00:12:49,037 --> 00:12:53,499
We can say the fill,
it's going to be the color provided.

183
00:12:53,499 --> 00:12:58,299
And the display is basically
the same display that we have

184
00:12:58,299 --> 00:13:02,104
been using in the display function, right?

185
00:13:02,104 --> 00:13:06,896
So what this display highlight is kind
of a temporary function to highlight

186
00:13:06,896 --> 00:13:11,456
some data, right, would allow us to
pass a color, say color blue, and

187
00:13:11,456 --> 00:13:16,647
paint this cell blue or red or whatever
color we want just when we need it, right?

188
00:13:16,647 --> 00:13:20,805
And we're not going to be executing it for
all cells at all times, but

189
00:13:20,805 --> 00:13:25,499
it's incredibly useful to be able to
highlight or draw them differently.

190
00:13:25,499 --> 00:13:30,244
So let's use this function
that we just created here.

191
00:13:30,244 --> 00:13:36,007
So if I get the cell,
which is the mouse cell,

192
00:13:36,007 --> 00:13:39,902
let's create a color.

193
00:13:39,902 --> 00:13:47,245
We're going to do the color.

194
00:13:47,245 --> 00:13:50,572
Let's do a red color just to
see if this function works.

195
00:13:50,572 --> 00:13:55,363
And the cell that we got,
which is where the mouse is holding,

196
00:13:55,363 --> 00:14:01,004
let's do this function,
display_highlight with the color, right?

197
00:14:01,004 --> 00:14:03,605
So we haven't drawn the neighbors yet.

198
00:14:03,605 --> 00:14:07,548
We're first getting the cell
where the mouse is, right?

199
00:14:07,548 --> 00:14:10,453
We're going to draw
the neighbors in a minute.

200
00:14:10,453 --> 00:14:15,207
Now, just to check if we're not running
into errors, let's call this function.

201
00:14:15,207 --> 00:14:17,604
Let's remove these comments.

202
00:14:17,604 --> 00:14:22,696
For a moment, I'm going to,
Comment out our capacity

203
00:14:22,696 --> 00:14:27,407
to paint walls just to kind of
test our neighbor calculation.

204
00:14:27,407 --> 00:14:30,428
So my_environment,

205
00:14:32,780 --> 00:14:41,411
.draw_neighbors(mousex, mousey), right?

206
00:14:41,411 --> 00:14:45,455
So let's see what we have so far.

207
00:14:45,455 --> 00:14:49,341
All right,

208
00:14:49,341 --> 00:14:54,394
we're running

209
00:14:54,394 --> 00:14:59,445
into an error,

210
00:14:59,445 --> 00:15:04,387
let's see.

211
00:15:04,387 --> 00:15:06,600
Okay, so
there was a problem with indentation.

212
00:15:06,600 --> 00:15:09,584
But as you can see, we press now and
we can highlight a cell, right?

213
00:15:09,584 --> 00:15:12,243
So that's pretty useful.

214
00:15:12,243 --> 00:15:14,793
The neighborhood,
basically we get the cell, but

215
00:15:14,793 --> 00:15:18,008
now we actually have the function
to pick the neighbors as well.

216
00:15:18,008 --> 00:15:19,183
So what would be the neighbors?

217
00:15:19,183 --> 00:15:22,664
So we have neighbors,

218
00:15:25,390 --> 00:15:30,174
= cell.get_neighbors.

219
00:15:32,679 --> 00:15:34,787
We know that's a list.

220
00:15:34,787 --> 00:15:40,724
The returning value from that calculation
is a list of up to four neighbors, right?

221
00:15:40,724 --> 00:15:44,975
So let's say for n, or short for

222
00:15:44,975 --> 00:15:48,604
neighbor, in neighbors.

223
00:15:48,604 --> 00:15:54,063
Let's do the same thing that
we did to this cell here.

224
00:15:54,063 --> 00:15:58,042
Let's display it with a highlighted color,
right?

225
00:15:58,042 --> 00:16:02,601
So in this case,
the cell in question is n,

226
00:16:02,601 --> 00:16:08,693
which is the entity within
the neighbor's collection.

227
00:16:08,693 --> 00:16:10,101
And let's just do a different color.

228
00:16:10,101 --> 00:16:11,276
Let's do blue.

229
00:16:15,459 --> 00:16:20,795
Right, so we're saying display
the cell you're on top of as a mouse,

230
00:16:20,795 --> 00:16:24,061
right, and display your four neighbors.

231
00:16:24,061 --> 00:16:25,286
And there we go.

232
00:16:25,286 --> 00:16:30,715
So this is kind of a very slow and kind of
way to kind of double-check that we are,

233
00:16:30,715 --> 00:16:34,848
in fact, doing a neighbor
calculation that works, right,

234
00:16:34,848 --> 00:16:39,085
that we can not only grab a cell,
but grab the neighbor cells.

235
00:16:39,085 --> 00:16:42,835
And that basically this is telling
us that the cell has access or

236
00:16:42,835 --> 00:16:45,470
information about its neighboring cells.

237
00:16:45,470 --> 00:16:47,557
And this is going to be
the foundation of the algorithm.

238
00:16:47,557 --> 00:16:51,617
So with this in mind and having this
working well, we'll leave it here and

239
00:16:51,617 --> 00:16:53,394
I'll see you in the next video.