Coding Challenge 51.2: A* Pathfinding Algorithm - Part 2
ฝัง
- เผยแพร่เมื่อ 27 พ.ค. 2024
- 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: th-cam.com/users/thecodingtrainjoin
🛒 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
This guy is like the Bob Ross of coding, only more enthusiastic.
*I FREAKING DID IT! I COMBINED THIS WITH YOUR MAZE GENERATION PROJECT!*
can you share the source code
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.
yes, thank for you clarifying this.
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...
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.
Nice bro!
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
Explained exceptionally well, as always.
I'm looking forward to the neural network videos.
Nice to hear thank you!
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.
You're so inspiring. Keep on these videos. Love them all.
really cool watching you code. that enthusiasm is great. thank you.
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).
yes, a good point indeed!
It can work to just approximate it to 1.4
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
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
RING THE BUG BELL, DAN
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.
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.
I feel so great finding this hidden part 2 :D
I always to release the full tutorial but "publish" one day at a time (seems to work best for youtube stats.)
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.
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
I wish I could re"like" the video everytime I learn from it
Hey i followed exactly your tutorial and successfully made this algorithm on my iPhone ;)
Darn good video. I wish your videos had been around when I was studying CompSci! Thank you!!
Thanks for the nice feedback!
your code is beautiful
thank you for the great content :)
thx a lot! I can't believe I found this. It's so great!
thanks for big work you do here!
Thank you so much, i finally understand!
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.
Great tip!
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.
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.
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)
Very cool and very inspiring
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...
Excelent video you are awesome dude!
Very helpful~ Thanks a lot
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.
Your videos are nice, since you make complicated things look simple. Also, I want to ask, do you have a degree in CS?
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.
Did you fix the first problem? That it goes in between two walls or ju
@@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
@@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!
@@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!
You are a magician.
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.
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))
thanks for the suggestion!
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?
Python is possibly one of the slowest languages out there, or at least, so I heard
Le due S It wouldn't surprise me, I'll try it in something like Java and see if I get a better result
and here I am programming a counter capable of displaying enormous numbers while Dan programs a fully functional algorithm :D
KusKusPL we all gotta start somewhere. keep at it man.
Loved it
Thank you dude
man you are awesome ❤️
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.
Beautiful
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?
+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!
yes indeed this is a good suggestion.
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
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 ?
Awesome
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.
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.
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.
Thank you for this excellent clarification!
Also, more or less famous Jump Point search was developed exactly for dealing with path symmetry in grids.
i love your dance in generic.
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"
this one is creating the block by own setting, can i implement this function in google map ？
it is different from the A*. you shall try the lowest cost one in the openSet first, right?
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). )
This is a good point that I should have covered in more detail.
For the algorithm to check if something is in the array or not, you can just keep track of it with another boolean array.
if i gonna take coding by ms mord hown should i do for that?
you could do some perlin noise to make the walls, im not sure how to implement that tho
You are my best friend now.
How about programming a cellular automata?
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!
Is there a book you would recommend for someone that is a beginner with programing?
You can certainly try mine if you like! learningprocessing.com/
hey, why your application goes through the wall.....but finally I know how to write an A-star solution. thanks a lot.
what's the pros and cons of c# & c++? I want to start coding but I don't know which to learn
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
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.
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
So what's a better way to add the neighbors?
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.
Tudor Dumitrescu That's p5.js, Processing doesn't do that pretty sure
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
I'm using the Atom editor.
Oh, thanks for the info!
the heuristic needs to be admissible for A* to be optimal (i sound like i know my stuff!)
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...
yeah thx i impelement it using Java (classes interfaces )) and ect ))) thx youu very much (i love you :D :D :D :D !
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
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
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
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?
@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?
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?
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.
tried jumppoint? jps version of a* is really good
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?
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
TechNerd01 thank you for your answer but i wanted to use it in a Screenshot making program like gyazo
Could you explain in details? I may be able to help... I dunno
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
Its a java library so you're gonna have to use processing and not p5js
can i do this with c++?
diagonal neighbors must cost sqrt(2) times more than non diagonal neighbors. isn't it?
Maybe if you actually implemented the Pseudo Code correctly, you would actually have optimal pathing.
EDIT: You realized it at the VERY end, haha!
Does g map also uses A* algo
aayush saini Not necessarily since there are faster algorithms than A*.
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?
Sebastián Mestre lol
15:36 If I am not wrong. It stops when it finds the 1st solution. But it can be shorter path, maybe next solution.
You are probably right
Can someone share github link please
You should try to code a pixel circle generator
Red Cocoon too easy
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)
Combine this with a maze generator!
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.
Thank you!
i will never accept diagonal path. Coincidentally I wrote a* path finding solution for my game i developer in 2015
Looked like Dwarf Fortress from the thumbnail.
where is the source ? can anyone send it to my?!
Diagonal should cost 1.4 otherwise super awesome.
What? When did you change your channel's name?
Le due S He changed it a few days ago due to trademark issues with something called "Reading Rainbow"
i want that whistle button thing
i need that whistle button thing
i need it now
Ah, it's wonderful when it works, isn't it?
"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?
Why is it a train now :(
KaletheQuick Trademark issues
you should not be able to pass "between" two obstacles just because you can walk diagonally.
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 ?
nosew? guapo
First
Can someone combine the maze generator with deez
for maze generator use first depth search algoritm
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
I hate this style of code, I mean using {
}
No, you didn't. Not working without diagonals
is he a computer science ??
yes
KusKusPL oh okay thx
Yeah... he is a computer science -_-
He is the CS himself.
if i gonna take coding by ms mord hown should i do for that?
i want that whistle button thing
i need that whistle button thing
i need it now