How does flood fill work?
Вставка
- Опубліковано 1 сер 2020
- Algorithm Archive: www.algorithm-archive.org/con...
Source code: In chapter
Github sponsors (Patreon for code): github.com/sponsors/leios
Twitch: / leioslabs
Discord: / discord
Github: github.com/leios
Music: www.joshwoodward.com/ - Наука та технологія
Flood fill a.k.a. the inefficient path finder
Or, you could mark a vertex as visited, which is more or less the same as coloring it as you go in the bf traversal. Nice video!
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.
@@busTedOaS Or a hashset
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.
This is an issue with recursion in general. Memory overhead gets huge.
Not if you're writing it in a language that can TCO
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 like how you explain things, very easy to follow and very relateable!
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)
That sounds really interesting! I'll have to play this through in my head.
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 a lot. I'd never implemented flood fill before and this was a great introduction to it. Had it working in no time.
The way you explain is wonderful.
Thanks!
I like this video! I've never seen the graph abstraction applied to pixels before, it makes sense!
Yeah. We'll be doing more graph-specific stuff soon!
This was great, I would love more on cellular graphical algorithms
Haha, there will be more! I just like to hop around different topics.
Really good and quickly explained.
Just wanted to say this is a phenomenal video.
Fascinating! Thank you for this.
I'm glad you liked it!
A nice explanation of flood fill
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.
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?
I use Blender for video editing. There aren't too many good linux options ^^
@@LeiosLabs thanks from the prompt reply! Well it seems to work great because they are really well edited, keep up the great content.
@@heliumhydride Thanks!
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.
I really want to!
Wow awesome video. Thanks. using Julia is great too
Yeah, I use Julia for everything nowadays
Thank you
Which coding program and software do you use? I think Lua myself. But it doesn't wuite seem like it. Thanks
This was all Julia
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.
@@laviekolchinsky9441 I just don't know how to load music in as an array. This is probably different depending on what language you want to use.
@@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?
@@laviekolchinsky9441 I am honestly not sure. I haven't really done this stuff before. Sorry!
What are those lines of code above you on the screen
CarbylAmine twitch chat
Looks like an IRC client.
Lol, I'm new to this world.
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.
How have you been? / Time has passed this year. I hope you take care of the cold weather and health based on Korea. ^O^
I will never understand why some people think that recursion is somehow easier or more natural.
I was curious about your terminal game, but the specterm.jl
repo just has a README and a LICENSE
I put everything in a development branch until it's ready. Lots of work left to do, so it's still in the development branch.
@@LeiosLabs Doh! I should know by now to check for alternate branches. Thanks!
Dude your vdo was awsome but one q where did you get the idea of naming your channel so unique ''Leios os" it's kinda weird and cool...
wow, what a beard!
Thanks, you too!
Does Go even count as a video game?
Ok, you are right. It's not a "video" game, but it was a game I played online.
😄
for pixel in areatofill:
fill(pixel);
is just that easy kappa
Thankfully that 6:33 didn't turn into a swastika.
I hadn't even considered that as a possibility!
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.
At that stage, we were treating it as a tree, where each point has 3 children, so tree traversal was appropriate. We'll do more graph-like stuff later
@@LeiosLabs 3:35 tree drawn, and after few seconds you fill picture, which is not a tree. Reduction to tree is discussed at 6:00
@@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.
Hmm, i just feel it's isn't right.
Like you're comparing low level algorithm vs high level algorithm