What does it do?
GraphQuest is a assisted design desktop tool that evolves schematic levels for adventure videogames. The designer may specify a number of parameter and restrictions for the algorithm to work with, and can be used to explore alternatives to an existing level or to quickly generate prototypes during the design process.
This proyect uses a evolutionary algorithm capable of producing a variety of levels for any combination of input parameters. Every generated level is guaranteed to be playable, that is, it has a set entrace point, the player can access every room and no door is without a key.
Game levels are divided in zones, accessible with the use of a key that is always located in one of the previous zones. This mechanic grants to the level a well defined order of traversal that the player has to follow. Each one of the zones is further divided into a set of interconnected rooms, that can be accesses in any order, and that are assigned content.
The types of content that a room can contain are defined by the designer, and are meant to provide a level of challenge and reward to the level. The relative proportions of content can be used as a search parameter for the algorithm.
How does it work?
The tool uses a evolutionary algorithm to optimize levels based on a number of fitness criteria. The levels themselves are defined as a group of graphs that define the structures on different abstraction levels. These graphs are produced by a grammar system, that can itself be adapted according to the designer parameters.
The gross structure of the level is defined by a graph that represents the connections between the different zones, and the order of traversal. The inner structure of each zone is defined by another graph, that describes the content of each room and its connections.
The evolution is directed by a fixed set of fitness functions that determine what constitutes a "pretty good" level. These functions can be expanded by user input, directing the search towards the desired outcome.