1
00:00:06,240 --> 00:00:08,900
Hi. Welcome to this new video.

2
00:00:08,900 --> 00:00:12,880
We are continuing to work
on the path finding series,

3
00:00:12,880 --> 00:00:16,140
and we've reached a point where
we can actually introduce

4
00:00:16,140 --> 00:00:18,340
a very interesting
algorithm that would solve

5
00:00:18,340 --> 00:00:20,725
some of the inefficiencies
that we've been working with,

6
00:00:20,725 --> 00:00:22,885
and that's the A-star algorithm.

7
00:00:22,885 --> 00:00:25,520
Let's understand what we
are already achieving,

8
00:00:25,520 --> 00:00:27,060
and what are the challenges

9
00:00:27,060 --> 00:00:29,045
for this particular
algorithm to work with.

10
00:00:29,045 --> 00:00:31,080
We have a path finding problem

11
00:00:31,080 --> 00:00:33,280
that if we use a
brute force approach,

12
00:00:33,280 --> 00:00:34,740
meaning that we're
actually looking at

13
00:00:34,740 --> 00:00:36,440
every possible
cell to eventually

14
00:00:36,440 --> 00:00:40,160
find the solution or the
path to get to a target,

15
00:00:40,160 --> 00:00:43,505
we end up losing a
lot of resources.

16
00:00:43,505 --> 00:00:45,240
We actually end up looking

17
00:00:45,240 --> 00:00:47,425
into the wrong places
for a long time.

18
00:00:47,425 --> 00:00:49,330
The A-star algorithm, alongside

19
00:00:49,330 --> 00:00:51,165
with other series of
path finding algorithms,

20
00:00:51,165 --> 00:00:55,530
has been path finding
solutions that try to

21
00:00:55,530 --> 00:00:57,570
build upon the optimization and

22
00:00:57,570 --> 00:01:00,945
efficiency for this algorithm
to run and perform better.

23
00:01:00,945 --> 00:01:03,510
The way this is
achieved, is that,

24
00:01:03,510 --> 00:01:06,710
we have some information
of distance or

25
00:01:06,710 --> 00:01:08,170
some heuristic that
would allow us

26
00:01:08,170 --> 00:01:10,900
to understand are
we getting closer?

27
00:01:10,900 --> 00:01:12,440
Is this potential path

28
00:01:12,440 --> 00:01:14,780
tentatively better
than another path,

29
00:01:14,780 --> 00:01:18,690
and we would actually
prioritize this path first.

30
00:01:18,690 --> 00:01:20,640
We will see that
there's an equation

31
00:01:20,640 --> 00:01:22,420
within the algorithm
that would determine

32
00:01:22,420 --> 00:01:24,420
not all cells are equal or

33
00:01:24,420 --> 00:01:25,760
consider equally
so that we don't

34
00:01:25,760 --> 00:01:27,320
grow the algorithm
in all directions.

35
00:01:27,320 --> 00:01:30,000
But some of them
seem to be pointing

36
00:01:30,000 --> 00:01:33,545
out that those are more
interesting to be explored first.

37
00:01:33,545 --> 00:01:36,760
If we think that the
algorithm starts

38
00:01:36,760 --> 00:01:39,840
from a start point and we
have the series of cells,

39
00:01:39,840 --> 00:01:41,990
the first thing that
the algorithm would do

40
00:01:41,990 --> 00:01:43,945
is actually create two sets;

41
00:01:43,945 --> 00:01:46,120
the open set and the close set.

42
00:01:46,120 --> 00:01:47,740
We could think about those

43
00:01:47,740 --> 00:01:49,080
similarly as we have been doing

44
00:01:49,080 --> 00:01:50,220
the flat field in terms of

45
00:01:50,220 --> 00:01:53,780
the frontier and
the visited cells.

46
00:01:53,780 --> 00:01:56,060
But we have to actually

47
00:01:56,060 --> 00:01:58,980
calculate that within
the evaluated cells,

48
00:01:58,980 --> 00:02:00,800
in this case, the open set,

49
00:02:00,800 --> 00:02:04,765
that would be the point
of looking for new cells.

50
00:02:04,765 --> 00:02:07,750
We would have a series
of calculations.

51
00:02:07,750 --> 00:02:09,990
The first one of them, there's

52
00:02:09,990 --> 00:02:11,555
going to be something
we're going to call h,

53
00:02:11,555 --> 00:02:14,430
which stands for a
heuristic function.

54
00:02:14,430 --> 00:02:16,530
For our returns of purposes on

55
00:02:16,530 --> 00:02:18,510
this grid it would be a
distance calculation,

56
00:02:18,510 --> 00:02:21,470
but heuristic function means
that we could actually use

57
00:02:21,470 --> 00:02:23,420
a different heuristic or

58
00:02:23,420 --> 00:02:26,750
a different criteria
to evaluate,

59
00:02:26,750 --> 00:02:29,270
say, something that is being

60
00:02:29,270 --> 00:02:30,910
more performative
than something else.

61
00:02:30,910 --> 00:02:33,710
If we imagine this
particular condition,

62
00:02:33,710 --> 00:02:37,310
the distance of each

63
00:02:37,310 --> 00:02:40,810
one of these cells to the
gold or to the end node,

64
00:02:40,810 --> 00:02:44,985
some of them would have
a closer distance.

65
00:02:44,985 --> 00:02:47,805
We might say, well, that's
actually potentially.

66
00:02:47,805 --> 00:02:49,040
We don't know if that's going to

67
00:02:49,040 --> 00:02:51,155
lead to the optimal path.

68
00:02:51,155 --> 00:02:54,125
That's potentially a better
way to explore first.

69
00:02:54,125 --> 00:02:57,320
We're going to prioritize
the cell, in this case,

70
00:02:57,320 --> 00:02:59,840
with the h of 89,

71
00:02:59,840 --> 00:03:02,400
that would be a cell

72
00:03:02,400 --> 00:03:04,700
that we're going to
be exploring first.

73
00:03:04,800 --> 00:03:08,020
There's a second layer of scores

74
00:03:08,020 --> 00:03:11,040
that would be taken into
account by this algorithm.

75
00:03:11,040 --> 00:03:15,890
The second series of course
is the g or the g-score,

76
00:03:15,890 --> 00:03:18,765
which actually stands for
the cost of the path.

77
00:03:18,765 --> 00:03:20,600
To understand this, is that,

78
00:03:20,600 --> 00:03:22,800
for instance, if you move
one point in the grid,

79
00:03:22,800 --> 00:03:24,020
you have a cost of one,

80
00:03:24,020 --> 00:03:25,320
if you move two points in

81
00:03:25,320 --> 00:03:27,730
the grid, you have
a cost of two.

82
00:03:28,300 --> 00:03:31,820
You actually might also be
taking into consideration how

83
00:03:31,820 --> 00:03:34,680
long has it taken you to be
in that particular position?

84
00:03:34,680 --> 00:03:36,460
That, together
with the distance,

85
00:03:36,460 --> 00:03:38,375
which is what we're
going to call f,

86
00:03:38,375 --> 00:03:43,020
which f is going to stand by
the summation of g and h,

87
00:03:43,020 --> 00:03:44,940
gives us a final score.

88
00:03:44,940 --> 00:03:47,155
We're going to be talking
about this final score f,

89
00:03:47,155 --> 00:03:50,295
which is a merger of

90
00:03:50,295 --> 00:03:54,510
how much has cost us to be
where we're at in the search,

91
00:03:54,510 --> 00:03:56,710
and how much is the
distance of what is

92
00:03:56,710 --> 00:04:00,105
left to arrive to the target.

93
00:04:00,105 --> 00:04:01,670
Those two conditions, if

94
00:04:01,670 --> 00:04:02,930
we're actually
reaching a dead end,

95
00:04:02,930 --> 00:04:04,670
if you imagine you're
reaching a dead end,

96
00:04:04,670 --> 00:04:08,325
it might be that your cost
starts being very high.

97
00:04:08,325 --> 00:04:10,650
You might switch to
a different part

98
00:04:10,650 --> 00:04:13,010
of the algorithm where
the cost was lower,

99
00:04:13,010 --> 00:04:14,910
but perhaps the
distance was higher,

100
00:04:14,910 --> 00:04:16,410
and perhaps that becomes

101
00:04:16,410 --> 00:04:19,290
the most tentatively
more interesting path

102
00:04:19,290 --> 00:04:20,645
to keep on evaluating.

103
00:04:20,645 --> 00:04:22,290
This algorithm
would actually not

104
00:04:22,290 --> 00:04:25,830
grow in a uniform way
in all directions.

105
00:04:25,830 --> 00:04:28,095
It would actually
grow specifically,

106
00:04:28,095 --> 00:04:30,100
on the areas that has a hint

107
00:04:30,100 --> 00:04:32,900
that could be performing better.

108
00:04:32,900 --> 00:04:34,500
This would give us incredible

109
00:04:34,500 --> 00:04:36,140
efficiencies in a
way in which we

110
00:04:36,140 --> 00:04:38,080
could arrive to a target

111
00:04:38,080 --> 00:04:40,870
in the least amount
of calculations.

112
00:04:40,870 --> 00:04:43,360
Let's look at a simple example.

113
00:04:43,360 --> 00:04:45,400
We're going to be looking
just at the f-score,

114
00:04:45,400 --> 00:04:48,860
which is the summation of
the cost and the distance,

115
00:04:48,860 --> 00:04:51,860
the h. If we start
on the start note,

116
00:04:51,860 --> 00:04:54,020
just by looking at
the cells here,

117
00:04:54,020 --> 00:04:55,780
we've marked with numbers,

118
00:04:55,780 --> 00:04:57,835
just the final f-score.

119
00:04:57,835 --> 00:04:59,680
There might be
cases in which you

120
00:04:59,680 --> 00:05:01,600
might have two f-scores
that are the same.

121
00:05:01,600 --> 00:05:03,740
In that extent, the
algorithm would

122
00:05:03,740 --> 00:05:06,260
actually pick the one that
is first in the list,

123
00:05:06,260 --> 00:05:08,240
but we could see
how the algorithm

124
00:05:08,240 --> 00:05:11,635
would be calculating constantly.

125
00:05:11,635 --> 00:05:13,980
We will not visit all
the cells in the grid.

126
00:05:13,980 --> 00:05:17,370
We would actually just move
rather quickly to the cells

127
00:05:17,370 --> 00:05:21,535
that are closer and
closer to the end node.

128
00:05:21,535 --> 00:05:24,350
This is the logic
of what we have.

129
00:05:24,350 --> 00:05:25,010
Let me show you

130
00:05:25,010 --> 00:05:26,530
a little bit of what we're
going to be building

131
00:05:26,530 --> 00:05:28,990
before we actually jump
into the code itself.

132
00:05:28,990 --> 00:05:31,860
We're going to be building
this in a couple of sessions,

133
00:05:31,860 --> 00:05:34,010
but if we have this
condition here,

134
00:05:34,010 --> 00:05:37,840
we have all the cells
marking the f, the h,

135
00:05:37,840 --> 00:05:43,250
and the g. As we still have
a dynamic environment,

136
00:05:44,960 --> 00:05:49,170
let's imagine that we're
creating this condition here,

137
00:05:49,210 --> 00:05:54,390
and maybe also
something like this.

138
00:05:54,530 --> 00:05:57,830
You can see that the amount
of cells that are being

139
00:05:57,830 --> 00:06:01,250
evaluated is drastically smaller

140
00:06:01,250 --> 00:06:03,050
than what we have been
using with the flat feel,

141
00:06:03,050 --> 00:06:07,580
and you can actually
start reading

142
00:06:07,580 --> 00:06:09,260
the numbers and
understanding that

143
00:06:09,260 --> 00:06:13,035
the f condition
constantly goes down.

144
00:06:13,035 --> 00:06:15,340
What is quite intuitive and

145
00:06:15,340 --> 00:06:17,340
interesting about doing this
interactive simulation,

146
00:06:17,340 --> 00:06:19,660
is that, by just drawing
a different environment,

147
00:06:19,660 --> 00:06:21,980
you would be able to
put to the test of how

148
00:06:21,980 --> 00:06:23,280
the algorithm performs when

149
00:06:23,280 --> 00:06:25,160
it has to find the
dead end condition,

150
00:06:25,160 --> 00:06:28,450
maybe we has to switch and go
back to a different route,

151
00:06:28,450 --> 00:06:30,920
and ultimately find a path

152
00:06:30,920 --> 00:06:33,075
to this labyrinth
that we're building.

153
00:06:33,075 --> 00:06:34,500
We're going to be
building this together

154
00:06:34,500 --> 00:06:35,860
in the next couple of sessions.

155
00:06:35,860 --> 00:06:38,280
I'll see you in the next video.