Nevin
Menu
Back to Project Log
[Complete]

Pathfinding Using Genetic Algorithm

A research project on pathfinding with a genetic algorithm, breeding paths over generations on a Unity grid.

Project Overview

This is a Unity research project on pathfinding with a genetic algorithm. You click to set the start, the exit and any walls on a 20x20 grid, then run it. Each frame draws the path held by the fittest genome found so far, and the search stops once a genome reaches the exit.

Key Features

  • Two-bit genes: A chromosome is a string of bits, and each two-bit gene decodes to one of four directions. Decoded end to end, it is one long walk out of the start.

  • Fitness by distance: A genome scores 1 / (|dx| + |dy| + 1) against the exit, so a walk that ends closer scores higher. The run stops the moment a genome lands on the exit.

  • Breeding loop: Roulette-wheel selection picks two parents with a probability set by their fitness. Single-point crossover swaps their bits at a random point about 70% of the time, and bit-flip mutation then edits the children.

  • Inspector tuning: Population size, mutation rate and chromosome length are set in the inspector, so runs with different settings can be compared.

SYS_SPECS

Language:
C#
Technology:
Unity3D
Platforms:
Windows, Linux