So a few weeks ago (how the time flies), I released a little evolutionary based AI car driving simulation, which you can play with here. And I want to take some time to talk through what I did and why, because I think it's pretty cool! Let me be clear, this kind of thing has been done before. But hey, I had fun and that's what's important!
My journey started when (for reasons I can no longer recall) I landed on the wikipedia page for Braitenberg Vehicles. To summarize, a Braitenberg vehicle is a simple machine that has a pair of wheels and some basic sensors. It moves around based on sensor input. For example, a light sensor on each side could be used to turn away from light, by speeding up either wheel depending on which sensor has a stronger reading. This can create interesting patterns and complex behaviour.
I thought that sounded really neat and wanted to see it happen. Now sure, there were a couple YouTube videos and the like. But they were lacking something deep. I wasn't sure what but when I was going to bed that night, it hit me. I wanted to fuck with em. I wanted to move the boxes around and change up the wiring and just play. The videos were all too static. Obviously, I could not play. I did not have the supplies or space to build a bunch of robots. And then I went "hey wait, I could totally simulate this".
First step of any project: choose your tools. I chose Godot engine. I had a couple of good reasons. One is that it has a good reliable physics engine built in which would save me a lot of time. Another is that Godot 4.0 had come out recently and I'd been meaning to play with it. And finally, I knew that Godot has easy export options if I ever finished the project (although that later turned out to be naive, don't expect an html compile of this one any time soon).
Alright so, step 1: draw a car. Two Line2D nodes (the lazy dev's sprites), select the points, colour, done.
Easy.
Then I got talking to a friend and showed her the picture. Her feedback led to this:
And you know what? I stand by that decision.
Now at this point, I had two choices. For the physics, I could either use a RigidBody2D or a KinematicBody2D CharacterBody2D because apparently Godot 4.0 had to rename everything and it took me 20 minutes to figure out what had happened and why I couldn't find a KinematicBody2D in the node list. Anyway, I slapped a CharacterBody2D on there, admired the basic platformer code that was added by default, ripped it out without hesitation, and got to work.
Why a CharacterBody2D? Great question! Because I thought it would be easier. The difference is that a rigid body is fully controlled by the physics engine. It has forces that act upon it, and can spin and slam into walls and bounce back by default. A kinematic character body has to have its every movement custom programmed. I thought that might be easier because it would give me more control over the motion of the car. Dear reader, I am a spectacular dumbass.
It's pretty easy to get a character body moving. It has a function for it, move_and_slide() which takes a vector as input absolutely no input at all, instead using the velocity variable that the body already contains. I'm learning so much about Godot 4.0 already and it only makes me want to claw my eyes out a little bit!
But how do I give my body sensors? Well if I were in 3.x Godot, I would just use RayCast2Ds. So I close my eyes, offer a little prayer to the dark and unpleasant gods of cyberspace, open up the node list, and get blessed. They're still there and they work exactly how I think they do.
A RayCast2D is an arrow that looks a little like this:
It works exactly like you would think. You can detect when something is crossing the arrow. And you can detect how far from the car it is. I started off simple: two arrows, each at a 45 degree angle.
And then it was pretty easy. If one goes off, turn away from it. If both go off, decide by distance. Otherwise, drive forwards. And this...
This was solidly okay.
The car drove. It rarely hit any of the walls I threw up. It kinda just drove in circles mostly. When I drew a big track, it could go most of the way around as long as the turns weren't too tight. Sometimes it would get confused and go backwards.
We had several major problems:
- It couldn't detect objects at many angles, particularly directly in front of it
- It didn't go very fast and when I made it go faster it would hit things more
- Collisions, when they occurred, were unphysical and kind of weird to look at
- Because I had handcrafted its movement, I was handtuning how well it could drive
- I was handtuning how strong its reaction to walls should be and had no idea what the optimal values are
- Multiple cars would often drive into each other because being so small, they often couldn't see each other.
- How long is optimal for the raycasts?
In summary, my physics model was bad, the sensors were bad, and there were a lot of parameters I was guessing at, but did not know.
The physics was an easy fix. Switch the car out for a RigidBody2D, like I should've done from the start. Rigid bodies are a little weirder to control. You have to provide them with forces. And while that will give you a much more accurate and efficient simulation of accelerating, braking, and hitting things than a character body would, there's one small gaping problem. Forces are not taken in relative to the body's rotation. That is, if I input a "forwards" force going left, and then my body rotates upwards, it will keep accelerating left.
This makes sense for almost all cases! The most common force to input is gravity, which should not rotate with the body. But I wanted my accelerating force to rotate with the body and that created problems. Thankfully I already had a solution. I'd been dicking around with a physics based racing game back in Godot 3.x, which I never did anything with because it never quite came together as fun to control. But I had solved this problem there, so I didn't need to solve it again here! The code imported easily, thankfully. I just needed to rename a few things.
The point here is that A) I have a huge stable of abandoned projects (as is normal) and B) having such a stable makes me better at my hobby (as is normal). I feel like that's kind of obvious but I've had at least 3 conversations in the past couple months where people expressed guilt about their own stables and surprise that I had one too.
The final version is the shockingly simple solution of: taking the desired force and rotating it to match the cars current rotation. Kinda makes sense, huh? The only trick is making sure you do it in integrate_forces(state), to prevent the physics engine from fighting you. The specifics of integrate_forces(state) vs _physics_process(delta) are niche and not worth getting into, however.
Alright, physics model solved. Next up: fixing the sensors. And I have an easy and excellent solution in mind for this:
Note that they all come out of the front. I figured that since it should almost always be driving forwards, this was optimal. I didn't want to waste processing time on the back raycasts. I did later add a single backwards raycast to tiebreak with the forward one, but that's it.
I had to change the turning value into an equation now, that dynamically considered every raycast. I'll spare you the tragedy of the 3 hours I spent trying things and weeping at how poorly they handled and give you the final version I settled on: use only the directly forwards and directly backwards casts to decide if driving forwards or backwards. Default to accelerating forwards unless detecting a closer front collision to a back collision. Take an angle weighted sum of the inverse distance to collision on all side raycasts and turn away from which ever collision rates as more imminent.
Not bad. But I still had one problem left: there were a lot of variables to change and while some combinations produced excellent results, others made the car crash frequently. So, I did the only thing I could think to do:
I called it a day and went to sleep.
I had a good system in place at this point. The car could drive and detect walls. It only needed some numbers to decide how fast to drive and how strong the turns should be and so on. And when faced with a lot of numbers that you need to converge to an optimal value, there's only one method I would turn to: sacrificing goats to Satan math!
Now, we could do some boring dumbass optimization with calculus and so on but two problems. A) that would require me to reduce motion to a bunch of equations to solve, defeating the point of having a simulation and B) I had like 6 variables and that's too many variables.
But thankfully, I have taken two different AI courses which makes me completely and fully qualified in all ways to do anything AI related. And I picked my favourite algorithm: the one that we didn't cover in detail and the profs just said "yeah it exists": genetic algorithms!
Sure, at this point I could've googled for a tutorial. But I thought I understood everything, so I could not be bothered and instead took my best guess as to how it's supposed to work.
The basic pitch of a genetic algorithm is to reduce what you're trying to solve to a "genome", which is a collection of numbers you're trying to optimize. Run a bunch of simulations for different genomes, rank them, and then use the top ranking genomes to make more genomes similar to themselves. Easy.
In our case, we ended up with the following variables to optimize:
- number of side ray casts
- length of ray casts
- acceleration power
- breaking power
- turning power
- base linear friction
- base rotational friction
Note that the stats of the car are changeable, not just the internal brain scheme. This allows me to push for the fastest car possible instead of trying to optimize turning for a set speed. As well, the lengths and priorities for all the side raycasts are the same. If I were to do a version 2, I would take a classical linear algebra approach, where each raycast has an associated coefficient for driving, breaking, turning left, and turning right.
I did later add a 8th variable to the genome, which was colour. Colour is an inherited property, so the cars all converge towards the colours of their parents, in a neat visual effect.
Given the genome, the procedure is pretty straightforwards. Set the cars unable to see or hit each other, drive like 100 of them down the track, take the winners and let them breed.
I decided that each number for a child's genome should have a 1/3 chance of coming from each parent and 1/3 chance of being the average of both. The genomes are initialized to be completely random over a very wide range. This approach does tend towards an average middling result, but that's not terrible.
To shake things up a little, we also apply mutations when breeding. Each number in the gene has a small chance of being multiplied by a random number close to 1. This can help it slowly adapt better to the track.
How do we select the winners? We need a scoring system. An obvious and easy rank is total distance travelled. The problem is this gives equal points for going forwards and backwards. An enterprising car might start to drive in circles. So I added a bunch of "gates" to the track, each of which reward the cars for passing them but can only be collected by a given car once.
We want to discourage collisions with the walls, so it's pretty easy to add a penalty that triggers on collision. Finally, we give a huge reward for completing the whole track.
And that's it! There was a bunch of implementation work to do (the most frustrating part of which was getting the lap marker to act as a one way barrier). I slapped some control sliders and informational text on there and called it a day. Done.
Another big question to solve was how much time per generation? The answer was to give them a little bit at the start and then increase the amount of time with each generation. Because no useful training occurs after a car gets stuck, you want to end the generation as soon as possible after every car gets stuck. This approach simulates that efficiently without having to actually figure out when to consider a car 'stuck'.
It isn't without flaws. If not given enough initial time, no cars may reach the first gate. In that case, they may never learn to drive forwards. If the collision penalty is too high, they often learn to not even try driving around the track. I'm pretty sure they overfit to the first section of the track. Moving the start position around randomly or having multiple (possible procedurely generated) tracks would fix that.
But overall, the system works really well. Depending on the values you pick, within 30-50 generations, the cars consistently will be zooming around the track. And I for one, am very proud of that.
So in conclusion, fuck big AI, only do small fun AI. Fuck cars, ride trains and bikes. Fuck amogus, it's a dead meme. Stay awesome, dear readers.
Today's cool link is Jet Lag: The Game! It's a fun game show played over (usually) public transit in various locations and the first episode of the new season went out just yesterday!