Coding Challenge 51.2: A* Pathfinding Algorithm - Part 2

Подписаться 1,7 млн

Просмотров 168 тыс.

50% 1

In this multi-part coding challenge, I attempt an implementation of the A* Pathfinding Algorithm to find the optimal path between two points in a 2D grid. Code: thecodingtrain.com/challenges...
💻 Github Repo: github.com/CodingTrain/AStar
🕹️ p5.js Web Editor Sketch: editor.p5js.org/codingtrain/s...
Other Parts of this Challenge:
📺 A* Pathfinder Algorithm - Part 1: • A* Pathfinding Algorit...
📺 A* Algorithm - Part 3: • Coding Challenge 51.3:...
🎥 Previous video: • Coding Challenge #50.1...
🎥 Next video: • Random Walker in p5.js...
🎥 All videos: • Coding Challenges
References:
📘 Artificial Intelligence: A Modern Approach: aima.cs.berkeley.edu/
🗄 A* Search Algorithm on Wikipedia: en.wikipedia.org/wiki/A*_sear...
💻 Online demo: codingtrain.github.io/AStar/
Live Stream Archive:
🔴 Live Stream #72: • Live Stream #72: A* Pa...
Related Coding Challenges:
🚂 #10 Maze Generator: • Coding Challenge #10.1...
🚂 #162 Self Avoiding Walk: • Coding Challenge 162: ...
Timestamps:
0:00:00 Introduction
0:00:40 Adding Obstacles
0:03:12 Dealing With Dead Ends
0:05:48 Adding Diagonals
0:09:30 Ideas For Optimization
0:11:40 Fixing Bugs in The Code
0:15:39 Choo Choo We Did It!
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain.com/
👾 Share Your Creation! thecodingtrain.com/guides/pas...
🚩 Suggest Topics: github.com/CodingTrain/Sugges...
💡 GitHub: github.com/CodingTrain
💬 Discord: / discord
💖 Membership: ru-vid.comjoin
🛒 Store: standard.tv/codingtrain
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/CodingTrain/Code-o...
This description was auto-generated. If you see a problem, please open an issue: github.com/CodingTrain/thecod...
#aalgorithm #pathfinding #heuristic #p5js #javascript

Опубликовано:

30 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 168

@noimodimi9020 7 лет назад

This guy is like the Bob Ross of coding, only more enthusiastic.

@neelparekh3448 3 года назад

*I FREAKING DID IT! I COMBINED THIS WITH YOUR MAZE GENERATION PROJECT!*

@bishakhdutta8427 2 года назад

can you share the source code

@dheerajlxst9141 7 лет назад

You're so inspiring. Keep on these videos. Love them all.

@GogiRegion 5 лет назад

Thank you so much for this. Ironically enough, I figured out how to add diagonals and go past walls all by myself just using the first video and using the octagonal heuristic from a Stanford article. I finished writing the pathfinding for the game I’m programming from the first video, and the second helped me make sure I got it right.

@danielromeo99 5 лет назад

Nice bro!

@aichabenlahrech635 5 лет назад

I ask : Why in the beginning of the video the spots moves in same time (i mean the x and y moves in the same same time )? Because he have the same (g) and same (distance) ? Every path is optimal and there are no best (g) and distance ? So he check evrey spot

@FlorianLagg 5 лет назад

really cool watching you code. that enthusiasm is great. thank you.

@TMacFuzz 7 лет назад

the no diagonal/no walls search looks funky because every path to the end using right and down movements has the same distance, so its going to search every spot. Every path is optimal.

@TheCodingTrain 7 лет назад

yes, thank for you clarifying this.

@pproba 6 лет назад

I was predicting this the moment he created the grid and defined the start and end points. I kept screaming at my screen, It was such a rollercoaster to watch...

@RobinsonGames 7 лет назад

Explained exceptionally well, as always. I'm looking forward to the neural network videos.

@TheCodingTrain 7 лет назад

Nice to hear thank you!

@KDChenStudio 7 лет назад

Hey i followed exactly your tutorial and successfully made this algorithm on my iPhone ;)

@LewisCowles 3 года назад

While I don't love the code, this looks to be a better A-star than I used yesterday, and the ability to watch the iterations is quite cool too.

@ne5i_ 7 лет назад

Darn good video. I wish your videos had been around when I was studying CompSci! Thank you!!

@TheCodingTrain 7 лет назад

Thanks for the nice feedback!

@umchoyka 7 лет назад

Not sure, but one additional change would be to calculate the diagonal movement differently than orthogonal movement. From the beginning, your "g" cost was always to add 1, but to move diagonally the actual cost should be sqrt(2).

@TheCodingTrain 7 лет назад

yes, a good point indeed!

@TiaKatt 5 лет назад

It can work to just approximate it to 1.4

@paladin1147 5 лет назад

I am not sure of the p5.js but the processing versions takes diagonals (g) distance as 1.41...... if you look in the console command

@elishmuel1976 5 лет назад

I wish I could re"like" the video everytime I learn from it

@RedouaneKhrifi 7 лет назад

your code is beautiful thank you for the great content :)

@Kalihomo 7 лет назад

I feel so great finding this hidden part 2 :D

@TheCodingTrain 7 лет назад

I always to release the full tutorial but "publish" one day at a time (seems to work best for youtube stats.)

@GABRIELFILMSTUDIOS 7 лет назад

You could actually make these private till release, so that actually nobody can see them until they are released. I think you can even let them be released automatically at a specific time.

@nicholascurry5536 7 лет назад

It would be cool if you made the path find its way outward from the center to any corner or "escape". Basically, an escape room AI... Just an idea

@zhangkin7896 6 лет назад

thx a lot! I can't believe I found this. It's so great!

@justinasbeinorius8817 7 лет назад

thanks for big work you do here!

@krakor92 6 лет назад

Thank you so much, i finally understand!

@NathanBreunig 7 лет назад

Very cool and very inspiring

@pepebec 6 лет назад

Excelent video you are awesome dude!

@JamesCoyle95 7 лет назад

You still have a bug in there. At 15:40 you can see the path moves around a red square rather than going through it. It also appears there is a shorter path through that end part. You could also take this further by considering that the path needs to be traveled by an entity which is not a single point. That means it can only travel diagonally directly if there is no wall adjacent otherwise it has to travel around the wall taking a path which is somewhere between sqrt(2) and 2 in length depending on the size of that entity. Also, ideally you would want an algorithm which can find the choke points and draw the lines between those to give a smooth diagonal path rather than one that is locked to 45 degree increments. This would probably require some sort of ray-tracing algorithm looping through the path and checking to see if there are obstacles between two points

@kuskus_th13 7 лет назад

RING THE BUG BELL, DAN

@Grizix 7 лет назад

James Coyle It's not a bug, each neighbour is considered as a distance of one, even the diagonals, but he knows that and argued that we can consider as a human for exemple that a step is the same thing orthogonally or diagonally, so moving across or around the red cell at 15:40 are two equally optimal solutions.

@76Raby 7 лет назад

I think too that it is really not the optimal way. The algorithm just before the first red spot should have gone down not to the right. Just by look of it I count 14 steps (blocks) against 17 step that the algorithm did.

@s45510325 6 лет назад

Very helpful~ Thanks a lot

@nicolascoral8470 11 месяцев назад

Thank you for this video. I know it's old but it came up when searching for videos about the A* algorithm. I do think there's another bug showing at 15'40. There's an isolated red point near the end. The path goes diagonal bottom right and top right around it. With the distance you chose, the shortest path should be straight through it. It's also showing in other examples you ran. Anyway, thank you very much. It was really interesting and well explained. May be it got fixed later.

@deltamico Год назад

Gonna leave here the heuristic for diagonal movement: y = vertical distance of current and goal x = horizontal distance of currenr and goal h = max(x, y)

@ezhilarasinanda5750 6 лет назад

You are a magician.

@elpsycongree1132 2 года назад

Loved it

@coderodion 6 лет назад

Your videos are nice, since you make complicated things look simple. Also, I want to ask, do you have a degree in CS?

@nidoking042 2 года назад

There's a significant optimization in calculating the heuristic only once for each Spot, rather than every time you evaluate it - the heuristic value never changes, so it's wasted effort. As for finding neighbors, my preferred method is to spend a bit more space and extend the grid by two in each dimension, filling the outermost cells with walls. Now you don't need to check for existence of neighbors in any direction - there will always be a neighbor in all directions for any non-wall Spot.

@DavidLindes 11 месяцев назад

I'm not really sure off hand what I would use it for, currently... but one thing I know that does use it is in the game Factorio. I think in several places -- for trains, probably, and certainly for "enemies", coming to attack you... they pick a target destination, and then use A* as a way to find what path to take. I believe they have a whole write-up about it...

@aaditya4998 3 года назад

man you are awesome ❤️

@valinkdevr5520 7 лет назад

Thank you dude

@josephandres4324 5 лет назад

Beautiful

@maximilientirard1720 7 лет назад

I think It might be more efficient to add new open paths at the beginning of the open path list. It would (I believe) safe time in cases where there are multiple paths but all of them have the same cost, like the situation in the very beginning of the video (beginning top left, end bottom right, no obstacles, diagonals not alowed). That way, it wall explore only one of all the same-costing paths.

@TheCodingTrain 7 лет назад

Great tip!

@Dayanto 7 лет назад

Was about to say this. In real world applications, it doesn't really matter much since two paths rarely are exactly equivalent, but with a grid based layout, it can become incredibly inefficient not to use a LIFO priority queue.

@tomburris8380 7 лет назад

+The Coding Train, If you had put the start in the middle, it would have shown how the algorithm works better, especially for the first part. Keep up the amazing videos!

@TheCodingTrain 7 лет назад

yes indeed this is a good suggestion.

@kuskus_th13 7 лет назад

and here I am programming a counter capable of displaying enormous numbers while Dan programs a fully functional algorithm :D

@GuardianTam 7 лет назад

KusKusPL we all gotta start somewhere. keep at it man.

@RodrigoNishino 2 года назад

Awesome

@quassseabass2770 7 лет назад

Another excellent video, Dan, and loving the new name. I've been building this alongside with Python but it's running painfully slowly, even with all the optimisation I can think of. Do you have any suggestions?

@ledues3336 7 лет назад

Python is possibly one of the slowest languages out there, or at least, so I heard

@quassseabass2770 7 лет назад

Le due S It wouldn't surprise me, I'll try it in something like Java and see if I get a better result

@hjjol9361 6 лет назад

i love your dance in generic.

@fiopio2422 2 года назад

I love your videos, but in that one there is a bug on the value of steps done, if you move diagonal it should add 1.4, not just 1, otherwise you have the same cost to move sideways than diagonal, and you don't want that, in some paths you can see that this is affecting the performance of the path.

@pianochess1882 5 лет назад

By using the taxicab-distance your heuristics will sometimes overestimate the distance (especially since you consider the diagonal steps to have length 1, but it would even if they were sqrt(2)). Example. Consider a 3x3 box. Moving diagonally takes 2 steps, but your heuristics would estimate it as 4.

@pianochess1882 5 лет назад

To fix this, go back to the Euclidean-distance and use sqrt(2) for diagonals. If you want to stick with step length 1 for diagonals use h= max(abs(i-x), abs(j-y))

@TheCodingTrain 5 лет назад

thanks for the suggestion!

@visintel 5 лет назад

The heuristic isn’t admissible even with the Euclidean distance. If we assume the goal is on the bottom right neighbor square, the current square would have a heuristic of square root of 2, which is larger than the actual distance (that is 1) since we are adding one after each step anyway

@aichabenlahrech635 5 лет назад

@kxtbit 2 года назад

two things i would like to mention: the diagonal wall check should be changed because there is a problem with the current design: if a cell had walls to its right and bottom, it could still go diagonally down right and bypass the walls. also, you could probably fix the thing where it goes out in every direction when diagonal movement is not enabled by adding a tiebreaker to the heuristic to keep it on just one path.

@souf7409 Год назад

Did you fix the first problem? That it goes in between two walls or ju

@kxtbit Год назад

@@souf7409 not sure what you mean, my comment was just a suggestion to the person making the video, i’m not the one who wrote the code

@souf7409 Год назад

@@kxtbit I meant: Did you fix the first problem? That it goes in between two walls or touches one corner of the wall. It's easy to mention it, but to fix it is hard ;) If someone knows how to fix it, let me know!

@kxtbit Год назад

@@souf7409 alright so i looked at the github repo and turns out some other people already fixed the bug. but to answer the question, what i was going to do was move the wall check from the main A* function to the getNeighbors function (so that the pathfinder will just work with whatever neighbors it gets) and then add a special check for the diagonal neighbors that checks if it also has a wall on one of the non-diagonal directions making it up. so basically, when it was checking for the up-left diagonal neighbor, it would not only check if there is a wall there but also if there was a wall up or left that would block the diagonal traversal, and if it was then it would count the diagonal as blocked and not a valid neighbor. if you wanted to allow corner-cutting then you could change it to up AND left instead of OR. hope that answers your question!

@gerardjensenolmos7862 3 года назад

So in 16:36, there is a mistake. On the right bottom part of the grid, he makes a 2 diagonal movement instead of going forward. That's because he didn't ad the g in sqrt(2) when it's diagonal. Am I right?

@Cfire100 6 лет назад

Yeah... now i know how i have to implement the A* Algorithm. I learned so much from you. Because java script is similar to c#. thank you

@nayanagarwal5312 4 года назад

People who are trying to implement A* for finding path in a maze try to use Euclidean distance in heuristic rather than Manhattan. Manhattan distance gives you a short path as compared to Euclidean distance when you are considering the diagonals. but if we are considering top right bottom left then no doubt Euclidean distance wins.

@expeng5861 5 лет назад

hey, why your application goes through the wall.....but finally I know how to write an A-star solution. thanks a lot.

@skundurks9307 2 года назад

you could do some perlin noise to make the walls, im not sure how to implement that tho

@coderodion 7 лет назад

2:24 It's called _*path symmetry*_: on 2D (even with some obstacles) grids there is bunch of paths of optimal cost that make A star visit an entire "rectangle". Assuming the taxicab distance, that is.

@TheCodingTrain 7 лет назад

Thank you for this excellent clarification!

@coderodion 7 лет назад

Also, more or less famous Jump Point search was developed exactly for dealing with path symmetry in grids.

@tomburris8380 7 лет назад

He fixed the heuristic which is good, the only thing missing now is he adds 1 to the g-cost every step, even if it's moving diagonally. ( Which should be root(2). )

@TheCodingTrain 7 лет назад

This is a good point that I should have covered in more detail.

@l1m3s34 6 лет назад

yeah thx i impelement it using Java (classes interfaces )) and ect ))) thx youu very much (i love you :D :D :D :D !

@Nellak2011 3 года назад

What about grids that are general rectangles, instead of squares? I have been following along with this, and of course when I try to run it on a rectangle it no longer works. It appears that it is trying to see a neighbor that is not on the grid itself. "Cannot read property 'wall' of undefined"

@Inyourwordwetrust 2 года назад

You are my best friend now.

@robertchen9979 7 лет назад

For the algorithm to check if something is in the array or not, you can just keep track of it with another boolean array.

@3zdayz 6 лет назад

Hmm thought I had commented that you should generate perlin-noise to give a gray-scale obstacle path.... I did this; it doesn't work very well... the estimation of how far to go doesn't work very well with gradients... sometimes it's too pessimistic sometimes too optimistic. It's bad to have your predicted length too short or too long; there's a balance in the middle where it does work...

@archtaurus 7 лет назад

it is different from the A*. you shall try the lowest cost one in the openSet first, right?

@5up5up 7 лет назад

the heuristic needs to be admissible for A* to be optimal (i sound like i know my stuff!)

@kelvinzhao4960 6 лет назад

So what's a better way to add the neighbors?

@qihaosaw4683 5 лет назад

this one is creating the block by own setting, can i implement this function in google map ？

@ceorecdeclec9774 6 лет назад

how are you running it so fast? mine does 3 cells per second and takes 10 minutes to do a 50x50 while yours is done in 10 seconds

@kxtbit 2 года назад

what programming language is it written in? how is the algorithm implemented? did you forget to remove wait statements for your code? could be one of those things, idk but 3 cells per second seems crazy inefficient

@ThunderDK74 6 месяцев назад

I'm looking at the time 16:45. Does anyone know a better solution to get a better path where there is only a single red dot... If the diagonal is longer it should not go down and then back up when going right two times (four times) ?? 🙂 Thank you for the tutorials.

@whozz 7 лет назад

How about programming a cellular automata?

@TheCodingTrain 7 лет назад

Yes, if you search cellular automata and shiffman you'll find a bunch of videos, but I think I should do a new coding challenge one!

@siekensou77 3 года назад

tried jumppoint? jps version of a* is really good

@roniburju 7 лет назад

if i gonna take coding by ms mord hown should i do for that?

@gokselkucuksahin 5 лет назад

diagonal neighbors must cost sqrt(2) times more than non diagonal neighbors. isn't it?

@ferdimone521 4 года назад

I have many of motif Dawan culture which i want to apply with p5.js. So i need this tutorial and toturials to take the pixel data from a image

@wesvanduine7773 7 лет назад

Is there a book you would recommend for someone that is a beginner with programing?

@TheCodingTrain 7 лет назад

You can certainly try mine if you like! learningprocessing.com/

@aliceorwell7541 7 лет назад

@5:43 for where there's no solution you say that's the best path it found. I would have thought the best path would finish closest to the endpoint whereas that looks to show the last evaluated path. How would you go about showing the best path in the case of a no solution grid? Track the fittest incomplete path?

@TheCodingTrain 7 лет назад

This is a very good point. Yes I think you are right about tracking the "fittest" incomplete path, the one that is the shortest to end up the closest?

@aliceorwell7541 7 лет назад

I was curious just how easy this would be to implement and it turns out to be really easy. If anyone else is curious I put some code on Github: aliceorwell.github.io/AStar/ The gist of what I did was track which discovered spot has the lowest h and in the event of a no solution render that particular spot's path.

@wazed9468 4 года назад

I did this in minecraft turned out to be pretty hard but I managed it (even tough minecraft already uses a* for their ai's thei're just not using diagonal movement in 1.8)

@souf7409 Год назад

How to prevent that the path travels in between two walls or touches one corner of the wall? It shouldn't be possible! Does anyone know how to code that?

@sebastianmestre2145 7 лет назад

you created a false boolean and then set it to true no matter what and then you tested if it was true. was that a mistake?

@kuskus_th13 7 лет назад

Sebastián Mestre lol

6 лет назад

15:36 If I am not wrong. It stops when it finds the 1st solution. But it can be shorter path, maybe next solution.

@wojtek9395 5 лет назад

You are probably right

@RedCocoon 7 лет назад

You should try to code a pixel circle generator

@svilenivanov9066 7 лет назад

Red Cocoon too easy

@Kalrox1 7 лет назад

what's the pros and cons of c# & c++? I want to start coding but I don't know which to learn

@iofish__ 7 лет назад

Kalahan Eagle You should probably start programming in JavaScript, Python or C#. C# is the best out of these for desktop applications. JavaScript works in browsers and is for web programming. Python does a 90% of everything and it is the prettiest. C++ has manual memory management which means if you have a degree in computer science C or C++ can be faster than other programming languages, but otherwise you will probably see very little benefit in terms of speed compared to writing good code in a high level language

@Kalrox1 7 лет назад

Matthew Biggs thank you , I have chosen to work with unity I am working on the basics of c# an the unity interface. I am getting help from my uncle whom made a game called "lovers in a dangerous spacetime". have a wonderful day, week, month, year, and decade.

@tudordumitrescu8707 7 лет назад

How did you get the Processing to auto fill in the functions and all that? It would really help me since I am new to this language.

@kuskus_th13 7 лет назад

Tudor Dumitrescu That's p5.js, Processing doesn't do that pretty sure

@tudordumitrescu8707 7 лет назад

I have p5.js editing app but it still doesn't fill those words in and color them the same way. Maybe it is just a macOS thing

@TheCodingTrain 7 лет назад

I'm using the Atom editor.

@tudordumitrescu8707 7 лет назад

Oh, thanks for the info!

@MultiMunding 7 лет назад

Hey i wanted to create a Sketch that is counting the number of clicks since its Start BUT without having the Sketch window selected. how is it possible?

@Texplanations 7 лет назад

I dont think that's possible... but you can use other software to get that info if you just wanna use it for something that is not done with the code

@MultiMunding 7 лет назад

TechNerd01 thank you for your answer but i wanted to use it in a Screenshot making program like gyazo

@Texplanations 7 лет назад

Could you explain in details? I may be able to help... I dunno

@MultiMunding 7 лет назад

TechNerd01 i already looked it Up and it Looks like there is a Java library for global hotkeys but i have no clue on how to Install it

@Texplanations 7 лет назад

Its a java library so you're gonna have to use processing and not p5js

@otesunki 6 лет назад

Combine this with a maze generator!

@XoIoRouge 5 лет назад

Maybe if you actually implemented the Pseudo Code correctly, you would actually have optimal pathing. EDIT: You realized it at the VERY end, haha!

@generaldave7455 7 лет назад

It's not much different. I just coloured a bit differently and "refactored" to clean up sketch.js. github.com/generaldave/A_Star_Simulation Also, I'm glad you are getting into machine learning, Daniel. I have recently gotten excited about machine learning and needed a good source of information. As always, your videos are educational and entertaining.

@TheCodingTrain 7 лет назад

Thank you!

@deva8496 2 года назад

i will never accept diagonal path. Coincidentally I wrote a* path finding solution for my game i developer in 2015

@aayushsaini9363 7 лет назад

Does g map also uses A* algo

@coderodion 6 лет назад

aayush saini Not necessarily since there are faster algorithms than A*.

@blackburnmichelson6189 3 года назад

can i do this with c++?

@WalterZarl 7 лет назад

Looked like Dwarf Fortress from the thumbnail.

@shashank007sharma 4 года назад

Can someone share github link please

@mohammadkazemzadeh2299 4 года назад

where is the source ? can anyone send it to my?!

@ledues3336 7 лет назад

What? When did you change your channel's name?

@kuskus_th13 7 лет назад

Le due S He changed it a few days ago due to trademark issues with something called "Reading Rainbow"

@bitworld2848 6 лет назад

i want that whistle button thing i need that whistle button thing i need it now

@TheSkepticSkwerl Год назад

Diagonal should cost 1.4 otherwise super awesome.

@hudson5365 3 года назад

Ah, it's wonderful when it works, isn't it?

@KaletheQuick 7 лет назад

Why is it a train now :(

@kuskus_th13 7 лет назад

KaletheQuick Trademark issues

@alekmoth 7 лет назад

"return, and that is going exit out of this function instantly. and then I have noLoop on the next line." .. meeep.. are you even listening to yourself?

@MarsCorporations 5 лет назад

you should not be able to pass "between" two obstacles just because you can walk diagonally.

@aichabenlahrech635 5 лет назад

@fcbtomtom7132 7 лет назад

First

@sebastiantamayoguzman552 3 года назад

nosew? guapo

@dibayuin7859 7 лет назад

PLEASE MASTER CODING TRAIN REPLY ME :(( I have processing and how to add p5 js ? where's the link video of that turtorial ?? I need reply somebody help :( I have to download p5 js and processing but I don' t know to use it pardon my bad english