Editing Flocking (section)

== Complexity ==
In flocking simulations, there is no central control; each bird behaves autonomously. In other words, each bird has to decide for itself which flocks to consider as its environment.

A basic implementation of a flocking algorithm has complexity <math>O(n^2)</math> – each bird could potentially interact and respond to every other bird. To limit complexity, it is assumed that birds only interact with a limited number of neighbors spatially in 2D or 3D. This was proven empirically in 2008 by Ballerini et al.,<ref>{{Citation | last1=Ballerini M. | last2 = Cabibbo N. | last3=Candelier R. | last4=Cavagna A. | last5=Cisbani E. | last6=Giardina I. | last7=Lecomte V. | last8=Orlandi A. | last9=Parisi G. | last10=Procaccini A. | last11=Viale M. | last12= Zdravkovic V. | title=Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study | publisher=Proc. Natl. Acad. Sci. | volume=105 | issue=4 |year=2008 | pages=1232–1237 }}</ref> where it was shown that Starlings typically interact with at most seven topological neighbors.

Improvements: 
* Spatial Subdivision.<ref>{{Citation | last=Hoetzlein, R. | title=Fast Fixed-Radius Nearest Neighbors: Interactive Million-Particles Fluids | year=2014 | publisher=GPU Technology Conference}}</ref> The entire area/volume of the flock is divided uniformly. Each bin stores which birds it contains. Each time a bird moves from one bin to another, bin contents are updated. 
** Complexity: <math>O(n k)</math>, k is number of surrounding bins to consider.

Lee Spector, Jon Klein, Chris Perry and [[Mark Feinstein]] studied the emergence of collective behaviour in evolutionary computation systems.<ref>{{cite web | url=http://hampshire.edu/lspector/gecco2003-collective.html | author=Spector, L. |author2=Klein, J. |author3=Perry, C. |author4= Feinstein, M.  | year=2003 | title=Emergence of Collective Behavior in Evolving Populations of Flying Agents | work=Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003) | publisher=Springer-Verlag | access-date=2007-05-01}}</ref>

[[Bernard Chazelle]] proved that under the assumption that each bird adjusts its velocity and position to the other birds within a fixed radius, the time it takes to converge to a steady state is an iterated exponential of height logarithmic in the number of birds. This means that if the number of birds is large enough, the convergence time will be so great that it might as well be infinite.<ref>Bernard Chazelle, ''The Convergence of Bird Flocking'', J. ACM 61 (2014)</ref> This result applies only to convergence to a steady state. For example, arrows fired into the air at the edge of a flock will cause the whole flock to react more rapidly than can be explained by interactions with neighbors, which are slowed down by the time delay in the bird's central nervous systems—bird-to-bird-to-bird.