'UE4_MissionGen' is a grammar-based, free and open source mission generator. The generator is designed as a tool to aid in the level design process by partially automating encounter design and assisting in the discovery of new emergent interactions between game mechanics, enemies, obstacles and any other game concepts that can be expressed via a spawnable actor.
Generative grammars were originally pioneered as a theory of linguistics whereby grammar is viewed as a cognitive faculty and language is generated by a set of pre-defined rules and procedures (Carnie, 2012). In this context, a grammar can be defined as the set of rules that generate a given language. As such, given a generative grammar with enough breadth and complexity in its ruleset, it is possible to produce all of the grammatically-correct phrases of a language.
In the context of procedural generation, a grammar is composed of symbols that express the content of a system and re-write rules that specify the relationship between symbols and the nature of their construction (Kybartas, 2017). The collective sum of symbols in a grammar is referred to as the grammar's alphabet and encompasses the total possibility space of a grammar. An alphabet can effectively be thought of as a dictionary that defines all of the possible relationships between symbols (aka game actors) and their re-write rules (aka the construction rules of game actors).
Symbols can be further classified as either terminal or non-terminal based on whether they contain any re-write rules or are the end point to any further recursive iteration. Terminal symbols are traditionally expressed with lowercase characters and non-terminal symbols with uppercase characters (Dormans, 2010).
For a game specific example, Kybartas (2017) proposes an example grammar for the generation of side quests - this is shown below whereby the symbol '→' is indicative of a transformational re-write rule.
[Journey] → [Journey] [Encounter]
[Encounter] → [Encounter] [Encounter]
[Encounter] → [Discovery] [Journey]
With the rules above and a starting input of [Journey], Kybartas demonstrates that example quests such as [Journey] [Encounter] [Discovery] [Journey] [Encounter] or [Journey] [Encounter] [Encounter] [Encounter]can be generated. Kybartas then adds more specific actions and events to his grammar below.
[Journey] → [go to town]
[Journey] → [go to the forest]
[Encounter] → [fight a goblin]
[Encounter] → [fight a dragon]
[Discovery] → [find gold]
[Discovery] → [find weapon]
With a more specific grammar in place, the previously abstract side quests generated from the old grammar are transformed into more specific quests, such as [go to town] [fight a goblin] [find gold] [go to the forest] [fight a dragon].
This project interprets the definition of a mission as a sequence of game objectives that a player must complete in order to reach the end of the level (Karavolos et al., 2015). As such, the project is only interested in the generation of a sequence of player objectives and contains no procedural geometry/level space generation.
For more specifics on generative grammars and the specifics of this implementation, please view the original academic report written on the project here (please note that whilst the UI and functionality of the generator have been updated since publication of the report, the methodological foundation remains the same).
Carnie, A. (2012) Syntax: A Generative Introduction (Introducing Linguistics). Hoboken: John Wiley & Sons.
Chomsky, N. (1957) Syntactic Structures. Berlin: Mouton de Gruyter.
Dormans, J. (2010) ‘Adventures in Level Design: Generating Missions and Spaces for Action Adventure Games’, PCGames 2010, June 18.
Dormans, J. and Bakkes, S. (2011) ‘Generating Missions and Spaces for Adaptable Play Experiences’, IEEE Transactions on Computational Intelligence and AI in Games, 3(3), doi: 10.1109/TCIAIG.2011.2149523, pp. 216 – 228.
Kybartas, B. (2017) ‘Story and Plot Generation’, in Short, T.X. and Adams, T. (eds.) Procedural Generation in Game Design. Boca Raton: CRC Press, pp. 187 – 197.
Lavender, B. (2015) The Zelda Dungeon Generator: Adopting Generative Grammars to Create Levels for Action-Adventure Games. BSc dissertation. University of Derby.
Middag (2016) Controllable generative grammars for multifaceted generation of game levels. MSc dissertation. Ghent University.
Tommy, T. and Lavender, B. (2016) ‘A Generative Grammar Approach for Action- Adventure Map Generation in The Legend of Zelda’, Artificial Intelligence Simulation and Behaviour 2016.