Experiments in AI - Evolution Part 4

that games guy Icon.

by that games guy

This is part of an ongoing series in which we experiment with different methods of AI. We’ll look at the state of the art and the out of fashion; the practical and the (seemingly) impractical; to find what works and what doesn’t. In this part, we will be writing the genetic algorithm that will evolve our UFOs behaviour. You can read the first part in the series for more information on what we are trying to accomplish. You can also see my earlier article for more general information on genetic algorithms, however, I’ll make sure to include the important parts here.

So what is a genetic algorithm?

A Genetic Algorithm (GA) is an attempt to mimic our evolutionary processes. GA’s are a specific type of evolutionary computing paradigm common to artificial life simulations. Solutions to problems are encoded in a structure called a chromosome (or genome). The solution can be represented as binary digits (bits) or in any other computer-readable format; we’ll be using the floating-point weights of our UFOs neural networks. Similarly, to biological evolution, new generations are created by mating two chromosomes and (possibly) applying mutation to produce a new offspring and consequently a new solution. So in terms of our game, the ‘mating’ will occur when we create a new neural network by combining two previously created neural networks.

Therefore by implementing a GA in our game, we want our UFOs to become more successful over subsequent generations. Just as we (and everything that’s alive) evolve over many generations to become more successful at survival and reproduction.
Crossover and Mutation
Chromosomes A and B are mated to produce an offspring. The crossover point can be dynamically selected or pre-determined; in the diagram the first block of A is crossed over with the second and third block of B. This produces a new offspring with characteristics of both parents. Mutation is not usually performed after every crossover; rather it is performed based on a mutation rate. During mutation, one or more digits is selected and changed in some manner e.g. if the chromosome is encoded in binary digits the digits are reversed.
A general process for a GA is shown in the diagram below.
A general process for a Genetic Algorithm.
A general process for a genetic algorithm.
There are a number of methods used to select individuals for crossover and mutation; however, fitness proportionate selection is commonly used in artificial life simulations due to its parallels with nature. This is what we’ll be using as well. Using this method, the fitter an individual (based on their fitness) the higher the probability of selection. However, it does not guarantee that the fittest individual will be selected. We’ll go into more detail when we write the code in the next part.
A problem being solved by a GA is defined by its fitness function. Individuals are evolved to have the best fitness values possible. The fitness function is used to evaluate the relative performance of possible solutions and is normally defined as a numerical, problem-independent, value. There is no general function; it must be tailored for each application. For our game, we’ll use the maximum time a UFO is alive.

While there was a lot of information hopefully as we write the genetic algorithm (which we will start now and finish in the next part) it will become more clear how this will help our UFOs.

For our GA to work, we need a method of deciding when to remove a UFO from the game and therefore creating ‘generations’. To accomplish this we’ll give each UFO an energy level. This energy value will decrease whenever they collide with another UFO or a screen edge, the two things we do not want our UFOs to do. When the energy reaches zero the UFO will be removed from the simulation and added to a ‘pool’. This pool represents a number of solutions to our problem, it is a collection of a UFOs predecessors. I’ll go into more detail as we go along but the general steps for genetic algorithm are:

Initial Stage:

  1. Spawn number of UFOs with random weights.
  2. Add UFOs to game.

Game Loop:

  1. UFOs energy reaches zero.
  2. UFO removed from the game and added to the pool.
  3. Pool sorted so that UFOs with the longest time alive are first in the pool.
  4. Select parents from the pool based on fitness (more on this soon).
  5. Crossover parents neural networks to create a new network.
  6. Possibly apply mutation to the neural network.
  7. Spawn new UFO.
  8. Add neural network to UFO.
  9. Add new UFO to the game.
The game loop will continue until we stop the game and you’ll notice it is very similar to the GA process I outlined earlier.
Create a new class called GeneticAlgorithm. This will be responsible for evolving our neural networks. Start by moving our SpawnUFO from SceneGame to our new class.
GeneticAlgorith.hpp
#ifndef GeneticAlgorithm_hpp
#define GeneticAlgorithm_hpp

#include "WorkingDirectory.hpp"
#include "ResourceAllocator.hpp"
#include "ObjectCollection.hpp"
#include "C_Sprite.hpp"
#include "C_Animation.hpp"
#include "C_Velocity.hpp"
#include "C_ScreenWrapAround.hpp"
#include "C_NeuralNetwork.hpp"

class GeneticAlgorithm
{
public:
    GeneticAlgorithm(ObjectCollection& objects, WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window);
    
private:
    std::shared_ptr<C_NeuralNetwork> SpawnUFO();
    
    ObjectCollection& objects;
    WorkingDirectory& workingDir;
    ResourceAllocator<sf::Texture>& textureAllocator;
    Window& window;
};

#endif /* GeneticAlgorithm_hpp */
GeneticAlgorith.cpp
#include "GeneticAlgorithm.hpp"


GeneticAlgorithm::GeneticAlgorithm(ObjectCollection& objects, WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window) : objects(objects), workingDir(workingDir), textureAllocator(textureAllocator), window(window)
{
    const unsigned int numOfUFOsToSpawn = 80;
    
    for (int i = 0; i < numOfUFOsToSpawn; i++)
    {
        SpawnUFO();
    }
}


std::shared_ptr<C_NeuralNetwork> GeneticAlgorithm::SpawnUFO()
{
    std::shared_ptr<Object> ufo = std::make_shared<Object>(); // Create new object
    
    auto sprite = ufo->AddComponent<C_Sprite>(); // Add sprite component
    sprite->SetTextureAllocator(&textureAllocator); // This provides the means for the sprite component to load images by name.
    
    const std::string spritePreName = "ufo";
    const std::string spritePostName = ".png";
    const std::string ufoCount = std::to_string(1 + (std::rand() % (4 - 1 + 1)));
    sprite->Load(workingDir.Get() + spritePreName + ufoCount + spritePostName); // Builds random name, can be ufo1, ufo2, ufo3, or ufo4.
    sprite->SetPivot(0.5f, 0.5f);
    
    const sf::FloatRect windowRect = window.GetViewSpace();
    const sf::Vector2u windowSize(windowRect.width, windowRect.height);
    const int minX = 50;
    const int minY = 50;
    const int maxX = windowSize.x - minX;
    const int maxY = windowSize.y - minY;
    const int randX = minX + (std::rand() % (maxX - minX + 1));
    const int randY = minY + (std::rand() % (maxY - minY + 1));
    ufo->transform->SetPosition(randX, randY);

    ufo->AddComponent<C_Velocity>();
    auto sight = ufo->AddComponent<C_Sight>();
    sight->SetObjectCollection(&objects);
    auto neuralNet = ufo->AddComponent<C_NeuralNetwork>();
    neuralNet->SetWindowSize(windowSize);
    
    const sf::IntRect spriteRect = sprite->GetTextureRect();
    auto wrapAround = ufo->AddComponent<C_ScreenWrapAround>();
    wrapAround->SetScreenSize({(int)windowRect.width, (int)windowRect.height});
    wrapAround->SetSpriteHalfSize({(int)(spriteRect.width * 0.5f), (int)(spriteRect.height * 0.5f)});
    
    objects.Add(ufo); // Adds object to game.
    
    return neuralNet;
}

The method is mostly unchanged however it now returns a reference to the created UFOs neural network. We’ll use this later to evolve the newly created UFOs. Don’t forget to remove SpawnUFO from the SceneGame class, we only want our GeneticAlgorithm class spawning UFOs from now on.

We need to instantiate our new GeneticAlgorithm class in SceneGame.

GeneticAlgorith.hpp
#include “GeneticAlgorithm.hpp"
…
class SceneGame : public Scene
{
…
    
private:
…
    GeneticAlgorithm GA;
};
GeneticAlgorith.cpp
SceneGame::SceneGame(WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window) : workingDir(workingDir), textureAllocator(textureAllocator), mapParser(textureAllocator), window(window), GA(objects, workingDir, textureAllocator, window) { }
I’ve also updated SceneGames constructor so that it calls our GAs constructor.
Hopefully, when the game is run there should still be 80 UFOs onscreen. Now let’s add energy levels and a method of removing the UFOs from the game. We’ll do this by adding new components to our UFO in our GeneticAlgorithm class.
GeneticAlgorith.hpp
#include "C_Energy.hpp"
#include "C_DamageOnCollision.hpp"
#include "C_DamageOnWallHit.hpp"

GeneticAlgorithm.cpp
std::shared_ptr<C_NeuralNetwork> GeneticAlgorithm::SpawnUFO()
{
…
    
    ufo->AddComponent<C_Energy>();
    auto wallHit = ufo->AddComponent<C_DamageOnWallHit>();
    wallHit->SetWindowSize(windowSize);
    ufo->AddComponent<C_DamageOnCollision>();
    
    objects.Add(ufo); // Adds object to game.
    
    return neuralNet;
}

We add three new components in SpawnUFO:

  • C_Energy: stores the UFOs current energy and allows us to modify it.
  • C_DamageOnWallHit: reduces energy to 0 when a UFO touches the screen edge.
  • C_DamageOnCollision: reduces energy whenever UFOs are colliding.
For more information on how these components work please see the classes in the Part 4 folder from the GitHub link at the top of the page.
Now our UFOs have an energy level we need to create a pool of UFOs to store the recently removed. To do this we’ll create a structure to store all of the information we require for each UFO in the pool.
GeneticAlgorith.hpp
struct UFOGAData
{
    std::shared_ptr<C_NeuralNetwork> neuralNet;
    std::shared_ptr<C_Energy> energy;
    std::shared_ptr<C_TimeAlive> timeAlive;
};
We also need to provide the GA with an Update function (to loop through every UFO and check if their energy levels have reached 0) and a PoolSort function that will sort the pool so that the UFOs that were alive the longest are at the front of the pool. We’ll need them sorted in this way when we come to select parents from the pool in the next part.
GeneticAlgorith.hpp
class GeneticAlgorithm
{
public:
…
    
    void Update(float deltaTime);
    
private:
        static bool PoolSort(std::shared_ptr<UFOGAData> a, std::shared_ptr<UFOGAData> b); // std::Sort requires static compare function.

    void AddToPool(std::shared_ptr<UFOGAData> ufo);
    
    std::vector<std::shared_ptr<UFOGAData>> pool;
    int maxPoolSize;
…
};
GeneticAlgorith.cpp
GeneticAlgorithm::GeneticAlgorithm(ObjectCollection& objects, WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window) : objects(objects), workingDir(workingDir), textureAllocator(textureAllocator), window(window), maxPoolSize(40) // Set max pool size 
{
…
}

void GeneticAlgorithm::Update(float deltaTime)
{
    std::vector<std::shared_ptr<Object>>& ufos = objects.GetObjects();
    
    for(auto& o : ufos)
    {
        auto energy = o->GetComponent<C_Energy>();
        
        if(energy != nullptr && energy->Get() <= 0)
        {
            auto neuralNetwork = o->GetComponent<C_NeuralNetwork>();
            
            if(neuralNetwork != nullptr)
            {
                std::shared_ptr<UFOGAData> gaData = std::make_shared<UFOGAData>();
                gaData->energy = energy;
                gaData->neuralNet = neuralNetwork;
                gaData->timeAlive = o->GetComponent<C_TimeAlive>();

                AddToPool(gaData);
            }

            o->QueueForRemoval();
        }
    }
}
We have to update the constructor to initialise our maximum pool size. The Update function loops through the UFOs in the game and gets their energy component. If their energy has reached zero we create a UFOGAData structure to store the information we need and add this to our pool collection. Lastly, the UFO is set to be removed from the pool by calling QueueForRemoval.
The AddToPool function is straightforward. It adds the data to the vector, sorts the vector, and then if the pool size is greater than the maxPoolSize the last UFO data is removed. As the pool was sorted before this removal, the last UFO in the vector is also the UFO with the lowest time alive and therefore the most unfit for our purposes.
GeneticAlgorith.cpp
void GeneticAlgorithm::AddToPool(std::shared_ptr<UFOGAData> ufo)
{
    pool.push_back(ufo);
    
    std::sort(pool.begin(), pool.end(), PoolSort);
    
    if(pool.size() > maxPoolSize)
    {
        pool.erase(pool.end() - 1);
    }
}

The comparator function for the sort method uses the UFOs time alive.

GeneticAlgorith.cpp
bool GeneticAlgorithm::PoolSort(std::shared_ptr<UFOGAData> a, std::shared_ptr<UFOGAData> b)
{
    return a->timeAlive->Get() > b->timeAlive->Get();
}
We need to call our new Update function from our SceneGames Update function so that it is called each frame.
GeneticAlgorith.cpp
void SceneGame::Update(float deltaTime)
{
…
    
    GA.Update(deltaTime);
}
If you run the game now you’ll notice the UFOs being removed as their energy levels reach zero, however you’ll also notice that no new UFOs are being spawned so eventually you’ll end up with an empty screen.
Thats all for this part, next part we’ll spawn new UFOs using our Genetic Algorithm. As always, thank you for reading 🙂