# Flood Fill Using Java Queue

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

## 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 on other sites
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 on other sites
I recommend using an interval (scanline) based filling algorithm instead. Pretty easy to write and much much faster

##### Share on other sites
might be worth trading points for just straight numbers... avoid a huge number of new points being created.

##### 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

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 15
• 21
• 21
• 11
• 9