Flock Simulation of Birds

A Comparison Between Two Boid Algorithms

By: Agnes Skattman Udd

Abstract

The aggregated motion of a flock of birds originates from the decisions of individuals in the flock. No bird is leading the flock. Rather each bird follows its closest neighbours and thereby keeping the topology of the flock. Similarly a simulated bird chooses its own course and navigates according to its local perception of the surroundings. Craig W Reynolds was first to introduce this way of simulating birds. He called the simulated individuals boids, and let each individual boid follow three simple rules to decide their movement. The rules were: cohesion – to keep the boid close to its nearby flock mates, collision avoidance – to avoid collision with nearby flock mates and obstacles, and alignment – to adjust the speed and heading to nearby boids. This study evaluates two algorithms based on Reynolds ideas. The study compares the algorithms regarding cohesion, collision avoidance and alignment of boids during grouping, flight in group and when exposed to obstacles. It discusses some issues with these algorithms and suggests improvements.

Sammanfattning

En fågelflocks samordnade rörelse uppkommer av individernas beslut i flocken. Ingen fågel leder flocken, utan varje individ följer sina närmsta grannar. Detta bibehåller topologi i flocken. På samma sätt bestämmer simulerade fåglar sin flygkurs och navigerar enligt uppfattning av omvärlden. Craig W Reynolds var först att introducera detta sätt att simulera fåglar. Han kallade dessa simulerade individer för Boids och lät dem följa tre enkla regler för att bestämma deras rörelse. De tre reglerna var: sammanhållning – för att hålla samman Boids som befinner sig när varann, undvika kollision – för att undvika krockar in i andra fåglar eller hinder, och anpassning – för att anpassa hastighet och färdriktning mellan Boids som befinner sig nära varann.  Denna studie behandlar två algoritmer som baserar sig Craig W Reynolds idéer. Studien jämför algoritmerna med avseende på sammanhållning, undvikande av kollision och anpassning mellan Boids, under gruppering, gruppflygning och möte av hinder. Den diskuterar problem med dessa algoritmer samt anger förslag på förbättringar.