All language subtitles for 1. How Pathfinding actually works

Here we are at pathfinding.
1

Pathfinding basically means an algorithm that given the point A and point B, of course, they should
2

be different.
3

It returns a sequence of steps that any object from point A can take to arrive to point B.
4

Usually these steps are optimized.
5

That means that it tries take the shortest route possible. At the core
6

the pathfinder searches a graph from a starting point to the end point from neighbor to neighbor. An algorithm
7

that's mostly used in game development for pathfinding
8

is called A*(start).
9

This is mostly hidden between layers upon layers.
10

For example, even in Godot, you can call it via a function and you don't know what exactly happens under
11

the hood.
12

This is good and bad at the same time.
13

The good part is that everything is kept simple.
14

You just use it, set it, and forget it.
15

The bad part is that everything is hidden from you, and if you want to customize it, you tweak it
16

a little to make your game special.
17

Then you will encounter some issues because, well, it's basically a black box.
18

But don't worry, because in this module we will be creating our own Pathfinder from scratch.
19

It's not as efficient as A*, but it's quite efficient for a lot of game types and also for some
20

structures that cannot be achieved with A* such as a flow field.
21

At the core of every Pathfinder, there are two parts: the domain and the actual algorithm.
22

Let's find out about each.
23

The domain or also the space is where the algorithm happens, where the AI knows what is a wall,
24

what is the space that it can move, what are some other obstacles and some destination targets?
25

And it's important for the domain to have these characteristics: Fast
26

The domain query needs to be fast because when you have 100 units doing the same queries over and over
27

again, then if you have a complex 3D environment, then not being fast means that your game will be
28

lagging and it will give a bad experience for the player.
29

For this, we need a simplified version of the environment.
30

One example of this is called navmesh or navigation mesh.
31

The domain also needs to be reliable.
32

That means that any domain that provides wrong paths through the walls or through obstacles is bad because
33

of course, it's clearly not working as intended.
34

So every query to the domain should be similar to what would be in the real world example.
35

And lastly, the domain should be stored properly.
36

And what I mean by this is using the correct data structures, because if you use the wrong data structures,
37

then it will take time to query the actual domain.
38

So of course, it needs to be stored in the proper ones.
39

We will use graphs for this.
40

Now let's look at the algorithm of a pathfinder. And there are many algorithms to do it.
41

A*(star), Dijkstra,
42

Depth-First Search (DFS), Breadth-First Search (BFS) and much more.
43

What they have in common is that they give you from point A to point B a path.
44

They work differently, and most importantly, they have different speeds of execution.
45

So some are faster and some are slower.
46

But of course, they do have slightly different results that can be used a little in more or less ways.
47

The algorithms can be categorized in two parts.
48

Uninformed and informed.
49

Uninformed means that the algorithm doesn't know more about the environment, except that what's a wall
50

or what's a space that it can use. Informed the means that the algorithm knows a lot more.
51

For example, this terrain is a swamp.
52

This terrain is grass.
53

This terrain is ice.
54

So of course, it has much more information about it.
55

In the next chapter, let's look at the pathfinding algorithm.