generazione di livelli di un rompicapo: un approccio basato sull'intelligenza artificiale

Automatic level generation is a long-standing problem in video game production. While big companies may afford to hire specialists in handcrafting levels, small companies and indie developers would benefit from a system that can automat- ically create engaging levels. This thesis tackles the automatic level generation problem for a puzzle game called Alea. Creating levels for a puzzle game poses a series of challenges that need to be overcome, such as ensuring the level is finishable and challenging enough to engage the player. The proposed system solves these specific challenges by generating levels going backward, i.e., starting from an ending configuration of the game (potentially provided by the designer) it uses the A* informed search algorithm to obtain an initial configuration. Going backwards offers several ad- vantages, among which, ensuring that the search returns at least a solution (i.e., the level can be finished), in fact, what represents the solution for the user is the starting point for the algorithm. Additionally, the system computes an estimate of the difficulty of the level, which aims to represent the cognitive effort the user has to make to solve the level. However, since the estimate is closely related to the sequence of moves used to generate the level, it has a narrow view of the possible solutions of the level; the system tries to get a more precise estimate by exploiting a forward search which looks for the easiest possible solution. To do so, a variant of the informed A* search algorithm is used; starting from the generated initial configuration, it looks for the easiest solution according to a heuristic. The main idea of this forward search is to reduce the possible estimation bias induced by the generation algorithm. Moreover, this way of working “forward” tries to simulate the users’ condition and behaviour so that the resulting estimate may be more reliable.