Floofill

[NON]

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.

[Z]

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).

[guest509]

  Your Flood-Foo is strong.

[naughty]

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.

[Krice]

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.

[NON]

Ä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.

[st33d]

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.

[SomeGuy]

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.

[Darren Grey]

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!

[Z]

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.