Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Fill free shape with allegro?

This thread is locked; no one can reply to it. rss feed Print
Fill free shape with allegro?
TeachMeHowToPro
Member #15,892
February 2015

Hello. I'm making a paint program, simular to micrrosoft paint, using allegro 5.0.10. But I get stuck at one point when coding. I have NO IDEA how to implement the "Paint bucket" tool. I'm sure that most if you are familiar with the paint bucket in painting progams. You click somewhere and it changes the color of the adjacend pixels that contain the same color as the pixel that is clicked on with another color.

I have been thinking for a while now, tried many diferent ways. Some people told me to use pathfinding mechanics, but I still have no idea what to do/

Any help or code examples will be welcome

Chris Katko
Member #1,881
January 2002
avatar

Flood-fill algorithm.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

StevenVI
Member #562
July 2000
avatar

A naiive implementation would be a recursive algorithm that looked at the neighbors of each pixel and colored them if they were the same source color. Something like this pseudocode:

function fill(bmp, x, y, color) {
  oldColor = bmp[x][y];
  bmp[x][y] = color;

  if (x < bmp.width - 1 && bmp[x+1][y] == oldColor) {
    fill(bmp, x+1, y, color);
  }
  if (x > 0 && bmp[x-1][y] == oldColor) {
    fill(bmp, x-1, y, color);
  }
  // similarly for y
}

However, you won't get very good performance out of it, especially if you're using video bitmaps. See al_lock_bitmap for more details.

In terms of a more efficient algorithm, might want to try Google. Looks like there's a discussion of flood fill algorithms on Wikipedia, too.

__________________________________________________
Skoobalon Software
[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]

TeachMeHowToPro
Member #15,892
February 2015

Thanks.
StevenIV: I will test this algorithm, but the thing that keeps bugging me is that you have included a color variable, which you do not write in when you cll again fill(). ( You enter the bmp,x and y but ignore/miss the color). Is this a mistake from your side or I just need to complete your code ( because currently it's not working code ).

Also when you use bmp[x][y], did you mean using al_get_pixel, or you can access pixel data with these [][]?

StevenVI
Member #562
July 2000
avatar

the thing that keeps bugging me is that you have included a color variable, which you do not write in when you cll again fill(). ( You enter the bmp,x and y but ignore/miss the color). Is this a mistake from your side

Yeah, that was a mistake on my part -- just updated it above. And as I said, it's pseudocode, so it's not meant to be copied verbatim, but rather just to demonstrate the algorithm. I don't actually use Allegro 5, so I have no idea what functions are available or how to interact with ALLEGRO_BITMAP objects. 8-)

Do check out the Wikipedia page that Chris and I referenced. I only skimmed it, but I believe it has more details on how to optimize the algorithm, and the references will probably be helpful.

__________________________________________________
Skoobalon Software
[ Lander! v2.5 ] [ Zonic the Hog v1.1 ] [ Raid 2 v1.0 ]

Chris Katko
Member #1,881
January 2002
avatar

StevenVI said:

I only skimmed it, but I believe it has more details on how to optimize the algorithm, and the references will probably be helpful.

It's got everything! I used it last year to build a grid atmosphere/pressure simulator to test an idea for "lazy" or "lagged" logic updating. Basically, you start at something important, like a pump, and recursively spawn out "seekers" that follow/fill all hallways and rooms and if they can't spawn any more, they die. It's just a flood fill, but the game logic happens inbetween flood fill steps allowing multiple fills to occur at the same time, each representing game state with newer state taking precedence over older state.

{"name":"e8Q4rt9.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164.png","w":600,"h":570,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/1\/e\/1e6ad0dd62739291ea869175d3085164"}e8Q4rt9.png

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

TeachMeHowToPro
Member #15,892
February 2015

Thank you so much for the help!
I got what I need and used the flood-fill algorithm. It's pretty slow even after locking the bitmap, but it's better than not working at least.

Chris Katko
Member #1,881
January 2002
avatar

You could make sure the bitmap is a memory bitmap so that per pixel access is really fast. OR, you could move the image to a memory bitmap, do the flood fill, and then move it back to the GPU. A couple block transfers might be a lot faster than lots of per-pixel access to a video bitmap.

-----sig:
“Programs should be written for people to read, and only incidentally for machines to execute.” - Structure and Interpretation of Computer Programs
"Political Correctness is fascism disguised as manners" --George Carlin

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

OR, you could move the image to a memory bitmap, do the flood fill, and then move it back to the GPU.

This is essentially what al_lock_bitmap does with video bitmaps. It has to create a buffer to store the changes into and then re-upload the pixel data to the texture. If you use ALLEGRO_LOCK_WRITE_ONLY it doesn't have to copy the video bitmap data to the buffer first, which slows things down.

Thomas Fjellstrom
Member #476
June 2000
avatar

If you use ALLEGRO_LOCK_WRITE_ONLY it doesn't have to copy the video bitmap data to the buffer first, which slows things down.

True. though that is of dubious use in the case where you want to flood fill existing areas in a bitmap.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Edgar Reynaldo
Major Reynaldo
May 2007
avatar

Right you are. Didn't really consider that.

If you use ALLEGRO_NO_PRESERVE_TEXTURE (and a sane graphics lib like OpenGL that doesn't have severe cases of amnesia (cough.. DX)), does that speed up the pipeline? You could implement a copy on write scheme, both ways, from video to memory and from memory to video. Only update the video copy when a paint action is performed. Then you could still use ALLEGRO_LOCK_WRITE_ONLY, as you would be copying a memory buffer to a video buffer and then blitting the video buffer onto the backbuffer. I wonder what fps that would get, uploading on each paint action.

Thomas Fjellstrom
Member #476
June 2000
avatar

If you use ALLEGRO_NO_PRESERVE_TEXTURE (and a sane graphics lib like OpenGL that doesn't have severe cases of amnesia (cough.. DX)), does that speed up the pipeline?

That should keep allegro from trying to save the textures when ever something changes yes.

--
Thomas Fjellstrom - [website] - [email] - [Allegro Wiki] - [Allegro TODO]
"If you can't think of a better solution, don't try to make a better solution." -- weapon_S
"The less evidence we have for what we believe is certain, the more violently we defend beliefs against those who don't agree" -- https://twitter.com/neiltyson/status/592870205409353730

Go to: