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.
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.
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.
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...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
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
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!
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.
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 : )
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 < 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; }
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!
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
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.
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#.
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 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!
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.
3:24 - You were wrong about Djkstra algorithm. It doesnt search all the possible paths. Instead it searches only the best path to vertex and uses it to search optimal path to it's neighbors. As it only makes updates from each vertex once and each update only uses one edge(as edge connects 2 vertexes it will only take part in 2 update attempts) it will have complexity O(|E| * upd) . As priority queue is used for updates, upd will have comlexity of O(log(|V|). So total complexity is O(|E| * log(|V|)) which is quiet fast and on average PC it will be able to handle graphs with amounts of edges and vertexes not greater than 100000 in 1 second
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.... :)
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.
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.
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
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 ❤
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.
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 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 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)
I don't want to take anything away from you, it's a great tutorial for understanding A* in a simpler situation. But using a grid with obstacles... does that not sound like a more straightforward Lee algorithm? From what I know, in Dijkstra and A* it's the vertices that have a certain cost, and in a grid that is always 1. Again, it's an awesome idea to simplify the concept, but this time it might be a bit confusing, as you ignore a crucial element from the generalized algorithm, and, even though it's harder to understand for some, I think it just has to use graphs. Amazing channel though. I love your simplicity and enthusiasm.
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***.
5:09 I think they just use g(n) and h(n) because g and h come after f in the alphabet. So it means that f(n) is the sum of the results of 2 other equations.
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)?
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 :)
….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)
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?
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
![Seungmin "그렇게, 천천히, 우리(As we are)" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/kAzmhLHePqU/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.
This is the problem with monospace font glyphs and bad vision. 😂
Classic
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.
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!
People like you do more for students than many universities around the world. Cheers to learning 🎉
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!
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.
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 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
I honestly don't know what I would do without you.
This guy is a genius! It looks so straight forward every single step. Amazing 🤩
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!
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.
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
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 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 < 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!
Best tutorial seen so far on A* algorithm
Thanks
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!
Really Really Really!!!! Fantastic Video. I really love his energy while he was teaching!! Wish I could have this man as my professor. Amazing!!
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
Thanks to your inspiration I finally managed to implement an object oriented version of Astar for Codewars. Keep up the good work!
So after a mess and 2 hours you finished it? You are BRILLIANT my friend!
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!
Absolutely amazing video! Your energy for coding is absolutely amazing and got me coding in p5
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#.
1:42 "needle in a haystack"
*Non-premium spotify user's ptsd intensifies*
Not funny
Didn't laugh
I'm really love the way you showing the coding... fun and relax.... with the great result.
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))`
found out about this channel afew days ago. your videos and walkthroughs are amazing.
For any of you wondering, this is the kind of algorithm top down view rpgs and mobas use like league, runescape, fallout etc
31:39 "some other life that you have"
buddy i barely have one life as it is
dude, I f*ing LOVE your website!
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'm in web dev and watching this. Idk why but this is refreshing some good memories lol
Very well explained, thanks! Love your enthusiasm for teaching!
You saved my semester! Brilliant work. You sir, are awesome!
Your beard is majestic
Holy crap what a good A* explanation at the beginning
Looks just like a robot finding an optimal path through a building. ;)
Thank you a lot. Why are you always the best person to explain things
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
3:24 - You were wrong about Djkstra algorithm. It doesnt search all the possible paths. Instead it searches only the best path to vertex and uses it to search optimal path to it's neighbors. As it only makes updates from each vertex once and each update only uses one edge(as edge connects 2 vertexes it will only take part in 2 update attempts) it will have complexity O(|E| * upd) . As priority queue is used for updates, upd will have comlexity of O(log(|V|). So total complexity is O(|E| * log(|V|)) which is quiet fast and on average PC it will be able to handle graphs with amounts of edges and vertexes not greater than 100000 in 1 second
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
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!
Thanks for showing result at the beginning of the video. Awesome
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.
When I will go to USA, I will meet you no matter what. I love you, man ❤️
Web dev trying to build a game as a hobby project, such a good tutorial - thank you!
So glad to hear!
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.
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.
why ?
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
I love the energy he has
Love you bro
Well done on the editing. Watched the livestream and felt sorry for the editor. But nice result.
Heh, I agree!
I don't even code but your videos are really fun to watch it makes me want to learn it
the joy of codingis to see the end result.....imaging dancing to that path as it finds its way to the end.
Thanks !!! You helped me a lot, and that works for Hex grids! (Of course just have to change neighbors conditions)
To remove a value from an array in javascript, the two main solutions I know are .filter and .splice(.indexOf)
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 don't understand any of that but i find it fascinating!
iam happy to see this work !
I absolutely love these coding challenges! Keep being awesome.
You deserve MORE MORE MORE Subscribers
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 :')
OMG 😱😱😍 amazing challenge
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 love your videos because it builds logic 😊
I like how you explain what's going on, and what you're going to do next, and why.
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
Thanks this helped me solve a real world problem!
Dude you're just amazing. Programming is so great!!!
I loved the part when pathfinder says "get ready, its Zipline time" and start pathfinding all over the place
Beautifull video very nice to view your channel is Very wonderfull go again
thanks you are awsome man !!.we need more complicated videos
Go to the coding Choppa !
Gregzenegair Skynet
"put the cookie down" - Arnold Schwarzenegger
I wish you were my teacher, and thank you for teaching me how to code
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)
Wow I'm a whole year late to this video.
Me too :)
yup same
13 months right here
Im 2.5 years late.
Huh novices
you are wonderfull, very entertaining see your coding process.
Thanks to this channel I moved all my draw engine of my project to p5 :D
This algorithm project is very interesting & amazing
yesss A*!! awesome
I don't want to take anything away from you, it's a great tutorial for understanding A* in a simpler situation. But using a grid with obstacles... does that not sound like a more straightforward Lee algorithm? From what I know, in Dijkstra and A* it's the vertices that have a certain cost, and in a grid that is always 1. Again, it's an awesome idea to simplify the concept, but this time it might be a bit confusing, as you ignore a crucial element from the generalized algorithm, and, even though it's harder to understand for some, I think it just has to use graphs. Amazing channel though. I love your simplicity and enthusiasm.
Wow, noch einer der schon Schall absondern kann!
I can't believe you take the time to like comments years after the videos come out.
Amazing 😍 video ❣️👌
"Are you still watching?"
Me, who just watched the entire coding challenge playlist: MOOOOOOOOOOOOOOOOOOOOORE
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***.
id sell my soul, donate kidney, donate blood, donate a leg to be as smart as this guy is in software.
Finally sunder pitchai's official youtube channel😂🤘
5:09 I think they just use g(n) and h(n) because g and h come after f in the alphabet. So it means that f(n) is the sum of the results of 2 other equations.
in the for loop with at 12:25 lines 14-16.
shouldn't the rows be first and then the columns?
I mean when you iterate through the 2D array you choose the row first and then the columns.
arr = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
arr[0][0] is 1st row 1st column not 1st column 1st row.
am I missing something here?
yes, he used cols for rows and visa versa
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)?
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 :)
….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)
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?
wonderful challenge coding game.
Sucesso Ao Canal 👍😀👍
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