A* Pathfinding (E01: algorithm explanation)

Welcome to the first part in a series teaching pathfinding for video games. In this episode we take a look at the A* algorithm and how it works.

Some great A* learning resources:

If you'd like to support the creation of more programming videos, I'd greatly appreciate your support on patreon:

Background music is 32. The Hidden Path by longzijun.

[abledbody]

I wish more programming tutorials explained things like this, the concept itself instead of the steps to create it. It's so spectacularly simple.

[doxel]

i give this tutorial an A*, good job!

[satyamedh]

8 years later still one of the best resources out there, THANKS!

[Denigrate]

Just wanted to say thank you for this video. The extremely clear demonstrations coupled with the pseudo code at the end made the algorithm clearer to me than any other explanation I have watched or read. I was actually able to write my own A* pathfinding algorithm from scratch after watching this video several times. Thank you, thank you, thank you!!!

[iAmVonexX]

this video is 8 years old and just gave me the idea to a game i will now start to plan and later make. this is finally the projectidea i needed to get myself into programming. thank you sir for your inspiration!

[Pppp-yflj]

dont think its possible to explain this algorithm any simpler and clearly, really well explained

[narf]

this is 1 of the best explanation of A* algorithm, thank you so much.

[raksipulikka]

nice formula for calculating heuristics :

h = min(dx, dy) * 14 + abs(dx - dy) * 10

where
val dx = abs(goalXcoord - nodeXcoordinate)
val dy = abs(goalYcoord - nodeYcoordinate)

where abs(x) returns the absolute value and min(x, y) returns the smaller value of the two inputs.

[creationsmaxo]

Thanks a lot for the information (and the detailled tutorial) about the A* path finding.
The cool thing is that I have upgraded the algorithm in my own way (though it's still a work-in-progress...)

I added something you rarely see inside an algorithm such as A* : the ability for the AI to do mistakes!
I know this might sound counter productive because the goal of the algorithm is to find the right path... but I added 3 layers in the behavior that can overtake the suggested path.

The first thing I added is the ability to the AI to be distracted.
So it has :
• A "MainObjectifAttention_Value" float + "MainObjectifAttention_V3" vector3,
• A "SubObjectifAttention_Value" float + "SubObjectifAttention_V3" vector3,
• Everything that can be a source of attention has an Attention multiplier.

For example, an AI spot the player which has an attention multiplier of 2.0 which quickly raise MainObjectifAttention_Value to 100. Once above 50, It starts following the player around, but loose track of it around a corner. The NPC move toward the corner where the player was last spotted then, the value starts dropping slowly. I also added "Points of interests" with a type category which, if compatible with the AI points of interest, raise the AI' "SubObjectifAttention_Value" while dropping "MainObjectifAttention_Value" and if the "SubObjectifAttention_Value" become higher than the "MainObjectifAttention_Value, there's a switch and the Main become Sub and vise versa. When "SubObjectifAttention_Value" is below 1, its vector 3 become the "point of origine" (or spawn point) of the AI and its value raise back toward 50 (not 100). As the previous statement... when the MainObjectifAttention_Value drop below 50 while the Sub is the point of origine, there's a switch and the AI return to his own spot.

The opposite is also possible as if the AI move close to a node that contains something it doesn't like, a multiplier will be added onto the node's value. With this, it's possible for example, to make an AI only move close to something like a trap or a pit of lava or acid or whatever harmful if they actually have an objective near it... It also remove the context where you see some guarding monster stationed right next to some lava pit without any kind of safeguard.

For example, if you have a game with vampires and werewolves moving around, you could put a 1.5 multiplier onto nodes with crosses, 1.2 multiplier onto nodes with garlics and 2.0 onto nodes with sunlight... So if it's "right" next to its target within sunlight, 2.0 multiplier would ensure it never wants to move there... yet the werewolf wouldn't be affected so for it, the block is 1.0 of value. You could also put point of interest (so lower multiplier) which makes an AI to do a small detour of 1 node when passing close to something... Like a dog passing next to a juicy piece of meat... which would have value multiplier of 0.5 (meaning the value would half so 2x more attractive to pass through.)

Finally, I added the effect that whenever a attracting or a unwanted thing come close to the AI, there's a chance that its MainObjectifAttention_Value drops 2x faster. or even alter the target destination a bit by cutting a couple of the last nodes from the path found.

So... Yeah, thanks a lot!

[dushanrathnayake]

Best A* tutorial from a person who knows what he is doing and not like other tutorials that read something from a textbook without any reasoning behind it. Thank you!

[PsicosisYT]

Literally made an entire library in like 2.5 hours with this explanation, the delivery and visuals were perfect.

[hadowfife]

After watching other tutorials I thought that pathfinding is hell, but this one is perfectly simple, took less than 2 hours to implement it for my game

[VladiMatt]

This is WONDERFULLY informative, thank you so damn much for these videos - pathfinding has always been something I struggled with because I hadn't the slightest idea as to how it really worked, but this explained it in a super easy to understand manner.

Liked, subbed.

[BarryGoodall]

A very clear and easy to follow example with step by step exlpanations. Thank you.

[CCcrafted]

By comparison to other tutorials/ explanations on this topic which I have seen, this is by far the best

[RedEyedJedi]

I only recently found this channel and I'm so glad I did. Sabastian goes into the perfect level of detail needed to fully understand the concept he is teaching. Rated A*

[apha]

You are using a square grid. THANK YOU ! So many people are trying to explain this using rounded bubbles and diagonal movement. I need this JUST for the computer. Just for the video games I'm writing. Hopefully your tutorial will finally explain how this method works.

[christophersavignon]

I have not seen an educational youtube video of this quality and clarity in quite some time.
I only coded as a little hobby years ago, but this actually makes me want to start again.

[Legenjerry]

the pseudo code walkthrough at 7:35 helped me implement the algorithm from scratch very quickly, thx!

[afandiyusuf]

Finally A* explaination that just 10 min, great explaination kudos to you.