2
\$\begingroup\$

I'm looking to do some pseudo-random map generation using graph grammars (graph rewriting). However, most of what I can find online on this is purely academic and, while helpful, doesn't have any direct practical application.

For the uninitiated, the thousand-foot view of this is that say a dungeon room is generated, then based on a set of rules for that room, one rule is randomly chosen and applied adding more rooms. From there, another specified room may go through the same or a different set of rules for additional growth of the map.

For the practical side of things, I'm thinking of storing the possible rules as arrays containing data about what additional rooms it contains, what order they are in, and which might also end up having a rule applied to it. But then mapping this to 2D space, while it seems easy, may end up with some complications, such as what happens if rooms end up overlapping.

At any rate, I was hoping someone might have some insight into whether this might be done in a better fashion than an array for the rules.

The results from the rules will likely be added to a custom class that will hold the layout as it's built.

Thoughts? :)

\$\endgroup\$
  • 2
    \$\begingroup\$ graph-grammars is probably a bit too niche for a GDSE tag, added procedural-generation instead \$\endgroup\$ – Pikalek May 23 '16 at 15:43
  • 1
    \$\begingroup\$ well, if you span your graph starting from 1 room, you could just move overlapping rooms until the first non-occupied spot. Taking suggestion from this, when the algorithm separates the rooms. You could just span them untile they don't overlap \$\endgroup\$ – Leggy7 May 23 '16 at 16:07
2
\$\begingroup\$

Most instances I've seen of graph rewriting for map generation solve the collisions problem (I.E overlapping rooms) by restricting the graph nodes to regular, modular components. For instance, this example, taken from Procedural generation of dungeons uses rooms that are laid out on regular intervals:

enter image description here

\$\endgroup\$
1
\$\begingroup\$

The other approach I've seen is to use a generate & test (aka trial & error) approach. Basically, a rule is selected & if the result would be valid, it is applied. If the result is invalid (I.E. overlapping rooms) usually it is discarded & a new rule is attempted. Other times, it may be possible to modify the results.

In a sense, both of these happen a bit with Brogue's level generation; I.E. bridges are built "until we can't find nice places to build them" whereas with water "we knock down the boundaries between similar lakes where possible."

The more complex your rules, the more difficult it may be to get results with a no modifying generate & test approach. The trade off is it can generate things of greater complexity than the modular approach discussed on my other answer.

\$\endgroup\$
1
\$\begingroup\$

One approach I had heard, (I want to try this, haven't had the opportunity yet) is to Generate a graph that is a regular arrangement of nodes (similar to the picture Pikalek posted) then work backwards from there to the Rooms you want.

i.e. The first node has only one corridor/exit so you pick a room at random from your selection of dead-end rooms and put that at your starting position. then maybe your next room has 3 exits (north south and east) so you pick a room at random from those you have with exits on the north south and east, and place it adjacent to your current room so the exits align.

This approach needs you to have created a whole lot of rooms, but can give you a map that looks more hand crafted than a purely procedural approach. (Diablo 3 is an example of this type of map generation.)

You can expand on the tile options By combining two horizontal nodes together and picking one Tile that fits over both nodes as well.

\$\endgroup\$

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.