LÖVE

A Google search comes up with a few algorithms but are old and embedded in other projects.

I basically have a building with rooms (many tiles in each room) and need to know which room each time belongs to.

I'm thinking flood fill but I wouldn't actually paint or fill an area but use the same algorithm to 'paint' an invisible layer placed over the map (probably with numbers 1,2,3 etc to identify different rooms). To check which room cell X/Y is in then I check cell X/Y in the invisible layer to determine this.

Is this making sense? Am I thinking it right? I'm thinking it won't be hard to roll-my-own functions/modules in Love2D.

And how would you do the checking exactly?

Floodfill kinda implies pixels, i don't think that's the way you want to handle this;

since you just want to tell what room tiles are in, why not do one of two things:

1. use one (or more, potentially overlapping, if the rooms aren't rectangular) rectangles to denote a room; by this, i don't mean to draw them, just put them in a table with their top, left coordinates and their width and height; you can check against that with the tiles to see what "rooms" they are in.

2. store the room index or whatever inside the tiles - this is more direct, but more memory-heavy.

Flood fill is just means of traversing an area. While people think about it traversing pixels and changing colors I intend to traverse a collison map (tiles) and set values in that collision map.

The walls will be built by the player in any configuration they like with no guarantee they will be square/rectangle.

I do know the exterior is fixed and the interior is subject to change so I was going to start in one corner of the tiled map and 'crawl' across the tiles, bumping into walls recursively, and tracking each room as I go (like the above #2).

Silly?

I've used flood-fill for a similar purpose to this. I think it's the right approach for things like checking reachability in irregular rooms.

The simplest algorithm is the recursive one, but it uses a lot of stack and is quite inefficient.

• If the current pixel is not fillable or has been already filled, return. Coordinates out of range count as not fillable.
• Fill the pixel.
• Call recursively for the pixel above.
• Call recursively for the pixel below.
• Call recursively for the pixel to the left.
• Call recursively for the pixel to the right.

The fastest algorithm I know consists of having a set of coordinates where to fill. You start by adding the first pixel to the set. Then:

• If the set is empty, stop.
• Take a pixel out of the set. If it is not fillable or has already been filled, start again.
• Go left until you find a non-fillable pixel.
• For the first fillable pixel, check if the pixel above it is fillable. If so, add it to the set.
• Same with the pixel below.
• Fill the line from left to right, paying attention to the row above and below. Whenever you detect a transition from non-fillable to fillable on the pixels above or below, add the fillable one to the set.
• Repeat.

The set is typically a queue, but it's sometimes more efficient to have it as a stack, like in the example below.

Example implementations attached.

... or ... is there a way to use an actual flood fill on a layer or image or canvas or something magical but hidden so that I can inspect the hidden pixel colour and then know which room was clicked (for example)?

I mean, I was simply going to use the algorithm on my tile map but what if I used an actual copy of the tile map (hidden image) and did a real flood fill (hidden) without going to the bother of rolling my own tile map flood fill? I'm not sure if that is possible or even easier.

togFox wrote: ↑Tue Apr 06, 2021 1:27 pm ... or ... is there a way to use an actual flood fill on a layer or image or canvas or something magical but hidden so that I can inspect the hidden pixel colour and then know which room was clicked (for example)?

I mean, I was simply going to use the algorithm on my tile map but what if I used an actual copy of the tile map (hidden image) and did a real flood fill (hidden) without going to the bother of rolling my own tile map flood fill? I'm not sure if that is possible or even easier.

No idea what you mean exactly, but if it helps, I've made applications where I used an extra invisible layer to track which points were being filled by the algorithm, in order to not affect the original image. I don't think you need a copy of the map to do that. You would reflect that in the fillable() function, so that it checks both the map, for boundaries, and the extra layer, for pixels already filled.

I don't know how your map is organized. If each of your tiles is a table, you could even use a field of the table. If the tiles are just numbers, you could use a parallel table to hold the filled positions. Depending on the sparseness, it could even be a hash rather than an array or an image. The best approach depends on your organization.

It can be helpful to use the polygon as the room area. Going to the right to the first wall, then going down to the first vertex. Keep going and collect all vertices.

Will you design the tilemaps manually, with a tile editor? If so then I'd implement a 'tag' attribute so that you can tag tiles that belong to the same room when you're drawing them (ie set tag to "Room 1", start plotting tiles). This way no preprocessing is needed.

If the tilemaps are being generated by code then this gets more complex: how do you define what a room is? You need a walkable space delimited by walls, and a portal/door. You'd need some way to detect which walkable tiles are portals (like considering as a portal every corridor of 3 tiles or more in length and 1 walkable tile in width), that you then treat as wall tiles in your flood fill algorithm.
So find a way to detect portals / corridors and you can floodfill the separate rooms. This floodfill logic uses the tile array data, not the actual image pixels of course.