• Advertisement
Sign in to follow this  

Flood Fill Using Java Queue

This topic is 2300 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey, everyone! I have a fairly simple yet tricky (to me, being somewhat of a lower intermediate programmer) method I've implemented to accomplish a flood fill (basically filling a solid shape with color in a pseudo-recursive fashion, storing all points to be filled in queue and iterating through it until the whole shape has been filled). However, the queue, when run, continues to enqueue limitlessly, and in increments of 1, specifically, when it could be enqueueing between 1 and 4 entries per loop iteration.

Here is the method I've written to try and make this work:



// this method fills the dungeon walls with interior color using a queue to simulate recursion
private void boundaryFill(int x, int y)
{
// create queue of points that will store all the points to be filled
Queue<Point> queue = new LinkedList<Point>();

// start the fill at the passed point
queue.add(new Point(x, y));

// while the queue has members left in it...
while (!queue.isEmpty())
{
// take the nearest Point out of queue
Point p = queue.remove();

// bounds check and color check
if (p.x > 0 && p.x < width - 1 && p.y > 0 && p.y < height - 1)
{
setPixel(p.x, p.y, DUNGEON_INTERIOR);

// test left
if (getPixel(p.x - 1, p.y) == GROUND_COLOR)
{
queue.add(new Point(p.x - 1, p.y));
}
// test right
if (getPixel(p.x + 1, p.y) == GROUND_COLOR)
{
queue.add(new Point(p.x + 1, p.y));
}
// test up
if (getPixel(p.x, p.y - 1) == GROUND_COLOR)
{
queue.add(new Point(p.x, p.y - 1));
}
// test down
if (getPixel(p.x, p.y + 1) == GROUND_COLOR)
{
queue.add(new Point(p.x, p.y + 1));
}
}

System.out.println("Size of queue: " + queue.size());
}
}


Basically, the setPixel and getPixel methods set or retrieve a given pixel of a bitmap image I'm writing to. The algorithm must simply test each point it adds to the queue if all its neighbors are the color to be filled in, as opposed to being the border color of the solid shape (in this case, I'm filling in a dungeon's interior color). I want to fill every GROUND_COLOR pixel, and it will not add a given point neighboring the test pixel if that point is the dungeon's wall color, which is the only other color in the image it will find besides the ground color, so it's almost like filling any single-colored shape, albeit with a few more angles and whatnot, but given the algorithm, that shouldn't make a difference as far as I understand it.

Anyways, some help would be greatly appreciated. :] Thank you all very much!

Best regards,
Colton

EDIT/UPDATE: I ran a case that tested for 1,000, 10,000, and 20,000 maximum queue entries and found that it always fills the exact same amount in before stopping but continuing to add more entries. It's in the correct diamond shape, but I still do not know what is causing the filling to stop but the enqueueing to continue.

Share this post


Link to post
Share on other sites
Advertisement
Wow, I figured it out. I was forgetting to set the pixel for each added Point once it was added to the queue to the interior color, so it was filling the queue and basically putting off tons and tons of pixels to be tested later, from what I can understand of it. Thanks anyways, guys! :]

Share this post


Link to post
Share on other sites
I recommend using an interval (scanline) based filling algorithm instead. Pretty easy to write and much much faster :)

Share this post


Link to post
Share on other sites
Thanks for the tips and links, guys! I'll be sure to mess with it soon, once I get some other stuff related to the same class taken care of. Optimization seems to be half the battle.

Colton

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement