Mutations, mutationss, mutationsss

After we’ve established our base game logic, it’s time to actually get into the why we’re making this game in the first place: to implement a genetic algorithm. From the intro post I made to this series, as a recap:

Genetic algorithms operate on the basis of simulating what we now call “evolution,” the driving factor of which is natural selection often due to random mutation. Genetic algorithms simulate this process in order to optimize a function. Base candidate functions are laid out, and generations after generations of further functions are tested and weeded out through mutation after mutation. In a system using genetic algorithms, there usually exists a genetic representation of what we are trying to optimize, as well as a fitness function that tells us how “good” our function is.

Here, our genetic representation of each entity is encapsulated in our Chromosome struct. The fitness function is what happens after our game logic is run: in this case, we can arbitrarily set it to the final four entities remaining after each generation.

Mutating

The crux of our genetic algorithm is the ability for entites to mutate. Through random mutations, the fittest entities are repeatedly iterated upon till their final forms, generation after generation. This logic is define by our mutate function:

// mutate a chromosome
fn mutate(genes: Chromosome) -> Chromosome {
    // calculate changes
    let bounds = Uniform::from((-10 as i32)..10);
    let mut rng = rand::thread_rng();
    let add_strength = bounds.sample(&mut rng);
    let add_aggressive = bounds.sample(&mut rng);
    let add_agility = bounds.sample(&mut rng);

    // apply changes
    let strength = (genes.strength as i32 + add_strength).max(0).min(100) as u32;
    let aggressive = (genes.aggressive as i32 + add_aggressive).max(0).min(100) as u32;
    let agility = (genes.agility as i32 + add_agility).max(0).min(100) as u32;
    Chromosome { strength, aggressive, agility }
}

Generations

The concept of generations has already been mentioned, but here let me cement that further.

// evolve when only four entities remain
if entity_count <= 4 {
    // check if generation has reached 13; if so, print info of remaining entities
    if generation == 13 {
        for i in 0..ROWS {
            for j in 0..COLS {
                for entity in &cells[i as usize][j as usize].entities {
                    println!("Entity at ({}, {}) with chromosome {:?}", entity.x, entity.y, entity.chromosome);
                }
            }
        }
        is_paused = true;
    } else {
        // otherwise, evolve entities for next generation
        let mut entities: Vec<Entity> = Vec::new();
        for i in 0..ROWS {
            for j in 0..COLS {
                for entity in &cells[i as usize][j as usize].entities {
                    entities.push(*entity);
                }
            }
        }
        let chromosomes = evolve(entities, 20);
        init_entities(&mut cells, chromosomes);
        generation += 1;
    }
}

This section of our SDL2 loop code shows how each generation is processed. A generation begins after the previous generation ends, and a generation ends when only four entities remain in the game. These entities are then passed into an evolve function, which will then call mutate on each of these remaining entities.

We set the maximum generation limit to 13, but this is an arbitrary number. Theoretically, the more generations the algorithm runs for, the better the resulting entities are.