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

enter image description here

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):

enter image description here

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?

  • \$\begingroup\$ Is that what you want? To have each space connected to the nearest space in the same area? \$\endgroup\$ – wolfdawn Mar 13 '14 at 8:09
  • \$\begingroup\$ Why not tunnel along an arbitrary line, not just horizontal/vertical lines? \$\endgroup\$ – user1095108 Mar 13 '14 at 9:06
  • \$\begingroup\$ @ArthurWulfWhite I want the whole map to be connected. Nearest space is a bit complicated (I don't track perimeter tiles yet). \$\endgroup\$ – ashes999 Mar 13 '14 at 10:41
  • 1
    \$\begingroup\$ Side note: switch to Linux, where there are nice terminals and use color! That's besides all the goodies that come for a programmer in a unix-based environement! \$\endgroup\$ – Shahbaz Mar 13 '14 at 10:58
  • \$\begingroup\$ @Shahbaz I primarily use Linux (at least for game dev). I'll update my screenshots with the (imo, nicer) Linux versions as soon as I figure out VirtualBox clipboard integration ... \$\endgroup\$ – ashes999 Mar 13 '14 at 11:21

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.
  • \$\begingroup\$ You may want to ask some questions about this if you don't have a CS background but generally you are looking for the real shortest path between rooms (that aren't connected [specifically looking through walls]) and once you find a path, clearing it up (removing walls) and then identifying them (the two new connected rooms) as the same set and moving on to connect the growing main area with all disjoint rooms by repeating the process with Dijkstra multiple times. \$\endgroup\$ – wolfdawn Mar 13 '14 at 8:29
  • \$\begingroup\$ I do have a CS background. The secret sauce here is using Dijkstra (or maybe A*) to traverse the wall cells. Very interesting idea; thanks, I'll try it. \$\endgroup\$ – ashes999 Mar 13 '14 at 10:46

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.

  • 1
    \$\begingroup\$ I see what you are doing but if you don't stop the bfs and restart only from the current outer walls of the perimeter it doesn't guarantee that the shortest paths will be taken between open areas. Other than that it should work pretty much the same and simplify the solution and it's complexity. \$\endgroup\$ – wolfdawn Mar 13 '14 at 8:56
  • \$\begingroup\$ well, it does guarantee the shortest path. And even if I'm making any mistake (that I really doubt), the paths generated will be near optimal. \$\endgroup\$ – Ali1S232 Mar 13 '14 at 9:13

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;

            if ( dx > dy )
                cumul = dx >> 1;
                for ( i = 1 ; i <= dx ; ++i )
                    x += xinc;
                    cumul += dy;
                    if (cumul >= dx)
                        cumul -= dx;
                        y += yinc;
                cumul = dy >> 1;
                for ( i = 1 ; i <= dy ; ++i )
                    y += yinc;
                    cumul += dx;
                    if ( cumul >= dy )
                        cumul -= dy;
                        x += xinc ;

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.

enter image description here

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

  • \$\begingroup\$ Yup, a minimum spanning tree would be optimal here. The other solutions are not as good. \$\endgroup\$ – wolfdawn Mar 14 '14 at 16:35

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.