Beck Lavender

Game Programmer, UK

Menu

Skip to content
  • Home
  • About
  • Career
    • Playtonic Games
    • 22cans
  • Projects
    • Yooka-Laylee
    • The Zelda Dungeon Generator
    • Godus
    • More…
  • Education
  • Blog
  • Contact

The Zelda Dungeon Generator

Personal Project, University Project

Research project completed for dissertation. Based on the previous work of Joris Dormans, the ZDG applies the use of generative grammars to a two-step process for procedurally generating Zelda-style dungeons. Graph grammars are used for the dungeon mission, and shape grammars are used for the dungeon space. Generated maps are then applied to a typical 2D tiled Zelda game, in order to see how traditional Zelda mechanics and patterns hold up when generated procedurally.

Grammar generation is performed using a C# backend which produces Lua to be used by the Solarus Zelda-based game engine.

PROCJAM TALK
SLIDES

ZDG_Procjam.pptx

(I forgot to explain the picture on the second lua slide – basically generating door tiles was very complex and intricate because they were made up of so many little pieces and that’s what it could look like if it went wrong!)

BACKGROUND

Dormans analysed dungeons in the Zelda series and found that they were best represented by two distinct structures: mission and space. When generating Action-Adventure dungeons, Dormans suggested that these structures be generated in two distinct steps, using graph grammars for missions and shape grammars for space. The use of generative grammars allows complex dungeon-spanning structures to be generated coherently, such as the formula of defeat miniboss -> get item -> use item to leave room -> use item to traverse dungeon -> defeat boss with item. By dealing with these structures, the technique solves some issues with general Action-Adventure generation, in which puzzles spanning several rooms (particularly of key and lock style) are common. Dormans had applied his theory to a game before, but not a typical 2D tiled Zelda game.

Dormans' analysis of the Forest Temple dungeon from Twilight Princess. The mission, a series of actions the player completes, can be seen mapped on to the dungeon's space.
IMPLEMENTATION

My implementation consisted of a graph grammar mission generator and shape grammar space generator, both written in C#. Mission generation was fairly straightforward whereas map generation was fraught with obstacles. For instance, the mission had to be traversed in an order which combined topological sort and depth-first traversal for chains of tightly coupled rooms. Issues such as these are described and solved in detail in my dissertation.

Mission graph generated using the ZDG.
Map layout generated using the ZDG.
Alphabet describing which nodes correspond to which types of room.
For the game, rectangular maps were created using the Solarus map editor, whilst functionality was taken from the open-source game Mystery of Solarus DX. The C# backend then creates Lua script which is applied to these maps, and generates doors and the connections between them at run-time to realise the dungeon map layout. Examples of rooms which represent some of the nodes from the mission graph are displayed below.
A multi-part lock room. Finding and defeating 4 gibdos will light the 4 lanterns and open the door.
A multi-part lock room. Finding and defeating 4 gibdos will light the 4 lanterns and open the door.
Bombs act as the dungeon item in the ZDG and are used to traverse the dungeon, find secrets and defeat the boss.
Bombs act as the dungeon item in the ZDG and are used to traverse the dungeon, find secrets and defeat the boss.
A secret test room.
A secret test room.
Another secret test room which requires bombs to traverse.
Another secret test room which requires bombs to traverse.
The dungeon boss.
The dungeon boss.
The goal room.
The goal room.
DISSERTATION

This project was completed as part of a research dissertation for my degree. Therefore, a thorough literature review of relevant research and similar work was conducted and the generator was thoroughly evaluated. Evaluation was based on Gillian Smith’s work in expressive range, and was used to analyse the output of the generator in meaningful ways, looking for biases and holes in content rather than, for instance, the number of different maps which could theoretically be produced.

A 2D histogram comparing the results of mission linearity and leniency when a control set of rules are applied to the generator. The results of 1000 missions are shown in this graph.
FDG EXTENDED ABSTRACT

View this document on Scribd

FULL DISSERTATION

ZDG_Dissertation.pdf

Post navigation

← < Godus
Yooka-Laylee > →
  • Email
  • LinkedIn
  • Twitter
  • How to buy remeron in usa
  • Canadian online pharmacy for cialis
  • Xifaxan 55 0mg tablet price in pakistan
  • Can you take synthroid and nature throid together
  • Protopic price canada
  • Online doctor lioresal
  • How to order xifaxan online
  • Advair and spiriva taken together
  • Where to buy propranolol pills
  • Can you get voltaren over the counter