Experiments in AI - Evolution Part 1

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.
You can download the source code for the project from the link above. You’ll find a folder for each part of the experiment so you can jump in and follow along. I’ll go through the code in some detail but there is a lot to cover so will brush over some programming concepts to focus on the AI components we are writing. This won’t be a tutorial for anyone that is just beginning to learn how to code.
In this first experiment, we will write an AI that can teach itself to follow a set of rules. In an ideal world, I could write one AI character that could adapt to any environment within the game and provide an engaging experience for the player. While we are a long way from that ideal, this experiment may be a small stepping stone towards it.

We’ll have a number of UFOs in space who are able to avoid each other and the edge of the screen. This would be an easy task by writing a few simple steering behaviours for each UFO to follow but that is not in the spirit of our overall goal, which is:

Have 60+ UFOs onscreen that have taught themselves to avoid each other and the sides of their environment.

In an ideal world, I could write one AI character that could adapt to any environment within the game and provide an engaging experience for the player. While we are a long way from that ideal, this experiment may be a small stepping stone towards it.
To accomplish this we will provide each UFO with a Feed-Forward Artificial Neural Network (ANN) (don’t worry if you’ve never written one before, this is the simplest neural network we can write and a good starting point for our experiments). We’ll evolve these neural networks using a Genetic Algorithm (GA). You can see my previous posts on Neural Networks and Genetic Algorithms for a bit of background although it’s not necessary as I’ll explain everything we need to know.
This series will be split into a number of tutorials:
  • In this tutorial, we’ll draw the UFOs onscreen using SFML and C++. We’ll get them moving around the screen randomly.
  • In parts 2 and 3, we’ll write the neural network. As the neural networks are created in a random state the UFOs will still be moving around randomly.
  • In parts 4, 5, and 6; we’ll write the Genetic Algorithm. At this point, our UFOs should be evolving and become better at the assigned task with each generation.
This tutorial is mostly setup for the next parts so feel free to skip it if you want to focus on the AI. Just start on the next tutorial and use the code from this tutorials folder.
Lets have a quick look at the behaviour we want by the end of this series. At the start of game we would expect the UFOs the be knocking into each other and the edge of the screen as they have not evolved to know any better.
UFOs at the beginning of the game. They bump into each other and the edges of the screen.
However after the UFOs have evolved for a number of generations (more on generations later in the series) we would expect them to maintain separation from each other.
UFOs maintain separation from each other after a number of generations.
While it may not be the prettiest or most functional ‘game’, thats not what we’re aiming for at the moment. We are only interested in the behaviour of our little UFOs.
We’re going to be using the game I am writing as part of my game dev tutorials. You can download the source code from here. Each tutorial has a separate folder. At the time of writing, tutorial 13 (Tilemap Parser Part 1) is the newest so I’ll use that and I recommend you do the same (who knows what I will have broken in future tutorials). The steps to import the code are different depending on your OS. Before you can use the code you need to import SFML, I recommend first following the ‘Getting started’ guides for your particular operating system.
There are a couple of additional steps for compiling in MacOS:
If you are compiling your code within Xcode, you can add a compiler flag by following these steps:
  1. Click on the game engine project in the sidebar.
  2. Click on Build Settings on the top row.
  3. In the search bar type “custom compiler flag”.
  4. In “Other C Flags” enter “-D MACOS”. The Other C++ Flags field will be automatically populated.
A window displaying the custom compiler flags in XCode.
On MacOS you will also need to link to the CoreFoundation framework for our custom code to work:
  1. You can do this on the General tab; you’ll find a section called ‘Linked Frameworks and Libraries’.
  2. Click on the plus sign.
  3. Locate CoreFroundation.framework.
  4. Click Add.
Once everything has been successfully imported, if you run the game you’ll see my logo briefly and then something like the image below.
The game screen. We'll be removing the Viking and tiles shortly.
We can ignore the Viking and the tiles as we’ll be removing them and replacing them with our UFO’s.
A quick note: If you want to change the window size you can do so in the constructor in Window.cpp.
We’ll start adapting the code to our needs by renaming the window.
Game.cpp
Game::Game() : window("AI Experiments 1 - UFOs")
...
We also need to remove everything in the SceneGame.OnCreate method. If you want to know more about the scene structure of the project see this tutorial. But basically we’ll place all of our setup code for the game scene in this function.
Game.cpp
void SceneGame::OnCreate()
{
    // Delete everything in this method.
}
Now if you run the game, and after the splash screen, you’ll see a blank canvas ready for our UFOs.
With the old code removed we can now write the code that will draw our UFOs. You can download the images I use from here, although you can use any image you like. You’ll find four ufo images, rename them to ufo1, ufo2, ufo3, and ufo4. You’ll see why we do this shortly. It doesn’t matter which ufo is 1 and which is 2 etc. I’ve also scaled the images to about 70% of there original size (so we can fit more onscreen). Import those images into your project.
UFOs images added to project.
With the images imported, create a new object and add a sprite component.
SceneGame.cpp
void SceneGame::OnCreate()
{
    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.
}
An object is a uniquely identifiable class that we can add components too. A component is anything that extends an objects functionality in someway. For example, the sprite component provides the ability to draw an image to the screen. For more information on these see: Objects and Components.
We need to tell the sprite which image to load, we’ll do that directly after we add the sprite component.
SceneGame.cpp
void SceneGame::OnCreate()
{
…
    
    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.

    objects.Add(ufo); // Adds object to game.
}
We generate a random number between 1 and 4 and use that as part of the file name. Appending this (pseudo) random number to our file name allows us to alternate between the four UFOs. This is done to provide some variation in the sprites that are shown. The different colours do not represent anything in-game they are used to provide a bit of diversity in our UFOs.
The last line adds the object to the objects collection. You don’t need to worry about that too much, just know that we have to add any object we want updated and drawn to this collection.
If you run the game now you’ll see a ufo in the top left of the window!
Our first UFO.
When we create an object its position defaults to (x=0, y=0). Some of you may have noticed that the UFOs top left point is actually at 0, 0 when really we want it to be the UFOs centre. To accomplish this we’ll add a method to our sprite component.
C_Sprite.hpp
class C_Sprite : public Component
{
public:
…
    void SetPivot(float x, float y);
…
};
C_Sprite.cpp
void C_Sprite::SetPivot(float x, float y)
{
    sf::FloatRect spriteRect = sprite.getLocalBounds();
    sprite.setOrigin(x * spriteRect.width, y * spriteRect.height);
}
Now we can set the sprites centre as a fraction of its size, which we’ll do in our OnCreate method.

SceneGame.cpp
void SceneGame::OnCreate()
{
    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);
    sprite->SetPivot(0.5f, 0.5f); // New call to the method we just created
…
}

We pass in 0.5 for both the x and y values. This sets the sprites pivot to its centre point. Running the game again will (hopefully) show that now the UFOs centre point is at position 0, 0.
Now we have the UFO lets place it in the centre of the window. To get the size of the window we will need to pass the window to our SceneGame.
SceneGame.hpp
class SceneGame : public Scene
{
public:
    SceneGame(WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window);
…

private:
…
    Window& window;
}
SceneGame.cpp
SceneGame::SceneGame(WorkingDirectory& workingDir, ResourceAllocator<sf::Texture>& textureAllocator, Window& window) : workingDir(workingDir), textureAllocator(textureAllocator), mapParser(textureAllocator), window(window) { }
Game.cpp
Game::Game() : window("AI Experiments 1 - UFOs")
{
…
    std::shared_ptr<SceneGame> gameScene = std::make_shared<SceneGame>(workingDir, textureAllocator, window); // We change this line so we pass in a reference to window as well.
…
}

Now we can use the window in our OnCreate method to position our UFO.

SceneGame.cpp
void SceneGame::OnCreate()
{
…
    const sf::Vector2u windowCentre = window.GetCentre();
    ufo->transform->SetPosition(windowCentre.x, windowCentre.y);
}
We’ve loaded our UFO and positioned it in the middle of the screen, now it’s time to get it moving by creating a very simple physics system, which will enable us to exert a constant force on our UFOs. Create a new component called C_Velocity.
C_Velocity.hpp
#ifndef C_Velocity_hpp
#define C_Velocity_hpp

#include <math.h>

#include "Component.hpp"

class C_Velocity : public Component
{
public:
    C_Velocity(Object* owner);
    
    void Update(float deltaTime) override;
    
    void Set(const sf::Vector2f& vel);
    const sf::Vector2f& Get() const;
    
private:
    sf::Vector2f velocity;
    sf::Vector2f maxVelocity;
};

#endif /* C_Velocity_hpp */
C_Velocity.cpp
#include "C_Velocity.hpp"
#include "Object.hpp"

C_Velocity::C_Velocity(Object* owner) : Component(owner), velocity(0.f, 0.f), maxVelocity(80.f, 80.f){}


void C_Velocity::Update(float deltaTime)
{
    owner->transform->AddPosition(velocity * deltaTime);
}

void C_Velocity::Set(const sf::Vector2f& vel)
{
    velocity = vel;
    
	// Clamp Velocity.
    if (fabs(velocity.x) > maxVelocity.x)
    {
        velocity.x = velocity.x > 0.f ? maxVelocity.x : -maxVelocity.x;
    }
    
    if (fabs(velocity.y) > maxVelocity.y)
    {
        velocity.y = velocity.y > 0.f ? maxVelocity.y : -maxVelocity.y;
    }
}

const sf::Vector2f& C_Velocity::Get() const
{
    return velocity;
}
This component provides a method of exerting a constant velocity on our UFO. I won’t go into too much detail about how it works as it is fairly straightforward. It provides an accessor and mutator for the object’s velocity. The mutator also clamps the velocity to ensure it does not exceed a pre-defined amount. The update function on a component is called every frame and adds the current velocity to our position scaled by the delta time.
We’ll add our new velocity component to our UFO in our OnCreate function.
SceneGame.hpp
#include “C_Velocity.hpp"
…
SceneGame.cpp
void SceneGame::OnCreate()
{
…
    
    auto velocity = ufo->AddComponent<C_Velocity>();
    velocity->Set({50.f, 0.f});
}
The UFO now moves 50 pixels to the right per second. Exciting!
Our UFO now moves to the right.
You’ll notice that if the game running for long enough, the UFO it will happily move off the screen and never be seen again. In the final game when the UFO moves offscreen we want it to re-appear on the other side. To do this we’ll create a new component called C_ScreenWrapAround.
C_ScreenWrapAround.hpp
#ifndef C_ScreenWrapAround_hpp
#define C_ScreenWrapAround_hpp

#include "Component.hpp"

class C_ScreenWrapAround : public Component
{
public:
    C_ScreenWrapAround(Object* owner);
    
    void LateUpdate(float deltaTime) override;
    
    void SetSpriteHalfSize(const sf::Vector2i& spriteSize);
    void SetScreenSize(const sf::Vector2i& screenSize);
    
private:
    sf::Vector2i screenSize;
    sf::Vector2i spriteHalfSize;
};

#endif /* C_ScreenWrapAround.hpp */
To do its job our wraparound component needs to know the size of the sprite and the window. It uses this to judge when the centre point of a ufo has moved out of the bounds of the window. LateUpdate is run after the Update method (where the UFO is moved), this ensures the UFO has finished its movement before we check if it has gone off screen.
C_ScreenWrapAround.cpp
#include "C_ScreenWrapAround.hpp"
#include "Object.hpp"

C_ScreenWrapAround::C_ScreenWrapAround(Object* owner) : Component(owner), screenSize(1920, 1080), spriteHalfSize(0, 0) {}

void C_ScreenWrapAround::LateUpdate(float deltaTime)
{
    const sf::Vector2f& pos = owner->transform->GetPosition();
    
    sf::Vector2f newPos = pos;
    
    if(pos.x < -spriteHalfSize.x)
    {
        newPos.x = screenSize.x + spriteHalfSize.x;
    }
    else if(pos.x > screenSize.x + spriteHalfSize.x)
    {
        newPos.x = -spriteHalfSize.x;
    }
    
    if(pos.y < -spriteHalfSize.y)
    {
        newPos.y = screenSize.y + spriteHalfSize.y;
    }
    else if (newPos.y > screenSize.y + spriteHalfSize.y)
    {
        newPos.y = -spriteHalfSize.y;
    }
    
    owner->transform->SetPosition(newPos);
}

void C_ScreenWrapAround::SetSpriteHalfSize(const sf::Vector2i& spriteHalfSize)
{
    this->spriteHalfSize = spriteHalfSize;
}

void C_ScreenWrapAround::SetScreenSize(const sf::Vector2i& screenSize)
{
    this->screenSize = screenSize;
}
With the component complete, we’ll add it to our UFO object.
SceneGame.hpp
#include “C_ScreenWrapAround.hpp"
SceneGame.cpp
void SceneGame::OnCreate()
{
…
    
    const sf::FloatRect windowRect = window.GetViewSpace();
    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)});
}
We retrieve the rect for the window and our UFO sprite and pass that to our newly created wrap around component. If you run the game now you’ll notice that our sprite jumps to the left of the screen and can now happily continue moving right forever.
The last thing we’ll do in this part is spawn a large number of UFOs and have them move around the screen randomly. Lets move all of the code in OnCreate to a separate method called SpawnUFO.
SceneGame.hpp
class SceneGame : public Scene
{
…
private:
    void SpawnUFO();
…
}
SceneGame.cpp
void SceneGame::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::Vector2f 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); // We now set a random start position for the UFO
    
    auto velocity = ufo->AddComponent<C_Velocity>();
    velocity->Set({50.f, 0.f});
    

    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.
}
This code is mostly the same except we now set a random UFO position within the bounds of the window.
We’ll call our new function from OnCreate.
SceneGame.cpp
void SceneGame::OnCreate()
{
    const unsigned int numOfUFOsToSpawn = 80;
    
    for (int i = 0; i < numOfUFOsToSpawn; i++)
    {
        SpawnUFO();
    }
}
Now we can easily set how many ufos to spawn.

The last step is to set a random movement direction for our UFOs. In OnCreate, change:

SceneGame.cpp
    auto velocity = ufo->AddComponent<C_Velocity>();
    velocity->Set({50.f, 0.f});
to:
SceneGame.cpp
    const float maxVelocity = 80.f;
    const float range = maxVelocity * 2.f;
    const float randVelX = range * ((((float) rand()) / (float) RAND_MAX)) - maxVelocity;
    const float randVelY = range * ((((float) rand()) / (float) RAND_MAX)) - maxVelocity;
    auto velocity = ufo->AddComponent<C_Velocity>();
    velocity->Set({randVelX, randVelY});
This will generate a random velocity in the range of -80 to 80 and with that, we now have 80 UFOs moving randomly around the screen. That’ll do for this tutorial, it’s become much longer than I first imagined but by being able to draw and move the UFOs around the screen we have set up the environment for the rest of the series.
Thank you for reading 🙂