Original subtitles

0 Anatomy of a pathfinder. 1

How does the AI know how to get from point A to point B, on a map? 2

What is the code sequence that enables that? 3

The code is an algorithm and there are many pathfinding algorithms out there. 4

In this chapter, we will look at the simple pathfinding algorithm called breadth first search (BFS). 5

BFS is an uninformed algorithm that deals with the situation at hand. 6

Its end result is a path between the starting node A and the final node 7

B. 8

Let's deconstruct the algorithm and see how a pathfinder works. 9

We will start by defining the space and for the space or domain, we will use a grid because it's one 10

of the most easiest ways to implement it. 11

Any position on the grid can be referenced using two indices: row index and column index. 12

For example, these positions. Regarding the implementation, a grid can be simply implemented with a list 13

of lists or an array 2D like this. 14

So it has one list that has multiple lists and each value represents a cell here. 15

Of course, it's good to know that we need to fill the space in order to simplify our edge cases. 16

And for this we'll consider the wall being -1 and the empty space being 0. 17

And we will mark the exterior of our grid with -1, which is the wall. 18

Let's quickly go to the queue, by the way, if you want to know more about the queue, there is the bonus 19

section where we discuss about the queue in much more detail, but basically the queue is just a list with a 20

spin. 21

You can only add elements at the end of it and you can only remove them at the beginning of it. 22

This is very similar to a cinema queue. 23

The queue is an important part of the breadth first search algorithm. 24

The next step is, of course, to study how we are going to move through the grid. 25

And if we take a position, let's say [3, 3], line: 3, column: 3 or simply 3 - 3, 26

then we can adjust the up, down, left or right movement by adding or removing one step to 27

either the column or the row, because you only move four directions and these new pairs of values will 28

be the next positions for our object that has the pathfinding algorithm. 29

How can we encode the movement patterns to be easily processed by the algorithm? 30

And for this we will use two lists called the DX and DY. 31

Of course you can name them as you like. 32

Basically they'll encode each step. 33

So for example, if we take the pair, that was [3, 3] initially and if I want up, I need to add 34

-1, which will be 2. 35

And for the Y, I need to add 0 because we only move row and we don't move columns. 36

So of course it's 0. 37

Let's take for the right, which is 0, so we don't move a row. 38

So the row needs to stay on the same one, but the column increases to this one further down and left. 39

It's the same. 40

Here's the example as you're taking the [3, 3] example. 41

By adding each of these pairs, we get these new values that are representing the adjacent positions. 42

Of course, by just adding more pairs to this list, for example, one and one, you will get this value, 43

this value, this value or this value. 44

By doing this, you'll enable your AI controlled Pathfinder to work 45

with eight directions instead of four. 46

Of course, you can even put more exotic directions, for example, like a knight in chess to move in 47

L-shape. 48

So, for example, encode this position, this position it needs to be L shapes. 49

But of course you can have any type of direction you want with this structure. 50

Now let's look at the algorithm itself. 51

Luckily for us, it just has only eight steps. 52

First, we need to add the starting point to the queue. 53

While the queue is not empty, we need to get the first position and if the first position is the destination, 54

then the algorithm reached its goal and we succeeded. 55

Yay! 56

But if it didn't reach the position, then we need to get the adjacent positions. 57

This can be done with the lists DX, DY. 58

Then we need to fill the positions and add them to the queue so they can be processed in the next step. 59

Of course, I also prepared a code because it might be much simpler to see it in actual GDScript. 60

The queue, as you can see here, is just a list. 61

I'm using GodotNext which has an array 2D, so it has a grid-like structure. 62

But basically we are adding the first position here while the queue is not empty and and the exit was 63

not found, we get the current position. Basically this is kind of the same, but this gets the value 64

of the current position because you'll also put in the steps. 65

So for example, the first step is one and then the next step is two, three, four until it reaches 66

the end position. 67

We only have four directions as you 68

remember, DX and DY where we get the X from the current position, we add the DX at the i position 69

and the same for DY. 70

Of course we get the next cell step. If the next cell is final, which is of course, if it's the goal, 71

then we don't need to work with it. 72

But if the cell is empty and this is really important because it can be a wall, and if it's a wall 73

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

adding the current step plus one. 75

So for example, if the first step was one and this cell is the next one, then it would be two. 76

And as you can see here, if you start in this position, the first step is zero, but then the next 77

step, the adjacencies are one, then the next positions are two. 78

For these steps, basically, they mean how many steps you need in order to get there from this initial 79

one, and so on and so forth. 80

By applying this, we end up with seven steps to position B. 81

I want to make an observation here. 82

Running BFS like this, it won't give us a path from A to B, it will just fill the map with how 83

many steps you need from A to reach a particular position. To get the actual final path 84

we need to do something called reconstructing the path, and we do this by getting to the last step 85

of the algorithm, which is the arriving at the position B and then we will use a recursive function. 86

Basically, a recursive function is a function that has a call to itself inside of its code. 87

You can find more in the bonus section. 88

For this we will be using this code to remake the path. 89

Let's quickly go through it and try to understand it. 90

So the first thing is we will use the current positions, X and Y, which are the end position. 91

These are the total steps that we reached so far. 92

We get the current position and the current cell 93

This is very, very important because we will be using the previous cell's step in order to advance backwards 94

through our algorithm. 95

So in this case, let's say we are here at five and we want to know what is the lower step basically. 96

So we want to go back to six, we only can go to four. 97

So these are the only possibilities. 98

If we are at four, we cannot go back to the five, so we can only go back to the three. 99

If the current cell is start, then that means that we have arrived at the destination here is setting 100

up the color, but basically this is it and if not, then of course it does the same. 101

It takes the same direction lists. 102

So of course we need four of them and we get the next position and it needs to check if the next cells 103

value is exactly one less than the current one. 104

Or in this case, if we add one, it should be exactly the same as the current step. 105

And, of course, if the next cell is not the wall. Of course the final color is not important for us. 106

This is for the algorithm to look nice, but it just returns remake path. 107

And as you notice, it is the same name as this function. 108

This means it is a recursive function. 109

And basically this calls this function again, but from the positions of the adjacent cell. 110

So if it go to the final result and are starting here, basically calling this function here will find 111

this position and we'll call this function from this point. 112

When this point is achieved, then it will call from this one and from this one. 113

And the end case is when it's called from this one. 114

And from this point, the next one is actually the original cell. 115

And this is how this function is called. 116

And it's really important when doing recursive functions to have this exit condition. 117

Otherwise the function will call itself indefinitely and it'll crash your game. 118

So make sure we have this in mind when implementing recursive functions and by running this function 119

you will end up with the final path. 120

And the final path can be used for the object in the position. 121

A to move to position B. What are the pros and cons of using BFS? 122

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

and can be used in various scenarios. 124

And its major con is that it's slower than A*(star). 125

It's actually useful in some cases, for example, generating flow fields in real time strategy games, 126

but it's not quite useful for large data sets as it will take much more time to process them. 127

BFS first can be used for quick custom implementations. 128

Alternatively, you can use the already created A*(star) implementation in Godot. 129

They work similar, but A* is more efficient. 130

In the next chapter we will look at Godot's navigation mesh implementation and how to use it.