Path Finding AI using Genetic Algorithm in Unity - Tutorial Part 3

In Part 3 of this series, we will create environments and creatures and learn how to run them using the networks and algorithms from Part 1 and 2.

Creating environment

For simplicity, we will first create an environment in a 2D scene -- although implementing it in a 3D scene should be similar. The creatures in our simulation must complete a track with different types of obstacles. The obstacles, creatures, and the goal should have separate layers to distinguish their collision bounds.

Creating Creatures

To control the creature, let's create a PathFinder class by inheriting data from Creatures class. We created the Creature class in Part 2 to interact with the Genetic Algorithm (GA). This creature senses its surrounding with 5 eyes. These eyes cast a ray to detect obstacles in front of it. By using raycasting, we can get the distance of the obstacles in front of the creature. A layer mask is then used to detect objects that exist only in the obstacle layer. Be sure to exclude the creature layer, as we are not trying to avoid each other. The distance of the obstacle from each eye will be used as input for the Neural Network (NN) model.

public class PathFinder: Creatures {
  public Transform eye_mid, eye_midLeft, eye_midRight, eye_Left, eye_Right;//position of eye
  public float eyeRange;// maximum range of eye

  private void FixedUpdate() {
    if (isRunning) {
      float[] input = new float[5];
      transform.position += (transform.rotation * Vector2.up * (Time.fixedDeltaTime * moveSpeed));
      input[0] = Physics2D.Raycast(eye_Left.position, eye_Left.transform.up, eyeRange).distance;
      input[0] = input[0] == 0 ? eyeRange : input[0];
      input[1] = Physics2D.Raycast(eye_midLeft.position, eye_midLeft.transform.up, eyeRange, hazardLayer).distance;
      input[1] = input[1] == 0 ? eyeRange : input[1];
      input[2] = Physics2D.Raycast(eye_mid.position, eye_mid.transform.up, eyeRange, hazardLayer).distance;
      input[2] = input[2] == 0 ? eyeRange : input[2];
      input[3] = Physics2D.Raycast(eye_midRight.position, eye_midRight.transform.up, eyeRange, hazardLayer).distance;
      input[3] = input[3] == 0 ? eyeRange : input[3];
      input[4] = Physics2D.Raycast(eye_Right.position, eye_Right.transform.up, eyeRange, hazardLayer).distance;
      input[4] = input[4] == 0 ? eyeRange : input[4];

      SendInputToBrain(input);
    }
  }
}

This creature is set to move at a constant speed in the direction it is facing. The only thing it will be able to control is the rate at which it can turn left or right. After sending input from the eye to the NN model, we will get an output in GotResultFromBrain method. As there is only one parameter we can control, only one output value is required to control the creatures.

public float steerSpeed;
public float moveSpeed;

protected override void GotResultFromBrain(float[] output) {
  float turn = output[0] * 2 - 1;
  transform.Rotate(Vector3.forward * turn * steerSpeed * Time.fixedDeltaTime);
}

For detecting collisions, we will use 2D colliders. I am using a polygon collider here because my creature is in triangle shape but you can use any type of 2D collider per your needs. Also, add a Rigidbody2D value to the creature so it can detect collision. Set the physics setting such that the creature collider will only collide with obstacle and goal colliders. Success/failure is called depending upon the type of collider it collided with. The creature will stop in both cases.

private void OnCollisionEnter2D(Collision2D other) {
  if (!isRunning) return;
  int collidedObjectLayerValue = 1 << other.gameObject.layer;
  if (collidedObjectLayerValue == hazardLayer) {
    StopCreature();
    OnFailed();
    return;
  }

  if (collidedObjectLayerValue == goalLayer) {
    StopCreature();
    GoalReached();
  }
}

As shown above, we have a creature with 5 inputs and 1 output. I am using 4 nodes in the hidden layer for this example.

Now, create a prefab of a creature with these specifications so that they can be instantiated in the scene.

Creating the Creature Manager

To manage all the creatures in the system, let's create a CreatureManager class. It will be responsible for initializing creatures, checking and handling the state of the creature, and creating new generations of offspring. This will also keep track of the score of all creatures i.e. the fitness of a creature. We are creating the following properties for this management system:

• startPoint : Creatures will start from this position facing the direction controlled by the transform value.
• numberOfCreatures : The number of creatures in a generation.
• creatures : The array of instantiated creatures.
• creaturePrefab : The prefabs of a creature.
• creatureScore : The score obtained by a creature at the end of a generation.
• numberOfCreaturesActive : The number of creatures currently active in the program. A creature will stop if they hit an obstacle or reach the goal. So, when the number of active creatures in a run is 0, a generation is completed. Then, we will start a new generation.

public class CreatureManager: MonoBehaviour {
  public Transform startPoint;
  public int numberOfCreatures;
  public Creatures[] creatures;
  public Creatures creaturePrefab;
  public float[] creatureScore;
  private bool _isRunning;
  public int numberOfCreaturesActive = 0;
}

We need to track the time passed since the start of generation as well because it will be used to calculate the score.

public float counter;

private void Update() {
  if (_isRunning) {
    counter += Time.deltaTime;
  }
}

We will now start the simulation by generating creatures and running them. A unique Id will be assigned for each creature. We will listen to the success and failure event for every such creature.

A fitness function will award a higher score for creatures who survive for the longest time. It will also add a large amount to the score when the creature reaches the goal. As the goal is reached, the time taken to reach the goal will be deducted so that faster creatures will get higher scores. Using this method, creatures will first learn to avoid obstacles and survive longer at the starting phase. Eventually, they will start learning how they can reach the goal faster.

void StartWorld() {
  creatureScore = new float[numberOfCreatures];
  GenerateCreatures();
  StartAllCreatures();
}

//initialize creature at first generation only. Reuse for other generation
void GenerateCreatures() {
  creatures = new Creatures[numberOfCreatures];
  for (int i = 0; i < numberOfCreatures; i++) {
    Creatures creature = Instantiate(creaturePrefab, startPoint.position, startPoint.rotation);
    creature.InitializeCreature();
    creature.id = i;
    creature.onGoalReached.AddListener(OnGoalReached);
    creature.onFailed.AddListener(OnFailed);
    creatures[i] = creature;
  }
}

void StartAllCreatures() {
  for (int i = 0; i < creatureScore.Length; i++) {
    creatureScore[i] = 0;
  }

  foreach(Creatures creature in creatures) {
    creature.transform.SetPositionAndRotation(startPoint.position, startPoint.rotation);//move to start point
    creature.StartCreature();
  }

  _isRunning = true;
  numberOfCreaturesActive = creatures.Length;
}

private void OnGoalReached(int id) {
  numberOfCreaturesActive--;
  creatureScore[id] = 5000 - counter;//give high reward for creatures reaching goal.

//start new generation if all dead
  if (numberOfCreaturesActive <= 0) {
    AllCreaturesTaskComplete();
  }
}

private void OnFailed(int id) {
  numberOfCreaturesActive--;
  creatureScore[id] = counter;//when failed, creature will get score equal to time they survived.
  
  //start new generation if all dead
  if (numberOfCreaturesActive <= 0) {
    AllCreaturesTaskComplete();
  }
}

When all of a creature's tasks are completed, we take their chromosomes and feed them to the GeneticAlgorithm to get the gene for their offsprings. We will set the selection chance and mutation chance values for their offspring as shown below. Then, a new generation can be started from the obtained chromosome.

private void AllCreaturesTaskComplete() {
  counter = 0;
  _isRunning = false;
  float[][] parents = new float[numberOfCreatures][];
  //get gene of parents
  for (int i = 0; i < parents.Length; i++) {
    parents[i] = creatures[i].GetBrainData();
  }
  //get offspring genes
  float[][] offsprings =
    GeneticAlgorithm.GeneticAlgorithm.GetOffsprings(parents, creatureScore, new [] {
      .4 f, .2 f, .2 f, .1 f, .1 f
    }, .01 f, numberOfCreatures);
  //create ofsprings
  for (int i = 0; i < numberOfCreatures; i++) {
    creatures[i].SetBrainData(offsprings[i]);
  }
  //run offsprings
  StartAllCreatures();
}

Considerations for Designing the Level

• Take the movement and turn speed of the creature into account. We must allow enough space for the creature to move, but not too large a space as creatures can sometimes turn back and move in the opposite direction.
• Make the difficulty of the track gradually harder instead of starting at the hardest track. Presenting creatures with a hard track from the beginning will confuse them, hence slowing their learning process.
• Interactions (collision and detection) between creatures are disabled in this example but you can try experimenting with it by allowing such interaction.

Demo

Up to now, we have created 3 modules: a Neural Network as a model, a Genetic Algorithm as a cost-minimizing function, and creatures/environments as a system. For a machine learning system, these modules can be exchanged with other modules. As an example, for a pattern recognition system, the GA function can be switched with Gradient Descend and Back Propagation functions instead.

To implement the AI in the game we can just take chromosomes from the best creature and apply it to the model. The learning system itself doesn't need to be included in the game.

Meet you in the next one. Please leave comments if you have any queries.