Flocking Algorithm crashes on 200+ boids

Question

I'm working on the implementation of a flocking algorithm into a bigger system. OGRE is used for rendering, luabind is used to be able to communicate from LUA, yatta yatta, stuff that shouldn't matter too much.

I implemented the algorithm basically following reynolds' boids-model. That means, one Boid (as in "one fish in a swarm") moves according to it's neighbours in a certain radius. AS things are, the basic complexity of that is O(n²), as every boid has to check all it's flockmates if they are in range and then considers some factors to calculate the own movement.

The algorithm itself is implemented and runs smoothly. It accepts models of all different sizes, it works in 2D and 3D space, it flocks nice etc, I'm working on it for a while already.

My Problem is that the algorithm crashes on runtime as soon as I hit a kind of "barrier" in boid numbers, which is roughly 200-250 and even varies. Now, if it would get slower and slower until I'm broken to 1 fps I could understand that simply performance of the algorithm is the problem. However, for example, 199 boids work perfectly, 201 don't work at all and crash on runtime. This is highly surprising for me.

I implemented 2 classes: "Swarm" and "Boid". Swarm is used to hold pointers to all boids of a swarm but doesn't calculate much, movement happens in Boid.

swarm.h:

#ifndef __SWARM_H__
#define __SWARM_H__

#include <vector>
#include "boid.h"

namespace Core {

    class swarm {

    public:
    swarm();
    ~swarm();
    bool move(float timeSinceLastFrame);
    bool addBoid(boid *thisBoid);
    bool removeBoidByName(std::string boidName);
    bool writeAllBoidNames();
    std::vector<boid*> getFlockMates();

private:
    std::vector<boid*> flock;
    float timePassed;

};

}


#endif

boid.h:

#ifndef __BOID_H__
#define __BOID_H__

#include "Ogre.h"
#include <vector>
#include <stdlib.h>

namespace Core {

class swarm;

class boid {

    public:
        boid(Ogre::SceneNode *thisNode, Ogre::String orientation, swarm *thisSwarm);            // Constructor - direkter Node-Zugriff
        boid(Ogre::MovableObject *thisObject, Ogre::String orientation, swarm *thisSwarm);      // Constructor - Node-Zugriff über das Objekt
        ~boid();                                                                                // Destructor
        Ogre::Vector3 getBoidPosition();                                                        // gibt die derzeitige Position des Boids zurück - nötig für Cohesion und Separation
        Ogre::Vector3 getBoidVelocity();                                                        // gibt die derzeitige Geschwindigkeit und Richtung des Boids zurück - nötig für Alignement
        std::string getBoidName();                                                              // gibt den Namen eines Boids zurück
        bool move(float timeSinceLastFrame);                                                    // bewegt das Boid

    private:
        swarm *flockMates;                                                                      // pointer auf den Schwarm
        float boidSize;                                                                         // die Größe des Boids
        Ogre::Vector3 boidOrientation;                                                          // Grundlegende Orientierung des Meshes eines Boids
        Ogre::SceneNode *boidNode;                                                              // Pointer auf die SceneNode des Boids - das Objekt, das tatsächlich bewegt wird
        Ogre::Vector3 velocity;                                                                 // derzeitige, bzw. letzte Geschwindigkeit

};
}

#endif

As you can see, I'm using a vector of pointers to boid objects in swarm. On runtime, swarm::move() is called, which iterates through the vector and calls boid::move() for every boid.

bool swarm::move(float timeSinceLastFrame) {
    std::vector<boid*>::iterator iter;
    for ( iter = flock.begin(); iter != flock.end(); iter++ ) {
        (*iter)->move(timeSinceLastFrame);
    }
    return true;
}

boid::move is very complex as it calculates the movement based on a lot of things. I will post the points that - imo - actually matter for here, not every single multiplication, as I don't want to bore you with unneeded stuff. Edited: Okay, now you got most of the code here.

bool boid::move(float timeSinceLastFrame) {

    Ogre::Vector3 cohesion = Ogre::Vector3(0, 0, 0);
    Ogre::Vector3 alignement = Ogre::Vector3(0, 0, 0);
    Ogre::Vector3 separation = Ogre::Vector3(0, 0, 0);

    int cohesionCount = 0;
    int alignementCount = 0;
    int separationCount = 0;

    std::vector<boid*>::iterator iter;
    std::vector<boid*> temp = flockMates->getFlockMates();

        for ( iter = temp.begin(); iter != temp.end(); iter++ ) {

        if ( (*iter) != this ) {

            Ogre::Vector3 p1 = boidNode->getPosition();
            Ogre::Vector3 p2 = (*iter)->getBoidPosition();
            Ogre::Real distance = p1.distance(p2);


            if ( distance <= 10*boidSize ) {

                //cohesion
                cohesionCount++;
                cohesion += (*iter)->getBoidPosition();

                //alignement
                alignementCount++;
                alignement += (*iter)->getBoidVelocity();

            }

            if ( distance <= 2.5*boidSize ) {

                //separation
                separationCount++;

                Ogre::Vector3 away = boidNode->getPosition() - (*iter)->getBoidPosition();
                away.normalise();
                away*=boidSize;

                away/=(distance/2);
                separation += away;

            }
        }
    }

    /* do some more stuff */

    /* actually move the boid */
    return true;
};

So, as you can see, the basic algorithm is quite heavy, agreeably. I run through a vector of boids, call a method of each boid which then again runs through the vector. The other calculations are basic, just throwing variables around so that everything looks good, nothing that exponentially increases the complexity.

Now, as already stated, I would expect the rendering to go slow at a high amount of boids. I would expect framerates to drop and so on, but that simply doesnt happen. Instead the algorithm runs perfectly fine with high and fluid framerates until I'm roughly at 200 boids +/-, then crashes instantly as soon as swarm::move() is called.

I already checked several loose ends. The vector container has enough room for >1 billion elements, so its not that. I can also initialise everything with 10000, 20000 boids, so it's not a basic memory allocation problem either. It just crashes as soon as swarm::move() is called.

So, why does this crash with a number of 200 and a few boids? Why doesn't the Framerate drop over time instead? Thanks for any help on this. I think I put up all necessary information, however, if you need additional code (or whatever), feel free to ask.

Additional Information via Edit: It doesn't change if I trigger swarm::move manually via click instead of via framerate. It still works with <200ish boids, it still doesnt work with more.

Edit²: Edited the boid::move() method and noted where the debugger catches the crash. However, it doesn't catch the crash at boid 1, which would make sense to me, but in boid 314 (in this case). So, the algorithm runs perfectly fine through the same vector 313 times and then crashes on the 314th time. Does that make any sense?

Edit³: Interesting enough, Debugging stuff confuses me far more than actually pointing towards where the problem lies. I updated boid::move() again and I'll throw in the code for swarm::getFlockMates, I'll explain why in a second.

std::vector<boid*> swarm::getFlockMates() {
    return flock;
}

What confuses me is the following. After I changed the calculation of the distance to what Ben voigt suggested, the code crashed at the finalized movement with values, that shouldn't crash it. Instead, I had a cohesionCount of 1.x million, while alignementCount and separationCount were still 0. This - again - doesn't make sense at all to me. cohesionCount cannot be higher than the total amount of boids, which is 1000 at the moment (and therefor crashing). Even if all Boids would be in range of the cohesion (distance < 10*boidSize), the maximum of it could not be higher than the total amount of boids stored in Flock.

This beeing said, is there a problem how I iterate my flock?

Answer 1

Turns out, the algorithm I proposed here doesn't have any flaws that did lead to this problem. The memory leak was in one of the Lua-Files I had to use, as this engine (and therefor also this algorithm) is used via that. Thanks for the help nevertheless to all of you!

Answer 2

In chapter 6.14 of his book, Daniel Shiffman proposes some algorithms to increase boid performance. It suggests that they shouldnt loop for all other existent boids, but only those close to it, pretty much like using a Quadtree.

http://natureofcode.com/book/chapter-6-autonomous-agents/