Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
0
1
00:00:00,360 --> 00:00:02,640
Anatomy of a pathfinder.
1
2
00:00:02,700 --> 00:00:07,440
How does the AI know how to get from point A to point B, on a map?
2
3
00:00:07,440 --> 00:00:09,930
What is the code sequence that enables that?
3
4
00:00:09,930 --> 00:00:14,490
The code is an algorithm and there are many pathfinding algorithms out there.
4
5
00:00:14,520 --> 00:00:20,040
In this chapter, we will look at the simple pathfinding algorithm called breadth first search (BFS).
5
6
00:00:20,050 --> 00:00:24,750
BFS is an uninformed algorithm that deals with the situation at hand.
6
7
00:00:24,780 --> 00:00:29,790
Its end result is a path between the starting node A and the final node
7
8
00:00:29,790 --> 00:00:30,060
B.
8
9
00:00:30,060 --> 00:00:34,380
Let's deconstruct the algorithm and see how a pathfinder works.
9
10
00:00:34,380 --> 00:00:41,100
We will start by defining the space and for the space or domain, we will use a grid because it's one
10
11
00:00:41,100 --> 00:00:43,410
of the most easiest ways to implement it.
11
12
00:00:43,410 --> 00:00:50,310
Any position on the grid can be referenced using two indices: row index and column index.
12
13
00:00:50,310 --> 00:00:57,450
For example, these positions. Regarding the implementation, a grid can be simply implemented with a list
13
14
00:00:57,450 --> 00:01:00,750
of lists or an array 2D like this.
14
15
00:01:00,750 --> 00:01:07,050
So it has one list that has multiple lists and each value represents a cell here.
15
16
00:01:07,080 --> 00:01:13,590
Of course, it's good to know that we need to fill the space in order to simplify our edge cases.
16
17
00:01:13,590 --> 00:01:19,050
And for this we'll consider the wall being -1 and the empty space being 0.
17
18
00:01:19,200 --> 00:01:24,090
And we will mark the exterior of our grid with -1, which is the wall.
18
19
00:01:24,150 --> 00:01:29,940
Let's quickly go to the queue, by the way, if you want to know more about the queue, there is the bonus
19
20
00:01:29,940 --> 00:01:36,030
section where we discuss about the queue in much more detail, but basically the queue is just a list with a
20
21
00:01:36,030 --> 00:01:36,540
spin.
21
22
00:01:36,600 --> 00:01:42,480
You can only add elements at the end of it and you can only remove them at the beginning of it.
22
23
00:01:42,540 --> 00:01:44,910
This is very similar to a cinema queue.
23
24
00:01:44,970 --> 00:01:49,440
The queue is an important part of the breadth first search algorithm.
24
25
00:01:49,440 --> 00:01:54,060
The next step is, of course, to study how we are going to move through the grid.
25
26
00:01:54,060 --> 00:02:00,540
And if we take a position, let's say [3, 3], line: 3, column: 3 or simply 3 - 3,
26
27
00:02:00,540 --> 00:02:07,950
then we can adjust the up, down, left or right movement by adding or removing one step to
27
28
00:02:07,950 --> 00:02:14,520
either the column or the row, because you only move four directions and these new pairs of values will
28
29
00:02:14,520 --> 00:02:20,280
be the next positions for our object that has the pathfinding algorithm.
29
30
00:02:20,280 --> 00:02:26,490
How can we encode the movement patterns to be easily processed by the algorithm?
30
31
00:02:26,490 --> 00:02:31,230
And for this we will use two lists called the DX and DY.
31
32
00:02:31,440 --> 00:02:33,090
Of course you can name them as you like.
32
33
00:02:33,090 --> 00:02:35,400
Basically they'll encode each step.
33
34
00:02:35,400 --> 00:02:42,660
So for example, if we take the pair, that was [3, 3] initially and if I want up, I need to add
34
35
00:02:42,660 --> 00:02:44,280
-1, which will be 2.
35
36
00:02:44,280 --> 00:02:49,740
And for the Y, I need to add 0 because we only move row and we don't move columns.
36
37
00:02:49,740 --> 00:02:51,300
So of course it's 0.
37
38
00:02:51,330 --> 00:02:54,780
Let's take for the right, which is 0, so we don't move a row.
38
39
00:02:55,020 --> 00:03:00,450
So the row needs to stay on the same one, but the column increases to this one further down and left.
39
40
00:03:00,450 --> 00:03:01,200
It's the same.
40
41
00:03:01,200 --> 00:03:05,370
Here's the example as you're taking the [3, 3] example.
41
42
00:03:05,370 --> 00:03:13,080
By adding each of these pairs, we get these new values that are representing the adjacent positions.
42
43
00:03:13,110 --> 00:03:20,610
Of course, by just adding more pairs to this list, for example, one and one, you will get this value,
43
44
00:03:20,910 --> 00:03:23,700
this value, this value or this value.
44
45
00:03:23,700 --> 00:03:28,380
By doing this, you'll enable your AI controlled Pathfinder to work
45
46
00:03:28,470 --> 00:03:30,900
with eight directions instead of four.
46
47
00:03:30,930 --> 00:03:36,720
Of course, you can even put more exotic directions, for example, like a knight in chess to move in
47
48
00:03:36,720 --> 00:03:37,350
L-shape.
48
49
00:03:37,350 --> 00:03:42,450
So, for example, encode this position, this position it needs to be L shapes.
49
50
00:03:42,450 --> 00:03:47,370
But of course you can have any type of direction you want with this structure.
50
51
00:03:47,400 --> 00:03:50,220
Now let's look at the algorithm itself.
51
52
00:03:50,220 --> 00:03:53,100
Luckily for us, it just has only eight steps.
52
53
00:03:53,100 --> 00:03:56,550
First, we need to add the starting point to the queue.
53
54
00:03:56,550 --> 00:04:03,180
While the queue is not empty, we need to get the first position and if the first position is the destination,
54
55
00:04:03,180 --> 00:04:07,050
then the algorithm reached its goal and we succeeded.
55
56
00:04:07,050 --> 00:04:07,450
Yay!
56
57
00:04:07,530 --> 00:04:12,120
But if it didn't reach the position, then we need to get the adjacent positions.
57
58
00:04:12,450 --> 00:04:14,640
This can be done with the lists DX, DY.
58
59
00:04:14,640 --> 00:04:20,970
Then we need to fill the positions and add them to the queue so they can be processed in the next step.
59
60
00:04:20,970 --> 00:04:27,810
Of course, I also prepared a code because it might be much simpler to see it in actual GDScript.
60
61
00:04:27,810 --> 00:04:31,050
The queue, as you can see here, is just a list.
61
62
00:04:31,050 --> 00:04:36,360
I'm using GodotNext which has an array 2D, so it has a grid-like structure.
62
63
00:04:36,360 --> 00:04:42,300
But basically we are adding the first position here while the queue is not empty and and the exit was
63
64
00:04:42,300 --> 00:04:47,280
not found, we get the current position. Basically this is kind of the same, but this gets the value
64
65
00:04:47,280 --> 00:04:50,490
of the current position because you'll also put in the steps.
65
66
00:04:50,490 --> 00:04:56,070
So for example, the first step is one and then the next step is two, three, four until it reaches
66
67
00:04:56,070 --> 00:04:56,880
the end position.
67
68
00:04:56,880 --> 00:04:59,580
We only have four directions as you
68
69
00:04:59,710 --> 00:05:08,170
remember, DX and DY where we get the X from the current position, we add the DX at the i position
69
70
00:05:08,260 --> 00:05:10,240
and the same for DY.
70
71
00:05:10,300 --> 00:05:16,660
Of course we get the next cell step. If the next cell is final, which is of course, if it's the goal,
71
72
00:05:16,690 --> 00:05:19,390
then we don't need to work with it.
72
73
00:05:19,390 --> 00:05:24,910
But if the cell is empty and this is really important because it can be a wall, and if it's a wall
73
74
00:05:24,910 --> 00:05:32,830
we don't care about it. If it's empty and then we can add this new position to the queue and also here, I'm just
74
75
00:05:32,830 --> 00:05:35,710
adding the current step plus one.
75
76
00:05:35,950 --> 00:05:41,770
So for example, if the first step was one and this cell is the next one, then it would be two.
76
77
00:05:42,100 --> 00:05:47,500
And as you can see here, if you start in this position, the first step is zero, but then the next
77
78
00:05:47,500 --> 00:05:51,400
step, the adjacencies are one, then the next positions are two.
78
79
00:05:51,400 --> 00:05:57,580
For these steps, basically, they mean how many steps you need in order to get there from this initial
79
80
00:05:57,580 --> 00:05:59,020
one, and so on and so forth.
80
81
00:05:59,020 --> 00:06:03,010
By applying this, we end up with seven steps to position B.
81
82
00:06:03,010 --> 00:06:04,960
I want to make an observation here.
82
83
00:06:04,960 --> 00:06:11,680
Running BFS like this, it won't give us a path from A to B, it will just fill the map with how
83
84
00:06:11,680 --> 00:06:17,140
many steps you need from A to reach a particular position. To get the actual final path
84
85
00:06:17,140 --> 00:06:23,140
we need to do something called reconstructing the path, and we do this by getting to the last step
85
86
00:06:23,140 --> 00:06:29,620
of the algorithm, which is the arriving at the position B and then we will use a recursive function.
86
87
00:06:29,620 --> 00:06:34,470
Basically, a recursive function is a function that has a call to itself inside of its code.
87
88
00:06:34,480 --> 00:06:36,640
You can find more in the bonus section.
88
89
00:06:36,640 --> 00:06:39,880
For this we will be using this code to remake the path.
89
90
00:06:39,880 --> 00:06:42,940
Let's quickly go through it and try to understand it.
90
91
00:06:42,940 --> 00:06:49,000
So the first thing is we will use the current positions, X and Y, which are the end position.
91
92
00:06:49,030 --> 00:06:52,510
These are the total steps that we reached so far.
92
93
00:06:52,510 --> 00:06:54,370
We get the current position and the current cell
93
94
00:06:54,370 --> 00:07:01,630
This is very, very important because we will be using the previous cell's step in order to advance backwards
94
95
00:07:01,630 --> 00:07:02,650
through our algorithm.
95
96
00:07:02,660 --> 00:07:09,310
So in this case, let's say we are here at five and we want to know what is the lower step basically.
96
97
00:07:09,310 --> 00:07:13,120
So we want to go back to six, we only can go to four.
97
98
00:07:13,180 --> 00:07:14,980
So these are the only possibilities.
98
99
00:07:15,220 --> 00:07:19,660
If we are at four, we cannot go back to the five, so we can only go back to the three.
99
100
00:07:19,660 --> 00:07:25,390
If the current cell is start, then that means that we have arrived at the destination here is setting
100
101
00:07:25,390 --> 00:07:29,980
up the color, but basically this is it and if not, then of course it does the same.
101
102
00:07:29,980 --> 00:07:31,510
It takes the same direction lists.
102
103
00:07:31,780 --> 00:07:37,170
So of course we need four of them and we get the next position and it needs to check if the next cells
103
104
00:07:37,180 --> 00:07:40,600
value is exactly one less than the current one.
104
105
00:07:40,600 --> 00:07:45,640
Or in this case, if we add one, it should be exactly the same as the current step.
105
106
00:07:45,640 --> 00:07:50,350
And, of course, if the next cell is not the wall. Of course the final color is not important for us.
106
107
00:07:50,350 --> 00:07:54,490
This is for the algorithm to look nice, but it just returns remake path.
107
108
00:07:54,490 --> 00:07:57,400
And as you notice, it is the same name as this function.
108
109
00:07:57,400 --> 00:07:59,410
This means it is a recursive function.
109
110
00:07:59,800 --> 00:08:05,410
And basically this calls this function again, but from the positions of the adjacent cell.
110
111
00:08:05,500 --> 00:08:12,310
So if it go to the final result and are starting here, basically calling this function here will find
111
112
00:08:12,310 --> 00:08:15,850
this position and we'll call this function from this point.
112
113
00:08:15,880 --> 00:08:20,200
When this point is achieved, then it will call from this one and from this one.
113
114
00:08:20,200 --> 00:08:23,230
And the end case is when it's called from this one.
114
115
00:08:23,230 --> 00:08:27,520
And from this point, the next one is actually the original cell.
115
116
00:08:27,520 --> 00:08:29,980
And this is how this function is called.
116
117
00:08:29,980 --> 00:08:35,200
And it's really important when doing recursive functions to have this exit condition.
117
118
00:08:35,200 --> 00:08:40,930
Otherwise the function will call itself indefinitely and it'll crash your game.
118
119
00:08:40,930 --> 00:08:46,360
So make sure we have this in mind when implementing recursive functions and by running this function
119
120
00:08:46,360 --> 00:08:48,370
you will end up with the final path.
120
121
00:08:48,370 --> 00:08:52,240
And the final path can be used for the object in the position.
121
122
00:08:52,240 --> 00:08:58,210
A to move to position B. What are the pros and cons of using BFS?
122
123
00:08:58,330 --> 00:09:06,490
The pros are that it's very easy and fast to implement. It's very easy to debug and also very easy to visualize
123
124
00:09:06,490 --> 00:09:09,040
and can be used in various scenarios.
124
125
00:09:09,040 --> 00:09:12,790
And its major con is that it's slower than A*(star).
125
126
00:09:13,120 --> 00:09:19,330
It's actually useful in some cases, for example, generating flow fields in real time strategy games,
126
127
00:09:19,360 --> 00:09:25,480
but it's not quite useful for large data sets as it will take much more time to process them.
127
128
00:09:25,480 --> 00:09:29,320
BFS first can be used for quick custom implementations.
128
129
00:09:29,320 --> 00:09:34,240
Alternatively, you can use the already created A*(star) implementation in Godot.
129
130
00:09:34,240 --> 00:09:37,600
They work similar, but A* is more efficient.
130
131
00:09:37,600 --> 00:09:43,090
In the next chapter we will look at Godot's navigation mesh implementation and how to use it.
14611
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.