Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
0
1
00:00:00,030 --> 00:00:02,340
Here we are at pathfinding.
1
2
00:00:02,640 --> 00:00:09,750
Pathfinding basically means an algorithm that given the point A and point B, of course, they should
2
3
00:00:09,750 --> 00:00:10,320
be different.
3
4
00:00:10,710 --> 00:00:18,540
It returns a sequence of steps that any object from point A can take to arrive to point B.
4
5
00:00:19,080 --> 00:00:21,720
Usually these steps are optimized.
5
6
00:00:21,730 --> 00:00:26,250
That means that it tries take the shortest route possible. At the core
6
7
00:00:26,430 --> 00:00:33,600
the pathfinder searches a graph from a starting point to the end point from neighbor to neighbor. An algorithm
7
8
00:00:33,600 --> 00:00:36,590
that's mostly used in game development for pathfinding
8
9
00:00:36,600 --> 00:00:37,830
is called A*(start).
9
10
00:00:38,460 --> 00:00:41,670
This is mostly hidden between layers upon layers.
10
11
00:00:41,670 --> 00:00:47,520
For example, even in Godot, you can call it via a function and you don't know what exactly happens under
11
12
00:00:47,520 --> 00:00:48,000
the hood.
12
13
00:00:48,330 --> 00:00:50,940
This is good and bad at the same time.
13
14
00:00:51,030 --> 00:00:53,640
The good part is that everything is kept simple.
14
15
00:00:53,640 --> 00:00:56,220
You just use it, set it, and forget it.
15
16
00:00:56,550 --> 00:01:03,030
The bad part is that everything is hidden from you, and if you want to customize it, you tweak it
16
17
00:01:03,030 --> 00:01:04,890
a little to make your game special.
17
18
00:01:05,310 --> 00:01:10,020
Then you will encounter some issues because, well, it's basically a black box.
18
19
00:01:10,320 --> 00:01:15,360
But don't worry, because in this module we will be creating our own Pathfinder from scratch.
19
20
00:01:15,750 --> 00:01:22,710
It's not as efficient as A*, but it's quite efficient for a lot of game types and also for some
20
21
00:01:22,710 --> 00:01:27,030
structures that cannot be achieved with A* such as a flow field.
21
22
00:01:27,300 --> 00:01:33,390
At the core of every Pathfinder, there are two parts: the domain and the actual algorithm.
22
23
00:01:33,690 --> 00:01:35,580
Let's find out about each.
23
24
00:01:36,330 --> 00:01:44,700
The domain or also the space is where the algorithm happens, where the AI knows what is a wall,
24
25
00:01:44,700 --> 00:01:50,700
what is the space that it can move, what are some other obstacles and some destination targets?
25
26
00:01:51,150 --> 00:01:55,330
And it's important for the domain to have these characteristics: Fast
26
27
00:01:55,830 --> 00:02:03,060
The domain query needs to be fast because when you have 100 units doing the same queries over and over
27
28
00:02:03,060 --> 00:02:10,170
again, then if you have a complex 3D environment, then not being fast means that your game will be
28
29
00:02:10,170 --> 00:02:13,170
lagging and it will give a bad experience for the player.
29
30
00:02:13,200 --> 00:02:16,740
For this, we need a simplified version of the environment.
30
31
00:02:17,070 --> 00:02:21,030
One example of this is called navmesh or navigation mesh.
31
32
00:02:21,060 --> 00:02:23,670
The domain also needs to be reliable.
32
33
00:02:24,120 --> 00:02:33,450
That means that any domain that provides wrong paths through the walls or through obstacles is bad because
33
34
00:02:33,780 --> 00:02:36,630
of course, it's clearly not working as intended.
34
35
00:02:37,050 --> 00:02:42,640
So every query to the domain should be similar to what would be in the real world example.
35
36
00:02:42,660 --> 00:02:45,510
And lastly, the domain should be stored properly.
36
37
00:02:45,510 --> 00:02:50,610
And what I mean by this is using the correct data structures, because if you use the wrong data structures,
37
38
00:02:50,610 --> 00:02:53,310
then it will take time to query the actual domain.
38
39
00:02:53,700 --> 00:02:56,700
So of course, it needs to be stored in the proper ones.
39
40
00:02:56,730 --> 00:02:58,200
We will use graphs for this.
40
41
00:02:58,470 --> 00:03:04,200
Now let's look at the algorithm of a pathfinder. And there are many algorithms to do it.
41
42
00:03:04,410 --> 00:03:05,500
A*(star), Dijkstra,
42
43
00:03:06,110 --> 00:03:08,820
Depth-First Search (DFS), Breadth-First Search (BFS) and much more.
43
44
00:03:08,910 --> 00:03:13,860
What they have in common is that they give you from point A to point B a path.
44
45
00:03:14,040 --> 00:03:20,820
They work differently, and most importantly, they have different speeds of execution.
45
46
00:03:20,850 --> 00:03:23,310
So some are faster and some are slower.
46
47
00:03:23,760 --> 00:03:30,670
But of course, they do have slightly different results that can be used a little in more or less ways.
47
48
00:03:30,810 --> 00:03:33,450
The algorithms can be categorized in two parts.
48
49
00:03:33,570 --> 00:03:35,400
Uninformed and informed.
49
50
00:03:35,640 --> 00:03:42,180
Uninformed means that the algorithm doesn't know more about the environment, except that what's a wall
50
51
00:03:42,210 --> 00:03:47,790
or what's a space that it can use. Informed the means that the algorithm knows a lot more.
51
52
00:03:47,820 --> 00:03:50,490
For example, this terrain is a swamp.
52
53
00:03:50,490 --> 00:03:51,630
This terrain is grass.
53
54
00:03:51,630 --> 00:03:52,790
This terrain is ice.
54
55
00:03:53,220 --> 00:03:56,190
So of course, it has much more information about it.
55
56
00:03:56,220 --> 00:03:59,460
In the next chapter, let's look at the pathfinding algorithm.
5902
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.