### Author Topic: Graph Grammar and Voronoi based Dungeon Generation  (Read 15460 times)

#### naughty

• Rogueliker
• Posts: 59
• Karma: +0/-0
##### Graph Grammar and Voronoi based Dungeon Generation
« on: April 03, 2013, 11:00:23 PM »
I made a video of a level generation system I've been working on for a while now. Hopefully not too boring :^)

Here's a screenshot:

#### Quendus

• Rogueliker
• Posts: 447
• Karma: +0/-0
• $@ \in \{1,W\} \times \{1,H\}$
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #1 on: April 04, 2013, 12:01:48 AM »
Awesome. Did a course in these a couple years ago, they've got a lot of potential for this kind of PCG.

I'm a little unsure about the disparity between the regular hex lattices in the middles of the islands and the rough edges - how do you envision these interacting with gameplay?

#### george

• Rogueliker
• Posts: 201
• Karma: +1/-1
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #2 on: April 04, 2013, 01:08:44 AM »
I'm curious about the hexes too.

That's an amazing generator and visualizer, were you inspired by any particular graph design tool or did you just make what you felt you needed?

#### naughty

• Rogueliker
• Posts: 59
• Karma: +0/-0
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #3 on: April 04, 2013, 07:25:01 AM »
Quendus: Thanks for the kind words. The walls are irregular because of how I fill the empty space between rooms and corridors. I am considering something a bit more controlled though. It's worth noting that I used random walk hexgrid rooms because they look nice for the demo but I also have room gen based on square grids and randomly assigned points. I just need a set of point for the voronoi to work.

Gameplay wise the idea is that you can walk to any connected cell (any cell that shares an edge with your current cell). Not sure if I'm going to have wall destruction but it wouldn't be hard to support. I've got used to the stained glass look of voronoi so thanks for bringing it up, more consistent walls would look better.

george: Thanks! The visualiser for the level generator is actually how it works under the hood, I'm using Force-based Graph Drawing. As I said above the hexgrids are purely to make the demo look nice, I have other room gen styles but I got impatient to make the video.

There's been loads of inspiration:
• Graph Grammars came from Automatic Generation of Dungeons for Computer Games by David Adams. The paper doesn't mention how to actually render the graphs it produces. Which is the main bit of work I've added.
• The idea to use voronoi came from IRDC 2012 in London where I showed the previous tech I was working on. Just after I did the presentation the projector had a screen saver that looked a bunch of voronoi cells.
• My previous tech was mentioned on an IRDC Roguelike Radio episode and it was remarked as looking 'spiderlike' and the maker of Hyperrogue made a comment about "it'll look fine after you make cells from it". I wasn't planning on doing that at the time but he was totally right and it encourage me to try.

#### kraflab

• Rogueliker
• Posts: 454
• Karma: +0/-0
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #4 on: April 04, 2013, 08:27:05 AM »
Nifty.

#### Quendus

• Rogueliker
• Posts: 447
• Karma: +0/-0
• $@ \in \{1,W\} \times \{1,H\}$
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #5 on: April 04, 2013, 10:51:04 AM »
Adding some Gaussian jitter to the hex-grid points would probably be enough to get the whole map looking consistently rough. Using floating-point positions might also have the advantage of removing those ugly intersections that occasionally pop up.

The main problem with previous top-down mapgen methods using graphs was that they didn't provide a way of turning the abstract graph into a concrete 2D map. Force-based graph drawing is a bit heavyweight and might not look amazing on a regular lattice, but you've pretty much got it down pat here.

#### Krice

• (Banned)
• Rogueliker
• Posts: 2316
• Karma: +0/-2
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #6 on: April 04, 2013, 11:13:14 AM »
Could be cool for 3D game environment, but you can get the same result (or even better) simply by plotting some blobs as rooms and connecting them with corridors.

#### naughty

• Rogueliker
• Posts: 59
• Karma: +0/-0
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #7 on: April 04, 2013, 11:20:57 AM »
Quendus: I'm not too bothered about inconsistent roughness if it makes sense, e.g. water, trees, natural rock formations. As you said though the walls are incongruous. I'll try out the noise on the hex points and I've got a few more ideas since you pointed it out to me.

The force-base graph drawing is by far the slowest part of it all (2-3 order of magnitude). In comparison the  subgraph isomorphism algorithm used to find the patterns has exponential running time but barely appears in profiles. It takes only a few seconds for up to 30 rooms, but 100 rooms took two minutes and 95% of the time is the graph drawing.

At least force-based graph drawing is simple to implement though :^) If anyone knows of a better graph drawing algorithm that would be cool. I've already looked into Tutte embedding and that doesn't really work, some of the planar graph drawing algorithms force everything into a big triangle which isn't any good either.

I found the secret to making the graph drawing work is to apply the force draw after each substitution step (which is very slow relatively). I also have to make sure the inserted part of the graph isn't too tangled up by using an edge from the matched part of the host graph to transform the substitute graph (this roughly rotates the substitute graph into the right position). You also have to prune the potential subgraph matches so only rotated matches are allowed, a flipped match makes it all fall down.

Krice: My previous system used that kind of algorithm, it was hard to get cells out of it though which is why I changed to Voronoi. I also wanted a level of control over the structure of the levels, hence graph grammars. Although the Space Colonisation algorithms I've seen recently might be a good idea as well.

#### naughty

• Rogueliker
• Posts: 59
• Karma: +0/-0
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #8 on: April 04, 2013, 01:02:59 PM »
Actually Krice do you have any examples of the blob plotting system you mentioned? I think I may have misunderstood what you meant,

#### Quendus

• Rogueliker
• Posts: 447
• Karma: +0/-0
• $@ \in \{1,W\} \times \{1,H\}$
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #9 on: April 04, 2013, 01:19:52 PM »
Krice - The advantage of graph grammars is that the room/corridor network is built top-down, starting with the important thing for gameplay (topology) and ending with the least important thing (exact room dimensions and positions). This means that differences in topology can be produced by tweaking topological parameters (the graph transformation rules), rather than as a by-product of tweaks to non-topological parameters (distribution of room sizes etc.). They also scale in more predictable ways than traditional dungeon-generation algorithms.

Naughty - The transformation rules you're using all seem reasonably easy to check, so it's not surprising that it runs so quickly. It's good that you've got room to add piles of complication into the rules for things like special room types, user configurability, support for larger levels, etc.
I can't give much advice on improving the planar drawing performance as it's not a subject I've investigated much.

#### Krice

• (Banned)
• Rogueliker
• Posts: 2316
• Karma: +0/-2
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #10 on: April 05, 2013, 10:56:30 AM »
Actually Krice do you have any examples of the blob plotting system you mentioned?

Some random shaped cavern rooms and then connect them. I don't get these ultra complex methods. It looks the same so who cares if they were clever.

#### Slash

• Creator of Roguetemple
• Administrator
• Rogueliker
• Posts: 1201
• Karma: +4/-1
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #11 on: April 05, 2013, 11:47:23 AM »
It matters if your maps are derived from an higher level logical design (for example a system of keys / barriers). Also those are not ultracomplex, you are just lazy.

#### Krice

• (Banned)
• Rogueliker
• Posts: 2316
• Karma: +0/-2
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #12 on: April 05, 2013, 08:18:27 PM »
It matters if your maps are derived from an higher level logical design (for example a system of keys / barriers

I want to see the roguelike where that kind of game design is used.

#### Slash

• Creator of Roguetemple
• Administrator
• Rogueliker
• Posts: 1201
• Karma: +4/-1
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #13 on: April 05, 2013, 10:48:18 PM »

#### Krice

• (Banned)
• Rogueliker
• Posts: 2316
• Karma: +0/-2
##### Re: Graph Grammar and Voronoi based Dungeon Generation
« Reply #14 on: April 06, 2013, 08:37:34 PM »
you are just lazy.

I'd like to say I'm practical. I'm also trying to find solutions to problems without complex math which can mean more work. I also started to program a major roguelike some time during 1996 and possibly hold the world record in the amount of hours put into development of a single game.