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