Temple of The Roguelike Forums
Development => Programming => Topic started by: Darren Grey on December 03, 2012, 12:56:07 PM
-
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.
-
And the title should be "Floodfill" not "Floofill", dagnabbit :P
-
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 (http://"http://roguebasin.roguelikedevelopment.org/index.php?title=The_Incredible_Power_of_Dijkstra_Maps"). Although the algorithm mentioned at the top of the article isn't very optimal at all.
-
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).
-
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.
-
Sure, but by adding distance calculation to the algorithm from the article in the simplest way, like this
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:
S.. 123
.#. -> 8#4
... 765
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 :)
-
Wouldn't the square below S be 2 instead of 8? So:
123
2#4
345
-
IMO the recursion goes as follows (with some irrelevant calls removed):
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.
-
Ah, good point! The beauteous recursion has its flaws...
-
Hey thanks Darren. I'll check it out.
Recursion huh? I should have guessed.
/golem/ I hates recursion. Hates iiiiiit! /golem/
-
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)
-
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. ;)
-
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.
-
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.
-
You can fix the recursive version to make distance/height/Dijkstra maps quite easily though:
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.
-
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.
What I do is to have the floodfiller take an array of blocking cells (bool) as argument, and another array to fill with values. That way, the floodfill doesn't "assume" anything about the use scenario. Anything in the program can set up any conditions they want.
I also have a collection of functions to build blocking arrays. For example, build an array for things blocking vision, or for things blocking a certain creature's movement, or for a movement type... consider other creatures as blocking or free, consider only adjacent creatures as blocking, etc.
-
You can fix the recursive version to make distance/height/Dijkstra maps quite easily though: [...]
This algorithm is correct, but you should change to the proper breadth-first search when the game starts running too slow (or if using inefficient algorithms is a shame for you).
-
Your Flood-Foo is strong.
-
This algorithm is correct, but you should change to the proper breadth-first search when the game starts running too slow (or if using inefficient algorithms is a shame for you).
I assume you mean the iterative rather than recursive implementation?
If so I totally agree with your point, a queue based and iterative solution would be faster. For my day job at a games company I would write the more optimal version. Similar logic applies to the original FloodFill() as well, it can be made a lot faster but requires more code and is trickier to understand.
I just wanted to show that changing FloodFill() to DistanceFill() isn't that scary and not too much work.
-
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.
Äh, it's too complex that way. But not a bad idea if you want to speed up the routine.
-
Äh, it's too complex that way. But not a bad idea if you want to speed up the routine.
Well it's one algorithm used in many places, so it makes sense to do it well. Then you afford to use it plenty in AI and level generation etc.
-
This is why I created all the dungeons in Red Rogue as images. Flash's BitmapData.fill runs at native speed, so it's faster than any algorithm you could possibly write in actionscript. Testing room connection was simply a matter of seeing if it had ended up a new colour.
http://www.robotacid.com/flash/red_rogue/mapping_demo/
I tried making a graph to help with the issue of gravity.
http://www.robotacid.com/flash/red_rogue/connections/
But what I didn't realise was that when the ladders are pushed out they can end up dropping into a new room - missing a drop and making an impossible to escape pit.
Solution? Double the size of the image and draw pixels on top of every surface and up every ladder. Then floodfill. BitmapData.getColorBoundsRect instantly reveals any detached surface.
Floodfill even let me do gate and key puzzles really quickly.
I'm really not looking forward to writing one when I start using a proper language.
-
I can't say if this is offtopic or not, but anyway...
In WitchavenRL I used a simple method for map generation that is basically to create random rooms, then create a door in each room and finally join each door with corridors using a pathfinding algorithm were walls are the walkable cells. This way I know every room is connected to each other because all doors are connected.
So, basically, using a pathfinding algorithn for each room against all other rooms could be a good method, and pretty fast IMO if you dont have thousand rooms.
-
This is why I created all the dungeons in Red Rogue as images. Flash's BitmapData.fill runs at native speed, so it's faster than any algorithm you could possibly write in actionscript. Testing room connection was simply a matter of seeing if it had ended up a new colour.
That's... quite hilarious :) I knew you used floodfill for some tricks in Red Rogue, but I didn't realise you did it like this!
-
Reminds me of the time when I have been playing DROD... There is a level which is a huge maze. I have solved this maze by opening the map in Paint and using its Flood Fill feature.