A* Pathfinding Algorithm (Coding Challenge 51 - Part 1)
ฝัง
- เผยแพร่เมื่อ 13 พ.ค. 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: 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
![🔴 [TRỰC TIẾP] Tứ Xuyên (Trung Quốc) VS BCTT Trường Tươi Bình Phước | Cúp VTV9-Bình Điền | JET STUDIO](http://i.ytimg.com/vi/5nF-PCh_Ojw/mqdefault.jpg)
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 🎉
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!
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
Thanks to your inspiration I finally managed to implement an object oriented version of Astar for Codewars. Keep up the good work!
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.
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!
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.
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!
Best tutorial seen so far on A* algorithm
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.
Really Really Really!!!! Fantastic Video. I really love his energy while he was teaching!! Wish I could have this man as my professor. Amazing!!
This guy is a genius! It looks so straight forward every single step. Amazing 🤩
This channel always when i don’t know what to do when i want to code something gives me motivation and ideas, pretty cool.
So after a mess and 2 hours you finished it? You are BRILLIANT my friend!
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
I'm really love the way you showing the coding... fun and relax.... with the great result.
You saved my semester! Brilliant work. You sir, are awesome!
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
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#.
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!
I cannot stop watching your videos. The way you explain your process of coding is excellent. Awesome videos, I always look forward the the next one!!
So nice to hear, thank you!
I did this a few years ago in one of my intro classes to programming. Was hell, still have the file though :)
Please keep making these vids, and thank you for teaching us
Very well explained, thanks! Love your enthusiasm for teaching!
I'm in web dev and watching this. Idk why but this is refreshing some good memories lol
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!
Thanks for showing result at the beginning of the video. Awesome
I absolutely love these coding challenges! Keep being awesome.
Web dev trying to build a game as a hobby project, such a good tutorial - thank you!
So glad to hear!
Thank you a lot. Why are you always the best person to explain things
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 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.
For any of you wondering, this is the kind of algorithm top down view rpgs and mobas use like league, runescape, fallout etc
1:42 "needle in a haystack"
*Non-premium spotify user's ptsd intensifies*
Not funny
Didn't laugh
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
To remove a value from an array in javascript, the two main solutions I know are .filter and .splice(.indexOf)
yesss A*!! awesome
thanks you are awsome man !!.we need more complicated videos
Holy crap what a good A* explanation at the beginning
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))`
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)
Looks just like a robot finding an optimal path through a building. ;)
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
I love your videos because it builds logic 😊
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 don't even code but your videos are really fun to watch it makes me want to learn 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
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?
31:39 "some other life that you have"
buddy i barely have one life as it is
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.
you should make 2048
dude, I f*ing LOVE your website!
When I will go to USA, I will meet you no matter what. I love you, man ❤️
Dude you're just amazing. Programming is so great!!!
Thanks this helped me solve a real world problem!
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.
Thanks to this channel I moved all my draw engine of my project to p5 :D
Hello, thank you for your video. I have implemented the A Star on Android Studio.
Can I share it with you ?
Have you ever though of making a Robot Localization with particles filter on simulation ? I have implemented it this weekend.
This algorithm project is very interesting & amazing
iam happy to see this work !
i don't understand any of that but i find it fascinating!
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.... :)
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 ^^
Exactly the comment i was looking for!
you are wonderfull, very entertaining see your coding process.
I like how you explain what's going on, and what you're going to do next, and why.
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
Well done on the editing. Watched the livestream and felt sorry for the editor. But nice result.
Heh, I agree!
Great video as always :)
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
I recommend using arrRows.forEach(function(row, i){ row.forEach(function(col, j){ console.log(row, i, col, j) } }); e.g. for the grid.
Awesome video!
I loved the part when pathfinder says "get ready, its Zipline time" and start pathfinding all over the place
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
Really enjoy all of your videos! cheers for the great content. I have a question,for a school project I want to build a map for a navigation where your location is fixed in the centre and the map moves along of your path as you move. What would be a good way to go about this (I was thinking canvas or p5js?) I get my location as well as the location of destination in coordinates from an api. Thanks!
you could look into mapbox.js for mapping stuff. but if you do it in canvas translate() will allow you to always "center" the view.
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)
26:35 if splice removes an element in the given index of the array, couldn't you use it as instead of creating the function removeFromArray? Loving the content ❤
yes.. Let's just say his brain's think quicker than a machine already so he doesn't need that extra optimisation :')
Your beard is majestic
So kool! Btw, there's bug in the video of the first loop openSet.length, right after check openSet.length > 0.
You should close bracket for the loop after the winner is found. The code in source control is fixed but the video is not :)
You should do coding challenges on different languages, such as python or CPP
Oh right. Python is much harder than JS XD
@@scholli99 that was not the point even if python is easier writing the code is as challenging as js
Well p5 is a js library, and p3 is a java library, so it wouldn't make much sense to switch up those languages.
@@scholli99 That's not the point...
What he meant was, to do different languages for educational purposes it's not just about the difficulty, after all this channel is for sharing information about programming.
Does anyone know how to adjust A* in order to find all shortest paths ranked by length in an a-priori manner? Say the current shortest path becomes unpassable due to a storm I need to quickly find the next best alternative path, etc. without having to repeat the entire A* calculation.
OMG 😱😱😍 amazing challenge
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
can u explain the this. function thing, because i dont understand how you were capable of keeping track of the path specifically after making the neighbors variable and checking the tempG ...
wonderful challenge coding game.
I love this channel
falloist who doesn't
me too!
Would it be better use a priority queue for the openSet since we are always looking at the node with the smallest f?
Amazing explaination....have you made any video on best- first search???
love your energy
An other possibility for the function to remove an item from an array, using filter :D
function removeFromArray(arr, toRemove) {
return arr.filter(e => e != toRemove);
}
What a lecture.
Easy to understand even though i live in non-english country.
Would love to see whole lectures
😁😁
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
Hello Daniel! Let me start saying that I discovered this channel like a month ago and I totally love it! You have made me start coding again after leaving it for a long time :)
I have kind of a silly question for you, I like following your examples and challenges as I'm watching the video, and I try to have the code as organized as you do, but I end up being much slower typing everything and specially spacing everything so it becomes much more readable. How do you make Atom automatically space things out (I'm not refering to indentation inside functions since that came with Atom right out of the box, but rather making a line such as (var i=0, i
Is there any way that can be done in Processing? If so, could you make a tutorial?