A* Pathfinding Algorithm (Coding Challenge 51 - Part 1)
VloĆŸit
- Äas pĆidĂĄn 6. 07. 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* Algorithm - Part 2: âą Coding Challenge 51.2:...
đș 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:01:26 A* Pathfinder
0:09:39 Coding a Grid
0:13:09 A* Pathfinder Algorithm
0:22:07 Choosing Best Available Path
0:27:05 Finding New Nodes
0:38:30 Adding Heuristic
0:41:50 Tracing Back
0:46:49 Using Better Heuristics
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: czcams.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
I ended up here while trying to fix my own version of A* code for a personal project. Although in a completely different language, I figured following the logic from start to finish would help. I am happy to say that after watching this twice, clocking in at a near 2 hours of of the most energetic coding I've ever observed, I realized one of my i's were a j.
This is an amazing story!!
I feel your pain before notepad++ we had notepad... it was as fun as you described!
I got intense nausea reading that last part.
â@rya7886 I you just took me way back lol thanks for that.
This is the problem with monospace font glyphs and bad vision. đ
I like it how you show the result at the beginning. Otherwise, I always have to go to the end and see if that is something I want to learn.
Yes, I hope to keep doing this with future challenges!
Sometimes it is obvious from description what are you going to do. So, please don't show final result until it really hard to understand!
I personally hate it when he shows the end result at the beginning. At least give a spoiler warning or a timestamp to skip it. For me, seeing the exact end result removes nearly all motivation to watch through an hour long two-part tutorial. I would rather watch the project organically come together as he builds it, without knowing exactly what to expect.
I agree to an extent I like the excitement and motivation of not knowing
You are impatient.
I love all your Coding Challenge videos. I'd love to see you make a multi-part series of you putting a lot of code and detail into a project.
Man, thank to you again!! I'm so interesting in algorithms and ML, but didn't know where to start. And your lectures are such a good place to start and go far! It's really great, new level, so different to compare with usual front-end JS, it's real science, it's interesting, it's improve you. Thank you!
I know this is a pretty old video, but for anyone watching. The reason it wasnt giving his expected results with no walls and no diagonals is because you need to add tiebreaking in. You can do this simply by changing
for (int i = 0; i < openSet.Count; i++)
{
if (openSet[i].F < openSet[winner].F)
winner = i;
}
Too
for (int i = 0; i < openSet.Count; i++)
{
if (openSet[i].F < openSet[winner].F)
winner = i;
else if (openSet[i].F == openSet[winner].F)//tie breaking
if (openSet[i].H < openSet[winner].H)
winner = i;
}
Thank you for this feedback!
People like you do more for students than many universities around the world. Cheers to learning đ
Best explanation of A* on the internet! By the way, you could have added neighbours to a spot just before looping through its neighbours. This way if you didn't need to check the neighbours of some spots, you wouldn't need to add neighbours to it. They could just be added to closed set without neighbours. This would save a lot of memory when you're dealing with many spots
If I had more professors who teach like you I was a better engineer now !
Yeah, the problem is, many of the university teachers are bunch of morons.
if teachers would teach like this you'd need longer days. Of course it's easy to understand when you already know how it's done.
@@MrTrollo2 ikr
I honestly don't know what I would do without you.
This was super helpful for actually learning A*. I have tried to do it multiple times in C# but never got it working, but ~3 days ago i figured it out thanks to this video. You rock!
You are one of the best teacher online and with a great personality .You have help me a lot with processing. We need more people like you in the world ,thank you.
Thanks for the nice comment!
This guy is a genius! It looks so straight forward every single step. Amazing đ€©
I have been binge watching your videos over the holiday vacation...and I just don't know how I can express my gratitude for making these amazing videos. Your enthusiasm, presentation style...makes what would be a tough process (learning to program) a VERY enjoyable learning process. A massive thank you for sharing your incredible knowledge. You just got a new member.
Thank you Rico! Did you fill out the google form and link your account to Discord?
@@TheCodingTrain...notbyet! Will do!! Did buy some Coding Train Merch though!
What I love the most about the videos you make...is that you don't edit out your mistakes. 'this dot' et all. They are mistakes all of us noobs will make and you show us that even pros make mistakes...and the debugging method is education in itself
@@sennabullet Thanks, I really appreciate this feedback!
Thanks to your inspiration I finally managed to implement an object oriented version of Astar for Codewars. Keep up the good work!
It is fantastic how this guy has so muck inspiration and energy to program,and a lot of that anergy actually hi is giving to us , BIG THANKS YO HIM :D
Tbh his overly childish display of energy is kind of annoying
@@Nickoking12 you must be fun at parties
Also like his energy and paired with it his intelligence you can hear and see
@@Nickoking12 there are always people that does not want someone be themselves, aren't there...
@@kavinbharathi yep
25:20 Array's splice method removes one or more elements from an array, closes the gap, and reduces the length. It makes an array of the removed elements, if any, and returns them. You can also insert zero or more new elements in that position by passing them as the subsequent parameters after removal range base and length.
Absolutely amazing video! Your energy for coding is absolutely amazing and got me coding in p5
found out about this channel afew days ago. your videos and walkthroughs are amazing.
Translating this into C# for unity is... interesting. Tough to find a good tutorial on pathfinding, luckily this seems to be working for me so far. Love the videos keep up the great work : )
I had to translate my js code for A* to C for my robotics team a couple of years ago. Great way to learn about pointers and dynamic memory.
This channel always when i donât know what to do when i want to code something gives me motivation and ideas, pretty cool.
Best tutorial seen so far on A* algorithm
I'm really love the way you showing the coding... fun and relax.... with the great result.
So after a mess and 2 hours you finished it? You are BRILLIANT my friend!
You saved my semester! Brilliant work. You sir, are awesome!
Really Really Really!!!! Fantastic Video. I really love his energy while he was teaching!! Wish I could have this man as my professor. Amazing!!
I absolutely love these coding challenges! Keep being awesome.
So cool to watch you programming, I've been learning C# for the past few months and it's cool to watch you working in Java but still understanding what you're doing. I'm going to have a go at doing this in C#.
Dan, you are one of the only CS instructors I've enjoyed listening to. Even when I'm not in a mood to program, watching your videos always makes me want to start something of my own. I've always struggled with finding motivation, and you have helped me find it again. Thanks a bunch! I'm glad I found your channel.
Thank you for the nice feedback!
BInary heap implementation of Dijkstra Algorithm runs in O(E)+|V|log|V| time which isn't particularly slow. Together with Hoare's Quicksort Algorithm, Dijkstra Algorithm must rank in the top 2 algorithm of the last century!
Excellent job on your videos, you are a great teacher!
Awesome video!
Please keep making these vids, and thank you for teaching us
Thanks for showing result at the beginning of the video. Awesome
Very well explained, thanks! Love your enthusiasm for teaching!
dude, I f*ing LOVE your website!
yesss A*!! awesome
Great video as always :)
I'm in web dev and watching this. Idk why but this is refreshing some good memories lol
I did this a few years ago in one of my intro classes to programming. Was hell, still have the file though :)
Thank you a lot. Why are you always the best person to explain things
Holy crap what a good A* explanation at the beginning
1:42 "needle in a haystack"
*Non-premium spotify user's ptsd intensifies*
Not funny
Didn't laugh
For any of you wondering, this is the kind of algorithm top down view rpgs and mobas use like league, runescape, fallout etc
iam happy to see this work !
OMG đ±đ±đ amazing challenge
Dude you're just amazing. Programming is so great!!!
thanks you are awsome man !!.we need more complicated videos
Hahahahaha love your videos!!!
Thanks !!! You helped me a lot, and that works for Hex grids! (Of course just have to change neighbors conditions)
I love the energy he has
Love you bro
Looks just like a robot finding an optimal path through a building. ;)
I like how you explain what's going on, and what you're going to do next, and why.
I built an A* PF viz in Processing the other day, and I was *this* close to tearing my hair out until I realized how I could simplify away almost half of the code I had written to fix edge cases by just... making a smarter Neighbors() function.
I watched this live stream. Must have been the hardest one to edit yet. Probably why part 1 wasn't released until 2 days after haha. Love your channel man, I swear I've put in at least 60 hours watching many of your vids. Btw, I started Frogger today in P5, I think you should consider it for a coding challenge. It's a long and tedious one though!
Frogger is a great idea.
I don't even code but your videos are really fun to watch it makes me want to learn it
I love your videos because it builds logic đ
you should make 2048
Thanks to this channel I moved all my draw engine of my project to p5 :D
Web dev trying to build a game as a hobby project, such a good tutorial - thank you!
So glad to hear!
Amazing
I know this is an old video, but a more effective way of removing a specific element from an array could be written as:
var myArr = ["foo", "bar", "bas"]
var element = myArr[2] //"bas"
function removeFromArray(arr, el) {
let i = arr.indexOf(el)
if (i > -1) {
arr.splice(i, 1)
}
return arr
}
myArr = removeFromArray(element)
use filter instead
// remove 2 from array
[1,2,3].filter(i => i !== 2)
I would personally use a linked list if random access is not needed and there is a lot of insertion / deletion happening
In this case your function is definitely better and faster. But it's not equivalent to what he wrote in general. If an array has duplicate elements his function will remove all of them while yours only the first occurrence (assuming that indexOf returns the first occurrence). I just wanted to point that out.
@@xerxius5446 I agree. I was referring to the code in the parent comment, not yours :)
The most effective way is just to use the winner variable, which already had the index of the item (and he instantly forgot that). Just openSet.splice(winner,1)
i don't understand any of that but i find it fascinating!
I loved it, espescially the way that without diagonal or obstacle, each way take same time to travel, your grid is 25 by 25, if it go down, right alternativly it will take 25 down and 25 right move to the other side, just like to go on the edge of the grid is 25 down + 25 right :D !
You helped me take the code train thank you prof. i would have kill to got prof like you in college.
Problem is that it's not actually A*. It's breadth first due to bugs. A* Would only need to check alternately going right down, right down etc or down right down right etc.
It found an optimal path but it checked all 625 cells doing it. A* would also find an optimal path, but would need to check fewer cells.
To remove a value from an array in javascript, the two main solutions I know are .filter and .splice(.indexOf)
you are wonderfull, very entertaining see your coding process.
31:39 "some other life that you have"
buddy i barely have one life as it is
love your energy
Thanks this helped me solve a real world problem!
great video
at 25:48 you create a function to find the index of the `current` element, but you already know that value, it is the value stored in `winner`, so I think you could just do `openSet.splice(winner, 1)`, or without side effects: `openSet = openSet.slice(0, winner).concat(openSet.slice(winner + 1, openSet.length))`
FANCY stuff. i really like your videos. how about trying to make a tut on creating 2d map from a camera or two could be fun
4:36 "The algorithm is typically written with a formula. The formula's actually quite simple, although any time you write a formula, it starts to be like, 'Oh my god, is this really what we're doing today?' "
haha ily dan
Love it
I found your channel about a month before your channel name changed from coding rainbow to Daniel Shiffman to coding train and I got really confused as to why the super awesome intro you had was all blurred out. Now I understand though. Anyway you are doing a great job and I love seeing your processing videos.
I'm wondering if I should have left the channel name to "Daniel Shiffman" even if the name name is "Coding Train" . .
Keep it as Coding Train
Brilliant
This algorithm project is very interesting & amazing
When I will go to USA, I will meet you no matter what. I love you, man â€ïž
You deserve MORE MORE MORE Subscribers
Well done on the editing. Watched the livestream and felt sorry for the editor. But nice result.
Heh, I agree!
Thaaaaaanks a lot! You are a genius! Well explained and easy to follow. Thanks to you I finally understood what A* is actually doing and I got this big piece of homework done. Thanksthankthanks and did I thank you already?
Your beard is majestic
This is a good video about A* pathfinding, but there are a lot of videos for simple 2d grids. What I miss are tutorials how I can implement A* in a 3d voxel world like Minecraft or Minetest, including jumping, fall height and so on. This is far more complex than the basic 2d grid algorithm
the joy of codingis to see the end result.....imaging dancing to that path as it finds its way to the end.
I love this channel
falloist who doesn't
me too!
What a lecture.
Easy to understand even though i live in non-english country.
Would love to see whole lectures
đđ
Wow. Just started studying computer science in college in the past year, and with most of your challenges I am able to follow along pretty well and feel comfortable with my understanding of your processes. This on the other hand...first time watching is kind of a mind f***.
wonderful challenge coding game.
Chapter 10 of the "Nature of Code" Book would be nice :D
Thanks, man !! You saved my day. I was struggling with this algorithm and your video helped me a lot. One thing I want to ask you. What could be other good heuristics methods we can use here (except euclidean and manhattan)?
Beautifull video very nice to view your channel is Very wonderfull go again
nice â€ïž
Amazing đ video âŁïžđ
Name of this channel was different ... I like the new name though !!!
He had trademark issues with Reading Rainbow, so he changed it.
KusKusPL Wasn't it coding rainbow?
Yes, but it was too similar.
Actually ... Even before that ... The channel name was his own name ... "Daniel Shiffman".
Ani H.â The channel had always been named Daniel Shiffman, but when he referred to his channel, he called it Coding Rainbow
Nice
I wish you were my teacher, and thank you for teaching me how to code
I recommend using arrRows.forEach(function(row, i){ row.forEach(function(col, j){ console.log(row, i, col, j) } }); e.g. for the grid.
interesting sir.â€ïž
first tried to do this without a tutorial. I started at (1, 1)(on a grid) and tried to get to (1, 2). let's just say it went to (-1, 0) then had an infinite loop
I already wrote A* in vb.net to learn how it works. (Tip: Don't write it recursive. The Stack will overflow.) But I started watching this video so see how some one would explain it. But now I am more interested in the p5* framework xD. (btw. very entertaining video #Like)
THANK YOU MISTER SHIFFMAN
I had studied c++ for 2 months, i'm 15 years old Vietnamese student, i had try to slove this in Back Tracking