The Genetic Algorithm is a Metaheuristic algorithm that takes its ideas from biology. From the iopscience paper, a Metaheuristic algorithm is defined as "High-level strategies that combine lower-level techniques for exploration and exploitation of search space" [1]. To find the shortest path, we slowly minimize the distance between our starting point and our desired end point.

How does it work?

Takes 3 basic ideas from biology: selection, inheritance, and mutation.

Selection:

Initially select some points within the population

Inheritance:

We takes the best "qualities" of our points to help us minimize our path to our desired location.

Mutation:

We take some of our points and randomly change some of its qualities/position to provide some randomness.

We repeat this process until the length of our path converges to an value and that would be our shortest path.

Applications to Video Games

Genetic algorithm is used in things such as AI and player Pathfinding. An Example Game: NERO

NERO

A game made from the University of Texas. The game focuses on an user giving instructions to their robots. Based on the instructions the user gives, the robots will act an certain way. The robots will slowly learn and adapt to improve given the instructions they were told. The University uses the genetic algorithm to help the AI adapt and improve with their given intructions such as better positioning or pathing. [2]