https://github.com/thatgamesguy/ai_experiments-evolutionThis 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.
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.
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.
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:
- Click on the game engine project in the sidebar.
- Click on Build Settings on the top row.
- In the search bar type “custom compiler flag”.
- In “Other C Flags” enter “-D MACOS”. The Other C++ Flags field will be automatically populated.
On MacOS you will also need to link to the CoreFoundation framework for our custom code to work:
- You can do this on the General tab; you’ll find a section called ‘Linked Frameworks and Libraries’.
- Click on the plus sign.
- Locate CoreFroundation.framework.
- 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.
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.
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. 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.With the images imported, create a new object and add a sprite component.
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. 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!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.
Now we can set the sprites centre as a fraction of its size, which we’ll do in our OnCreate method.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.
Now we can use the window in our OnCreate method to position our UFO.
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. 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. The UFO now moves 50 pixels to the right per second. Exciting!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.
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. With the component complete, we’ll add it to our UFO object. 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. 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. 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:
to: 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 🙂