I'm trying to create a small roguelike and went as far as random generating rooms and corridors. Each room is an instanced object and contain an arraylist of the others rooms connected by a corridor.

I can single out unconnected rooms but how can I know the rooms that are connected only to each other but not to most of the others, forming an island?

to illustrated better the problem here is an image from the console on a bogged level. Rooms 5 and 6 are connected only to each other. What algorithm can I use to detect that?

enter image description here

  • Problem with using the image? That pastebin link will only last a month. – MichaelHouse Oct 17 '12 at 21:19
  • Yeah, I didn't quite understand at first what you did here. Sorry, I reverted your change. – petervaz Oct 17 '12 at 21:22
  • 1
    Why don't you construct it so that there can't be any separate rooms in the first place? Or do you want there to be isolated sets? – AlbeyAmakiir Oct 17 '12 at 22:03
  • @AlbeyAmakiir as I said on another comment below, I generate the rooms separately by trial and error until I fill the map, only then I run a routine to connect, and then will run another to connect those islands. I know it is probably too convoluted but couldn't figure another way. – petervaz Oct 17 '12 at 23:01
up vote 14 down vote accepted

Start with a full list of rooms. Pick a starting room. Navigate from that room to all connected rooms. For each room you visit, remove it from the list of rooms and add it to a list A. Once you've visited all your connections, any rooms remaining on the list are not connected to the starting room or any of the rooms on list A.

You can then continue by selecting a room from what remains of the full list, and navigating again. This time adding to list B. Continue this process until you have no more rooms on the original list. You now have lists of all the connected room sets.

Problems like this are easily adapted to graph theory problems. For example, the problem you've described above directly relates to connectivity.

  • 1
    any search tree algorithm should work. That or you could change your generation algorithm to avoid this problem. If you change your generation algorithm just generate a random number of rooms attached to your start room, then a random number of rooms attached to each of the following, then you can add some random connections between existing rooms to spice things up a bit with shortcuts and such. Personally I would just do a search tree algorithm though. – Benjamin Danger Johnson Oct 17 '12 at 21:08
  • That's very logical. I must be tired. Thanks for your help. Will accept as soon as it allows. – petervaz Oct 17 '12 at 21:10
  • @BenjaminDangerJohnson Your comment seems more appropriate for the question and not this answer. – MichaelHouse Oct 17 '12 at 21:10
  • @petervaz No problem. I guess my CS degree has its uses after all. – MichaelHouse Oct 17 '12 at 21:12
  • @BenjaminDangerJohnson my generating algorithm is just placing random rooms until fill the space and looking for connections later. =P Will try to fix the connections before resorting to change the creation. – petervaz Oct 17 '12 at 21:13

Your collection of rooms is essentially a graph, and your problem boils down to finding connected components ("islands") in that graph.

A simple way to find connected components is to do BFS (breadth-first search) from each vertex. Doing BFS from a vertex A will get you all the vertices in the connected component which vertex A belongs to.

So, basically, you start with an arbitrary vertex, do a BFS and mark each encountered vertex as a member of the 1st "island". Then you move on to the next unmarked vertex and do a BFS again, this time labeling encountered vertices as members of the 2nd "island", and so on.

You can picture the rooms as vertices on a directed graph. By doing that, you will be able to apply well known algorithms to solve your problem.

Dijkstra's algorithm, for example, produces a shortest path tree for a given starting vertex on a graph. This tree will contain all the reachable vertices from the starting point. You can then deduce that the vertices not present in the tree are part of other islands. You can apply the algorithm to these vertices in order to get trees representing every island.

  • 1
    Even an undirected graph would do it... except you have one way only routes. – Aron_dc Oct 19 '12 at 16:24
  • @Aron_dc, you are right, you can picture the rooms as vertices on an undirected graph and get similar results by using Kruskal's algorithm. I just suggested picturing it as directed graphs because of the way petervaz represented the connections - i.e., Room 1 > 3 – Asakeron Oct 19 '12 at 17:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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