NEA computer science project by TomMakesThings - 2017/2018
This application runs a custom genetic algorithm that optimises generations of stick figures so that over time they improve at navigating obstacles including spikes, pits, and caves. The code was written in Python 3.5 and GUI displayed using Tkinter.
| Term | Explanation |
|---|---|
| Genetic algorithms | Heuristic search algorithms that use techniques inspired by natural selection, including selection, mutation and inheritance |
| Generation | The population of stick figures in each iteration |
| Genotype | The set of properties, in this case actions, that can be mutated and altered |
| Crossover | Combining genomes from two stick figures |
| Mutation | A random change the genotype, such as swapping one attribute for another, addition or deletion |
At the start, the initial population of non-playable stick figures are created with the aim that over time their descendants will learn to navigate their way around obstacles placed within the environment. Each is assigned a unique genotype consisting of randomly generated actions including: walk, jump, stand. These are encoded as 'W', 'J' or 'S' retrospectively. The most successful individuals of this population then pass their genotypes to offspring through crossover and mutation.
In each generation, stick figures start with 100 health. Their ID, distance travelled and remaining health are displayed in a table that is updated as the simulation progresses. If a stick figure collides with an obstacle, they will loose health as follows:
- Walking into a pit causes 100 damage causing that individual's turn to end
- Walking into a spike causes 25 damage
- Jumping while walking through a cave causes 5 damage
The simulation will end once at least one individual from a generation reaches the end of the obstacle course.
Flowchart of stick figure life cycle
➊ Download the code from the repository
➋ Extract the contents of the zip
➌ Open a terminal with Python installed
➍ Navigate to the folder of the code
➎ Run python Simulator.py
The number of obstacles in the environment and individuals in each generation can be configured by editing parameters at the top of Simulator.py
obstacleNumber = 100
generationSize = 10