Yeah. I was planning on using that as a way to talk about more general graph traversal. We just hadn't talked about it yet and I didn't want to confuse anyone!
That requires mutable node state though. Some would call it less elegant from a programmer's point of view. Could create trouble with multithreading and stuff.
One more thing to mention is that recursive version of flood fill can get stack owerflow exception if you try to flood fill big maze. I got this exception with maze image 4000x4000.
Awesome explanation! It helped me a lot when I tried to create an Etch-a-Sketch game. I have watched lots of other explanations but yours is the best hands down. I really cannot express enough how grateful I am for your video and a respective article on the archive.
I solved this in 1996 by pushing the points onto a stack and popping them randomly. Random popping keeps the stack size minimized without slowing down the search - this is better than either depth first (which can make the stack blow up very large) and breadth first (which can delay leaks into new regions)
Random popping from a stack adds the overhead of removing nodes from the middle of the stack, which either means a linked list traversal or an array copy. Does it really help enough to offset that?
Tim H. I used array copy - moving the last element to the random „popped“ position - fast and much cheaper than testing a step. It’s amazing - the surface of the floodfill spreads out like a circle - irrespective of the complexity and „mazed-ness“ of the shape - it’s beautiful to watch - randomness is truly the most efficient approach in terms of stack size, elegant and simple.
Tim H. It massively helps as the stack size stays always the size of the circumference of the expanding circle - If you go depth first through a maze every point on Each side of the path goes on the stack, meaning the stack can easily be double the number of points searched. With „random stack“ the stack size never grows much larger than sqrt(area/pi)
@@idjles Ah, that makes sense. Swap the term to be popped with a random one further down the stack and use that one instead. If we're going to be popping in a random order, then we don't have to preserve insertion order. I'll have to play with that some time, the nondeterminism makes the algorithmic analysis much more interesting. I'm assuming it's a uniform distribution over the size of the stack?
Thanks for the video! Flood fill is easy to understand, but implementing it efficiently is quite difficult. I'm currently using a Hoshen-Kopelman implementation for domain labeling on a 3D lattice, but performance still isn't ideal.
Oh yeah, it gets really tricky really quickly! I wanted to introduce it as a way to do more graph-y methods on the channel. At this point, we've only really done tree traversal.
Are you going to add a chapter to the algorithm archive on maze generation at any point? There's like 14 different algorithms and some of them are really interesting.
Awesome video. This is pretty unrelated, but is it possible to have a software that converts mp3 into a sum of sine functions and then express that function algebraically? For example, since we can visualise sound in visualiser software or simply by putting for example sand on a speaker, we can express the process that's going on. A lot of sound visualisation methods rely on Fourier methods and I know you have experience with Fourier-stuff so if you have any ideas that'd be cool.
I don't know of any software, specifically, but a Discrete Sine Transform will do precisely what you want. Each element in the output array will just be the the "amount" of that frequency in the music. I was thinking about this recently as well when considering algorithmic composition (music with code), but didn't really get anywhere. Sorry I couldn't me more helpful!
@@LeiosLabs I was also thinking of using the Discrete Sine Transform but wasn't sure how to implement it (in an algorithmic sense), especially with my poor programming skills. I just have an ongoing joke where my friends and I graph Fourier series and pretend it's some amazing music. I'll keep looking into it because it's definitely possible. People have done it for musical instruments before so it'll work by the same principles.
@@LeiosLabs I'm not entirely sure how that would work either, but you could use a visualisation software for the wave (these are readily available), then write a program to find the amplitudes, after which you do a Fourier transform to get the sine waves. Is that a valid method in general?
Great video as always! I mainly got into coding because of desiring to simulate and visualize or plot concepts from physics and mathematics. I do have a question, what software do you use to edit the videos?
Yeah, like everyone said, it's twitch chat. I'm trying something new with my most recent videos by showing the chat and doing minimal editing from my twitch stream. This helps me get content out quicker, allows me to keep my face on screen the whole time, and advertises the stream a bit.
regarding floodfill using dfs you said that you can do it by tree traversal and didn't mention that it's not tree and normal tree traversal is not applicable.
@@r75shell I believe you have it backwards. You are right that I should have covered graph traversal in a previous video, but up until 6:00, we are traversing through trees. It is a graph, in principle, but we are using tree tactics. At 6:00, we start treating it like a graph to some extent, but even then we still treat it as a tree with some nodes no longer connected. I recognize that treating these as a true graph is the more traditional approach, and that will be covered soon-ish.
@@LeiosLabs Ha! It's funny. You actually have *thing* in code in chapter that handle it, but none of text is mention it. In chapter it's not mentioned, like if it's not so important as in bfs. Similarly in video here your pseudocode doesn't mention it, nor your words. It's when you return from recursion if color is already equal to color you are filling. It's similar thing to how you're not enqueue twice in bfs. If you remove this code, even for 4 (four) pixels for fill, you'll get infinite recursion, because tree traversal doesn't check for visited status, because it's intended for trees. But here you may have not a tree. By the way if tree is not "rooted" if you run same tree traversal without check for visit status, you'll also get infinite recursion because you may "oscilate" between two nodes back and forth.
@@r75shell Correct, this is not an n-ary tree, but it is still a tree in this approximation. Each node has a parent and up to 3 children. I understand that this can also be represented as a graph and I mention that it *is* in-fact a graph for later, but by showing it in a more tree-like way, it allows me to work off of what we already have and is slightly more intuitive in my mind. We could have an argument about what is most intuitive, and that's fair... Also why there will be subsequent videos.
