Visualizing Pathfinding Algorithms

In this video I code a visualization of a couple of different pathfinding algorithms.

LINKS
▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀

█▀ █ █ █▄▄ █▀ █▀▀ █▀█ █ █▄▄ █▀▀
▄█ █▄█ █▄█ ▄█ █▄▄ █▀▄ █ █▄█ ██▄

[andrewtoasterr]

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

[plagosus]

The sound effect turned up much cooler than I expected tbh. Great work here!

[AceStreaming]

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

[HyperFocusMarshmallow]

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!

[plectro]

8:24, your algorithm just straight up played Flight of the Bumblebee

[uvata]

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.

[PumpkinBear]

This is really cool! What happens if the target is fully encased in solid tiles?

[Speiger]

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.

[danyaeger]

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.

[toffeejc]

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

[woi]

Man, this visualization is phenomenal, and the sound is awesome. Thanks and subscribed.

[the_cheese_cultist]

you can make a c++ priority queue order from minimum to maximum like this:

std::priority_queue<int, std::vector<int>, std::greater<int>>

[paicemaster]

So glad i found your channel! Awesome video and your newer ones look even more interesting ^_^

[grassypaddy]

this is a great pathfinding algorithm! thanks for the epic video!

[XoIoRouge]

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.

[comeycallate]

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

[thePrplMonkey]

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.

[wangtang]

i didn't expect how satisfying the generation would sound lol

[blazester]

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!

[catmaxi]

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