Friday 6 April 2012

Flood fill failure

It's obvious that the flood fill search fails to detect nearby double doors.


As a debug measure I made the filler paint lava tiles where it did visit. The result was kind of interesting. Looks like it's quitting after couple of tiles. It's possible that the algorithm is confusing me, because for me even simple algorithms are hard to understand or visualize.

2 comments:

  1. Floodfill is far from a simple algorithm. You've got a regression that can easily become infinite if not bounded properly, and just as commonly traverses more tiles than it needs to.

    I used floodfill in the Dance of Death and The Adventurer's Guild dungeon generators to ensure dungeon connectedness, and, from what I recall, it was the least efficient part of the entire process. On my current roguelike-like project, I've built Djistra maps for various uses (of which floodfill is a main component), and it seems to run more quickly, likely because of the less sparse maps.

    What does your algorithm look like?

    Ebyan "Nolithius" Alvarez-Buylla
    http://www.nolithius.com

    ReplyDelete
  2. It's a simple seed finder iterating the entire map. I was able to fix the bug. It was in the routine that was checking rules for filling. It was badly written code so bugs were a natural result of that.

    ReplyDelete