Genetic Algorithm Pathfinding

Project Overview

I started this project to understand the basics of machine learning and to develop my understanding of Processing. The program implements a genetic algorithm for pathfinding around obstacles.

How It Works

1. The user draws a rectangular obstacle on the screen.
2. 800 particles are created with a random set of left, right, up, and down directions that are executed throughout each frame of the generation.
3. Each particle has a velocity that is modified by the set of random directions.

4. At the end of each generation, each particle's "fitness" is measured by its distance from the target in the top right.
5. Particles that hit the obstacle are disabled and their fitness value is set extremely high.
6. The better half of the population (lowest fitness values) is kept for the crossover function.

Crossover and Mutation

In the crossover function:

1. Two particles are picked from the top half.
2. Their "directions" are split at a random point.
3. One part of the directions from each "parent" is used to form a new particle for the next generation.
4. This is repeated until there are enough particles for the next generation.
5. There's a 5% chance that a particle's directions will be modified at one point, adding extra variation.

Results

In each generation, the directions from the best-performing particles eventually spread throughout the entire population, and the average fitness starts to converge rapidly with the best fitness.