Procedural content generation for games using grammatical evolution and attribute grammars

The benefits of using some type of automation to reduce the time and cost of software development is generally accepted in most domains, video games1 included. While there are a wide variety of automation techniques available we shall focus on the technique used to produce content for games, commonly referred to as Procedural Content Generation (PCG). PCG uses some form of algorithmic approach to generate content, rather than doing so manually. The content produced using PCG needs to be meaningful within the context of the overall design aesthetic of a game, so assessment of the role the content produced will have within the game, along with the impact it will have on the overall design is extremely important if any PCG tool is to be of use to a game designer. Grammatical Evolution (GE), a grammar-based EvolutionaryAlgorithm(EA), is a widely used method for automatically generating solutions to a wide variety of problems across a diverse set of domains. GE operates by producing potential solutions (usually in the form of programs), to a predefined problem, by combining symbols specified in Backus-Naur Form (BNF), a convenient way of describing a Context Free Grammar (CFG). A CFG provides a means of specifying the syntax of programs, by outlining a set of rules which control the sequences of symbols allowed to appear in each program. While a CFG provides a means of specifying program syntax, it does not support specification of semantics, information which could guide the generation of more meaningful programs. Taking the generation of levels for a 2D Platformer game for example, using a CFG, we could describe the syntax of tile layouts that make up a level. While layouts produced would be syntactically correct they may be unplayable, e.g., contain gap too large for player avatar to jump over. Allowing designers to also specify level semantics will help overcome issues such as this and also allow designer better encode known useful layouts. A CFG can be extended by annotating production rules with semantic functions, where necessary, to become an Attribute Grammar (AG). Standard GE systems use CFG, so we propose adding AG support before using GE as a means of PCG for games. We highlight the benefits of using an AG over a CFG, detailing how having the ability to encode both syntactic and semantic information can make GE a better PCG method in the context of games.