A* Pathfinding Algorithm (Coding Challenge 51 - Part 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* 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: kzread.infojoin
🛒 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
Пікірлер: 614
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.
@TheCodingTrain
2 жыл бұрын
This is an amazing story!!
@rya7886
Жыл бұрын
I feel your pain before notepad++ we had notepad... it was as fun as you described!
@greatcesari
Жыл бұрын
I got intense nausea reading that last part.
@arcalypse1101
Жыл бұрын
@rya7886 I you just took me way back lol thanks for that.
@nightwintertooth9502
5 ай бұрын
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.
@TheCodingTrain
7 жыл бұрын
Yes, I hope to keep doing this with future challenges!
@ilyaexo2005
7 жыл бұрын
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!
@Twurl
5 жыл бұрын
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.
@tx6723
4 жыл бұрын
I agree to an extent I like the excitement and motivation of not knowing
@luckylove72
4 жыл бұрын
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 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.
@TheCodingTrain
2 жыл бұрын
Thank you Rico! Did you fill out the google form and link your account to Discord?
@sennabullet
2 жыл бұрын
@@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
@codingtraintwitcharchive3277
2 жыл бұрын
@@sennabullet Thanks, I really appreciate this feedback!
People like you do more for students than many universities around the world. Cheers to learning 🎉
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!
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 { if (openSet[i].F winner = i; } Too for (int i = 0; i { if (openSet[i].F winner = i; else if (openSet[i].F == openSet[winner].F)//tie breaking if (openSet[i].H winner = i; }
@TheCodingTrain
5 жыл бұрын
Thank you for this feedback!
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
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.
@TheCodingTrain
7 жыл бұрын
Thanks for the nice comment!
Thanks to your inspiration I finally managed to implement an object oriented version of Astar for Codewars. Keep up the good work!
Absolutely amazing video! Your energy for coding is absolutely amazing and got me coding in p5
I honestly don't know what I would do without you.
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.
This guy is a genius! It looks so straight forward every single step. 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 : )
@smolboye1878
2 жыл бұрын
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.
So after a mess and 2 hours you finished it? You are BRILLIANT my friend!
This channel always when i don’t know what to do when i want to code something gives me motivation and ideas, pretty cool.
found out about this channel afew days ago. your videos and walkthroughs are amazing.
If I had more professors who teach like you I was a better engineer now !
@neotodsoltani5902
3 жыл бұрын
Yeah, the problem is, many of the university teachers are bunch of morons.
@MrTrollo2
3 жыл бұрын
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.
@justarandomlol
2 жыл бұрын
@@MrTrollo2 ikr
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.
Really Really Really!!!! Fantastic Video. I really love his energy while he was teaching!! Wish I could have this man as my professor. Amazing!!
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#.
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
@Nickoking12
5 жыл бұрын
Tbh his overly childish display of energy is kind of annoying
@FeLiNe418
4 жыл бұрын
@@Nickoking12 you must be fun at parties
@BloodyClash
4 жыл бұрын
Also like his energy and paired with it his intelligence you can hear and see
@kavinbharathi
3 жыл бұрын
@@Nickoking12 there are always people that does not want someone be themselves, aren't there...
@skmgeek
2 жыл бұрын
@@kavinbharathi yep
You saved my semester! Brilliant work. You sir, are awesome!
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!
Very well explained, thanks! Love your enthusiasm for teaching!
For any of you wondering, this is the kind of algorithm top down view rpgs and mobas use like league, runescape, fallout etc
Please keep making these vids, and thank you for teaching us
Thanks for showing result at the beginning of the video. Awesome
I absolutely love these coding challenges! Keep being awesome.
Thank you a lot. Why are you always the best person to explain things
I'm in web dev and watching this. Idk why but this is refreshing some good memories lol
1:42 "needle in a haystack" *Non-premium spotify user's ptsd intensifies*
@linuxterm7622
4 жыл бұрын
Not funny Didn't laugh
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!
@TheCodingTrain
7 жыл бұрын
Frogger is a great idea.
Holy crap what a good A* explanation at the beginning
dude, I f*ing LOVE your website!
Thanks !!! You helped me a lot, and that works for Hex grids! (Of course just have to change neighbors conditions)
I did this a few years ago in one of my intro classes to programming. Was hell, still have the file though :)
Looks just like a robot finding an optimal path through a building. ;)
Web dev trying to build a game as a hobby project, such a good tutorial - thank you!
@TheCodingTrain
Жыл бұрын
So glad to hear!
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.
@phizc
4 жыл бұрын
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.
I love the energy he has Love you bro
I don't even code but your videos are really fun to watch it makes me want to learn it
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.
@TheCodingTrain
7 жыл бұрын
Thank you for the nice feedback!
yesss A*!! awesome
31:39 "some other life that you have" buddy i barely have one life as it is
iam happy to see this work !
Awesome 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))`
you should make 2048
To remove a value from an array in javascript, the two main solutions I know are .filter and .splice(.indexOf)
I love your videos because it builds logic 😊
OMG 😱😱😍 amazing challenge
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.
Dude you're just amazing. Programming is so great!!!
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.
@TheCodingTrain
7 жыл бұрын
I'm wondering if I should have left the channel name to "Daniel Shiffman" even if the name name is "Coding Train" . .
@kenan2386
3 жыл бұрын
Keep it as Coding Train
thanks you are awsome man !!.we need more complicated videos
Great video as always :)
i don't understand any of that but i find it fascinating!
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?
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
This algorithm project is very interesting & amazing
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
Thanks this helped me solve a real world problem!
you are wonderfull, very entertaining see your coding process.
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)?
I recommend using arrRows.forEach(function(row, i){ row.forEach(function(col, j){ console.log(row, i, col, j) } }); e.g. for the grid.
I like how you explain what's going on, and what you're going to do next, and why.
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)
@xerxius5446
4 жыл бұрын
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
@mannyc6649
4 жыл бұрын
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.
@mannyc6649
4 жыл бұрын
@@xerxius5446 I agree. I was referring to the code in the parent comment, not yours :)
@chrismanning5232
4 жыл бұрын
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)
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
Your beard is majestic
love your energy
When I will go to USA, I will meet you no matter what. I love you, man ❤️
Many years later… but I just wanted to point out that dijkstra’s doesn’t actually search all possible paths like some backtracking DFS. It greedily chooses the shortest routes to the next node from the node it’s currently on. That’s why it’s faster with ElgV time (and possibly faster depending on the data structure you use to track the current shortest edge you found) It also can’t work on negative edges or else the heap your using will break the invariant assumption you’re making (the fastest route to me is myself, 0). That means negative edges will break that invariant, but the minheap doesn’t know any better :)
@avatar098
Жыл бұрын
….unless you’re using uniform weighted edges (or non weighted). In which case Dijkstra’s will essentially turn into BFS behavior. BFS is guaranteed to find shortest paths but will take longer O(VE)
Thanks to this channel I moved all my draw engine of my project to p5 :D
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)
the joy of codingis to see the end result.....imaging dancing to that path as it finds its way to the end.
I had studied c++ for 2 months, i'm 15 years old Vietnamese student, i had try to slove this in Back Tracking
Name of this channel was different ... I like the new name though !!!
@kuskus_th13
7 жыл бұрын
He had trademark issues with Reading Rainbow, so he changed it.
@manuelbonet
7 жыл бұрын
KusKusPL Wasn't it coding rainbow?
@AsifMehedi
7 жыл бұрын
Yes, but it was too similar.
@igniculus_
7 жыл бұрын
Actually ... Even before that ... The channel name was his own name ... "Daniel Shiffman".
@manuelbonet
7 жыл бұрын
Ani H. The channel had always been named Daniel Shiffman, but when he referred to his channel, he called it Coding Rainbow
You deserve MORE MORE MORE Subscribers
great video
dud i watched it to see your implementation of binary heap, what is used to store values and pull minimum value, but you made it pretty trivial. Anyways, thanks :D
Amazing
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
Well done on the editing. Watched the livestream and felt sorry for the editor. But nice result.
@TheCodingTrain
7 жыл бұрын
Heh, I agree!
I wish you were my teacher, and thank you for teaching me how to code
wonderful challenge coding game.
Hahahahaha love your videos!!!
I want to do this on a curved surface that changes over time where there is no translation to a flat surface. I'm thinking I may be able to use an estimated curvature and use collision boxes around it to the end point to find probable relevant points on the ground. And then weigh them with their height relative to the estimated curvature. Maybe I can reuse those boxes until it gets there/changes path in case it all changes while traveling. That all sounds complex though.
Beautifull video very nice to view your channel is Very wonderfull go again
id sell my soul, donate kidney, donate blood, donate a leg to be as smart as this guy is in software.
Chapter 10 of the "Nature of Code" Book would be nice :D
Interesting how the animation at the beginning looks a bit like the "stepped leader" of a lightning strike. I wonder if this has any bearing on that phenomenon, which I believe isn't that well understood - could be an opportunity for some cross-disciplinary research.... :)
@sylv171
3 жыл бұрын
Actually, a lightning IS looking for the shorter way ! So i thinks that it's pretty much the same thing :) Sorry for my english i'm french ^^
@AshishBihani
2 жыл бұрын
Exactly the comment i was looking for!
Love it
I love this channel
@kuskus_th13
7 жыл бұрын
falloist who doesn't
@badmin236
7 жыл бұрын
me too!
I put this on and fell asleep immediately and had spme werid ass dream about path finding algorithms and dkrndmdk algorithm xDD
i love heuristics. it's one of the only 80's bands i like
Amazing 😍 video ❣️👌