This project was an exploration into Genetic Algorithm to train non-playable game objects to move towards a specified object or goal. It was decided to use this learning technique over others as there is no deep learning or machine learning model used with it, which would require a larger implementation and learning time.
The program implemented is a simulation of a duck pond, where the objective of the game objects (ducks) is to get from their spawn point to a specific point at the other end of the pond.
A genetic algorithm works by creating an initial population of random agents and then progresses in steps, or generations. Every generation, the algorithm selects a group of agents in the current population and makes them acts as ‘parents’. The algorithm takes their ‘genes’ and passes them on to the ‘children’, who will be the agents of the next generation. The algorithm works by selecting agents that have better fitness value as the parents to breed the next generation’s population. The fitness and mutation functions can be customised in ways that suit the program/problem.
Mathworks describes the children of the next generation as three categories:
- Elite child; agent of the current generation with the best fitness value.
- Crossover child: creating by combining the genes of the parents.
- Mutation child: created by introducing random changes (mutations).
- Elite child; agent of the current generation with the best fitness value.
- Crossover child: creating by combining the genes of the parents.
- Mutation child: created by introducing random changes (mutations).
The algorithm would create crossover children by combining the fittest agents (parents) in the current population and at each entry of the child vector, the crossover method would select a gene from the same entry as the parent and pass it onto the child. The fitness of a parent is determined by specifying a set of requirements for the agent and then essentially judges how well an agent has met the requirement. Kinnear, the editor of Advances in Genetic Programming, explains that the “fitness function is the only chance that you have to communicate your intentions to the powerful process that genetic programming represents. Make sure that it communicates precisely what you desire.” This process of judging fitness, selecting, mutation and crossover repeats for every new generation.
Ideally this would be expanded into a game that requires NPC’s or other game objects to move independently of the player, such as a racing game with computer-controlled opponent cars, or a game where enemies move towards the player/monuments (i.e. a tower defence). A neural network could also accompany a genetic algorithm however, that implementation would require significantly more computational resources and time, whereas for this program a genetic algorithm alone is substantial.
This program was developed using Unity, and was submitted as part of a project for an AI module.