Predator-Prey Simulator (Flocking, Obstacle Avoidance & Pursue Steering Behaviors)
It is basically a Predator-Prey Simulator.
- We can control the predator with our mouse (The predator seeks the cursor).
- The prey try to run away from the predator (evade).
- At the same time, they try to stay together (flock).
- They also avoid obstacles (obstacle avoidance).
This is a game in which Tanks collect mines. Genetic Algorithm is used to train the tanks to collect more mines.
- Selection: Roulette wheel selection was used for selection of parent chromosomes to produce offspring, wherein individuals are given probabilities that are directly proportional to their fitness.
- Crossover: Single point crossover technique was used wherein you choose a locus at which you swap the remaining alleles from one parent chromosome to the other.
- Mutation: In order to ensure that the individuals are not all exactly the same, you allow for a small chance of mutation wherein, you loop through all the alleles of all the individuals, and if that allele is selected for mutation, you can either change it by a small amount or replace it with a new value.
A game of 6 x 6 tic- tac- toe, with each line of 4 X's or O's scoring a point until every space is filled.
- Score Evaluation: The 6 x 6 grid was divided into 9 overlapping smaller (4 x 4) grids. This helped in reducing the win patterns.
- Win Patterns: 16 bit win patterns were used to check whether each smaller 4 x 4 grid had a win pattern.
Flocking (Steering Behavior)
Flocking model consists of three simple steering behaviors which describe how an individual boid maneuvers based on the positions and velocities of its nearby flock mates:
- Separation: Steer to avoid crowding local flock mates. This is the negative of steering vector resulting from adding the relative position vectors of the local flock mates.
- Alignment: Steer towards the average heading (forward vector) of local flock mates.
- Cohesion: Steer to move toward the average position of local flock mates.
- I have added a pursuer AI entity into the system. The flocking AI evade the pursuer while continuing to flock.
Path Finding & Following
- Path Finding:
- A* algorithm was used wherein the distance from the start point (Dijkstra’s Algorithm) and the estimated distance to the goal point (Greedy Best-First Search) are added to find the shortest distance.
- 4 types of nodes were used with different costs.
- Path Following:
- Entity performs "seek"-like steering for the intermediate nodes along the path, and "arrival"-like steering for the goal node.
- The velocity of the entity is affected by the node's cost.
Obstacle Avoidance (Steering Behaviour)
- This steering behavior anticipates the vehicle's future path as indicated by the black box. The length of the box is a constant time multiplied by the current velocity of the vehicle.
- Lateral steering force: The nearest obstacle intersecting the black box is chosen for avoidance and a lateral force is applied in the direction opposite to the obstacles's center. This force varies linearly with the urgency (the distance from the tip of the black box to the point of potential collision)
- Braking (deceleration) force: This force is directed opposite to the velocity direction and varies quadratically with urgency.
Pursue & Evade (Steering Behavior)
- The green vehicle pursues the gray "drone" vehicle, while the red vehicle evades it.
- The green pursuing vehicle uses seek behavior to approach the estimated target position (calculated based on the position, velocity, and its distance to the pursuer (or evader)), while the red evading vehicle uses flee to escape from it.
- The steering force is the result of the desired velocity subtracted by the current velocity (acceleration is rate of change of velocity).