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
(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.
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.
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.
