Step 1 of the generation phase within Atlas is the “Sketch” step. This involves a high-level FlowMap (shape and flow) of the entire level. Until now, I had been treating flow as an undirected, weighted graphical model, and using a formal, context-sensitive, parametric L-System grammar to generate it. The parameters of the L-system grammar were to be induced from the sample level during the Analysis Phase.

However, I see now that there might be a more intuitive method of generating this level “Sketch”: An evolutionary algorithm.

I'd be loathe to call a classical Genetic Algorithm “creative”, even though it possesses a fitness function, and thus is in a sense 'appreciative'. However, In general, Creativity is actually quite similar to an evolutionary search, albeit with highly deliberate and intelligent 'mutations' and 'crossover'. We tend to like Genetic Algorithms because they can sometimes efficiently search a space via basic operations without needing to actually understand the space. Unfortunately, Genetic Algorithms often have the following drawbacks:

• GAs do not scale well with complexity: In theory, given a good fitness function and genotype representation, a GA will eventually produce a good result. However when the complexity of the task is great, the time required to converge on a good solution may be completely unreasonable.
  • In part, we seek to mitigate this in Atlas by creating MANY different GAs which are focused on smaller, specific, narrowly-scoped tasks. It would not work well to use a GA to generate the entire level tile-by-tile, but using it JUST for a high-level sketch might be effective.

• GAs generally cannot sacrifice short-term loss in order to gain long-term benefit (no ability to plan, anticipate).
  • We seek to mitigate this in Atlas by introducing a hierarchical revision structure, backtracking, and artistic 'vision'.

• GAs generally are slow to converge for large problems spaces: Tile-based level design is indeed a large problem space (trillions or quadrillions of raw variations).
  • We seek to mitigate this in Atlas by using very deliberate, intentional mutations (rather than random), and very deliberate, intentional selection of which components to mutate (rather than a fixed proportion or random selection). For example, when trying to space nodes of a flowMap evenly, Atlas might only mutate offending nodes (nodes that are too close), rather than picking them at random. This should achieve much faster convergence.

To quickly test some of these methods, I wrote a brief genetic algorithm that simply places nodes of a flow-map on the screen (no connections between them), and tried to space them out so that no two were adjacent. This was straightforward, but a pure-random mutation and crossover resulted in a long convergence time (dozens or hundreds of generations). I then compared this with very deliberate mutations (only selecting offending nodes that were too close, and only nudging them one space in a random direction). The latter method achieves convergence in 5-6 generations.

30 initial points

50 initial points

Now how hard would it be to increase the complexity of the criteria? Instead of preserving space between nodes, let's try aligning all nodes horizontally and vertically with one another. In this test, the goal was to get nodes which keep exactly 1 tile between themselves and their neighbors, and want to be vertically or horizontally aligned.

Using smart mutations (rather than random), and selecting only offending nodes to mutate, this was accomplished in less than 50 generations:

Alignment task

Using deliberate domain-specific mutations, we can achieve extremely efficient exploration of a space on simple tasks. If we can break down flow generation into a series of these simple tasks, then we can do flow generation quite cheaply.

I need to do experiments on a full flowMap involving global properties such as branching factor, connections, segment length, angle, etc. One of the tricky parts of evolutionary algorithms is selecting a fitness function that is reasonably cheap to compute. Global fitness functions tend to be quite expensive on complex domains. However, I think I can mitigate this by using global properties which can be computed on-line (that is, they don't need to be re-evaluated from scratch. Each small change can incrementally update the properties listed above).