Quadtree and Flocking Simulation

Flocking

This flocking simulation is based on Craig Reynolds' steering behaviours. Three basic rules are needed to create the effect of units moving in flocks:

  • Alignment: head towards the average direction of nearby units
  • Cohesion: steer towards the average location of nearby units
  • Separation: avoid crowding in one place

The strength of these effects can be manipulated with sliders. The parameter 'A vision' controls the range in which a unit can perceive its neighbours.

The sliders 'fear' and 'containment' and the corresponding 'vision' sliders control how determined a unit tries to stay away from the predator and the edges of the window.

'Steering' adjusts the force with which a unit steers towards its desired direction.

Quadtree

"Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions." [Wikipedia - Quadtree]

Instead of having to run through the locations of every single unit in the window each frame, Quadtrees significantly reduce the number of checks a unit has to make in order to find its closest neighbours. By using a Quadtree for storing locations, only these units have to be checked that are located in Quadtree cells that intersect with the searching unit's vision range.

The parameter 'capacity' refers to the number of units a Quadtree cell can hold before it gets subdivided into 4 smaller cells.

This is a great tutorial on how to implement Quadtrees.

Controls

  • MOUSE CLICK - set predator target
  • P - pause
  • 1 - show/hide Quadtree
  • 2 - show/hide units
  • 3 - highlight one individual unit
  • 4 - show/hide predator's path generation
  • 5 - enable/disable predator
  • 6 - wrap/unwrap walls