1
00:00:05,610 --> 00:00:08,210
Hi, welcome to this new video.

2
00:00:08,210 --> 00:00:09,770
We're going to continue working

3
00:00:09,770 --> 00:00:11,630
on our path-finding series,

4
00:00:11,630 --> 00:00:13,950
and this time around
in this video,

5
00:00:13,950 --> 00:00:15,130
we're going to be
looking at how to

6
00:00:15,130 --> 00:00:17,105
calculate the optimal path.

7
00:00:17,105 --> 00:00:20,250
Let's start by understanding
what we have achieved.

8
00:00:20,250 --> 00:00:23,735
We have been working with a
flat field algorithm that

9
00:00:23,735 --> 00:00:27,290
grows a search area,

10
00:00:27,290 --> 00:00:29,590
as you can see in the
blue cells on the right,

11
00:00:29,590 --> 00:00:33,190
and a frontier that keeps
looking for this end node.

12
00:00:33,190 --> 00:00:36,230
When one of the frontier nodes

13
00:00:36,230 --> 00:00:39,290
overlaps with the end node,

14
00:00:39,290 --> 00:00:43,970
we know that we have found
a path or there is a path,

15
00:00:43,970 --> 00:00:47,930
in fact, to reach that end
note from our start point.

16
00:00:47,930 --> 00:00:50,570
But we still need to
figure out how to kind of

17
00:00:50,570 --> 00:00:54,840
reconstruct the optimal path
back to the start note.

18
00:00:54,840 --> 00:00:57,250
This problem is something that

19
00:00:57,250 --> 00:01:00,410
we need to do a
second calculation,

20
00:01:00,410 --> 00:01:01,950
basically, a second
loop where we're going

21
00:01:01,950 --> 00:01:06,360
to trace the path
that took us there.

22
00:01:06,360 --> 00:01:08,050
We need to be able to store

23
00:01:08,050 --> 00:01:10,290
some information in all
the cells of what is

24
00:01:10,290 --> 00:01:12,250
the cell that took me to

25
00:01:12,250 --> 00:01:15,115
the point in which I'm
evaluating currently.

26
00:01:15,115 --> 00:01:17,550
As long as each cell has,

27
00:01:17,550 --> 00:01:19,770
let's say, we're going to
call that a parent cell,

28
00:01:19,770 --> 00:01:22,375
a cell that took
me to that cell,

29
00:01:22,375 --> 00:01:24,075
once we reach the Bengal,

30
00:01:24,075 --> 00:01:26,330
that goal would be
able to trace back

31
00:01:26,330 --> 00:01:30,370
its path to the starting node.

32
00:01:30,800 --> 00:01:33,015
That's what we're
going to be doing.

33
00:01:33,015 --> 00:01:35,010
We're going to be
writing a function

34
00:01:35,010 --> 00:01:37,070
that is going to be
reconstruct path.

35
00:01:37,070 --> 00:01:39,850
That's going to
use a while loop,

36
00:01:39,850 --> 00:01:41,590
where we're going
to use this new

37
00:01:41,590 --> 00:01:42,850
property that we're
going to create,

38
00:01:42,850 --> 00:01:44,930
which is the parenting property

39
00:01:44,930 --> 00:01:47,930
that we basically
start building up

40
00:01:47,930 --> 00:01:50,250
the series of cells
that contribute to

41
00:01:50,250 --> 00:01:53,670
the solution or
the optimal path.

42
00:01:53,670 --> 00:01:56,450
Let's remind ourselves
where we're at.

43
00:01:56,450 --> 00:01:59,190
We are here in our
path-finding system.

44
00:01:59,190 --> 00:02:03,010
We have a way of drawing walls,

45
00:02:03,010 --> 00:02:04,790
and with S. By pressing S,

46
00:02:04,790 --> 00:02:06,010
we can start the flat field

47
00:02:06,010 --> 00:02:08,040
algorithm that we'll
start searching.

48
00:02:08,040 --> 00:02:10,890
You could see this
Canvas is rather large,

49
00:02:10,890 --> 00:02:12,850
and it might take a while to

50
00:02:12,850 --> 00:02:15,780
test our condition of success.

51
00:02:15,780 --> 00:02:18,310
We could decrease the resolution

52
00:02:18,310 --> 00:02:20,310
of our Canvas a
little bit so that we

53
00:02:20,310 --> 00:02:25,275
can actually run this
situation a bit easier.

54
00:02:25,275 --> 00:02:29,110
Let's just do maybe half
of what we have currently.

55
00:02:29,110 --> 00:02:31,315
We can do 30 by 15.

56
00:02:31,315 --> 00:02:34,520
That's the columns and rows.

57
00:02:34,520 --> 00:02:38,400
You can see the solution
becomes a lot easier to

58
00:02:38,400 --> 00:02:41,300
evaluate because
we actually get to

59
00:02:41,300 --> 00:02:44,190
the goal in a much quicker way.

60
00:02:44,190 --> 00:02:46,080
What we want to do
is at this point,

61
00:02:46,080 --> 00:02:48,320
once the objective is reached,

62
00:02:48,320 --> 00:02:51,700
we can trace back
the information

63
00:02:51,700 --> 00:02:54,410
to the path to the start node.

64
00:02:54,410 --> 00:02:58,340
Let's start by going
into our tile node,

65
00:02:58,340 --> 00:03:01,720
and we're going to
create a new property,

66
00:03:01,720 --> 00:03:04,755
which we're going to
call self-parent.

67
00:03:04,755 --> 00:03:07,770
This is going to
be equal to none.

68
00:03:07,770 --> 00:03:11,300
By default, we're going to
say this property is empty.

69
00:03:11,300 --> 00:03:15,945
This property, it's going
to be another node.

70
00:03:15,945 --> 00:03:17,770
We're going to be
giving reference

71
00:03:17,770 --> 00:03:21,520
to what would be the
node that took me here.

72
00:03:21,860 --> 00:03:24,010
The next thing we have to do is

73
00:03:24,010 --> 00:03:25,410
actually start looking into

74
00:03:25,410 --> 00:03:27,510
our flood fill calculation and

75
00:03:27,510 --> 00:03:30,790
understand where
within the code.

76
00:03:30,790 --> 00:03:34,130
We basically go through
the evaluation.

77
00:03:34,130 --> 00:03:37,190
But at this point, when
we reach the end node,

78
00:03:37,190 --> 00:03:38,630
this statement here say,

79
00:03:38,630 --> 00:03:42,850
goal reach, we actually have
something that points out,

80
00:03:42,850 --> 00:03:45,410
look, we actually
reached the goal.

81
00:03:45,410 --> 00:03:48,330
Here, let's say, what
we want to do is

82
00:03:48,330 --> 00:03:53,925
the reconstruction, of the path.

83
00:03:53,925 --> 00:03:57,770
This happens only once,
once we reach the goal,

84
00:03:57,770 --> 00:04:04,065
and we will store this
information into a new list.

85
00:04:04,065 --> 00:04:08,310
Let's just look into how to
construct that new list.

86
00:04:08,310 --> 00:04:10,110
Let's just go back up here,

87
00:04:10,110 --> 00:04:15,270
and we do have the stack list,

88
00:04:15,270 --> 00:04:18,115
which is the frontier,
basically, the searching.

89
00:04:18,115 --> 00:04:22,600
Let's just create
another one called path.

90
00:04:23,090 --> 00:04:25,470
This is also going to be empty.

91
00:04:25,470 --> 00:04:28,340
The path is going to
be an empty list,

92
00:04:28,340 --> 00:04:29,880
and we're going to
populate that list with

93
00:04:29,880 --> 00:04:33,590
our reconstruct path function.

94
00:04:33,590 --> 00:04:35,585
We have that information now.

95
00:04:35,585 --> 00:04:36,800
We know where we have to call

96
00:04:36,800 --> 00:04:40,680
the function, which is here.

97
00:04:40,680 --> 00:04:44,820
Now the only thing that we're
actually missing to be able

98
00:04:44,820 --> 00:04:48,290
to really write that function
is to store the data.

99
00:04:48,290 --> 00:04:54,040
We don't have a way of
currently storing the data.

100
00:04:54,040 --> 00:04:55,660
But if you think about it, as we

101
00:04:55,660 --> 00:04:58,220
are going through the loop here,

102
00:04:58,220 --> 00:05:00,300
each neighbor cell or each cell,

103
00:05:00,300 --> 00:05:02,220
we go through its neighbors.

104
00:05:02,220 --> 00:05:04,580
In fact, we grow

105
00:05:04,580 --> 00:05:06,420
the searching in that
particular direction,

106
00:05:06,420 --> 00:05:07,620
meaning that it hasn't been

107
00:05:07,620 --> 00:05:09,620
visited and it's
not an obstacle,

108
00:05:09,620 --> 00:05:12,540
we add it to the stack.

109
00:05:12,540 --> 00:05:15,280
At this point, this cell also,

110
00:05:15,280 --> 00:05:18,335
we could say that
the neighbor parent.

111
00:05:18,335 --> 00:05:21,040
The neighbor is
basically the cell

112
00:05:21,040 --> 00:05:23,880
we're evaluating
from the neighbor,

113
00:05:23,880 --> 00:05:31,070
the parent, is equal
to the current cell.

114
00:05:32,490 --> 00:05:36,385
Basically, this is
the cell that took me

115
00:05:36,385 --> 00:05:40,615
to that new neighbor.

116
00:05:40,615 --> 00:05:42,475
This is a way in which we could

117
00:05:42,475 --> 00:05:44,830
fill information for those cells

118
00:05:44,830 --> 00:05:46,675
that actually do have in fact

119
00:05:46,675 --> 00:05:49,255
neighbors that
continue the search.

120
00:05:49,255 --> 00:05:51,325
This is a way of
creating this linkage

121
00:05:51,325 --> 00:05:56,170
between each node
and its parent node.

122
00:05:56,170 --> 00:05:58,630
Now that we have a
parent information,

123
00:05:58,630 --> 00:06:00,295
we can actually
write the function.

124
00:06:00,295 --> 00:06:07,340
Let's write the function that
is called reconstruct path.

125
00:06:08,190 --> 00:06:10,930
We're going to start with self,

126
00:06:10,930 --> 00:06:13,940
and let's give current cell.

127
00:06:15,210 --> 00:06:17,440
What we want to do,

128
00:06:17,440 --> 00:06:19,900
as we discussed is
a while loop while

129
00:06:19,900 --> 00:06:25,360
this current cell has a parent,

130
00:06:25,360 --> 00:06:29,450
so parent is not known.

131
00:06:31,650 --> 00:06:35,005
We're starting here
because we know that we

132
00:06:35,005 --> 00:06:37,990
have identified a parent
by default is known.

133
00:06:37,990 --> 00:06:44,120
If it's not known,
self.path.append.

134
00:06:47,280 --> 00:06:54,020
We're going to add to this
new path the current cell.

135
00:06:54,120 --> 00:07:01,670
Now the current cell equals
the parent of that cell.

136
00:07:02,640 --> 00:07:05,530
What we're doing here is that

137
00:07:05,530 --> 00:07:07,480
we're starting from one cell,

138
00:07:07,480 --> 00:07:09,445
which is going to
be the end node.

139
00:07:09,445 --> 00:07:12,355
We reach the target.
We have the end node.

140
00:07:12,355 --> 00:07:15,205
We find the parent of that node.

141
00:07:15,205 --> 00:07:16,600
We go back to that node,

142
00:07:16,600 --> 00:07:17,890
and we do the process again.

143
00:07:17,890 --> 00:07:20,095
Does this cell has
a parent, yes.

144
00:07:20,095 --> 00:07:22,585
It goes back to the parent
that took it there.

145
00:07:22,585 --> 00:07:23,800
Basically, we keep doing

146
00:07:23,800 --> 00:07:25,870
this sequence until we
reach the start point,

147
00:07:25,870 --> 00:07:27,520
which, in fact, if
you think about it,

148
00:07:27,520 --> 00:07:30,400
the start point would not
have any parent because

149
00:07:30,400 --> 00:07:31,780
the default condition of

150
00:07:31,780 --> 00:07:34,990
the start node is to
not have any parents,

151
00:07:34,990 --> 00:07:38,395
and that is only a property
that is path as we can

152
00:07:38,395 --> 00:07:42,205
calculate further into
the path-finding.

153
00:07:42,205 --> 00:07:45,230
Let's just write self.path.

154
00:07:46,920 --> 00:07:49,675
Finally, I mean,
outside the loop,

155
00:07:49,675 --> 00:07:51,640
once we finish the loop
and just in order to

156
00:07:51,640 --> 00:07:56,065
contain the start
note into this list,

157
00:07:56,065 --> 00:07:58,270
assuming that we can exit

158
00:07:58,270 --> 00:07:59,770
the list when we
reach the start note,

159
00:07:59,770 --> 00:08:02,060
we will add the start node

160
00:08:07,470 --> 00:08:10,795
to the path.

161
00:08:10,795 --> 00:08:13,825
Basically, that should be it.

162
00:08:13,825 --> 00:08:16,555
We are reconstructing.
Let's see.

163
00:08:16,555 --> 00:08:19,370
I think we have everything here.

164
00:08:19,650 --> 00:08:23,740
Instead of this comment
that we left here,

165
00:08:23,740 --> 00:08:30,775
we could say self.reconstruct
the path using

166
00:08:30,775 --> 00:08:41,155
the current cell as the
point of reconstruction.

167
00:08:41,155 --> 00:08:43,090
If things run well,

168
00:08:43,090 --> 00:08:44,320
we would actually
end up with a path,

169
00:08:44,320 --> 00:08:45,250
but we wouldn't see anything.

170
00:08:45,250 --> 00:08:46,765
This is just data at this point.

171
00:08:46,765 --> 00:08:50,575
If you think about it, let's
say we will have the path,

172
00:08:50,575 --> 00:08:52,915
but we won't be able to see it.

173
00:08:52,915 --> 00:08:54,625
Let's just do one more,

174
00:08:54,625 --> 00:08:58,720
which is draw path assuming
that that path has been

175
00:08:58,720 --> 00:09:03,340
found now. We can draw path.

176
00:09:03,340 --> 00:09:04,990
Let's just do copy paste,

177
00:09:04,990 --> 00:09:06,385
the same thing that we have,

178
00:09:06,385 --> 00:09:07,990
because it's basically
the template

179
00:09:07,990 --> 00:09:10,750
for what we're going
to be doing here.

180
00:09:10,750 --> 00:09:12,115
Let's do a color.

181
00:09:12,115 --> 00:09:16,420
It's maybe 255, 0.

182
00:09:16,420 --> 00:09:19,075
This is going to be like
a magenta-like color.

183
00:09:19,075 --> 00:09:23,860
What we want to loop through
here is for cell in path.

184
00:09:23,860 --> 00:09:27,055
We want to check all
the cells in the path,

185
00:09:27,055 --> 00:09:32,965
and then display with a
highlight version of that.

186
00:09:32,965 --> 00:09:36,685
Now that we have a
function to draw the path,

187
00:09:36,685 --> 00:09:40,600
let's draw it after
visited somewhere

188
00:09:40,600 --> 00:09:43,390
here because I do want

189
00:09:43,390 --> 00:09:47,870
to draw the end node and
start node on top of it.

190
00:09:48,690 --> 00:09:51,640
Let's see if we have
any errors and we come

191
00:09:51,640 --> 00:09:54,025
back and fix anything that
might be not working.

192
00:09:54,025 --> 00:09:56,425
Let's just run the algorithm.

193
00:09:56,425 --> 00:09:58,735
Let's create some obstacle.

194
00:09:58,735 --> 00:10:02,320
The algorithm goes very
quickly through that.

195
00:10:02,320 --> 00:10:04,405
We've reached the goal,

196
00:10:04,405 --> 00:10:05,950
and now if you think about it,

197
00:10:05,950 --> 00:10:08,560
what we're doing is starting
from here, we draw this.

198
00:10:08,560 --> 00:10:11,725
Cell this cell start being added

199
00:10:11,725 --> 00:10:15,730
up to the path until
we reach here.

200
00:10:15,730 --> 00:10:18,370
The path is complete, and
now we're actually drawing

201
00:10:18,370 --> 00:10:21,835
those cells into the canvas
with this magenta color.

202
00:10:21,835 --> 00:10:26,425
If you try it now with a
slightly more complex path.

203
00:10:26,425 --> 00:10:28,795
I'm going to try to create
something that would make

204
00:10:28,795 --> 00:10:30,370
the algorithm have to struggle

205
00:10:30,370 --> 00:10:32,890
in terms of searching
the solution.

206
00:10:32,890 --> 00:10:35,005
It's still pretty easy,

207
00:10:35,005 --> 00:10:38,110
but we'll see that the flat
field will get to the goal,

208
00:10:38,110 --> 00:10:41,770
and then the goal in
order to get back to

209
00:10:41,770 --> 00:10:43,990
the starting point
has to go through

210
00:10:43,990 --> 00:10:47,410
this particular
sequence to do so.

211
00:10:47,410 --> 00:10:49,825
So we do have a path-finding
algorithm at this point.

212
00:10:49,825 --> 00:10:51,085
But as you can realize,

213
00:10:51,085 --> 00:10:53,155
this algorithm is
not very optimal.

214
00:10:53,155 --> 00:10:55,585
We have a lot of visited cells,

215
00:10:55,585 --> 00:10:57,100
a lot of computation
that is wasted.

216
00:10:57,100 --> 00:10:58,270
It's taking quite a bit of time,

217
00:10:58,270 --> 00:11:00,775
especially if we're working
with a much larger canvas.

218
00:11:00,775 --> 00:11:01,780
We're going to be looking at

219
00:11:01,780 --> 00:11:03,240
different techniques of
how we can improve and

220
00:11:03,240 --> 00:11:05,560
optimize this algorithm
in the future lessons.

221
00:11:05,560 --> 00:11:08,640
I'll leave it here and I'll
see you in the next video.