Original subtitles

0 Welcome to the Data Structures Bonus Section. 1

In this module, we will look at various data structures that are useful in game AI algorithms. 2

In order to implement the game AI, we need to store information and we do this by using variables or lists. 3

But for the algorithms, sensors, pathfinding and other things that are required for game AI 4

algorithms, well, we need more data structures. 5

Let's look at some other options that are out there and how can we use them. 6

Let's start by looking at the queue. 7

The queue is very similar to a list. 8

That means that it does contain data stored in an array-like format similar to a list. 9

It's an abstract type, which means that it doesn't have a specific implementation. 10

But in most game engines and in most languages, it's already implemented in a way or another. 11

The main difference from a list is the fact that the elements in the queue get added only at the end 12

of it as here, and they are removed only from the beginning of it as here. 13

And this is very similar to a cinema queue in real life. 14

Now let's look at the implementation of the queue in GDScript. 15

Here we have a queue, which is basically a list in Godot, and we can use the append function, which is 16

the same as for a regular array. 17

And the result is of course, [1], [1, 2], [1, 2, 3], and actually append at the end of 18

the list. 19

So it's really good for us. 20

If we print this out, then this will be the answer. 21

And as I mentioned, we only need to remove elements from the beginning. 22

In order to do this. 23

We can use only this function called pop front, which will give us the first element in this case is 24

1 and the queue will remain with just 2 and 3. 25

The queue is very valuable in algorithms for pathfinding, but not only. Let's now look at the graph. (the graph) is also 26

an abstract data structure. 27

That means it doesn't have a strict implementation. 28

The user can implement it as they see fit, but a graph's main feature is its nodes, which can store 29

data as data containers and they can be linked together with edges. 30

Of course, if we arrange them in a grid shape and we put edges between all the neighbors, we end up 31

with a grid-like shape. 32

So basically a grid is just the specific case of a graph. 33

Please keep that in mind because we use also grids in this course. 34

So how can we implement graphs? Well, there are actually a couple of different ways: 35

This first implementation, while it is simple, I don't think it's really that much used maybe in some 36

particular cases, but it's really easy to understand. 37

So just imagine that each node has a specific ID. 38

In this case, it's 1, 2, 3, 4, 5, and we have a matrix or a 2D array that has 39

indices for each row and column. 40

And if we take a pair, let's say [1, 2]. 41

If the value here is 1, that means that there is an edge between them. 42

And if it's 0, then it means it's not. 43

So with this same logic, then of course, this diagonal is 1 - 1 - 1 ... because it's for the same element. 44

But then for [1, 2], [1, 3], [1, 4], [1, 5], we have the relationships. 45

So basically only [1, 2] has it. 46

Please note that also if we cut this diagonal, all of these values are mirrored, and this is because 47

this graph can work in both directions. 48

So for example, from 1 I can go to 2, but from 2 I can go to 1. 49

So if I query instead from 2 to 1, it's also 1. 50

So this is the first graph implementation. 51

Let's look how this can be made in code. 52

And for this, I use a particular functionality called array2D. 53

Please note that Godot by default doesn't support 2D arrays. 54

So this is actually from a library called GodotNext. 55

You can find it by quickly searching on Google. 56

And the first thing of course is to create a variable called grid, then to give it a size, which 57

in this case is 6x6. These two FORs are just to set everything to 0 and this is just to 58

make sure that everything is clean and then we can set up the relationships between them. 59

So from 1 to 2, we have 1. 60

From 2 to 1, we have 1 as well. 61

And if we move down for each pair of nodes, we have the edges. 62

So basically this is how we can implement the graph using this kind of structure. 63

Now one common issue is: okay, we have a graph, but we need to actually go from element to element 64

and how can we do this? 65

There are a couple of ways how we can implement this, and the most common ones are breadth first search (BFS) 66

and depth first search (DFS). 67

And in fact, these are also used for pathfinding algorithms. 68

In the example in this session we will discuss the depth first search. 69

But if you check the section "Anatomy of a Pathfinder", we will discuss the breadth first search (BFS) as well. 70

So make sure to check that. 71

But how is the depth first search implemented? 72

It's a recursive function if you don't know what the recursive function it's in the previous module. 73

Quickly, just to sum it up, it's a function that calls itself. 74

So that's one point. 75

And the other it needs an exit condition. 76

That means a way for the function to actually not call itself to infinity. 77

And we do this by using something called was node visited. 78

So we will use a secondary array that will store the IDs of the nodes that we already parsed. 79

So how does this parsing work? 80

Basically we have a function, let's say parse graph it receives a node ID, let's say 1. 81

It prints that 82

node ID 83

And then it puts the node ID in the list. In the visited list. And then for all the other IDs, 84

and we remember that in the previous one, the grid was of length 6. 85

So in this case, for every possible neighbor, we can check if the cell from the current node to the 86

other value is different than 0. 87

Then this means there is a connection between them. 88

But of course "i" here and current_node might be the same node. 89

So they are always 1. 90

So we need to make sure that is out of the question. 91

But luckily we have this. 92

So this node needs to not be visited already. 93

Let's see if it's the same node. 94

So it's 1 then this would be false because it's already visited. 95

This also works 96

for example, we are in 1 and then we move to 2 and then we go back. 97

We cannot actually go back because 1 is already visited. If we are here, 98

so okay, we are in 1 and we find out that the next node available is 2. 99

Then we call this for 2. 100

I actually have an example, so don't worry about not understanding this code properly. 101

Basically it runs until there is no other neighbor for it. 102

Let's find out exactly how it works in an example. 103

So here we have a little different graph. 104

I want to run the algorithm, with you, starting from the first point. 105

A depth first search (DFS) would go first in the depth of the graph, hence the name depth, and then go back when 106

it's no longer possible to go forward and then try another path. And, in the end go to the first node 107

and finish the algorithm. 108

So let's start: 1 109

The first node available is 2, as noted here. 110

Then we have 3. 111

And then, as I mentioned, the next one is in depth. 112

So it would be 6, not 4. 113

So it's 6. Then, 114

this node has no other neighbors, so that means that the parsing here is finished and then we move 115

back to 3. 116

It's also noted here, but with red. 3 is also finished because it doesn't have any other neighbor. 117

It goes to 2. 2 as another neighbor. 118

So it goes to 4, then 7, then 8. 119

Then it goes back to 7, goes back to 4. 4 still has one more neighbor 5, 9. 120

So these are the actual nodes that get parsed. 121

And then going back 5 again, 4 to 1 and the algorithm finishes. 122

So what we will see on the screen are these numbers with the red ones missing. 123

Basically this is a graph traversal using DFS. 124

BFS works a little differently because it will parse 1, 2 and then 3, 4, 5 and then 125

6, 7, 8. 126

So see, it's more like a spread instead of going in depth first. 127

Okay. 128

Now let's move on with the different implementation for the graph. 129

And this is implementing via classes. 130

So basically that means to have another object of (data) structure that has the list of its neighbors included. 131

And then we can have multiple nodes that specify their own neighbors instead of matrix that actually 132

contains all of this. 133

This is actually more useful in a lot of real cases. 134

For example, in the case of intersections in a city, for other cases where we need more flexibility 135

because with the matrix we are kind of dependent on the size. 136

But with this one, we actually use all the possible elements. 137

One special case for the graph is called directed graph, and this means that once we go from 1 to 2, 138

in this case, we can no longer go back to 1. 139

Because while 1 does have a connection to 2, 2 does not have a connection to 1. 140

If we were to implement this with the array2D method, then that would mean that we have a connection 141

from 1 to 2. 142

It would be 1, but from 2 to 1 it would be 0. 143

And in the neighbor method, we would have probably an object to the ID being 1. One of its neighbors 144

being 2, and then the object to the ID 2 that doesn't have the neighbor 1, but has the neighbor 145

3 and 4. 146

This is it with the common data structures in game AI algorithms. 147

Of course there might be others, but these are the most common ones.