Constrained procedural generation of 2D mazes and intelligent artificial agents for cognitive therapy

People affected by cognitive impairments, such as Parkinson’s disease, can be monitored and stimulated by calibrated exercises, appearing in the form of games, that doctors have to carefully design for each patient. In order to have a more powerful and more efficient system, these exercises can be created, quickly and in a well diversified manner, by using techniques of procedural content generation. However, one game has shown a peculiar complexity in taking control of generative constraints and imposing a requested difficulty: the maze. Dealing with its constrained procedural generation lacks a valid solution in literature and poses a series of other problems, such as determining an objective measure of difficulty. This work addresses all the problems with novel solutions that have been implemented with success. An original procedural strategy has been designed to build constrained mazes by means of spanning trees generations and an SMT solver for combinatorial optimization. A custom search algorithm based on SMA* and Depth-first search has been introduced for the first time, giving rise to artificial agents capable of solving mazes like humans, with the addition of a system for emulating cognitive impairments. A performance measure and an evaluation strategy have been successfully experimented to define a scientific score system, for classifying mazes, based on simulations; then multiple regressors have been trained as predictors to infer scores from mazes, the most notable one being a variant of a Graph Neural Network. Finally, customized genetic algorithms and statistical methods have been exploited to solve the problem of retrieving mazes and agents from requested scores and performances. The entire work introduces many novel approaches with benefits in the medical field, but not only.