1
00:00:05,920 --> 00:00:08,780
Hi, welcome to this final video

2
00:00:08,780 --> 00:00:10,720
of our path finding series.

3
00:00:10,720 --> 00:00:14,720
We're going to conclude
this week with

4
00:00:14,720 --> 00:00:15,920
a conversation of how

5
00:00:15,920 --> 00:00:17,520
this path finding
algorithm could

6
00:00:17,520 --> 00:00:19,260
be used in different
contexts of design,

7
00:00:19,260 --> 00:00:22,200
but also stylizing a little
bit the calculations.

8
00:00:22,200 --> 00:00:25,560
We've been spending time
on visualizing the data,

9
00:00:25,560 --> 00:00:27,520
but sometimes we have to

10
00:00:27,520 --> 00:00:29,300
increase the resolution
of the algorithm and

11
00:00:29,300 --> 00:00:31,840
see some of the complexity

12
00:00:31,840 --> 00:00:33,700
that emerges out of
this calculation,

13
00:00:33,700 --> 00:00:36,455
which I think in many ways
could be very beautiful.

14
00:00:36,455 --> 00:00:41,490
Let's start by discussing
this A-star algorithm.

15
00:00:42,040 --> 00:00:44,625
You have to think
that path finding,

16
00:00:44,625 --> 00:00:46,060
first of all, it's not

17
00:00:46,060 --> 00:00:48,285
just a problem that could
be applied to grids.

18
00:00:48,285 --> 00:00:50,280
I know that we're actually
looking at as a grid,

19
00:00:50,280 --> 00:00:53,260
and we have discussed
that this is a problem

20
00:00:53,260 --> 00:00:54,580
that could be extrapolated to

21
00:00:54,580 --> 00:00:57,185
all different graph networks.

22
00:00:57,185 --> 00:01:02,310
It could be incredibly flexible
for different solutions.

23
00:01:02,310 --> 00:01:04,585
Obviously, it could
work in 3D as well.

24
00:01:04,585 --> 00:01:07,790
Let's look at what environments.

25
00:01:07,790 --> 00:01:09,940
If we think of
architecture and planning,

26
00:01:09,940 --> 00:01:11,920
you could start thinking
of route optimization,

27
00:01:11,920 --> 00:01:15,780
you can talk about
building evacuation.

28
00:01:15,780 --> 00:01:18,400
If you start thinking
of game design,

29
00:01:18,400 --> 00:01:20,120
there's beautiful games such as

30
00:01:20,120 --> 00:01:24,195
Tor Fortress that
are very simple,

31
00:01:24,195 --> 00:01:25,440
like Asky graphics, but at

32
00:01:25,440 --> 00:01:27,360
the same time they use
an incredible amount of

33
00:01:27,360 --> 00:01:28,815
computation of
path finding where

34
00:01:28,815 --> 00:01:31,210
NPC have to move
through the world.

35
00:01:31,210 --> 00:01:33,520
This is one of the first places
where I would invite you

36
00:01:33,520 --> 00:01:35,900
to play with this algorithm
in terms of like,

37
00:01:35,900 --> 00:01:39,320
how can you guide an
agent within the world,

38
00:01:39,320 --> 00:01:42,820
not through just the
flow of a vector,

39
00:01:42,820 --> 00:01:45,665
but perhaps with
very specific tasks?

40
00:01:45,665 --> 00:01:48,890
An agent could actually
go and maybe find

41
00:01:48,890 --> 00:01:50,490
a particular resource and bring

42
00:01:50,490 --> 00:01:52,190
that resource back to
a particular location,

43
00:01:52,190 --> 00:01:54,870
and that might
require path finding

44
00:01:54,870 --> 00:01:57,070
in multiple sequences.

45
00:01:57,070 --> 00:01:58,850
In many of those cases,
the path finding

46
00:01:58,850 --> 00:02:00,530
calculation, it's invisible.

47
00:02:00,530 --> 00:02:02,010
It's an invisible layer.

48
00:02:02,010 --> 00:02:04,270
But perhaps you want to
show some of this data

49
00:02:04,270 --> 00:02:07,010
of how the construction
of a train

50
00:02:07,010 --> 00:02:08,890
or the construction
of an environment

51
00:02:08,890 --> 00:02:10,710
dynamically might
change the way in

52
00:02:10,710 --> 00:02:12,880
which these agents might behave.

53
00:02:12,880 --> 00:02:17,060
NPC movement in the
opposite direction,

54
00:02:17,060 --> 00:02:19,005
you could actually
think of level design.

55
00:02:19,005 --> 00:02:21,840
If you pre calculate paths

56
00:02:21,840 --> 00:02:24,120
that might be the way in
which you navigate a system,

57
00:02:24,120 --> 00:02:25,860
you can use that to make

58
00:02:25,860 --> 00:02:28,040
environments that are
always accessible,

59
00:02:28,040 --> 00:02:31,650
always available to be
navigated as opposed

60
00:02:31,650 --> 00:02:33,360
to environments that might

61
00:02:33,360 --> 00:02:36,070
end up without any
capacity for navigation.

62
00:02:36,070 --> 00:02:38,030
Within industrial design,

63
00:02:38,030 --> 00:02:39,920
you could find
robotic path finding.

64
00:02:39,920 --> 00:02:42,710
How do you move from one
point to another one,

65
00:02:42,710 --> 00:02:45,450
and what is the
optimal path for that?

66
00:02:45,450 --> 00:02:48,170
Finally, again, out of many more

67
00:02:48,170 --> 00:02:50,075
examples that you
can think of in

68
00:02:50,075 --> 00:02:53,070
transportation design,
traffic flow analysis.

69
00:02:53,070 --> 00:02:55,850
These are a whole range of
areas where they could start

70
00:02:55,850 --> 00:02:58,830
using some of these algorithms
to take part of it.

71
00:02:58,830 --> 00:03:00,250
The images that
I've been showing

72
00:03:00,250 --> 00:03:02,790
you are a little bit

73
00:03:02,790 --> 00:03:04,070
where we're going to
be concluding with.

74
00:03:04,070 --> 00:03:05,930
We're going to just stylize
some of the algorithm,

75
00:03:05,930 --> 00:03:07,650
look at it in high risk,
but also start looking

76
00:03:07,650 --> 00:03:09,510
at the data not
just numerically,

77
00:03:09,510 --> 00:03:12,490
but also how it's
represented when we actually

78
00:03:12,490 --> 00:03:15,780
use it to colorize
some of the tiles.

79
00:03:15,780 --> 00:03:18,420
Let's see the code.

80
00:03:18,420 --> 00:03:20,550
We're going to just continue

81
00:03:20,550 --> 00:03:22,770
working where we have left off.

82
00:03:22,770 --> 00:03:24,885
If you remember,

83
00:03:24,885 --> 00:03:27,730
the way in which we have
to increase or decrease

84
00:03:27,730 --> 00:03:31,070
the resolution of the
algorithm is done here.

85
00:03:31,070 --> 00:03:34,270
We're going to go back
to a much larger grid.

86
00:03:34,270 --> 00:03:38,090
I'm going to comment out some
of these functions here.

87
00:03:38,090 --> 00:03:40,545
I don't want to draw
the data anymore.

88
00:03:40,545 --> 00:03:42,380
If you think about
it, we're not even

89
00:03:42,380 --> 00:03:46,020
visualizing the visited tiles.

90
00:03:46,020 --> 00:03:48,620
We are drawing the path,

91
00:03:48,620 --> 00:03:49,940
we want to draw the start node,

92
00:03:49,940 --> 00:03:51,990
the end node, and
the open stack.

93
00:03:51,990 --> 00:03:54,060
Those are fine, but we

94
00:03:54,060 --> 00:03:56,540
want to also add maybe
the closed stack.

95
00:03:56,540 --> 00:03:58,600
Let's just see what
we have so far.

96
00:03:58,600 --> 00:04:00,500
We have a much larger grid.

97
00:04:00,500 --> 00:04:06,420
We can paint. Let's invert to
play with our color scheme.

98
00:04:06,420 --> 00:04:10,480
If we go back to our tile here,

99
00:04:10,560 --> 00:04:13,100
in our display function,

100
00:04:13,100 --> 00:04:17,160
we would say that
if it's a floor,

101
00:04:17,160 --> 00:04:20,865
we're going to do black.

102
00:04:20,865 --> 00:04:23,990
This is going to
be a white line.

103
00:04:23,990 --> 00:04:29,270
If it's a wall, it's
going to be white.

104
00:04:29,270 --> 00:04:33,830
We're inverting the
color scheme here.

105
00:04:34,260 --> 00:04:38,670
If you think that the
stroke is too intense,

106
00:04:38,670 --> 00:04:41,890
you can bring this down a
little bit like maybe 80.

107
00:04:44,180 --> 00:04:47,325
Here, we have the same system.

108
00:04:47,325 --> 00:04:50,420
Finally, I would like to
draw one more function,

109
00:04:50,420 --> 00:04:52,540
which would be a very slightly

110
00:04:52,540 --> 00:04:54,220
different way of
displaying the data.

111
00:04:54,220 --> 00:04:59,820
We have been displaying the
data in this numeric fashion.

112
00:04:59,820 --> 00:05:02,995
Let's just display the
data in a graphic fashion.

113
00:05:02,995 --> 00:05:08,710
We're going to say the
def display_visual_data.

114
00:05:15,460 --> 00:05:18,350
Here, we're going
to say that the

115
00:05:18,350 --> 00:05:24,680
mapped F. I'm going

116
00:05:24,680 --> 00:05:25,850
to create a variable
that is going to

117
00:05:25,850 --> 00:05:27,515
be mapping the value of F,

118
00:05:27,515 --> 00:05:29,030
which is what we
want to visualize,

119
00:05:29,030 --> 00:05:31,400
which is ultimately what
drives the algorithm.

120
00:05:31,400 --> 00:05:35,790
Let's map the value of self.

121
00:05:36,460 --> 00:05:39,860
The mapping technique,
we have been using a lot

122
00:05:39,860 --> 00:05:43,160
to change the domain of a
variable into another one.

123
00:05:43,160 --> 00:05:44,570
We know that this
variable might go

124
00:05:44,570 --> 00:05:46,250
between zero and 1,000,

125
00:05:46,250 --> 00:05:47,780
which is roughly the distance

126
00:05:47,780 --> 00:05:48,905
that you might be able to get,

127
00:05:48,905 --> 00:05:50,855
maybe a bit more, but
we're going to just

128
00:05:50,855 --> 00:05:53,135
estimating it at the moment.

129
00:05:53,135 --> 00:05:54,875
We're going to say
between zero and 1,000,

130
00:05:54,875 --> 00:06:00,410
that's going to be transfer
into a color of 0-255.

131
00:06:00,410 --> 00:06:02,420
Now we could say that

132
00:06:02,420 --> 00:06:05,960
the color or call
the variable color,

133
00:06:05,960 --> 00:06:08,240
it's going to be a color of the

134
00:06:08,240 --> 00:06:16,190
mapped F. A 2550.

135
00:06:16,190 --> 00:06:19,490
I'm going to use that in the
red channel of this color.

136
00:06:19,490 --> 00:06:21,170
RGB, we're going to keep 255.

137
00:06:21,170 --> 00:06:22,820
These are two arbitrary
colors just to

138
00:06:22,820 --> 00:06:25,160
give we can play with
these variables later,

139
00:06:25,160 --> 00:06:30,260
but I'm going to use the
mapped FED red channel.

140
00:06:30,260 --> 00:06:34,680
Let's feel the cell
with the color.

141
00:06:36,000 --> 00:06:39,250
Let's just do a stroke.

142
00:06:39,250 --> 00:06:42,470
Then let's do the rectangle,

143
00:06:43,150 --> 00:06:48,650
which is going to be
self dot position.

144
00:06:48,650 --> 00:06:54,790
The x self-position to y and

145
00:06:54,790 --> 00:07:00,175
self dot cell size

146
00:07:00,175 --> 00:07:06,290
and self dot cell size.

147
00:07:06,290 --> 00:07:09,060
We have this display
visual data.

148
00:07:09,670 --> 00:07:12,830
Now we need to call this.

149
00:07:12,830 --> 00:07:19,655
We're going to call it the way
we have been doing before.

150
00:07:19,655 --> 00:07:21,650
You see the same way we drew

151
00:07:21,650 --> 00:07:28,380
the stack let's find that
function. It's here.

152
00:07:29,140 --> 00:07:31,970
Let's just copy that function,

153
00:07:31,970 --> 00:07:44,270
and it's call it
draw closed stack,

154
00:07:44,270 --> 00:07:52,340
and go through the closed stack.

155
00:07:52,340 --> 00:07:56,000
Instead of drawing
the highlighted,

156
00:07:56,000 --> 00:07:57,950
you see that we had a specific

157
00:07:57,950 --> 00:08:00,050
highlighted that used the color,

158
00:08:00,050 --> 00:08:04,130
we would actually use
display visual data,

159
00:08:04,130 --> 00:08:06,350
which is a new function.

160
00:08:06,350 --> 00:08:08,540
We're going to be applying.

161
00:08:08,540 --> 00:08:10,925
This one doesn't actually
have an argument.

162
00:08:10,925 --> 00:08:13,370
Because it uses its own
mapping function to

163
00:08:13,370 --> 00:08:17,220
define the color itself.

164
00:08:17,800 --> 00:08:26,070
Let's just put it just after
the stack here, self-dot.

165
00:08:28,180 --> 00:08:32,850
Close to. Let's see if we're
running into any errors.

166
00:08:34,480 --> 00:08:39,110
We're not so we can see the
calculation being executed.

167
00:08:39,110 --> 00:08:41,810
As you can see now the cells.

168
00:08:41,810 --> 00:08:45,740
Actually, we are
overriding the path.

169
00:08:45,740 --> 00:08:48,545
The path should actually happen

170
00:08:48,545 --> 00:08:55,230
after because we are not
seeing once the path is found.

171
00:08:55,450 --> 00:08:58,055
But we have a much
larger Canvas now.

172
00:08:58,055 --> 00:08:59,240
I invite you to really

173
00:08:59,240 --> 00:09:02,030
know create a little bit

174
00:09:02,030 --> 00:09:04,415
of a challenge for
the algorithm.

175
00:09:04,415 --> 00:09:06,770
Where you could
actually start seeing,

176
00:09:06,770 --> 00:09:09,410
especially if you create
pockets that are dead ends,

177
00:09:09,410 --> 00:09:12,455
areas that need to be
searched for prior,

178
00:09:12,455 --> 00:09:16,835
especially with a much larger
canvas, such as this one.

179
00:09:16,835 --> 00:09:19,550
I go back to my
childhood when I could

180
00:09:19,550 --> 00:09:23,135
just draw little
labyrinths in a page.

181
00:09:23,135 --> 00:09:27,365
You start thinking about how
you would navigate those,

182
00:09:27,365 --> 00:09:29,000
and how would people
navigate those,

183
00:09:29,000 --> 00:09:31,085
maybe trying one
path or another.

184
00:09:31,085 --> 00:09:32,660
Notice that obviously
like any of

185
00:09:32,660 --> 00:09:35,450
these gaps that you might play

186
00:09:35,450 --> 00:09:39,110
into the algorithm
would very quickly

187
00:09:39,110 --> 00:09:44,220
make use of any exploitation
that you might have.

188
00:09:44,620 --> 00:09:47,090
We need to make
sure that you don't

189
00:09:47,090 --> 00:09:48,770
run out of the canvas,

190
00:09:48,770 --> 00:09:50,030
we seem to be having an error

191
00:09:50,030 --> 00:09:52,445
that if you go out
of the Canvas,

192
00:09:52,445 --> 00:09:57,395
you will crash the algorithm.

193
00:09:57,395 --> 00:09:59,885
I invite you to draw

194
00:09:59,885 --> 00:10:05,090
a difficult
environment just spend

195
00:10:05,090 --> 00:10:10,670
a little bit of time
drawing something.

196
00:10:16,650 --> 00:10:23,720
That might be tricky to resolve.

197
00:10:25,630 --> 00:10:29,465
Then pressing as to
start the algorithm,

198
00:10:29,465 --> 00:10:34,600
you'll see how different
areas are being evaluated.

199
00:10:34,600 --> 00:10:37,140
But you see quite efficiently,

200
00:10:37,140 --> 00:10:39,880
the amount of waste
that this algorithm

201
00:10:39,880 --> 00:10:42,920
had in certain pockets
is quite small,

202
00:10:42,920 --> 00:10:45,100
and even with a larger terrain,

203
00:10:45,100 --> 00:10:46,880
it can perform very well.

204
00:10:46,880 --> 00:10:50,190
It does so remarkably fast.

205
00:10:50,620 --> 00:10:54,135
With this demonstration
with this setup,

206
00:10:54,135 --> 00:10:55,900
we're going to leave
this week here

207
00:10:55,900 --> 00:10:57,760
and we're going to move
to the final week.

208
00:10:57,760 --> 00:11:01,020
We're going to start a new
project. So I'll see you then.