ASP - For Level Generation
In this short article, we introduce Answer Set Programming (ASP) as a method to generate levels for two dimensional video games.
Level design for 2D video games can be a time-consuming task — depending upon the the required amount of detail as well as the number of levels required for a game. Game mechanics, narrative, and immersion all become important aspects that can extend the period of time required for level generation. In order to save time, game developers can utilize Procedural Content Generation (PCG): the method of generating game content using algorithms. Once certain rules are in place, PCG algorithms can quickly generate hundreds of trees, for example, where slight variance in the assets help create different appearing foliage.
This same approach can be used to generate levels within a game. However, there are challenges to this approach:
- is the level passable (i.e., can the player complete it and move onto subsequent levels?
- are there multiple entrances or multiple exits, and does those entrances and exits support the game narrative?
- does the generated level support the game mechanics (e.g., jumping onto higher ground)?
- are all locations within a level reachable by the player?
Figure 1, ASP Level Generation.These challenges can be overcome by using Answer Set Programming (ASP), a declarative programming language that is useful in solving search problems. ASP searches a given problem domain and determines the satisfiability (i.e., whether a Boolean expression evaluates to TRUE) within that domain. So a Boolean expresion may consist of checks such as:
- is there at least one entrance?
- is there at least one exit?
- are all sections within the 2D grid accessabile to the player?
- is there an order in which the player has to accumulate items (e.g., sword, magic wand, etc.) and does that order support the games narrative?
A games developer could write PCG code that generates levels and use ASP to determine whether a level is successful or not, where successful is whether or not a level satisfies requirements (such as the ones provided previously). Figure 1 demonstrates an example level with sections that have locks and keys. Players must find the keys first in order to unlock sections within the level.
In this article, we've introduced some of the key concepts of ASP which is to allow games developers a way of testing whether a PCG level within a 2D game is satisfiability as well as the types of Boolean expressions that may be part of the solvable search space.
1. Noor Shaker, Julian Togelius, and Mark J. Nelson (2016). Procedural Content Generation in Games: A Textbook and an Overview of Current Research. Springer. ISBN 978-3-319-42714-0.