How can I detect "rooms" in a 2D side scrolling game?

Question

I'm looking to create a system that recognizes certain types of buildings and rooms you can create in game, like how Terraria detects "residences." In that game, a house can be constructed in a tile-based world by constructing a zone of blocks satisfying a set of conditions:

1. The zone is completely insulated from the "outside" by player-placed blocks.
2. The zone can fit a 5x7 rectangle.
3. there is at least one table, one light source, and chair in the enclosed area.
4. There is a door leading out from the zone.
5. Terraria has both a foreground and background tile layer. The entire background of the zone must be filled with player-placed blocks.

How can I efficiently detect when a player has constructed a suitably-sized area, and how can I efficiently check that the area contains all the required furnitture/components?

Example of an interior zone that satisfies all the housing requirements:

Answer 1

I'm not familiar with Terraria, but that can be easily done using a flood-fill algorithm.

Instead of pixel, you check the tiles, and for each tile checked, you evaluate if the algorithm can proceed checking other tiles, while storing in an array or list which objects are found during the process.

The algorithm starts at the tile where the character is at. You can start each 1 second, 2... it's a matter of tweaking to find the best interval.

It's also a good idea to prevent the algorithm to run for too long, which can be accomplished by limiting the number of tiles that the algorithm can run per run, otherwise your algorithm will cause long lags when the character is in an open area.

Edit

As stated in the comments, you can use other approaches on when to start the algorithm, such as when the player change a tile, or the tiles having an am I modified? variable that, if true, start the algorithm. However, you must be careful with this approach:

• What if a tile that is part of the room, but not a tile that your character is at, is modified? Maybe the tile was changed by other player, or an environment event, or the life-time of the tile ended. Your character will be unaware of the modification and won't execute the algorithm to detect the updated room, an error-prone situation.

You could implement some sort of approach to detect these modifications on tiles that your character is not at, but executing the algorithm on intervals is the simplest approach, and less error-prone. Just make sure to not execute flood-fill on every frame.

End of edit

Answer 2

Like @Ferreira da Selva said, try the flood fill algorithm. Though, you can use a few different criteria when running the algorithm to determine whether it is enclosed.

For example, for each tile you check if there is a background tile, and if there isn't, then you know that it isn't enclosed. Or you could have it perform a deferred execution by separating it over a number of frames, thus lightening the load on the processor and reducing lag. Or you could create a room size limit that the player would have to adhere to.

Using a combination of these would allow you to do it more efficiently and for effectively.

Answer 3

There are 2 hard problems in computer science. Naming things, cache invalidation and off-by-one errors.

This is a cache invalidation problem.

If you have a record of "is this inside", whenever a block is placed or removed it is pretty easy to update it and its region via a flood fill.

To optimize this you may want to have a set of tiers of "insideness".

A "cell" is a region surrounded by player-placed blocks (up to a certain size).

A "room" is a cell with background tiles.

"Inside" is a room with a door, a light and a chair.

When you place a player-placed foreground block, do a clockwise/counterclockwise walk to see if a new cell is formed. When you remove a player-placed foreground block, examine if it breaks any cells -- if so, see if a new cell is formed by merging the two.

When a new cell is formed or unformed, check for it being a room or an inside.

Cells can keep track of how many background tiles they need to be a room. Then a simple count when a cell is formed, a background tile is added or removed from the cell, can determine if it is a room.

Similarly, Cells can keep track of how many chairs and light sources (and in fact objects of all kinds) are within them. Then the inside check is trivial.

A count of entrances can also be done.

---

So we augment the map with "cells". When tiles are added or removed we check the cell of the location, and increment/decrement the count in the cell.

Use clockwise/counterclockwise walking to define the interior and exterior of a cell when a foreground block is added or removed. As the size of cells is limited, this walk will take a bounded number of steps.

As a bonus, you now have a cheap way to talk about "opulant" rooms, or "room is blessed by a holy fountain", or anything else about a room, as rooms have a count of each object type within them. (Or, as rooms are bounded in size, just do an iteration; this removes a cache).

Each location is in at most one cell, so you can store the cell-id of each location on the main map.

Answer 4

When using the flood fill algorithm, make also a variable, that will increment with each tile checked, so if it is higher than 35 (7*5, the max size of the room) it just stops checking!