Original subtitles

0 Now that we have implemented our first pathfinding algorithm breadth first search, let's put it to the 1

test and execute it 2

with a grid. And you can find this example in the attached project for this course, but I'm going to 3

quickly show you how to use it. 4

So you have the left click to put the start position, left click again to put the end position, and with 5

the right click we can specify some walls between our two positions. 6

This will actually make the map harder for the algorithm. 7

And if we click execute, then we can get a step by step path from the origin to the final position. 8

Now, let's see if we put the start position and the end position and execute the algorithm step by 9

step. 10

So the first step is actually to check the direction above. 11

So we'll see. 12

The next position is labeled two because we need two steps to go here. 13

And in our queue we have [1, 2], which is this one. 14

It's line one and two. 15

Please note that the first line is zero and the first column is also zero. 16

If we click next step again, then the right position was checked. 17

But it's a wall, so nothing to do here. 18

The next one would be down. 19

So another wall, nothing to do here but the left position in this case, it's okay. 20

So this would be added to the queue as well as the step number would be updated 21

with two. Now, 22

if we proceed, the first one to get out of the queue would be [1, 2], which is this one and we'll 23

check top, left, down, which is already parsed so we don't count that and left. 24

Let's do it. 25

As you see this position ended because there's no way to continue. 26

So the algorithm will just continue with this and this. 27

And boom, now we have the end position. 28

So this is how breadth first search works. 29

Of course, it is good to keep in mind that this is the first step because we need to recreate the path 30

and to recreate the path. 31

We use the recursive function that we discussed in the previous section.