Connecting Circular Rooms

Question

My roguelike generates a number of circular rooms. I quite like the current results, which look something like this:

It's generated by carving out random circles in a filled space.

I have one main problem with it: several circles are completely unconnected. I cna't quite figure out what algorithm to use to connect them.

I tried "for each circle, find the nearest circle, and tunnel to its center (horizontally then vertically)," but I get something horrible instead (same map as above):

What seems to be the right fit is something like "for each self-enclosed space, find the nearest empty space and tunnel to it." That seems complexity-hard though (for each circular enclosed space, compute the distance to every other space) and will probably be slow (running on Ruby too)

Is there a simple solution to this problem?

Answer 1

Alright. There is a rather computationally inexpensive solution for this issue. First use Union Find to keep track of rooms that are not connected yet.

Each square will now belong to some set with a unique index.

1. When you create a circular room, merge all squares inside of it to the same set.
2. When you create a room that overlaps with another room, unify the two sets into one.
3. Once you are done, you should have a bunch of spaces, each connected space has it's own unique ID in the union find data structure.
4. Pick the largest open space (you need to keep track of the size of sets in union find).
5. Treat the map as a graph of nodes where each node is connect to it's left, right, up and down by an edge. If an edge leads to a wall, it costs (1), otherwise it costs epsilon 0.0001. All other rooms (empty spaces) will be connected to a virtual destination node with a free edge.
6. Use Dijkstra to find the shortest path from the current room space to the destination and clear that path by removing the walls in this path.
7. Now merge the sets (the joined rooms) and continue this process with Dijkstra.

Answer 2

Arthur's answer seems to solve your problem, but here is an easier approach:

1. start from from one of the empty cells.
2. using BFS algorithm, mark all the cells in that area.
3. add all the nodes visited in previous step to start list of new BFS algorithm, and using it explore through the walls until you find some other empty area not already visited
4. clear the path your second BFS took to reach the new area.
5. repeat process from step 2, until all the cells are visited.

note that in each repetition you just have to continue previous BFS. I mean restarting the algorithm from the beginning will only reduce your performance, and it won't generate any better results.

Answer 3

If you want a simpler solution still, since the rooms are simple and circular you could do this instead:

1. Pick one room at random.
2. Add it to the (currently empty) list of visited rooms.
3. Iterate over some data-structure that contain all unvisited rooms and find the closest unvisited room. If the distance between them is smaller than the sum of their radiuses then there is probably no reason to connect them but at any case "draw" a corridor with one non-straight line between their centers(I will describe the algorithm later).
4. Reiterate over all unvisted and find the one closest to one of the visited ones.
   • min [(xu-xv)^2 + (yu-yv)^2].
5. Connect the two rooms, add the new room to the visited, remove from the unvisited and repeat until all rooms are all visited successfully.

This should work find with a map that has less than a hundred rooms but could be improved in computational efficiency in many ways (that are irrelevant to the question).

To draw a non-straight line use the following pseudo algorithm:

The code was taken from here

       /**
        * Draw a line
        * 
        * @param x0     first point x coord
        * @param y0     first point y coord 
        * @param x1     second point x coord
        * @param y1     second point y coord
        * @param c      color (0xaarrvvbb)
        */
        public function line ( x0:int, y0:int, x1:int, y1:int, color:uint ):void
        {   
            var dx:int;
            var dy:int;
            var i:int;
            var xinc:int;
            var yinc:int;
            var cumul:int;
            var x:int;
            var y:int;
            x = x0;
            y = y0;
            dx = x1 - x0;
            dy = y1 - y0;
            xinc = ( dx > 0 ) ? 1 : -1;
            yinc = ( dy > 0 ) ? 1 : -1;
            dx = dx < 0 ? -dx : dx;
            dy = dy < 0 ? -dy : dy;
            setPixel32(x,y,color);

            if ( dx > dy )
            {
                cumul = dx >> 1;
                for ( i = 1 ; i <= dx ; ++i )
                {
                    x += xinc;
                    cumul += dy;
                    if (cumul >= dx)
                    {
                        cumul -= dx;
                        y += yinc;
                    }
                    setPixel32(x,y,color);
                }
            }else
            {
                cumul = dy >> 1;
                for ( i = 1 ; i <= dy ; ++i )
                {
                    y += yinc;
                    cumul += dx;
                    if ( cumul >= dy )
                    {
                        cumul -= dy;
                        x += xinc ;
                    }
                    setPixel32(x,y,color);
                }
            }
        }

Answer 4

Unfortunately, both of Arthur's solutions did not prove usable for me; it came down to a problem which is solvable, but didn't run fast enough (took an order of magnitude of seconds to run; I need something almost instantaneous.)

This is perhaps my fault, because I did not implement everything exactly as he suggested, but instead went for simpler code (over faster code).

That said, I found a simple solution which is fast to run and easy to code. The main steps are:

• Assume the "starting" room is not the biggest, but the room the player spawns in
• For every unconnected room, find the closest connected room (O(n^2))
• Create a tunnel connecting the two rooms

This is not a minimum spanning tree, so there are cases where the order matters -- I iterate rooms in the wrong order, and end up connecting them a longer way instead of a shorter way.

For my game and requirements, this worked. In the future, I may expand it by using a minimum spanning tree instead.

For posterity, here's the same floor generated with my solution.

You can see a snapshot of the core code on GitHub, starting here.