This is a computational intelligence car evolution project, a replica of BoxCar2D made entirely in Processing and a Java wrapper by Daniel Shiffman for the Box2D physics engine.
Each car consists of one central vertex and eight other vertices at random distances from the central vertex. Each triangle so formed is initialized as a separate Box2D body to allow concave polygons. Each vertex has a 60% probability of spawning a wheel. The radius of the wheel is also selected at random. Wheels are built from the CircleShape class of Box2D and have a density and friction of 1 and a coefficient of restitution of 0.5
The DNA consists of 36 values between 0 and 1. Let's divide the DNA array into sequences of 4 elements. These four elements together make up the properties of a vertex. The first 32 elements thus encode the genetic information for the eight vertices. The last four elements decide the color (R, G, B, A values). The first two elements of a vertex encode the magnitude and direction of the position vector relative to the fixed origin. The third element decides whether the vertex gets a wheel. The fourth element decides the radius of the wheel if any.
The surface (or the track) is built using the ChainShape class in Box2D. The vertices for the chain shape are generated procedurally using Perlin Noise. The surface is the same for all genomes of a population to maintain even difficulty for all genomes. It is changed after every population though. As the track progresses, the offset of the perlin noise function is changed due to which, the later parts of the track becomes more bumpy and difficult to maneuvre.
Each car has a DNA sequence which is optimized over using a Genetic Algorithm. Each generation has 20 genomes. The fitness is calculated by distance of travel. Fitnesses are mapped to the DNA and these DNA arrays are selected according to their weights and a mating-pool is generated. Two random elements from the mating pool are selected. Care is taken to prevent both genomes being identical. There is a choice between split recombination and uniform recombination. By default, the DNA is split into two parts only.
Clicking discards the current genome. This can be useful to manually set up the first generation. If the first generation is manually set up, the algorithm will converge sooner. If a car is stationary for 300 frames, it will be discarded automatically.
This program demonstrates how a population of rockets can be taught to meander around an obstacle using genetic algorithms. Is it deployed here
Each rocket consists of an origin vertex, where all the forces are applied. An arrow-like shape is drawn around this origin, to resemble a rocket.
Each rocket lives for 400 frames and hence the DNA consists of 400 vectors, one for each frame. The corresponding vector is applied as a force to the rocket at each frame.
The DNA sequences thus obtained are subjected to optimization using a genetic algorithm in order to create an array of vectors (the physics vectors) that would lead the rocket to the target circle at the top of the screen.
This program is a variation of the Smart Rockets example where the rockets are left in an agar.io like environment where each rocket tries to survive by eating green pellets (+health) and avoiding the red ones (-health). Health decreases every frame by a small amount. The rocket with the perfect balance of speed, visibility range and steer torque survives the longest. It is deployed here
Each rocket consists of an origin vertex, where all the forces are applied. An arrow-like shape is drawn around this origin, to resemble a rocket.
Each DNA sequence consists of four elements. The first element encodes the affinity of the rocket towards the food (green particles), the second element encodes the affinity towards the poison (red particles), the third and fourth elements encode the visibility ranges for food and poison respectively.
The movement of the rockets is based on Craig Reynolds' work on steering behaviors. Specifically, the rockets use the seek behavior to reach a target, where the direction of motion is a fraction of the actual required direction vector. This allows for more smooth and natural-looking movement.
The DNA sequences obtained are subjected to optimization using a genetic algorithm in order to find the set of parameters that enable a particular rocket to survive the longest. The genetic algorithm in this example is an example of mitosis, ie, recombination doesn't require two parents, instead, if an individual survives for long, it generated two copies of itself, one with a mutation rate of 1% and another with a mutation rate of 50%. This helps prevent convergence into local optima.
This is the link to the actual project.
The environment, created on Unity-C#, consists of a track on an island. The track is marked with waypoints. Cars can run on the tracks following the waypoints. Each car tries to steer towards the next closest waypoint. A function similar to the seek behavior by Craig Reynolds is used to handle the steering of the cars.
Each DNA sequence contains 18 optimizable variables. Each element handles a physical property of the car. The 18 variables are:
- maxSteerAngle
- topSpeed
- maxMotorTorque
- maxBrakingTorque
- centerOfMass.y
- Mass
- sensorLength
- sensorSkewAngle
- 4WheelDrive?
- 4WheelBrake?
- 4WheelTurn?
- switchToNextWaypointDistance
- sense()?
- brakingConditions1
- brakingConditions2
- avoidMultiplier parameter
- lerpToSteerAngle?
- turningSpeed The use of some of these variables will be apparent only after looking at the source code.
A modified genetic algorithm is used to optimize over the DNA sequence in order to find the set of parameters that allow a car to achieve the lowest track time. The lowest time recorded yet was about 16 seconds.
