Huh, that's useful because I had to write a floodfill a couple of days ago and it was a pain in the arse.
I'll be converting my code to the stackless version toot sweet.
brcmthrowaway · 2026-10-27 15:07:57 UTC
Why were you needing floodfill?
zimpenfish · 2026-10-27 15:47:46 UTC
To find connected regions on a map. I could probably have been smarter about the initial generation and connected things as they were generated (but that has only just occurred to me. Worth a go, I suppose.)
hyperhello · 2026-10-27 15:30:12 UTC
The algorithm uses about half a byte per pixel and saves the path it follows. That kind of implies that the stack is still there and present, it’s just bounded to the number of pixels, and could actually be modified to just use a bounded area of the heap. But conceptually it’s easier to follow the way the paper was written. Neat.
voidUpdate · 2026-10-27 15:49:13 UTC
How does this deal with one pixel gaps? The algorithm can enter it just fine but there's no space to go back out again, and there doesn't seem to be a system for backtracking, unless I've misunderstood the algorithm
Jtsummers · 2026-10-27 16:24:34 UTC
It backtracks using the origin direction. As it traces back to the original starting pixel, before filling the current pixel it attempts to scan the remaining directions for each pixel (which may be none). If those lead to further pixels needing to be filled it'll start going forward again, and eventually hit a dead end and trace back to the branch point and continue to scan around it, eventually discovering is itself a dead end and go to its own predecessor.
Basically, a pixel will go through states like:
(U,R) ;; came from up, went right
(U,D) ;; came from up, went down
(U,L) ;; came from up, went left
(U,U) ;; came from up, went up
Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.
Comments
I'll be converting my code to the stackless version toot sweet.
Basically, a pixel will go through states like:
Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.