The star algorithm was invented by computer scientists Nils Nilsson, Peter Hart and Bertram Rafael
while working on developing a navigation system for the Shakey, the Robot Research Project at Stanford
in 1968.
They had two algorithms that they were working on at the time, trying to find optimized ways of determining
paths through environments.
They called them a one and a two.
It turned out that a two was actually the most optimal, and so they then just called it a star.
The aStar algorithm is pretty synonymous with A.I. in games and used everywhere from planning actions
and characters to determining the best path through an environment.
The star algorithm tends to be something that's a little bit scary when you first get into computing
and you have to develop your own and often you'll find your own library and just use that instead because
it's going to work and then you won't have to understand what's going on underneath.
But it's a very intuitive algorithm based on the way that humans actually think.
So first, let me give you a little bit of a challenge.
Given this maze that I've already created and in fact, just I guess it's a room, but you can only
move in straight up and down or side to side movements.
And I want you to think about what would your path from this starting position be to this ending position
pause video now and maybe draw yourself a little diagram to have a think about what you might do and
then the reasoning about why you did it.
Okay.
How did you go?
Well, there's a number of different ways you can go now.
You can't go diagonally, which would be the shortest path from start to finish, because we have to
move in up and down or left and right, because that's the way we're building our maze.
And so there's a variety of different patterns that you could have come up with going up and across
and up and across, nothing across until you actually hit that upper corner.
And here's just one of them.
Now, you could have gone across and down and then across a few times and then go up.
But I bet that you didn't do that.
And the reason being is that if you go down at any point from the start, you're actually getting further
away from the finish.
And so therefore your choice of which step to take next should be getting you closer to the finish,
not further away.
Okay, so now what if I told you that the maze actually looks like this and there's a bit of a problem
with the path you came up with?
There's actually a wall in the road, and therefore you can't go that way.
Which way would you go instead?
Well, you'd head down to begin with and then come back up again, because that is the only way that
you can go.
But the thing is, when you don't know, those walls are there, so you can't actually see that far
ahead.
You're wanting to move closer to your goal position because that seems to be the more intuitive way
to go.
And this is really the basis of the star algorithm.
It wants to keep trying squares that are closest to the final goal.
Let's step through how a star works by considering this map.
Starting in the bottom right corner, we have to decide which neighbour to pick.
Remember, we are only moving vertically and horizontally.
However, if you did allow a diagonal move then you would have one more extra neighbor.
The algorithm will work the same, but we aren't doing diagonals at the moment so we can forget about
that particular point.
So which neighbor to make part of the path?
Well, if you eyeballed it, the distance in a straight line from each of these neighbors is pretty
much the same.
Well, it's exactly the same, but a computer algorithm can't eyeball it.
It can, however, calculate the distance that the goal is away from each neighbor.
So we first add to our star algorithm the value of H.
Now H ideally represents the cost of getting from the neighbor to the goal.
In this case, we are going to use the distance as our cost.
Though you could include other things in the cost, such as the shorter path might take you through
a love of bit and therefore you wouldn't just consider the distance as one of the things included in
the cost, but also how much damage to the player it will cause.
So in this case, the distance for each neighbor and thus the h value is 5.8, which I determined using
Pythagoras theorem.
You could also determine it using the number of X moves, plus the number of Y moves between the neighbor
and the goal.
It doesn't really matter how you measure it, as long as it's consistently done for all neighbors to
understand the next value used in the algorithm, we will take a quick look at an example.
Let's say two people are travelling from the surf club to the golf club.
At some point in time one person is here and the other is here just by eyeballing where they are.
Can you guess which one took the shorter path?
If you were to just take their distance to the goal, you wouldn't be getting the full story of how
far they had already travelled.
However, if you combine the distance from the points to the start with the remaining distance, you'd
have a better idea of the total distance travelled by each, and then you could figure out what the
shortest path was.
And that's what the estar algorithm does.
It considers not only the distance from the point to the goal, but also how far you've travelled to
get to that point.
In this case, the distance from the start to each neighbor is one.
This value is denoted by the variable g.
We then combine H and G and get an F value, which is the total of these.
Essentially, the F represents the fitness of that particular neighbor to be on the path towards the
goal.
Once all neighbouring values have been calculated, the neighbor with the lowest F value is chosen as
the next point on the path to keep track of which points have been visited.
There is an open and closed list, so obviously START is going to go on the closed list after its neighbors
are generated because it is well, definitely on the path.
Next, in this case, we have neighbors with the same F values.
So we can choose either one because neither is lower than the other.
So let's just go up.
We add this point to the closed list and then open its neighbors.
Any new neighbors are added to the open list.
Their H, G and F values are calculated in this case.
We now have two points in the open list.
Where do we go next?
Well, we find the point that has the lowest F and we go back to there and have a look at its neighbors.
So in this case, we actually go up for a little bit.
And then because the F value of the Green Point down the bottom is the smaller one, we come back to
there and put it in to the closed list and then open its neighbors.
And we continue like that until we reach the goal location.
Okay.
Let's have a look at an example of this working.
Okay.
So I've generated a maze using the recursive method.
Plus I've done a little bit of random wall removal and I've put in here some markers to show you where
the start and end for our A Star is going to be.
So the orange is the start and the yellow down here is the ending position.
So each marker is going to show you a G, H and F value.
So G is the distance from the start which is here can you can see that it's one for that one and one
for this one.
So these were the two neighbors that you could move into and the h value is the distance to the yellow.
So I'm just using a straight old distance calculation Pythagoras theorem.
And so from this one it's 4.47 and from this one down here it's 4.24.
So this one is obviously closer.
The F value, which is the addition of those two, gives us 5.24 for this red one and 5.47 for the purple
one.
Now, both of these get put into the open list and then the one that has the smallest F value in this
case, this one gets picked out as the next point to have a look at to generate neighbors from now.
That's why it's gone red.
So it's going to go immediately red as it selects the next one from the open list.
So it gets taken out of the open list, which means it can't come back to that one.
Okay, so now let's go and have a look at the next values that are generated.
Right?
So this one here generated some neighbors.
Now it's gone back and generated one at the start, which is okay, because in this case I don't have
my start added into the open list at the beginning and then it's not marked as closed though.
I could do that, but this still works anyway.
Let's have a look at the distance values.
So the distance of this one from the start is going to be the distance that it's parent one is so where
it came from, which was one plus the distance from there.
Okay, so now we get two, which makes us two from there.
So we add this distance and this distance, the distance is then this distance across to here.
Now this got it calculated as well, but because it's further away, it's basically going to get ignored.
This one here would then have had its values updated again.
So it's going to be still one from the actual start, which is still here.
Now, you might be wondering, why does this say 24g up here?
Because this was a node or a neighbor of this one, and it actually went the path to get back to this
one, went like here and then back to there.
So that's why that's a two.
And it puts it out of contention basically because it's a very high value.
Okay.
So let's have a look at what's going to be chosen next.
This one obviously, because it's gone red already and it's been put in the closed list, 5.47 for the
F value.
And down here we got 5.61.
So this one is just going to sit in the open until it becomes a smallest, if ever.
Okay, so let's go again.
Right.
So now this one has generated another point back to there, which is just basically ignored.
And its other neighbor, which is over here, has its G, which is two.
Okay, because it's like one, two and then it's H value which is 4.12.
Again, this distance here gives it 6.12.
This value here got recalculated or reused because it was still open, remember?
And so it's smaller, so it gets chosen.
So now the neighbors for this will get generated.
So that means this one gets generated.
Remember, that one's already in the closed list, so it won't happen.
Okay.
Now, if we have a look at these two values, we can see that this is obviously going to be the closest.
So we go again and we get here.
Now, look at this.
This one is now 6.24.
Even though it's actually closer, we can see physically that it's closer.
This point up here is 6.12.
Now, this was still open until recently, just went red, which means it's in the closed list.
It's the one that's going to get the next neighbor calculated.
So if we go for that, it didn't generates a point over here.
Now, it ended up with an F of seven, which put this one back into contention.
So we've come back to here.
Okay, we get some more neighbors.
So these two, this one ended up closer, then we generate another neighbor there.
Okay.
Now, if we have a look at these ones that are open, you can see that they are, in fact, all values
of.
Seven.
So it's just picking one of those at random because it's going to order them by the smallest, but they're
all the same, so we're just picking one.
So we've just bounced up back to there.
It'll generate this one, which is 8.12.
Now, you saw that this went red, so it decided it would pick this one instead, which generates that
one, which then comes down and generates this one, which is our final value.
Okay.
So you can see that the a star doesn't just go dum dum dum dum dum dum all the way down here.
It actually will bounce back and forward a bit as it explores more of the stuff around it.
The beauty of that is that it's never really looking ahead too far at all, okay?
It's only ever calculating those distance values, the distance that you've already travelled and the
distance you've still got to go, basically.
Okay, so now if I just hit my mapping key that I've programmed in, it will show us our path that was
calculated.
Now to get the path at the end, you end up with all of these neighbours or nodes.
We could call them in the closed list right back to here.
So what we do is we start with this one and we follow it back to the points that we came from.
So as we're travelling around, every time we go to a new neighbour, the neighbour has to remember
its parent.
So in the end we can travel back up through that parent tree and get our path.
Okay, so that is the star algorithm and how it works.
So it is quite a simple algorithm.
I mean, the ideas are very simple.
It's not doing anything extraneous, like I said, looking ahead or anything like that.
And so now I hope that you have a better understanding conceptually of how it goes together, because
when we come back in the next lecture, you're going to actually build this into your maze system.