# Computational Geometry Algorithms to Determine Rooms in a Dungeon (or a Building)

This topic is 2105 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I am currently using a Unity3D plugin to generate random dungeons (here: https://www.assetstore.unity3d.com/#/content/10250). After the generator finishes its work, it gives me access to the generated room tiles not the rooms themselves. The room tile are the small parts that are glued together to create the rooms and corridors of the dungeon.

This is a screenshot that explains what I am saying: http://postimg.org/image/f3to0unex/full/. As you can see the selected "RoomPart" is just a single tile of the room.

What I am looking for is an algorithm to outline or separate rooms as whole units.

Are there any computational geometry algorithms that can assist me to achieve what I want?

##### Share on other sites

The first step for solving this problem is defining the term 'room'.

Anyways:

Assuming it's not possible to do the grouping yourself in the editor, because you generate dungeons at runtime, I'd advice you to ask

the developer of this plugin. It looks like the dungeons are glued together from predefinied pieced anyways, so ask him to include

triggers for the 'glue points'. After all, you paid a lot of money for this :)

##### Share on other sites

Well unfortunately I contacted them and their design wasn't built to support such functionality. Actually I have already made some modifications and tweaking to the plugin code so as to make it conform to my needs. So I guess I'll continue with that path and try to do this on my own.

A room to me is a unit surrounded by walls, stairs, and doors. It doesn't have to be square or rectangular shape.

Since the rooms are composed of tiles or small parts called RoomParts, I am thinking of using Union-Find and Dynamic Graph Connectivity algorithms to find the connected components in the dungeon which are in my case the rooms.

##### Share on other sites

Can't you just do a flood fill in every unfilled tile, and stop flooding if your flood fill would pass through a door/wall/stairwell. Start flood filling in any tile, flood fill with room ID = 1. When that flood fill runs out of tiles, get the next unfilled tile, and flood fill with ID = 2.

That assumes that doors/walls/stairs are boundaries of tiles though... you have to be a bit cleverer if that isn't the case (you can have more than 1 ID per tile then).

EDIT: This also needs the map to be enclosed, i.e. no open edges where the flood fill can escape from. EDIT2: You also need to know the connectivity of the tiles. If you don't know this you can preprocess to find tile edges (faces in 3d) which are shared.

##### Share on other sites

Can't you just do a flood fill in every unfilled tile, and stop flooding if your flood fill would pass through a door/wall/stairwell. Start flood filling in any tile, flood fill with room ID = 1. When that flood fill runs out of tiles, get the next unfilled tile, and flood fill with ID = 2.

That assumes that doors/walls/stairs are boundaries of tiles though... you have to be a bit cleverer if that isn't the case (you can have more than 1 ID per tile then).

EDIT: This also needs the map to be enclosed, i.e. no open edges where the flood fill can escape from.

Yeah, that's similar to union find. Or, to be more specific, as far as I know union-find is one of the steps involved to solve the flood-fill problem.

• 21
• 11
• 9
• 17
• 13