24
\$\begingroup\$

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:

enter image description here

\$\endgroup\$
  • 5
    \$\begingroup\$ Could you elaborate? What do you mean by "types of builds" and what is a "residence" in Terraria? Keep in mind that not everyone has played that game, also focus on one question if you want people to help, and make sure that question has a definite answer (not opinions) \$\endgroup\$ – TomTsagk Jul 23 '18 at 23:05
  • 1
    \$\begingroup\$ With types I mean different components/tiles used. My question is solved below. I will try to ellaborate more and be more specific on future questions, thanks for the help. \$\endgroup\$ – Bernardo Becker Jul 24 '18 at 3:03
  • 1
    \$\begingroup\$ As an aside, ensure that there is a difference between a room and a residence. Your bullet list suggests that you see them as the same definition. Using Terraria as an example, enemies don't spawn in rooms, even if they are not eligible as residences (e.g. missing a table, or only 5x5 in dimension) \$\endgroup\$ – Flater Jul 24 '18 at 10:09
37
\$\begingroup\$

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

\$\endgroup\$
  • 9
    \$\begingroup\$ Why not flood-fill only among "player-placed block" tiles? This could prevent or reduce infinite flood-fill in open areas (as long as caves/mansions aren't filled with "player-placed blocks"). \$\endgroup\$ – jimbo1qaz Jul 24 '18 at 4:51
  • 20
    \$\begingroup\$ Why would you run this on a fixed interval? Surely you can just run it when a block is placed (or destroyed, if applicable, and both of those cases can probably be done in amortized constant time per block) or when loading a particular part of the map, and then store the result from there. \$\endgroup\$ – NotThatGuy Jul 24 '18 at 6:48
  • 3
    \$\begingroup\$ @immibis: I'm pretty sure that Terraria doesn't require you to change the floor. I also wouldn't expect a game to change it's room recognizing behavior based on who placed the tile. What if I e.g. build a room adjacent to a cliff? \$\endgroup\$ – Flater Jul 24 '18 at 10:05
  • 3
    \$\begingroup\$ Terraria requires one to put background walls and will not form a house with natural background dirt/rock. It really does check only player-placed blocks. \$\endgroup\$ – loa_in_ Jul 24 '18 at 10:17
  • 3
    \$\begingroup\$ To save CPU, I only would run the algorithm on block change and then store the state for each block. With this, it's a simple isRoom() \$\endgroup\$ – Herr Derb Jul 24 '18 at 11:07
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 7*5 is the minimum size rectangle that must fit inside the room \$\endgroup\$ – Rick Jul 25 '18 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.