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

Flood-fill algorithm.

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.

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 [][]?

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.

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.

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"}

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.

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.

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.

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

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.

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