I was inspired to start this project after stumbling across Smart Rockets. The long of the short of it is that this program spawns a random group of spaceships that all have to navigate their way to a target. This is not done via a path finding algorithm, but rather a genetic algorithm. The first generation starts of with a random set of instructions to follow, and this guides the spaceships in the corresponding directions. Once all of the rockets, crash a new generation is spawned, this time with instructions made by "mating" pairs of spaceships from the previous generation. This process continues forever and you will find that eventually all of the rockets go from flying around the screen aimlessly to effortlessly gliding straight to the target, avoiding all obstacles.
Algorithms have always been an interesting topic to me, but I have never really worked with them in any capacity. So I thought that it would be a good idea to take this existing project and put a little spin on it. The original Smart Rockets project is 2D, so naturally I wanted to make this project difficult and make it 3D. So I booted up Unity and got straight to work.
Before I began coding, I had to first research genetic algorithms and review how I would go about programming my own version.
A genetic algorithm is a metaheuristic that is inspired by Charles Darwin and his work on natural selection. This being said, the mechanics of selection, crossover, and mutation are implemented in this problem. The streamlined process for the algorithm is:
- Simulate the current generation of rockets
- Determine the fitness of each rocket
- Breed new generation of rockets
In my implementation, this process will repeat forever until the user input is detected, telling the program to stop running. Now we need to understand how the processes of selection, crossover, and mutation fit into this three step process.
The process of selection is the most complicated part of this algorithm. Each rocket instance has DNA, a Vector3 list, that is used to add Torque to the rocket. This is what steers/rotates the rockets in various directions. Since I am using the fitness proportionate selection genetic operator in this algorithm, each rocket must be evaluated and a numerical value must be attributed to them in order to determine how likely they are to be selected as parents to breed the next generation.
We will call this value the fitness of the rocket.
There are tons of ways to determine the fitness of a rocket. In my implementation, I decided that it was best to determine the fitness based on the distance from the target on the last frame of the generation. In addition, I added some modifiers to make the algorithm more efficient:
- The base fitness is 1 / distance
- If the rocket crashes into an obstacle, divide the fitness by 10
- If the rocket makes it to the target, multiply the fitness by 10
- If the rocket makes it to the target before any other rockets, multiply the fitness by 2
Now that we have calculated the fitness of each rocket, we must normalize all of these values. This allows us to have consistent fitness values, between 0 and 1, for all rockets. This is done by taking the maximum fitness value and dividing it by each rockets fitness.
The last step in the selection section of the algorithm is to establish the mating pool. This is where we will extract our parents and breed them during the crossover section. The mating pool is simply a list of rocket objects. First we iterate through each rocket in the current generation, and add it to the mating pool based on its fitness times 100. If a rocket has a fitness of 0.5, it will be added to the mating pool 50 times. This makes it more likely to be randomly chosen in comparison to a rocket with a fitness of 0.1 which would only appear in the mating pool 10 times. Once the mating pool has been established we can now move on to creating our new generation of rockets.
During the crossover section of the algorithm, we randomly choose two parents from the mating pool, combine their DNAs, and create a new rocket object with this newly constructed DNA. I make sure that the two chosen parents are not the same rocket (since I am unsure if rockets are asexual or not), then I iterate through both parent DNAs and randomly choose an instruction for each index. Here is a rough illustration of what the crossover process looks like.
Once the current generation has mated enough to replace themselves, we now move on to the last stage of this algorithm.
Mutation is an integral part of any genetic interaction. In real life, mutation has its pros and cons; Mutation can lead to organisms developing immunity to some harmful bacteria, or it can lead to the development of cancer. In this simulation, mutation allows for subtle variations in rocket DNA which can help a generation if it is stuck on an obstacle, or cause a generation to run into more obstacles than usual. After each child has been bred, we now call the mutation function on their DNA and this has a very small chance of changing an existing instruction to a randomly generated instruction.
Now that we have created a new generation, we simulate it, and repeat the process until eventually all of the rockets reach the target.
Implementation in Unity
I had no clue how I would implement this algorithm in Unity.
After much testing, I decided to have a populationControl script attached to the floor of the scene. This keeps track of the current generation of rockets, evaluates the fitness of each rocket in the generation, and handles the breeding process. This is also the brains of the algorithm and allows everything to run.
Attached to each Rocket prefab is a Rockets script that holds the information for the rocket's DNA and has the functions that add forces to the rocket, calculate the fitness, handle the crossover process of DNA, and handle the mutation process along with other various accessor and mutator methods.
One Small Problem
One of the most important things in this project is that the paths that the rockets take are consistent. Before crossing and mutating the DNA, I wanted to make sure that a rocket would take the same path every time. I added a Constant Force object to the prefab, and changed the torque and the upwards force, but this happened to be problematic. I believe since I was changing the values so much on a CONSTANT force component, this was causing issues. I tried updating these values in both the Update and FixedUpdate functions to no avail (these functions will come into play later). So I just decided to use a rigidbody, which allows objects to receive forces and makes physics handling simple, and used AddForce and AddTorque to propel and rotate the rockets respectively. But still after much debugging and testing, I was getting inconsistent paths still. It made no sense.
After deleting all of my code and restarting out of frustration, it all became clear to me.
The Difference Between Update and FixedUpdate
In Unity there are two main functions that are called consistently and handle calculation, physics, etc. These functions are Update and FixedUpdate.
The Update function runs once per frame and is used for most general operations and calculations.
The FixedUpdate function can run zero, one, or many times per frame and is used for physics calculations.
Of course I had not been paying attention and typed all of my physics instructions into the Update function. This is a big problem because Update is frame dependent whereas FixedUpdate is not and all calculations are guaranteed to be in sync with the physics engine itself.
Once I squashed this bug, it was all smooth sailing.
Once I finished implementing the algorithm as stated above and fixed all major bugs, I had to make my project look more professional. I installed some rocket prefabs from the Unity asset store along with some textures and skyboxes to make the scene look like it was taking place in another galaxy somewhere in the astros.
The project went from looking like this:
To looking like this:
The final step in this process was creating a user interface; allowing the user to manipulate different variables and test the algorithm on different obstacles while being able to choose from different rockets with varying physical traits. Here is the finished project.
You can find all of the code for the project here.
Overall this was a very fun project and a good use of time over my spring break. I really do look forward to working with more algorithms and seeing how I can add my own little twist to them. For now I leave you with a link to a short video demo of my project.
Subscribe to CSTHINGS
Get the latest posts delivered right to your inbox