Floofill

[Darren Grey]

Jo messaged me with a Floodfill question and I figure it's best to respond publicly so others can chime in with further ideas.

I read you going on about Flood Fill both here and on your blog. Do you have any links talking about how it works? I'd love to be able to find the dead ends in my dungeon builder and fill them with cool things, with locked doors.

Well, here's some initial info on floodfill:

http://roguebasin.roguelikedevelopment.org/index.php?title=FloodFill#How_do_you_make_sure_all_your_rooms_and_passages_are_reachable.3F

That's for ensuring connectivity, but it can be stretched beyond that.  The basic idea is simple - keep recursively marking squares as connected till you run out of unconnected squares you can reach.

Now if you want to do the more interesting heightmap stuff then instead of simply marking squares 0 or 1 for connected/unconnected, you give numbers higher than 1 the further they are from the entrance.  So every tile starts at zero.  The starting stairs get marked as 1.  The tiles beside the stairs are 2.  You keep spreading, marking every next square as 1 higher than the square it's connected to.  Thus you end up with a heightmap.  The squares in the dungeon with the highest numbers are the furthest from the starting stairs.  Here are some places to put interesting content.  Room dead ends tend to be in these maxima.  The combination of a room with a high height value + only one entrance door implies that you should try to connect it to another room nearby.  You may also wish to put the exit stairs at one of these further locations.

Another technique for finding dead-ends is to look for squares which have only 1 neighbour floor.  These are corridor ends.  Either put something in this place (maybe dig out a room, or have a treasure chest that summons monsters) or fill in the whole corridor (fill it and then keep filling adjacent floors that have only one neighbour floor).

Always solvable lock/key puzzles is another application of floodfill.  There's lots of approaches, but the basic idea is to use the floodfill to make sure that the key item is placed on a tile connected to the entrance stairs.  Thus when doing the floodfill you make it not able to cross the lock location (treating it like a wall).  It doesn't have to be a literal key and locked door of course - the lock could be a river of lava and the key boots of levitation.  How you choose which areas to lock off is up to you, though of course with floodfill you can ensure that the lock you place really does segregate that whole area from the stairs - a good idea with many of these is to segregate an area from both sets of stairs, so the whole puzzle can be bypassed if the player can't find the key item.

[Darren Grey]

And the title should be "Floodfill" not "Floofill", dagnabbit 

[naughty]

The point you made about more than just 0 and 1 reminded me of Brain Walker's (of Brogue fame) article about The Incredible Power of Dijkstra Maps. Although the algorithm mentioned at the top of the article isn't very optimal at all.

[Z]

You need something a bit more complicated than the algorithm in the article if you want to calculate the distances correctly (you need breadth first search, not depth first search -- otherwise the numbers you calculate will not be the shortest distances).

[Darren Grey]

Optimisation and absolute correctness aren't all that important though    Heck, you can throw some randomness into the whole thing just to make sure it can't lead to easily gameable situations.

[Z]

Sure, but by adding distance calculation to the algorithm from the article in the simplest way, like this

Code: [Select]

void FloodFill(int x, int y, int d)
{
  if ((Dungeon[x][y].Content == FLOOR) && (Dungeon[x][y].Flags == 0))
    Dungeon[x][y].Flags = d;
  else
    return;
  FloodFill(x+1, y, d+1);
  FloodFill(x-1, y, d+1);
  FloodFill(x, y+1, d+1);
  FloodFill(x, y-1, d+1);
}
you get something which is usually very far from correctness:

Code: [Select]

S..    123
.#. -> 8#4
...    765


Code: [Select]

S......
.......
....... -> this will generate a path from S to E which goes through all the dots
.......
.......
E......

Although stair placement might be one of these situations where incorrect algorithms give better results

[Darren Grey]

Wouldn't the square below S be 2 instead of 8? So:

123
2#4
345

[Z]

IMO the recursion goes as follows (with some irrelevant calls removed):

Code: [Select]

FloodFill(1,1,1)
  FloodFill(2,1,2)
    FloodFill(3,1,3)
      FloodFill(3,2,4)
        FloodFill(3,3,5)
          FloodFill(2,3,6)
            FloodFill(1,3,7)
              FloodFill(1,2,8)
                FloodFill(1,1,9)
  FloodFill(1,2,2)

FloodFill(1,1) will execute FloodFill(1,2) only after FloodFill(2,1) has performed the whole cycle.

[Darren Grey]

Ah, good point! The beauteous recursion has its flaws...

[guest509]

  Hey thanks Darren. I'll check it out.

  Recursion huh? I should have guessed.

/golem/ I hates recursion. Hates iiiiiit! /golem/

[kraflab]

Just don't use recursion if you don't want to.  You could instead use a loop and add the tiles you want to FloodFill into a queue, where you always act on the earliest added piece.  (This also automatically means you act on the closest tiles first)

[guest509]

  That will definitely be my method.

  It may seem as if I'm a bit of a quitter, but I gave up on incursion in the 90's. I really like to be able to visualize what's going on...

  I had the same problem with infinity in calculus. I understood the process to get to the answer, a sort of cut and paste parrot mode of doing math, but I knew that if I couldn't understand it conceptually I'd make a shit engineer.

  Then came the change to history which led to flawless grades, accolades from the academic community and eventually a doctorate in law...and finally to my frequently repeated phrase...

"Sometimes it's not how smart you are, it's just how your brain works."

  Hurray for tangents. 

[Krice]

I have serious problems with math, since I'm actually a pure artist myself. However you can do floodfill without recursion and it's such a simple process even I can understand it. It goes like this: you start with a seed number 1 from the origin. Then check the area (usually the level) for that seed number. If you find it, check four main directions around it and if the tile is floor (or any passable tile) without a seed number, set it to seed+1. Next time check all seeds 2, etc.

[NON]

Then check the area (usually the level) for that seed number [...] Next time check all seeds 2, etc.

I don't think you should iterate over the map to find cells with a certain seed number. You'll get a faster algorithm if you store the added cells to a queue, then remove them once they've been used as origins themselves.

As mentioned by Jo, always acting on the earliest cells gives you breadth first search:

[...] add the tiles you want to FloodFill into a queue, where you always act on the earliest added piece.  (This also automatically means you act on the closest tiles first)

Which you'll need for A* pathfinding, finding furthest cells etc.

[naughty]

You can fix the recursive version to make distance/height/Dijkstra maps quite easily though:

Code: [Select]

void DistanceFillAux(int x, int y, int d)
{
  if ((Dungeon[x][y].Content == FLOOR) && (Dungeon[x][y].Depth > d))
    Dungeon[x][y].Depth = d;
  else
    return;
  DistanceFillAux(x+1, y, d+1);
  DistanceFillAux(x-1, y, d+1);
  DistanceFillAux(x, y+1, d+1);
  DistanceFillAux(x, y-1, d+1);
}

void DistanceFill(int x, int y)
{
  // First we need to set all the tiles to the furthest away they can be.
  for (int dx=0; dx < DUNGEON_WIDTH; ++dx)
  {
    for (int dy=0; dy < DUNGEON_HEIGHT; ++dy)
    {
      Dungeon[dx][dy].Depth = INT_MAX;
    }
  }

  DistanceFillAux(x, y, 0);
}

The important changes are setting the Depth to INT_MAX at the start and using a > comparison on the Depth in the DistanceFillAux() test.

It's also easy (but a bit tedious to write) to change the above code to do distance maps from groups of tiles instead of just a single tile. Then you can use it like Brogue does to show a warning when your levitation potion is going to run out while you are over lava.