Two to the path finding video Siri's.

We originally did the A style with him, and he can look at that video by clicking on the link in the top, right.

But this time we're going to look at a slightly different algorithm, perhaps simpler than a star in certain situations, or but also maybe less useful, too.

I think it's quite a debatable one.

We're going to look at wave propagation, and this is what I'm going to be developing in this video.

And if it looks eerily familiar than well, yes, it should, because you've probably seen the programming a star video.

In fact, it looks exactly the same.

We have a starting point marked in green, which we can move around on.

We have an ending point marked in red, which I can't move around.

In this particular video, we could see an array of nodes, which are blue for empty space and gray.

Four solid obstacles on, just like with the A star video.

If you start placing obstacles, it finds different paths or in this case, it's trying to find the shortest path, and it has done on.

I've marked it with a yellow circles.

It's time to make the path a little bit more visible.

You also see that I've assumed eight way connective ity so things could move in diagonals.

We'll see in this video that that doesn't have to be the case.

We can also use four waken activity on just with a star.

If there is no path, you could have just blocked it off here than there is no path.

There's no solution that can be found trying.

Make it go a long way round and we see the performance is actually quite fine on here.

It's running about 900 frames per second now.

This is a very small area.

It has two path over.

But that's one of the nice things about the wave propagation approach to path.

Finding is it's relatively computation.

Lee Simple.

Now, just before I get too stuck into explaining the algorithm, you'll notice also that this seems to be quite a high resolution, and that's because I'm doing it in the pixel game engine instead of the console game engine on.

I wanted the high resolution to demonstrate an effect later on.

And for the first time ever in a one lone code video, I'm going to make a little personal announcement.

I've had a surprising number of requests that people would in some way like to support me.

As a result, I've created a patriotic page.

You can find the link to the pantry on below on what I will say is it is entirely up to you.

There is no obligation at all, I probably wrote Be producing any exclusive content, and it is unlikely that I'll even mention your names in any videos.

But if you'd like to buy me a cup of tea, then pop on over to the pantry on page.

When I looked at the A star algorithm, one of the fundamental assumptions we made was that the locations, the waypoints, didn't necessarily have to be organized in any particular way.

We just had a graph off interconnected notes, and so the algorithm was really tasked with trying to find the shortest path from one note to the other, knowing some sort of heuristic onto the distance between the notes.

The A star algorithm itself was computational.

Quite simple, but conceptually it was a little tricky.

And as part of that demonstration, I made another fundamental assumption.

Even though we could use a star on generic graphs like that.

In fact, what we did was have routinely position nodes in a grid on dhe.

We applied the star algorithm to nose with different types of connectivity.

So in this case, we've got four waken activity between all of the notes, and this was quite convenient and used in many real time strategy games and path planning applications for robots.

It's quite nice to represent your world as an array such as this, but this begs the question.

If we've got routine structure like this, do we need most of the A star facilities in order to find the shortest path?

And the answer is no.

For a long time, there's been an alternative algorithm based upon wave propagation.

I'm quite sure all of you will have used wave propagation, and some of you may not know that you've used it.

If you ever used the flood fill tool in paint or in photo shop or gimp, then you have used a form off wave propagation fundamentally What we're trying to achieve is the transmission off information from a starting point across the array on this way front carries the information.

The contents of the raid itself can change what happens to that way front.

So let's assume we've got an area of solid on our map on we cast out the same wave just like a sound wave.

It propagates around the corner.

This is a very useful dynamic of wave propagation.

Okay, so path finding by wave propagation is a little bit different.

And I'm gonna hand walk through an example here.

I'll start off with quite a bit of detail, but as we get the hang of it are probably speeded up a little bit.

The advantage to doing wave propagation is it works very nicely on to D grids, and we can see here I've got a two D array off well, effectively, billions.

Either an obstacle exists it shaded grey, or it doesn't.

And whereas you can implement wave propagation on nodes, it means more when you're operating on a grid.

So what I'm going to show is how we get from a start location to an end location, which I've marked with green and red dots.

Red is the end.

Green is the start.

Now we can solve this problem very quickly by looking at it, we can see which Siri's of cells do we need to pass through to get from one to the other.

But of course, the computer doesn't have this top down perspective.

It needs to generate some method of passing from one location to the other, and ideally, we want to try and find the shortest path.

Now I'm going to prime our two D array with some information already.

So if the cell contains an obstacle or a block, I'm going to fill it with the value minus one on for cells that represent empty space to fill it with the values.

Zero.

The objective here is to fill the map with the distance away from the target location.

On will do this by emitting the distance in Italian location and watching it flood fill the map.

The boundary of the flood fill is effectively are wave propagation.

Now that I've set up the array with information to help us work out where the obstacles are, I'm also going to maintain a couple of lists on these lists of notes.

Now I'm going to use the word node or sell interchangeably here.

Typically, Node wouldn't really be implied on the two d matrix like this, but that's what I mean.

Now, to start the algorithm, I'm going to prime it with the target location.

So in this list on the left, I'm going to put in the coordinates of where we want the path to stop.

That's five in the X axis, one in the Y axis on.

I'm going to set another value called De Tau one, and D is going to represent the distance.

And so here we go.

I'll step through the algorithm, quite verbose.

Flee to start with.

We take the first entry in our list of discovered nodes, and we look at the devalue on.

We write the devalue to that location.

So 51 is.

Here is where we end the path, so we'll change that zero to a one.

That's the first step.

The next step is to look at our immediate neighbors and see if the value they contain is non zero.

If it is non zero, we're not interested.

So let's have a look.

We'll take the northern neighbor first appear, we can see its value is minus one.

I'm not interested in that note.

Well, look at the eastern neighbor here.

Well, that's minus one.

Also, that's not zero.

Now we'll look at the southern neighbor.

We can see the value is zero.

And so this means we want to do something.

We have discovered a new note.

Nothing has touched this note before, but it's a valid know that we're interested in.

So I'm going to add the coordinates off this new note to my second list here.

So this is a five in the X two in the why on dhe To calculate the devalue, we take our current devalue, which is one and add one to it.

So D in this instance becomes, too, on al drawer square around it to say that that's a newly discovered node.

The final neighbor left a check is our western neighbor on Indeed, Again, the value is zero.

So that means we have discovered and no, that's not been discovered before, so we'll add that to our list as well.

In this case, it's 41 on two again because we take the value of our current node at one to it and stall that is the distance in our newly discovered node list.

So for our first node here, which is the end location for the path we've now finished the algorithm.

Let's move on to step two.

Step two is quite simple.

We look at our list of newly discovered nodes on we remove any duplicates.

Well, we haven't got any duplicates here.

And so what I'm going to do is remove the note that we have now processed copy over our newly discovered notes and clear the newly discovered node list.

So let's continue with the algorithm we're now up to here.

So the first thing we're going to do is find this note.

This is five and two.

So that's this node.

Here on first stage is to take the Devalue and write it into the cell.

So we'll replace the zero here with two.

We then start checking our neighbors who are looking our northern neighbor.

Well, that's non zero.

That's a one, so that neighbor has been seen before.

It's not new, so we're not interested in it.

Let's look towards our eastern neighbor.

Well, that's a minus one that's non zero.

Not interesting towards our southern neighbor.

Well, that is a zero.

We are interested in that one somewhere.

To add that to our newly discovered node list.

In this case, it's location five by three on we take our current devalue wish in this case is, too.

We add one to it and store that as the new devalue.

Now all we've got left is our western neighbor, which again is zero.

It's a cell we've not discovered.

I'll just draw in the newly discovered cells on.

We'll add that one also to our lists.

In this case, it's for two and again three because we take our current devalue and add one to it.

We have now completed at this note so we can smooth shit out.

There we go on, we look at the next load that's in our list for want to, which is here.

The first thing we want to do is take our devalue and write that into the location of the cell.

So get rid of that zero and put two.

And now we check our neighbors well north is minus one.

No good East is one that's not a zero either self.

Now we have discovered this note before, but as far as we're concerned, it's still a zero at this point in time.

So I'm going to add that again to the list of newly discovered note.

This is four and a two, and we calculate day in exactly the same way.

It's our current devalue plus one, 4 to 3.

We've only got one note left to check.

Now that's our western neighbor.

Well, that's a minus one.

That's not very interesting.

And then we're done.

So the next phase is to look at our newly created nodes and remove the duplicates.

And we could see we did have a duplicate, therefore two and three.

So we don't want that.

Once we've got rid of the duplicates we copy over the newly discovered nodes into our list of notes to process, and we'll clear this list, right?

We're up to 533 now, so that's here.

The first thing we want to do is write in our Devalue into this cell that we check our northern neighbors, not zero eastern neighbor, not zero.

Southern neighbor is zero.

So I'll flag that as a newly discovered note, get its coordinate.

54 Take my devalue and add one to it.

So we're storing this is it for this time.

And finally check my western neighbor against one is zero.

So it's a newly discovered node going to capture that it's Ah, 434 this time and then we've run out of neighbors we've done north, South, East and west were done.

Squid that one out.

We're now going to process node 4 to 3.

So Step one is to write in The Devalue replaced the zero without three.

And now we check our neighbors Well to the north, I've gotten non zero to the East, her non zero to the south.

I have got to zero, so I'm going to add that to the list.

It's 43 and four.

Again.

We've got a duplicate for enough.

We know we'll get rid of that in a minute and finally got my western neighbor, which is a newly discovered node wishing this case is 3 to 4.

I've got no neighbors left now, so I've done processing that note.

It's time to look for duplicates and copy them over and remove them.

Well, I can see here I have got some duplicates for three and four.

So I'm going to remove one of them.

A copy over the new nodes.

54 and four, 43 and four, 32 and four.

Going to run out of space at the bottom.

But we'll worry about that in a minute.