Genetic Algorithms: Cannon (English)

For the past few days, I have continued to experiment with genetic algorithms. I built a cannon that learns by itself how to hit a target. The logic behind it is the same as in my last post (ML: Hello World). The result, however, is more spectacular.

This time I used the graphical aspects of Construct 3 more. Objectively, the result is more captivating.

The idea is simple: a cannon fires and tries to hit the target. As for Hello World the classic solution is more performing. But it is interesting to understand how to achieve the same result through a genetic algorithm. To begin we decide what to use as genes and then how to compose the chromosome. But first we have to decide how to move the bullets.

In Construct 3 there is a very useful behavior: Bullet. Using it allows us to solve two problems:

1. we can delegate to C3 the management of the “physics of the world”
2. leave some randomness to the movement of the bullets

There are 3 properties that affect the trajectory:

• the shooting angle
• the starting speed
• the acceleration of the bullet

To these features we add two world constraints:

• the force of gravity
• the possibility or not for the bullets to bounce off some elements of the simulation

Knowing this we can create a chromosome containing 3 genes:

1. speed
2. acceleration
3. angle of motion

The next step in the simulation is to throw the bullets and see how they behave. There can only be 2 possible outcomes:

1. bullets are destroyed when they hit an obstacle
2. bullets are destroyed when they hit the target

We can use the distance between the bullets and the target as the basis for calculating the fitness of the chromosome. Then we can select the elements to cross and those to change. During this step I added a condition: if the fitness of a chromosome is less than 1000 then that element will not be changed or destroyed. In this way I bring the generations to stabilize without interrupting the simulation.

That said it’s time to move on to the code. And let’s start by extending an existing class:

export default class RocketInstance extends globalThis.ISpriteInstance {
	constructor() {
		super();
		
		this.behaviors.Bullet.bounceOffSolids = Globals.WorldDefault.bounceOffSolids;
		this.behaviors.Bullet.gravity = Globals.WorldDefault.gravity;
		
		this.ml_Fitness = 9999;
		this.ml_onCreation_speed = 400;
		this.ml_onCreation_acceleration = 400;
		this.ml_onCreation_angleOfMotion = 400;
	}
}

The RocketInstance class extends the Construct 3 Sprite class allowing us to directly access the “native” properties of the object. In the class constructor I set the general rules (gravity and the possibility of bouncing) and the particular ones.

I define the 3 genes of the genome as:

this.ml_onCreation_speed = 400;
this.ml_onCreation_acceleration = 400;
this.ml_onCreation_angleOfMotion = 400;

I also add an ml_Fitness property.

For the randomize, fromDNA and calcFitness functions refer to the repository on GitHub. Let’s look at preserveExperience instead

preserveExperience() {
  const memory = new Experience({
    speed: this.ml_onCreation_speed,
    acceleration: this.ml_onCreation_acceleration,
    angleOfMotion: this.ml_onCreation_angleOfMotion,
    fitness: this.ml_Fitness
  });
  return memory;
}

This function preserves the chromosomes even after the destruction of the bullets. Basically at the time of destruction we execute a code similar to this:

bullet.calcFitness({x,y});
const experience = bullet.preserveExperience();
Globals.Population.generation.add(experience);
bullet.destroy();

The Experience class takes care of performing various operations on the saved chromosomes. Its constructor is simply:

export default class Experience {
	constructor({speed = 400, acceleration = 0, angleOfMotion = 1, fitness = 9999} = {speed:400, acceleration:0, angleOfMotio:1, fitness:9999}) {
		this.speed = speed;
		this.acceleration = acceleration;
		this.angleOfMotion = angleOfMotion;
		this.fitness = fitness;	
	}
}

We can perform 3 operations: crossover, mutate and mutateConservative. Also for these I refer to the code on GitHub.

Finally there is the Population class.

export default class Population {
	constructor() {
		this.members = [];
		this.generationNumber = 0;
	}
}

The methods present are very similar to “Hello World” and can be seen on GitHub.

Turning instead to the code on the C3 event sheet. When starting the layout we execute:

Globals.Population.generation = new Population();
Globals.Population.generation.createRandomGeneration(Globals.Population.size);

Instead when a bullet is destroyed we use

const rocket = g_runtime.objects.Rocket.getFirstPickedInstance();
const target = g_runtime.objects.Target.getFirstInstance();
const {x, y} = target;
rocket.calcFitness({x,y});

const experience = rocket.preserveExperience();
Globals.Population.generation.add(experience);

rocket.destroy();

Finally, to start a new generation, just write

Globals.Population.generation.generation();

That’s all. The code for this project is available on GitHub:

• the project to GitHub
• the online demo
• Patreon