Author Topic: Generating well-connected maps  (Read 11332 times)

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Generating well-connected maps
« on: February 21, 2014, 03:17:38 PM »
A lot of roguelikes, especially 7DRLs using libtcod's built-in BSP dungeon generator, have very badly connected maps. Typically the rooms will be connected in a tree-like structure. This has some unfortunate consequences:
  • There's only one route between two locations.
  • Fully exploring the level means backtracking a lot.
  • A hazard blocking one corridor can interdict half of the level.
Some very rushed roguelikes even have dungeons with disconnected sections; the disadvantages are clear enough in that case.

I've written a small Python module that alters maps to make them 2-connected. That means:
  • Blocking one tile can never prevent access to any region of the level.
  • Explorers can clear a level much more efficiently than in a basic BSP dungeon.
  • There are more tactical options, especilally when fleeing or avoiding a monster.

The code (public domain) can be found at https://www.dropbox.com/s/kjwnidb3h6q8nc0/biconnect.py. You can test it online at http://ideone.com/9B12Dn. Here's an example use case:
Code: [Select]
import biconnect
my_width = 80
my_height = 40
# The module still uses some ugly global variables.
# These can be factored out into a class.
biconnect.width = my_width
biconnect.height = my_height
# Format: list of lists of bools
# True: Floor, False: Wall
# eg. [[False,False],[True,False]]
my_map = [[False]*my_width for y in range(my_height)]
# ... add some floor tiles ...
# or generate a random selection of disconnected rooms
my_map = biconnect.disconnected_map(12)
biconnected.render(my_map)
my_map = biconnect.biconnected_map(my_map)
biconnected.render(my_map)

Here's some sample output (with the source maps for reference). I used plain rectangular rooms, but the algorithm can handle any input map with more than one floor tile.
Code: [Select]
################################################################################
################################################################################
################################################################################
################################################################################
###########........#################################################.......#####
###########........#####################......######################.......#####
###########........#####################......######################.......#####
###########........###....#####...######......######################.......#####
###########........###....#####...######......######################.......#####
###########........###....#####...######......######################.......#####
###########........###....##############......######################.......#####
####################........###########.......######################.......#####
####################........###########.......###################........#######
#################...........###########.......###################........#######
#################..........######################################........#######
#################..........######################################........#######
#################..........######################################........#######
#################..........######################################........#######
#################.....########################....##########################....
########################........##############.......#######################....
########################........##############.......#######################....
########################........##############.......#######################....
########################........##############.......#######################....
########################............##########......########################....
########################............##########......########################....
########################............############################################
########################............############################################
############################........###############......#######################
############################........###############......#######################
############################........###############......#######################
###################################################......#######################
###################################################......#######################
###################################################......#######################
###################################################......#######################
###################################################......#######################
#############........###########################################################
#############........###########################################################
#############........########################################.....##############
#############........########################################.....##############
#############........########################################.....##############


################################################################################
################################################################################
################################################################################
################################################################################
###########........#################################################.......#####
###########........#####################......######################.......#####
###########........#####################......######################.......#####
###########........###....#####...######......######################.......#####
###########........................................................#............
###########........###....#####...######......####################.#.......####.
###########........###....##############......####################.#.......####.
############.#######........###########.......####################.#.......####.
############.#######........###########.......###################........######.
############.####...........###########.......###################........######.
############.####..........######################################........######.
############.####..........######################################........######.
############.####..........######################################........######.
############.####..........######################################........######.
############.####.....########################....##########################....
############.###########........##############.......#######################....
############.###########........##############.......#######################....
############.###########........##############.......#######################....
############.###########........##############.......#######################....
############.######.................................########################....
############.######.####............##########..................................
############.######.####............###########################.################
############.######.####........................................################
############.######.########........###############......######.################
############.######.########........###############......######.################
############.######.########........###############......######.################
############.######.###############################......######.################
############.............................................######.################
###################.###############################......######.################
###################.###############################......######.################
###################.###############################......######.################
#############........##########################################.################
#############........##########################################.################
#############........########################################.....##############
#############........########################################.....##############
#############.....................................................##############

################################################################################
################################################################################
###########################################################################...##
###########################################################################...##
###########################################################################...##
###########################################################################...##
################################################################################
######..........#################...############################################
######..........#################...######################.......###############
######..........#################...######################.......###############
######..........#################...######################.......###############
######..........#################...######################.......###############
######..........#################...######################.......#######...#####
########........##########################################.......#######...#####
#############################################...##########.......#######...#...#
#############################################...##########.......#######...#...#
################################.........####...########################...#...#
################################.........###################################...#
################################............################################...#
###################################.........#......#########################...#
###################################.........#......########....#############...#
#########################################...#......########....#################
#############################################......########....#################
###########################################################....#################
###########################################################....#################
################################################################################
#########################################################......#################
#########################################################......#################
#########################################################......#################
#########################################################........###############
####################.....################################........###############
####################.....################################........####.......####
####################.....############################################........###
#####################################################################........###
#####################################################################........###
#####################################################################........###
#####################################################################........###
#####################################################################........###
########################################################################.....###
########################################################################.....###


################################################################################
################################################################################
###########################################################################...##
##########################################################....................##
##########################################################.################...##
##########################################################.################...##
##########################################################.#################.###
######..........#################...######################.#################.###
######..........#################...######################.......###########.###
######..........#################................................###########.###
######..........#################...######################.......###########.###
######..............................######################.......###########.###
######..........#################...######################.......#######.....###
########........###################.######################.......#######...#.###
##########.########################.#########...##########.................#...#
##########.########################.#########....................#######...#...#
##########.#####################.........####...################.#######...#...#
##########.#####################.........######.################.###########...#
##########.#####################............###.################.###########...#
##########.########################.........#......#############.###########...#
##########.########################.........#......########....#.###########...#
##########.#############.......................................#.############.##
##########...............##########.#########......#######.....#.############.##
########################............######################.....#.############.##
########################.##########.######################.......############.##
########################.##########.######################.##################.##
########################.##########.#####################......##############.##
########################.##########.#####################......##############.##
########################.##########.#####################......##############.##
########################.##########.#####################........############.##
####################.....##########.#####################.....................##
####################.....##########.#####################........####.......####
####################................#################################........###
###################################.#################################........###
###################################..........................................###
#####################################################################........###
#####################################################################........###
#####################################################################........###
########################################################################.....###
########################################################################.....###
The generator takes a few seconds to run (not too bad for a process that runs once per level), but it is in highly unoptimised python. If it's too slow, there's still a lot of room for profiling and optimisation. Running in pypy or translating to a more performant language would no doubt reduce the time to less than a second.
It takes about half a second to run on the examples here.

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Generating well-connected maps
« Reply #1 on: February 21, 2014, 05:17:19 PM »
uh, okay, I'm going to go out on a limb here and suggest something radical: If you don't like the topology of your levels, you should use tools to guarantee, say, adequate connectedness as part of generation, not try to go back and fix it by adding extra stuff.

There are lots of programs that do this kind of thing. For example, you can use Brendan McKay's plantri:

http://cs.anu.edu.au/~bdm/plantri/

or alternatively, if you want huge graphs and don't want to exhaustively enumerate them, there is a program for uniformly sampling from the set of planar graphs with certain properties, e.g.:

Also worth noting, if you're dealing in reasonably small levels, you can just maintain a database of planar graph data to draw from as necessary. There's no need to actually call these programs or libraries from your own code (which may have some nontrivial licensing ramifications). The data they produce is free as the grass grows.
« Last Edit: October 11, 2015, 02:08:32 PM by mushroom patch »

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Generating well-connected maps
« Reply #2 on: February 21, 2014, 06:23:46 PM »
uh, okay, I'm going to go out on a limb here and suggest something radical: If you don't like the topology of your levels, you should use tools to guarantee, say, adequate connectedness as part of generation, not try to go back and fix it by adding extra stuff.
That's exactly what this module does. You can feed it any input. Give it a set of disconnected rooms and it "guarantees adequate connectedness as part of generation". It's also flexible enough to be used as post-processing on any pre-existing algorithm that generates grid maps.

Quote
There are lots of programs that do this kind of thing. For example, you can use Brendan McKay's plantri:

http://cs.anu.edu.au/~bdm/plantri/

or alternatively, if you want huge graphs and don't want to exhaustively enumerate them,
This becomes infeasible before 12 rooms - hardly "huge". It's 3 more than the levels in Rogue.
Quote
there is a program for uniformly sampling from the set of planar graphs with certain properties, e.g.:

http://www.lix.polytechnique.fr/~schaeffe/

Also worth noting, if you're dealing in reasonably small levels, you can just maintain a database of planar graph data to draw from as necessary. There's no need to actually call these programs or libraries from your own code (which may have some nontrivial licensing ramifications). The data they produce is free as the grass grows.
These are some very nice achievements in abstract graph theory, much more impressive than my humble domain-specific 180-line Python module thrown together over lunch. Unfortunately, dealing in abstract graphs makes them quite unsuited to roguelike map generation. In the real world, the output of those programs has to be converted from an abstract graph format to a grid, with axis-aligned edges. Not a trivial task.

Now there are a few papers describing methods to do that, but a pre-assembled solution that operates directly on roguelike maps is far easier for the average programmer to get their head around and assemble. Or copy, since there's a complete implementation right here in < 180 lines of well-commented Python with no licensing ramifications.

"You shouldn't have had that shower installed. We already have a bathtub, a furnace, and a canal - what more could you want?"

guest509

  • Guest
Re: Generating well-connected maps
« Reply #3 on: February 21, 2014, 06:39:52 PM »
Might have to lift some of this later for Gunfist: Gaiden.

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Generating well-connected maps
« Reply #4 on: February 21, 2014, 07:18:04 PM »
Actually, it is easy to embed these graphs -- they're not merely abstract graphs, they're planar and even come with cyclic orderings of the edges around a vertex so they at least come with a topological embedding. If you use a package like networkx, the layout algorithms produce planar layouts of planar graphs pretty consistently. With slightly more sophistication, you can use a 3d embedding computed by either spectral projection or a spring layout engine (both included in networkx) plus some projection scheme, e.g. normalize the embedding to live on a sphere + stereographic projection, to get an initial planar embedding -- for a 3-connected graph this is pretty much guaranteed to work without much fuss since your 3d embedding will be some crooked version of a polyhedron.

But I see the virtue of what your script does. If you're interested only in what your rooms are shaped like and not how they connect together (beyond 2-connectedness, which is an important property, I agree), it sounds like your code does the job nicely.

Quendus

  • Rogueliker
  • ***
  • Posts: 447
  • Karma: +0/-0
  • $@ \in \{1,W\} \times \{1,H\}$
    • View Profile
    • Klein Roguelikes
Re: Generating well-connected maps
« Reply #5 on: February 21, 2014, 07:59:47 PM »
Actually, it is easy to embed these graphs -- they're not merely abstract graphs, they're planar and even come with cyclic orderings of the edges around a vertex so they at least come with a topological embedding. If you use a package like networkx, the layout algorithms produce planar layouts of planar graphs pretty consistently. With slightly more sophistication, you can use a 3d embedding computed by either spectral projection or a spring layout engine (both included in networkx) plus some projection scheme, e.g. normalize the embedding to live on a sphere + stereographic projection, to get an initial planar embedding -- for a 3-connected graph this is pretty much guaranteed to work without much fuss since your 3d embedding will be some crooked version of a polyhedron.
I've seen some nice graph layouts using networkx, but I haven't networkx draw axis-aligned edges with at most one corner. For that you want something like this paper: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.6677. Bresenham lines don't make good corridors in the average roguelike.
Quote
But I see the virtue of what your script does. If you're interested only in what your rooms are shaped like and not how they connect together (beyond 2-connectedness, which is an important property, I agree), it sounds like your code does the job nicely.
Apart from games that have special rules for corridors, room design is typically much more constrained than connectivity in roguelikes. There are limits beyond which additional connectivity is detrimental to gameplay, but few algorithms risk hitting those limits.

Some games may require rectangular rooms, others might want to fit in predesigned rooms or cavernous irregularly shaped rooms. Some may not even have a concept of rooms in some areas (such as maps generated by cellular automata or diffusion-limited aggregation), but still have a need for good connectivity. This script works for all of them (but the line drawing may need to be altered to give a more natural flavour).

mushroom patch

  • Rogueliker
  • ***
  • Posts: 554
  • Karma: +0/-0
    • View Profile
Re: Generating well-connected maps
« Reply #6 on: February 21, 2014, 10:06:22 PM »
Oh, right, you make a good point about converting an edge into an aesthetically pleasing grid-aligned path. This takes some work, for sure.

This method of yours is obviously better for putting together something quick than the kind of bsp schemes you criticize in the OP -- I guess I don't follow 7DRL's and such carefully enough to be aware that this is an issue. I'm just suggesting that for a more polished product, one should consider something more systematic.

Btw, re: feasibility, plantri will produce all 3-connected planar graphs on 12 vertices with minimum vertex degree 3 in .02 seconds on one of the worst computing devices I've ever owned (my laptop). If you weaken the requirements to 2-connected with minimum degree 2, it takes 5 seconds to find over 4 million graphs -- all such graphs up to planar isomorphism without repetition. Minimum degree 2 is a silly thing to look at though. In 6 seconds, plantri will find all 15 vertex 3-connected graphs with minimum degree 3. That's 12 million distinct graphs on a garbage computer running on a battery. This is forgetting about the possibility of using programs that sample rather than enumerate and the fact that the computation need only be done once to get the data.

I would also remind you that even if you used 9 rooms, as in rogue, you get substantially more diverse layouts by this technique than you see in rogue.


EDIT: On closer inspection, in the example computations I report on above, I was generating triangulations, not general planar graphs. The correct time for 3-connected planar graphs with degree at least 3 and 12 vertices is about 15s. Other times similarly increase, but one gets quite a lot of graphs from this computation and the data only need be computed once.
« Last Edit: February 22, 2014, 03:19:23 PM by mushroom patch »

Pickledtezcat

  • Rogueliker
  • ***
  • Posts: 62
  • Karma: +0/-0
    • View Profile
    • Pickledtezcat Game Development Blog
Re: Generating well-connected maps
« Reply #7 on: February 22, 2014, 09:19:35 AM »
Have you considered using multiple levels or scales of generation?

In my system I use [levels[room_arrays[rooms[walkable_tiles]]]]

I use a room system that handles room sized blocks of the map (10x10) and also larger "room arrays" such as a 4x4 spiral or a 2x3 "L" shaped room. I'm working with a 3d program but I'm sure it could be converted easily to work with a 2d game engine. A room array looks like this:

Code: [Select]
[[1,1],[0,1],[0,7]]]
####
#oo#
##o#
##e#
####

The border walls are implicit in the generator and don't have to be defined in the array. The 1's =Ordinary rooms and the 7= Exit, a special square which is used as the linking point with other room arrays. A room array may have one or several exit squares, but most contain at least one otherwise the room won't be connected (a function could be added to automatically add an exit square if one is not present).

The result looks like this:



The crosses are just simple visual representations of a single tile for quick testing for the main algorithm, the final result uses a NorthEastSouthWest tile picker to ensure rooms and corridors have the right shape: http://www.youtube.com/watch?v=NfzyUwUDFmw

For example if the northern neighboring tile is an ordinary room and the current tile is an ordinary room it uses a ordinary room transition tile for the northern quadrant. If the eastern neighboring tile is a corridor and the curent square is an exit square it will use a doorway complete with pre-placed door or the Easternmost quadrant of that room. If the current tile was not an exit it would use a wall quadrant instead, blocking access to the corridor from that tile.

My rooms are 3d objects with a walk mesh, but it would be easy to specify rooms as arrays, and even to randomly generate room types or room quadrants (with alcoves, doors, pillars etc...) to form a dictionary which could then be sampled to provide rooms for the level builder. Because the generator works with 10x10 chunks instead of individual tiles it's quite fast, for example you can work with a 200x200 graph as easily as with a 20x20 graph.

I use A* to generate corridors and a couple of simple functions to randomly rotate and mirror the room arrays so they don't get too repetitive. when running the A* pathfinder I can give existing corridors a lower movement cost to encourage the path finder to use existing corridors whenever possible (increasing connectedness). I can also use some additional rules when calculating the paths:

(room_list is a list of all rooms tagged as exits from the list of room_arrays when generating the map)

1: forwards single connectedness (all rooms are connected to the start room, no extra incentive for A*to use existing corridors) start tile for A* is room_list[0], end tile is room_list[room_index] (sounds like the algorithm the OP was complaining about, not really a bad algorithm, unless it's the ONLY algorithm).
2: backwards single connectedness (all rooms are connected to the end room, no extra incentive for A*to use existing corridors) start tile for A* is room_list[-1], end tile is room_list[room_index]
3: Multiple cyclic connectedness (all rooms connected in sequence) start tile for a* is room_list[room_index-1] end tile is room_list[room_index]
4: Random multiple connectedness (as above but randomly select the room index from a temporary list and .pop() each index as you go through the list.

You could also run multiple corridor generation functions with different rules to be sure of multiple connectedness.

Some things to consider:
  • The script could be much faster, I learned a lot about A* during development of my game and I'm sure I could cut the generation time to just milliseconds just by implementing a few improvements, something I plan to do later when I've got time to spend on optimizing features that work already (such as using python's heapq in the A* algorithm or using smaller graph sections i.e. limiting the search area, or just by using a more efficient graph style, as I currently use an array of lists). Anyway, the slowest one you can see there is a 60x60 grid which would be a 600x600 tile dungeon, covering an area of 360,000 tiles and generated in just 6 seconds.
  • The corridors are a little boring, if you check out the video above you'll see I also experimented with adding granularity to the map on order to make corridors snake and turn a little more to avoid areas of hard rock.
  • Having more rooms and less corridors may be preferable, if so just raise the target number of rooms or reduce the graph size.
  • I used 10x10 chunks with double square doors and corridors in this particular generator as that's what the tile set is designed for, but you could use 5x5 chunks and single square doors and corridors quite easily (something else I plan on implementing in the future when making a different tile set).
  • This is still in testing, so I have quite a limited variety of room arrays, so you can see lots of repetition (only 58 unique room arrays, max size 4x4). In the final game there will be lots and lots of potential room arrays, I may even write script to automate generation of new arrays.
  • If you're going to be working with big levels like this you'll need to speed up how your game handles such things as path finding, LOS or rendering of the dungeon. The program I use, Blender game engine does this by only rendering tiles in the camera view fulstrum, and I help it along by disabling animations and logic for objects outside that area. I also use dictionaries to store my level and skip any tile which is not a room or corridor tile when building the dictionary. When building a graph for LOS or pathfinding I first check a tile to see if it is in the dictionary and if not I can ignore it or have it return False to any boolean check. In that case the room at the beginning of my post would be a dictionary of 4 entries instead of a 4x5 array of 20 tiles, as only those 4 tiles are important. You can do other things such as using Bresenham lines to pre-explore a route to a target tile before kicking in the A* pathfinder, if the route is clear you don't need to use the more time consuming algorithm.

I'm sure you guys know all this stuff already, but I wanted to be thorough in my explanation as I'm rather new to coding and don't know all the terminology, and I don't know what is commonly done in roguelikes to speed up performance. You probably do all the things I suggested already, or can tell me why they are a bad idea and you don't use them. :)
« Last Edit: February 22, 2014, 05:01:06 PM by Pickledtezcat »
A blog about my 3d Roguelike: http://pickleddevblog.blogspot.kr/

Zireael

  • Rogueliker
  • ***
  • Posts: 604
  • Karma: +0/-0
    • View Profile
Re: Generating well-connected maps
« Reply #8 on: March 18, 2014, 08:30:39 PM »
I am having a similar connectedness problem in my T-Engine module (getting a single-room level with no corridors quite often).

Ended up borrowing chunks of code from Zizzo's ToME 2 port, but it's not working yet, and he complained that the T-Engine tunnel function is buggy.
I guess I'll have to rewrite the tunnel function myself. I looked at Incursion's level gen code, that is, the tunneling part, and I like it, I'll try to port some of it over. Basically, I want to stop the random direction changes from happening too often, and I want a human-readable direction of the corridor, which is what Incursion does.

T-Engine uses Lua, for those who don't know. Any tips?