@@Skyblue92uno he means AFTER its done Just like the sorting algorithm, after the sorting is done, you hear one last noise wich is the complete one, which should sound nicer then all the noise
@@FriedMonkey362 Noise? Those were all single notes with defined frequencies, played fast or slow. It might sound like noise to a non musician I guess.
I love how you showed “mistakes”. That’s so useful for learning. Maybe you even made mistakes on purpose to be pedagogical, I don’t know. Very useful regardless!
Your explanation of breadth first search plus a short conversation with someone about how nodes work instead of tiles was enough for me to get a working breadth first search algorithm in a day, and I've never made a pathfinding algorithm before
You should have written which is which. Btw a lot of other algorithms exist: like there are various speedups for A* for grid-like spaces like this that are more efficient and there are hierarchical pathfinding algorithms that basically create bigger grids and pre-calculate which connects with which (info needed only at boundary) and then you can do a higher level search on the bigger grid and then a low-level search for the inside of the grid. This ensures scalability much better. A further speedup to the original A* is to "look ahead" so instead of just using the hint values for the cell to visit - we look ahead and its hint becomes hint values of that + all its neighbors that are k distant from it. This ensures much better heuristic hints at the cost of more operations - but can lead to better results. One can also pair this up with data structures that hold the grid not the usual 2D array ways, but as a hierarchy where close-by elements are more often cache local to each (this is especially powerful if you can make the grid 0s and 1s.
Heh just seeing this video now, and i love it. The one thing i thought was missing is a final going up the scale as the purple line is drawn in. It was a little disappointing after all that awesomeness to not get that final glissando when it's found the path. Always found that to be the most satisfying part of the sorting method videos.
I know this is one year late. But the breath first algorithm has 1 upside that the A* cant really compete in. And that is when you have multiple targets, or if you don't know where the targets are on the grid. The second one is fairly simple because the A* requires target locations to work optimally. The first one is not so simple, with a finite set of targets you could optimize it to work, but if the size gets to big even a optimized priority queue that is designed to handle multiple targets you simply lose in complexity gained because you have to iteratively check against all targets, while the breath first simply can simply check on a set if it is contained. It's basically List.indexOf vs Set.contains problem. And pathfinding usually contains multiple targets at once.
@@DMG. It will turn into a N*M problem while breath first stays in the same logic complexity level. Because you need to evaluate the "closest" distance for every possible target on every node. Breath first doesn't have this issue.
@@Speiger ya so cool! Recently discovered flow fields after playing a plague tale and I love this style of pathfinding! Instead of using each agent to request an A* path you just bake each navTile or mesh with a direction to the goal!
The biggest thing missing is information on each pathfinding. My favorite part about Timo Bingmann's video is that I could identify which sort I liked the best and look it up for more information. I wish I knew which pathfinding algorithm was being used.
The difference of the sound use is the algorithm is linearly increased, from sorting algorithms is more exciting because of the pseudo randomized opening and the ordered ending
I think you could have shown Dijkstra and depth first search too. Perhaps djikstra ends up almost doing the same as bfs it still worthwhile pointjng out the differences
I was wondering where your other videos are? I'm new to the channel and it seems you've had more videos but I only see four. Sorry if this has already been asked or if I'm wrong about there being past videos. By the way seems like a very good channel!
I did have some old videos but they aren't very good. I just want to keep making better videos and my old ones weren't up to the standard I want to work towards.
I know this is an old video, but at 7:33, it looks like your heuristic might not be pointing in the right direction. It should naturally go from top left to bottom right, not to the middle of the right side.
I can't help but wonder if your a* method would have problems if the optimal route to the goal involved substantial back-tracking, especially at the start. All your examples involved only forward-pathing.
A* copes wih that just fine. But, like any algorithm that explores the best-looking regions first, it'll have to do a lot of backtracking if the things that look good turn out not to be good. And there's plenty of backtracking shown in the video. In the example that starts at 8:24, you can see that the algorithm starts by heading broadly in the right direction, but it gets stuck in a bit of a dead-end at about 8:30. It then spends quite a while investigating minor deviations closer to the source, before finally breaking through.
The efficiency of the second algorithm seems a little suspicious, when you start in x+ direction and the target is exactly in the x+ direction. It would be nice to add at least a part of the c code, to give a hint, what you are doing there.
it tooks the closest tile to targetTile as first tile to move, so if target in x+ direction it goes x+ (Fcost is lower in that direction, it's greedy to get target faster as it can inspite of correct shortest way), It doesn't take other direction until it reaches dead end in first direction, and other tiles get additional cost if not selected, so it's hard to back to previous tiles. The best con of this is speed of calculations (it even needn't closed list to use algorithm, I guess)
Great video, but could have been better if you showed which approach/algorithm is being implemented after adding the sound effects. you've put in great efforts.
"it's time for the fun part: the noise" but you've already added noise, I thought, it's just simple white noise for the solid tiles probably should have said "sound" here instead
It's a nice enough video, but A* was kinda base level when I studied computer science more than 20 years ago so there are many many videos explaining it. It'd be nice to see videos that go into the various improvements that have been created since then.
I believe your videos would be even better if you had less clips of other people laughing or saying something and instead just have yourself, you are way cooler than you probably think, to me at least
Good question. I am a self taught programmer and began with Python. One of my first projects was making a game so I've kinda been making games forever.
That last part, with the noise... feels like it should come with some kind of warning. "Those of sensitive hearing, beware!" or maybe "Please don't listen to this part with headphones in, for your own sake"... something like that. Nice video otherwise, though!~
Love your videos, but there’s a jarring feeling when you insert loud laugh gag clips. I know you are trying to add humor like other RUclipsrs I love such as @codebullet and @civvie11.
The sound effect turned up much cooler than I expected tbh. Great work here!
I'm glad you liked it!
What I think would be cool if the path was not generated instantly, but was constructed tile by tile with the noise. Just like the algorithms
Isn’t that literally what he did?
@@Skyblue92uno he means AFTER its done
Just like the sorting algorithm, after the sorting is done, you hear one last noise wich is the complete one, which should sound nicer then all the noise
@@FriedMonkey362 Noise? Those were all single notes with defined frequencies, played fast or slow. It might sound like noise to a non musician I guess.
@@jutube821, no, noise as in sound in general, not white noise
@@jutube821you know how when you say "loud noises", well noise as in that: a sound
I love how you showed “mistakes”. That’s so useful for learning. Maybe you even made mistakes on purpose to be pedagogical, I don’t know. Very useful regardless!
Trust me, I don't need to create mistakes to show because I make plenty already 😆
@@CodeNoodles Sorry I doubted you XD
8:24, your algorithm just straight up played Flight of the Bumblebee
Lol you're right it kinda does 😆
Personally, I heard the screams of a desperate algorithm losing hope that it will accomplish its singular goal in life!
eh
Your explanation of breadth first search plus a short conversation with someone about how nodes work instead of tiles was enough for me to get a working breadth first search algorithm in a day, and I've never made a pathfinding algorithm before
That's awesome, I hope the video gave you sufficient information!
You should have written which is which. Btw a lot of other algorithms exist: like there are various speedups for A* for grid-like spaces like this that are more efficient and there are hierarchical pathfinding algorithms that basically create bigger grids and pre-calculate which connects with which (info needed only at boundary) and then you can do a higher level search on the bigger grid and then a low-level search for the inside of the grid. This ensures scalability much better.
A further speedup to the original A* is to "look ahead" so instead of just using the hint values for the cell to visit - we look ahead and its hint becomes hint values of that + all its neighbors that are k distant from it. This ensures much better heuristic hints at the cost of more operations - but can lead to better results. One can also pair this up with data structures that hold the grid not the usual 2D array ways, but as a hierarchy where close-by elements are more often cache local to each (this is especially powerful if you can make the grid 0s and 1s.
Heh just seeing this video now, and i love it. The one thing i thought was missing is a final going up the scale as the purple line is drawn in. It was a little disappointing after all that awesomeness to not get that final glissando when it's found the path. Always found that to be the most satisfying part of the sorting method videos.
You're right. I love the sorting algorithm videos as well! Maybe I should do a video about them 🤔
@@CodeNoodles Nice, i'd totally watch that :) btw, I hope i didn't come off too harsh with my prior comment, i just get nitpicky sometimes :-P
Man, this visualization is phenomenal, and the sound is awesome. Thanks and subscribed.
I’ve watched all your videos and I subbed, I can’t wait to see you post more. I really want to get into coding now
this is a great pathfinding algorithm! thanks for the epic video!
This is really cool! What happens if the target is fully encased in solid tiles?
Thanks! If the target is fully encased once the algorithm runs out of tiles it just stops and no path is generated.
@@CodeNoodles I saw that coming but I don't think the algorithm did
Bud dump dink
in addition to no complete path being generated, generally you still remember the closest valid tile to the goal and can still make a path towards it
You have to remember that 'no path' is a valid result sometimes and allow for that exit point once everything has been checked.
How come the final path appears to go through the frontier tiles as seen at 6:06? If they're in the frontier, they shouldn't have been searched yet.
I forgot to mention that the A Star algorithm doesn't use a searched tile list. It can go over a tile multiple times if it produces a better path.
@@CodeNoodles what happened to the duck hunting game video?
I know this is one year late.
But the breath first algorithm has 1 upside that the A* cant really compete in.
And that is when you have multiple targets, or if you don't know where the targets are on the grid.
The second one is fairly simple because the A* requires target locations to work optimally.
The first one is not so simple,
with a finite set of targets you could optimize it to work, but if the size gets to big even a optimized priority queue that is designed to handle multiple targets you simply lose in complexity gained because you have to iteratively check against all targets, while the breath first simply can simply check on a set if it is contained.
It's basically List.indexOf vs Set.contains problem.
And pathfinding usually contains multiple targets at once.
You could probably get A* working with multiple targets without much issue
@@DMG. It will turn into a N*M problem while breath first stays in the same logic complexity level.
Because you need to evaluate the "closest" distance for every possible target on every node.
Breath first doesn't have this issue.
@@Speiger ya so cool! Recently discovered flow fields after playing a plague tale and I love this style of pathfinding! Instead of using each agent to request an A* path you just bake each navTile or mesh with a direction to the goal!
So glad i found your channel! Awesome video and your newer ones look even more interesting ^_^
Thanks, it means a lot!
you can make a c++ priority queue order from minimum to maximum like this:
std::priority_queue
The biggest thing missing is information on each pathfinding. My favorite part about Timo Bingmann's video is that I could identify which sort I liked the best and look it up for more information. I wish I knew which pathfinding algorithm was being used.
The difference of the sound use is the algorithm is linearly increased, from sorting algorithms is more exciting because of the pseudo randomized opening and the ordered ending
Spaggetiiiiii
7:18 to get to the part of the video you clicked for
I think you could have shown Dijkstra and depth first search too. Perhaps djikstra ends up almost doing the same as bfs it still worthwhile pointjng out the differences
Or Jump Point Search
i didn't expect how satisfying the generation would sound lol
*Adds sounds*
Algorithm:
-I am cop
-Now I am cat on piano
Well, the sound is horrific and satisfying at the same time
0:43 Oh is that a "Sounds of the Mandelbrot set"?
(colorful ♪)
Really cool piece of software !
8:21 Me telling a story.
8:24 My gf telling the same story.
I was wondering where your other videos are? I'm new to the channel and it seems you've had more videos but I only see four. Sorry if this has already been asked or if I'm wrong about there being past videos. By the way seems like a very good channel!
I did have some old videos but they aren't very good. I just want to keep making better videos and my old ones weren't up to the standard I want to work towards.
@@CodeNoodles Perhaps unlist them and put it in a playlist called "Old Videos" or something
I know this is an old video, but at 7:33, it looks like your heuristic might not be pointing in the right direction. It should naturally go from top left to bottom right, not to the middle of the right side.
8:24 R2D2 on drugs
another very epic and cool video
Life changing video!
I can't help but wonder if your a* method would have problems if the optimal route to the goal involved substantial back-tracking, especially at the start. All your examples involved only forward-pathing.
You're correct. The A* algorithm isn't always the fastest, it just is well balanced for most situations. Good observation!
A* copes wih that just fine. But, like any algorithm that explores the best-looking regions first, it'll have to do a lot of backtracking if the things that look good turn out not to be good. And there's plenty of backtracking shown in the video. In the example that starts at 8:24, you can see that the algorithm starts by heading broadly in the right direction, but it gets stuck in a bit of a dead-end at about 8:30. It then spends quite a while investigating minor deviations closer to the source, before finally breaking through.
The efficiency of the second algorithm seems a little suspicious, when you start in x+ direction and the target is exactly in the x+ direction. It would be nice to add at least a part of the c code, to give a hint, what you are doing there.
it tooks the closest tile to targetTile as first tile to move, so if target in x+ direction it goes x+ (Fcost is lower in that direction, it's greedy to get target faster as it can inspite of correct shortest way), It doesn't take other direction until it reaches dead end in first direction, and other tiles get additional cost if not selected, so it's hard to back to previous tiles. The best con of this is speed of calculations (it even needn't closed list to use algorithm, I guess)
What happened to your duck hunting video, I saw it and liked it but now it's gone?
This reminds me of, a bit obviously, echolocation, as well as Slime molds!
Is there a combination of layout and algorithm that would make the audio sound like the harp intro to Zelda's Fairy Fountain theme?
That's such a cool idea, but I don't know if such a layout like that exists.
Hi Mr. Pasta, it's fortunate to see you not being gulped down by philosophers.
4:28 Nooo, I do'nt want to go there, nooo! XD 'perfectly inefficient', could see that it actually would work with the fix you applied🙂
Great video, but could have been better if you showed which approach/algorithm is being implemented after adding the sound effects. you've put in great efforts.
I still don't see why you don't have as many subscribers as other channels who do the same kind of content
New channels tend to get less traction, even if the content is basically a copy but modified. (pain)
"it's time for the fun part: the noise" but you've already added noise, I thought, it's just simple white noise for the solid tiles
probably should have said "sound" here instead
It's a nice enough video, but A* was kinda base level when I studied computer science more than 20 years ago so there are many many videos explaining it. It'd be nice to see videos that go into the various improvements that have been created since then.
I agree. I made this video when I had a very limited understanding of pathfinding algorithms, so I should do something better in the future.
Would be cool to make a game using this.
Cool video! : )
Just with a higher pitch
I feel the struggle of the cpu from scanning that algorithm grid lmao
This works wonderfully but most of the outcomes are not the shortest distance.
Have you improved this algorithm to always give the shortest distance?
You could totally make music with this, and each algorithm would have different methods to do so...
Posted 7 seconds ago this is the earliest I've ever been anyways hello
Sound effect should be low fart at the start, then get higher pitched as it gets closer.
What library did you use for the visualization?
HI, how did you created grafics for c++?
Just wondering there is no glass header file in the repo ,could u please help with that???
Please see ur github repo
Awesome video! :D
Now give this to some music producers and they will make a song by creating a maze!
Where is your duck hunt vid? That was really great!
Hey Noodles! Where/How would I get the code for this. I wanted to experiment with the program but I wasn't sure how to do that.
It's on my Github, which is in the description of my videos.
Would've been fun to see an algorithm that picks at random, just for the sound of it
Really good video!
I believe your videos would be even better if you had less clips of other people laughing or saying something and instead just have yourself, you are way cooler than you probably think, to me at least
You should generate a sound in sync with the drawing of the final path. (instead of the silence!)
Your videos are great, but flashing back to the white background has destroyed my retinas.
Please fix in the next patch
Very nice video!
7:58 why does this sound like the roblox death sound
I love your videos
Why not make both the start and end pathfind to the other until they meet in the middle and make a path? Would it be faster or slower?
this is called a bidirectional search. it's usually faster, but the implementation is more complex
DUDE, it would be very fun if the topology of the grid - or map? - make the pitches purposefully sound like music hahaha
7:49 it sounds like the oof sound efect
(;24 example is very interesting, as it kind of get some steps back to find the solution
Nice Vid but did you seriously compare A* and BFS ??
A Path finding algo vs a path optimization algo.
Nice!
So cool!
Now i wait for Jump Point Search
Wow that's why I am subscribed for free codes
if polibeus existed this is tha music
bro im doing packman and i looked this up for the algortythm the chances
4:28 Generous best-first dearch
Niiiice
Watching this made me hungry for noodles...
3:43 : Try saying that 3 times fast
Me: Greedy Breast F- wait what?
You should use this to make a pathfinding algorithm play never gonna give you up
I wonder if someone could make music with this…
codenoodles i have a question
7:50 "OOF"
Damn it you forgot to put the titles of the algorithms.
its that where did you discover coding and where did you use to code before making custom games
Good question. I am a self taught programmer and began with Python. One of my first projects was making a game so I've kinda been making games forever.
@@CodeNoodles oh ok im still a beginer in coding
Could you fill your character eyes ? It's real scary NGL
7:49 lmfao oof sound
That last part, with the noise... feels like it should come with some kind of warning. "Those of sensitive hearing, beware!" or maybe "Please don't listen to this part with headphones in, for your own sake"... something like that. Nice video otherwise, though!~
No Dijkstra's algorithm???
on a graph with uniform edge cost, dijkstra works identically to bfs
Cool!
hello there
General Kenobi
How this comment get 5 likes?
Maybe it's better to use vectors here instead of straight lines, to optimize it's movement
i apprecated the greedy worst-first search
Wow!
2:51 pls don‘t use Nikocado clips. Its satisfying to look at those paths. A cool video.
Love your videos, but there’s a jarring feeling when you insert loud laugh gag clips. I know you are trying to add humor like other RUclipsrs I love such as @codebullet and @civvie11.
Commenting 4 algorithm
I think you should put this online so other people can use it.
bet you can't port it to 3ds
Try ds
"Manathan distance" ... use the proper math term "Euclidian distance"
those are different. Manhattan distance is abs(x1-x2)+abs(y1-y2). Euclidean distance is sqrt((x1-x2)^2 + (y1-y2)^2)
ThAt soUnd