How It Works: A-Star (Pathfinding) Part 3/3

Part 3 of 3 of my little series on the A-Star pathfinding algorithm.

Part 1: http://www.youtube.com/watch?v=Kw8AMmyc6vg
Part 2: http://www.youtube.com/watch?v=uIVu7ViLaZo
Part 3: http://www.youtube.com/watch?v=kcYkd1Oxnrc

More Indepth information:
http://www.policyalmanac.org/games/aStarTutorial.htm

All About Heuristics:
http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Any questions feel free to send me a message or post a comment. If you use my library please give me credit, just a thank you and I will be happy!

Downloads:

AStarTester Application (Compiled)
http://www.megaupload.com/?d=DVNI1SEQ

AStarTester + LibAStar (Source)
http://www.megaupload.com/?d=G1AJEO7O

Category:

Education

Tags:

• astar
• path
• finding
• pathfinding
• a-star
• algorithm
• A*
• dooobs
• doobs
• hojo
• artificial
• intelligence
• networks
• advanced
• computer
• science
• games
• bots
• bot
• automation
• breadth
• first
• maze
• solver
• part

[Marein86]

Why do you say it's un-human-like to 'zag across'? If a human would want to move to their friend behind a wall, they would take the shortest way from where they were around the wall, not first bump into the wall and only then start moving around it (as the program does at 3:48), right?

[Dooobs]

@Marein86 Not really, in my opinion humans are slack and if you couldnt walk diagonally you would take straight lines...

[igalEpshtein]

looks interesting

where i can find this source code ?

[Dooobs]

Read the sidebar....

[Cambesa]

im not english so don't blame me for this question. what is c-sharp actualy? is that c# or c++?

[Dooobs]

C-Sharp is C# and C++ is C Plus Plus.

[nakedburrito]

I must say, that was quite helpful in helping to make my understanding lucid; doubly so given that visualizations are a lot like taste - sometimes you need just the right one to make you full. Thank you kindly for taking the time to make this. It's a testament to your clarity that you still get views years after this video's creation :)

[mdsalmaniqbal]

megaupload is inaccessible... it would be nice if you could share the source code for reference...

[wvanderp1]

can you reupload the code? megaupload is down!!!

[BrandonBlanchard]

This was astoundingly helpful thank you

[Chirmaya]

Thanks a lot for the set of three videos. This helped me get the A* concept into my head more firmly.

[iglor]

great stuff

[KoffeeAddikt]

Dude, do you have a video for D-Star?

[Julz333666]

woah, nice optimisation man! so quick.

[jeanfrg93]

Assign diaginal paths with a 7 score and str8 paths with a 5... it will solve the bugs

[NeilRoy65]

Very nicely done, thanks, you explained that very clearly. Clear enough that am confident I can recreate it without seeing any source. :) (at least I'll try)

I done my own simple pathfinding a while ago which basically starts at the end, marks that with a ZERO, then marks all surrounding walkable locations with 1, marks all movable locations surrounding the 1s with a 2 and so on until you reach the start. You then can move from start to finish moving to the path with the lowest number.