Author Topic: Can You Flood Fill?  (Read 4378 times)

0 Members and 1 Guest are viewing this topic.

Offline LincolnB

  • Check It Out Now
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1115
  • Rating: +125/-4
  • By Hackers For Hackers
    • View Profile
Can You Flood Fill?
« on: October 04, 2011, 11:13:30 pm »
Hi everyone. For PaintPad, I'm really close to releasing the first version, but before I do, I need a flood fill algorithm. I've tried a little bit, but haven't been able to get anything to work. So, I'm making it a contest of sorts.

I'm uploading a very, very, very watered down version of PaintPad, all it supports is pixel drawing and deletion. All I need is a simple flood fill function - the template is there, all that it needs is the code.

So yeah. If you're up to it, check it out, and upload or post the code for your floodfill function.

Also, here's the code for anyone not wanting to go to the trouble of downloading an sending the attached source file, FLOODSRC.

Spoiler For code:
Code: [Select]
.FLOOD
.The challenge is to write a   good,solid floodfill function.

DiagnosticOff

.Cursor coordinates
10->X->Y

.Start the program with the cursor at 10,10

.The arrow keysmove the cursor

.When you pressALPHA, call the flood fill function
.When you press2ND,it draws a  pixel at the X,Yposition

ClrDraw
ClrDraw^^r

.Clear exits
Repeat getKey(15)

.This code is  unoptimized,and I use a lot of  functions, for  clarity purposes
Input()

.^All this function does is getinput from the  arrow keys

.Now,to get input from 2ND and ALPHA
.Remember-
.2ND=Draw pixel
.ALPHA=Flood fill
.And [DEL] deletes pixels

If getKey(54)
Pxl-On(X,Y)^^r
End
If getKey(56)
Pxl-Off(X,Y)^^r
End

.Now,its your  turn to write   some code.
.All I need is someone to writethe Flood() function.
If getKey(48)

Flood()
.^That.
.Scroll down tosee what code   needs to be written.

End


.Now,for some  boring display  stuff

.Everything is stored on the   back buffer
.The front buffer is for displaying the cursor and other stuff

RecallPic

.Display cursor
Cursr()

DispGraph
Pause 75


.End of main   loop
End
Return


.Finally,the flood fill function!
Lbl Flood

.YOUR
.CODE
.HERE

.Remember, dontwrite to the    front buffer,usethe back buffer

Return



.Other functions

Lbl Input
If getKey(1) and (Y<63
Y++
End
If getKey(2) and (X>0
X--
End
If getKey(3) and (X<95
X++
End
If getKey(4) and (Y>0
Y--
End
Return

Lbl Cursr

Rect(X,0,1,63
Rect(0,Y,95,1
Pxl-Off(X,Y

Return

Eh, spacing on the comments is a little weird^^

PS for anyone who doesn't know what I mean by "flood fill function", it's pretty much the bucket tool in mspaint.
Completed Projects:
   >> Spacky Emprise   >> Spacky 2 - Beta   >> Fantastic Sam
   >> An Exercise In Futility   >> GeoCore

My Current Projects:

Projects in Development:
In Medias Res - Contest Entry

Talk to me if you need help with Axe coding.


Spoiler For Bragging Rights:
Not much yet, hopefully this section will grow soon with time (and more contests)



Offline Deep Toaster

  • So much to do, so much time, so little motivation
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 8217
  • Rating: +758/-15
    • View Profile
    • ClrHome
Re: Can You Flood Fill?
« Reply #1 on: October 05, 2011, 12:44:11 am »
Builderboy once gave me an awesome little tutoring session on how it works. Let's see if I can dig it up...
« Last Edit: October 05, 2011, 12:44:40 am by Deep Thought »




Offline LincolnB

  • Check It Out Now
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1115
  • Rating: +125/-4
  • By Hackers For Hackers
    • View Profile
Re: Can You Flood Fill?
« Reply #2 on: October 05, 2011, 09:42:49 am »
hey, sounds great. PM me or post it here if you find it.
Completed Projects:
   >> Spacky Emprise   >> Spacky 2 - Beta   >> Fantastic Sam
   >> An Exercise In Futility   >> GeoCore

My Current Projects:

Projects in Development:
In Medias Res - Contest Entry

Talk to me if you need help with Axe coding.


Spoiler For Bragging Rights:
Not much yet, hopefully this section will grow soon with time (and more contests)



Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Can You Flood Fill?
« Reply #3 on: October 05, 2011, 09:44:42 am »
Code snippets in spoiler tags are messed up in Chrome. Yay for one line source viewing!
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline aeTIos

  • Nonbinary computing specialist
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3915
  • Rating: +184/-32
    • View Profile
    • wank.party
Re: Can You Flood Fill?
« Reply #4 on: October 05, 2011, 09:44:55 am »
ARGH. Code + Spoiler + Chrome = guess?
Argh. you ninja'd me.
« Last Edit: October 05, 2011, 09:51:56 am by aeTIos »
I'm not a nerd but I pretend:

Offline Chockosta

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 447
  • Rating: +169/-6
    • View Profile
Re: Can You Flood Fill?
« Reply #5 on: October 05, 2011, 02:38:27 pm »
I don't know anything about Axe... Does it allow recursive functions ? If yes, it's really easy...
Anyway, Wikipédia is really interesting about that.
http://en.wikipedia.org/wiki/Flood_fill

Offline calc84maniac

  • eZ80 Guru
  • Coder Of Tomorrow
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2912
  • Rating: +471/-17
    • View Profile
    • TI-Boy CE
Re: Can You Flood Fill?
« Reply #6 on: October 05, 2011, 02:45:30 pm »
I don't know anything about Axe... Does it allow recursive functions ? If yes, it's really easy...
Anyway, Wikipédia is really interesting about that.
http://en.wikipedia.org/wiki/Flood_fill
It does, but the stack isn't big enough to nest so many function calls
"Most people ask, 'What does a thing do?' Hackers ask, 'What can I make it do?'" - Pablos Holman

Offline Chockosta

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 447
  • Rating: +169/-6
    • View Profile
Re: Can You Flood Fill?
« Reply #7 on: October 05, 2011, 02:52:34 pm »
Aw, too bad.
So I guess you'll have to use use the fixed memory way (right-hand fill method) to do this.
But it is quite slow with complex shapes.
So, good luck :P
« Last Edit: October 05, 2011, 02:52:42 pm by Chockosta »

Offline LincolnB

  • Check It Out Now
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1115
  • Rating: +125/-4
  • By Hackers For Hackers
    • View Profile
Re: Can You Flood Fill?
« Reply #8 on: October 06, 2011, 09:38:50 pm »
Deep? You find it? (or BuilderBoy, for that matter)
Completed Projects:
   >> Spacky Emprise   >> Spacky 2 - Beta   >> Fantastic Sam
   >> An Exercise In Futility   >> GeoCore

My Current Projects:

Projects in Development:
In Medias Res - Contest Entry

Talk to me if you need help with Axe coding.


Spoiler For Bragging Rights:
Not much yet, hopefully this section will grow soon with time (and more contests)



Offline thepenguin77

  • z80 Assembly Master
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1594
  • Rating: +823/-5
  • The game in my avatar is bit.ly/p0zPWu
    • View Profile
Re: Can You Flood Fill?
« Reply #9 on: October 06, 2011, 10:44:50 pm »
I've done flood fills, though, it wasn't for painting or anything, but here's how I did it.

1. Make a buffer the same size as the number of pixels in your drawing area and fill it with 00's.
2. Take all the spaces eligible for filling and mark them with 01 on the new buffer.
3. Mark the space that was picked by the cursor with a 02.

This part is a loop:
4. Search the buffer for a 02
5. When you find it, check the 4/8 (depending on implementation) squares around the 2, if they are 1, mark them with 2, if they are 0, do nothing.
6. Mark the current square with a 03
7. Repeat this part

Flood fill is over when there are no more 02's left.
8. Find all of the 03's and fill them in back on the original picture


This technique should work as long as you don't have a massive buffer. But even if you did have a buffer the size of the screen, a full buffer for this would only require 6,144 bytes. Then, since this method only has values between 0 and 3, you could potentially store 4 pixels to a byte and get your size down to 1,536.

If space is not a problem, I also have an optimization to make this technique run faster. Checking the edges can slow the process down because you always have to figure out whether you need to check all 4 sides. This can be avoided by making your buffer 1 extra row wide and 2 extra rows tall. Let's say you have a 16x16 picture. If you make your buffer 17 pixels wide, you'll have 1 pixel boundary along both edges, this would mean you never have to check left/right boundaries. Then, if you give the buffer an extra row on the top and bottom, you can check the whole thing without fear of going over an edge. Just remember, you obviously don't want to perform your buffer operations on that 17th row, just skip it when checking for 02's.


Edit:
    After I wrote this, I wrote a tutorial on it. I've decided that instead of making posts like this, from now on I'll just write tutorials and link them ;D
« Last Edit: October 06, 2011, 11:16:15 pm by thepenguin77 »
zStart v1.3.013 9-20-2013 
All of my utilities
TI-Connect Help
You can build a statue out of either 1'x1' blocks or 12'x12' blocks. The 1'x1' blocks will take a lot longer, but the final product is worth it.
       -Runer112

Offline LincolnB

  • Check It Out Now
  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1115
  • Rating: +125/-4
  • By Hackers For Hackers
    • View Profile
Re: Can You Flood Fill?
« Reply #10 on: October 07, 2011, 10:21:23 am »
Hey, great, it works perfect. Except one thing - it's so slow that's faster just to fill in the pixels by hand...I'll post some code in a bit and maybe you guys can help me out?
Completed Projects:
   >> Spacky Emprise   >> Spacky 2 - Beta   >> Fantastic Sam
   >> An Exercise In Futility   >> GeoCore

My Current Projects:

Projects in Development:
In Medias Res - Contest Entry

Talk to me if you need help with Axe coding.


Spoiler For Bragging Rights:
Not much yet, hopefully this section will grow soon with time (and more contests)