Welcome back to part six on the Easter algorithm.
Now, although I said the concept is really simple, the code just goes on and on, but we're almost,
almost done.
I think I might have actually said that in the last video.
Anyway, what you've got so far, you should be able to run.
So I hope you had a little bit of a look at it.
But if you couldn't kind of work out what was going on, let's just run it through with you.
So let's press play and we'll generate our ten by ten maze.
So here it is.
Here.
Now, if we hit the P key, we'll get a starting and ending node system sitting in there.
Now, when you hit C, it's going to generate positions on, you know, to start exploring basically.
Let's see if I can just turn this around so we can see the values on those nodes.
There you go.
So we've got G, H and F values just in there.
Now, if we hit C again, then we'll start adding more.
Now, as a node is explored and put into closed, it becomes red, which means we don't explore it again.
So then we keep going and you'll see that we're searching out in both directions until we find a path
all the way to the end.
At which point, if you keep hitting C, nothing's going to happen.
So we've actually found the point here is our final position this way didn't work, we ran out.
And what we have to do now is to actually get the path.
The path isn't all of the red nodes, okay, because they're over here.
So the path to get to here doesn't actually involve these nodes.
We just searched through them.
The path can be found by getting the last node and actually working our way back around to where we
started from.
Now at this point you can hit the p key and because of the way that we coded this, you can start again
and then work through that at your own pace.
To get a better understanding, you'll be able to see how the G, H and F values get updated and changed
in here.
Now, if you want to work with a bigger maze, you can do that too.
So if we click on our maze and come over into the recursive script and change this to say 30 by 30 and
then press play, you'll see how the algorithm behaves in a bigger setting.
Now, of course, we'd have to zoom out to actually see the whole thing, which means you could lose
a lot of the detail of the F values, but you might not be interested in that.
So let me click over here and we hit the P, there's our starting and ending and then you can just hit
the C until we just keep going and going until we eventually get to the end and find a path which could
take a little bit of time.
So I won't sit here and continue doing that, but you'll again see how we've got a lot of closed nodes
in the search that's going on over here, which is probably not going to be part of this actual path
to getting to this point.
And we want to work backwards.
Okay.
So that's the last bit that we actually have to put into our code is getting the path.
Each time we press C, we're going to do a search with our last position.
Now, if we go back up to our search, the last position is set at the end, which is the marker from
the open list with the smallest value.
And then if we have a look at the top and remember what we did is that if we passing through this node
and it's actually equal to the goal node, it's just going to return without doing anything and set
done to equal true.
So that means after we have finished finding the goal location and what I'm going to do just down in
here to make sure we don't keep trying to run that is put and not done.
It's going to basically stop us doing anything when we press.
See, now, what have we got at this point?
Well, if we have a look at an example map, what you'll see is a whole bunch of closed nodes there,
all the red ones.
This isn't the path, as I've said, these are just all the ones that we've explored and could possibly
be on the path.
The ones that are on the path are the ones linked by that parent value that we added right up here.
So here's our parent value in our path marker.
So if we get our very last node, our goal location node and follow it backwards up to its parent,
then get the parent of that one and the parent of that one until you'll get all the way back to the
start.
We will actually have our a star path.
Okay.
So considering by the time this C key doesn't work anymore and done.
Is equal to true.
The value of last position is going to have the goal position in it.
Taking that into consideration, we're going to use that to backtrack up through the parent list.
So let's put another IFF in here, input dot get key down and I'll put key code dot m for map in this
case.
And then if that is the case, we're going to get path.
Of course, we haven't written that yet, so that's going to be above the update.
Void.
Get path.
And in here, what I'm going to do is, first of all, remove all of the markers, which means we've
cleared all those little blocks off of the map and we can actually put markers just where the path is
and we'll get our starting position.
So path marker.
Begin equals the last pause.
Okay.
Now, you didn't think it was going to be that easy or that I'd let you off that easy?
What I'd like you to do as a challenge is finish this method.
So you're going to have to start with the last pause and loop somehow back up through all the parents.
Each time you encounter the parent, you want to put a marker down on the map at that location.
And this is going to happen when you press the key.
Once you've gone through all the C's and you've run out of actual markers and you've found a path,
okay, so pause the video now go and give that a go.
And when we come back, I'll show you my solution.
Okay.
How did you go with that?
Bit of a challenge, but nothing that I'm sure you can't handle.
I'm going to use a wall loop for mine.
So while we're not at the start node.
So start.
Node dot equals begin.
So we'll begin.
It's not the same as the start node and begin does not equal null.
So hopefully we actually have a path marker to start from.
While this is true, we're going to instantiate.
A path pe prefab at the position so new vector three and it'll be begin location dot x and don't forget
to multiply it by our maze dot scale zero and then begin dot location dot z multiplied by maze dot scale
and then of course a kitten in.
Dot identity.
Just to finish off the creation.
Now that creates a block or a marker at that last pause.
We want to now step up to the parent of last pause or in this case begin, because we've started at
begin.
So what we're going to do is say that begin now equals begin dot parent.
Like that.
Okay, great.
Now, once we've done that, we can also put the starting node there, the one we actually started from,
just in case it's not in any of these lists.
And the start node actually doesn't have any parents or anything, so it might be left out.
So I'm just going to instantiate that.
Path pea new vector three start node dot location dot x multiplied by our maze dot scale zero and our
start.
Node dot location y multiplied by our maze dot scale.
And then a turn in identity.
Okay, now, because we're looping while we're not equal to the start, meaning that we actually have
to do this here at the end and not forget to put a comma at the end of there.
I just had the idea that this could be a do while loop, which would then incorporate that in there,
and you may have actually done that yourself.
So if you did, well done and this is pretty much it.
Noticed I've just got a Y there instead of a Z.
If you've come up with something different for this loop, then please do share it on the forums or
the Q&A wherever you can get in touch with us because we're always interested to see in how other people
have solved the same problems.
And as I always say, my code is not the most optimized or efficient.
It's built so that you can actually read what I'm doing.
Okay, so let's save that.
We're going to go back into unity and we're going to try this out.
So first of all, let's go the maze and make it smaller again.
So let's make it like 15 by 15.
Okay, so we press play, which will get us our maze.
Let's just get that into the screen so you can see it.
Now we hit P, which will give us our starting and ending positions.
Then we hit C until we actually find a path.
And this is the case.
It's quite easy.
Then if we hit M to get our path, you can see that goes through and it deletes everything and just
leaves you what is in that path list.
K Let's have another go.
So let's go to P again.
They're a little bit further away this time and we hit C until we exhaust our search or get to the end,
which we're going to K and then we hit the key and it gives us our path from one to the other or this
one goes like that and around there, okay.
So that is the a star path algorithm visually represented so that you can actually work through it,
work through the values and the calculations of the G and F.
So you really get a handle on how it works.
And trust me, there's no end to the uses for this particular algorithm.
We see it all the time in AI, so I hope you really enjoyed this section and you got a lot out of it.