Sample Genetic Algorithm Level Generator

This is a search-based level generator based on the Feasible Infeasible 2 Population Genetic Algorithm. The initial population is generated using the Sample Constructive Level Generator. The levels are represented as a 2D array of tiles. Each tile consists of an array of strings representing all sprites at that tile. The generator uses one-point crossover which swaps the 2 chromosomes around a random tile. For mutation it uses 3 different operators:

• Create: creates a random sprite to any random tile position.
• Destroy: clears all sprites from a random tile position.
• Swap: swaps the sprites in two random tile positions.

The level generator uses an altered version of the Adrienctx controller for simulation-based fitness and constraint evaluation. Adrienctx is a reasonably good controller, as it was the winner of the 2014 edition of the GVGAI competition. The controller has certain super-human skills (i.e. fast reaction time), and it was therefore altered to make its playing style somewhat more human-like. This is achieved through two modifications: adding action repetitions so that the controller has a tendency to repeat the last action for few time steps, and adding NIL repetition so that the controller has tendency to add NIL values between changing actions. These modifications make sure that the controller cannot handle situations which require extremely fast reactions, which in turn discourages the generation of levels that include such situations.

Some of the fitness and constraint evaluations are compared with a OneStepLookAhead player or a DoNothing player. The OneStepLookAhead player plays by greedily choosing among the immediate next actions. The DoNothing player simply applies the NIL action. Both players play for the same amount of steps as the altered Adrienctx controller. The feasible population is subjected to two different heuristic functions:

• Score Difference Fitness: difference between score achieved by Adrienctx and the best score achieved by OneStepLookAhead (over 50 runs).
• Unique Rule Fitness: the number of unique events that happened in the level due to the avatar or any sprite spawned by it.

The fitness functions are treated as an average value of both the Score Difference Fitness and the Unique Rule Fitness. The Infeasible population is subject to the seven constraints classes provided with the system using the CombinedConstraints class.