植绒算法在200多个boids上崩溃

Question

我正在研究将植绒算法应用到更大的系统中.OGRE用于渲染,luabind用于能够从LUA,yatta yatta进行通信,这些东西不应该太重要.

我基本上按雷诺'boids-model实现了算法.这意味着,一个Boid(如"群中的一条鱼")根据它在某个半径内的邻居移动.事情就是这样,它的基本复杂性是O(n²),因为如果它们在范围内,每个boid都必须检查所有它们的flockmates,然后考虑一些因素来计算自己的运动.

算法本身实现并运行顺畅.它接受所有不同尺寸的模型,它可以在2D和3D空间中工作,它很好吃,我已经有一段时间了.

我的问题是,当我在boid数字中遇到一种"障碍"时,算法会在运行时崩溃,大约200-250甚至变化.现在,如果它变得越来越慢,直到我被打破到1 fps,我就能理解,算法的简单性能就是问题所在.但是,例如,199 boids完美运行,201根本不工作并且在运行时崩溃.这对我来说非常令人惊讶.

我实现了两个类:"Swarm"和"Boid".Swarm用于保存指向swarm的所有boid的指针,但计算不多,在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

正如你所看到的,我正在使用一个指针向量来插入swarm中的对象.在运行时,调用swarm :: move(),它遍历向量并为每个boid调用boid :: move().

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非常复杂,因为它根据很多东西来计算运动.我将发布 - imo - 在这里实际上很重要的点,而不是每一次乘法,因为我不想让你厌烦不必要的东西.编辑:好的,现在你已经获得了大部分代码.

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;
};

所以,你可以看到,基本的算法是相当沉重的,愉快.我运行了一个boids向量,调用每个boid的方法然后再次遍历向量.其他计算是基本的,只是抛出变量,以便一切看起来都很好,没有任何指数增加复杂性.

现在,正如已经说过的那样,我希望渲染在大量的boid中变慢.我希望帧率下降等等,但这根本不会发生.相反,算法在高和流畅的帧速率下运行得非常好,直到我大约200个boids +/-,然后一旦调用swarm :: move()就会立即崩溃.

我已经检查了几个松散的结尾.向量容器有足够的空间容纳超过10亿个元素,所以不是这样.我还可以使用10000,20000个boid初始化所有内容,因此它也不是基本的内存分配问题.一旦调用swarm :: move(),它就会崩溃.

那么,为什么这会导致200和几个boids崩溃？为什么帧率没有随着时间而下降？感谢您的帮助.我想我提供了所有必要的信息,但是,如果你需要额外的代码(或其他),请随时提出.

通过编辑的附加信息:如果我通过点击而不是通过帧率手动触发swarm :: move,它不会改变.它仍适用于<200ish boids,它仍然无法使用更多.

编辑²:编辑boid :: move()方法并记下调试器捕获崩溃的位置.然而,它并没有捕获到boid 1的崩溃,这对我来说是有意义的,但是在boid 314(在这种情况下).因此,该算法在相同的向量上运行313次,然后在第314次崩溃.这有任何意义吗？

编辑³:有趣的是,调试内容让我感到困惑,远远超过实际指向问题所在.我再次更新了boid :: move(),我将抛出swarm :: getFlockMates的代码,我将在一秒钟内解释原因.

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

令我困惑的是以下内容.在我将距离的计算更改为Ben voigt建议的内容之后,代码在最终的运动中崩溃了,值不应该崩溃.相反,我有一个1.000百万的cohesionCount,而alignementCount和separationCount仍然是0.这再次 - 对我来说根本没有意义.cohesionCount不能高于boids的总量,此刻为1000(因此崩溃).即使所有Boids都在内聚力范围内(距离<10*boidSize),它的最大值也不能高于Flock中存储的boid总量.

这个说法,我是如何迭代我的羊群的？

Answer 1

事实证明，我在这里提出的算法没有任何导致此问题的缺陷。内存泄漏发生在我必须使用的 Lua 文件之一中，因为该引擎（因此也是该算法）是通过该文件使用的。尽管如此，还是感谢大家的帮助！