我正在将植绒算法实现到更大的系统中。 OGRE用于渲染，luabind用于能够与LUA，yatta yatta进行通信，这些东西不应该太重要。
我基本上按照雷诺兹的boids模型实现了该算法。这意味着，一个Boid(例如“一群鱼”)会根据其邻居在一定半径范围内移动。实际上，它的基本复杂度是O(n²)，因为每个小鸟都必须检查所有的队友是否在范围内，然后考虑一些因素来计算自己的运动。
该算法本身已实现且运行平稳。它接受所有不同尺寸的模型，可在2D和3D空间中工作，效果很好，等等，我已经在研究了一段时间。
我的问题是，一旦我碰到了一个大约200-250甚至不同的伯德数“障碍”，该算法就会在运行时崩溃。现在，如果它变得越来越慢直到我被破坏到1 fps，我就可以理解，简单地执行算法就是问题所在。但是，例如199个boid可以正常工作，而201个bob则完全不工作，并且在运行时崩溃。这对我来说是非常令人惊讶的。
我实现了两个类:“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
如您所见，我正在使用一个指针 vector 来编排swarm中的对象。在运行时，将调用swarm::move()，它会循环访问 vector 并为每个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;
};
因此，正如您所看到的，基本算法相当繁重，可以接受。我遍历boid的 vector ，调用每个boid的方法，然后再次遍历该 vector 。其他计算是基本的，只是将变量抛出周围，以使一切看起来都不错，没有任何东西以指数方式增加了复杂性。
现在，如前所述，我希望渲染大量的物体时渲染速度会变慢。我希望帧速率下降等等，但是那根本不会发生。取而代之的是，该算法在高且流畅的帧速率下运行良好，直到我大约达到200 boid +/-，然后在调用swarm::move()时立即崩溃。
我已经检查了几个松散的末端。 vector 容器具有足够的空间来容纳超过10亿个元素，因此并非如此。我还可以使用10000、20000个boid初始化所有内容，因此这也不是基本的内存分配问题。只要调用swarm::move()它就会崩溃。
那么，为什么会因为200个和几个伯德而崩溃呢？为什么帧率不会随时间下降？感谢您对此的任何帮助。我想我提供了所有必要的信息，但是，如果您需要其他代码(或其他任何代码)，请随时提出。
通过编辑的其他信息:
如果我通过点击而不是通过帧速率手动触发swarm::move，它不会改变。它仍然适用于
编辑²:
编辑了boid::move()方法，并指出了调试器捕获崩溃的位置。但是，它并没有捕获第1号投标的崩溃，这对我来说是有意义的，而是第314号投标(在这种情况下)。因此，该算法在相同的 vector 上运行313次完全正确，然后在第314次崩溃。这有任何意义吗？
编辑³:
足够有趣的是，调试东西比实际指出问题的根源更使我感到困惑。我再次更新了boid::move()，我将输入swarm::getFlockMates的代码，稍后我将解释原因。
std::vector<boid*> swarm::getFlockMates() {
return flock;
}
让我感到困惑的是以下内容。在将距离的计算更改为Ben voigt建议的值之后，代码在最终移动时使用值崩溃了，这不应该崩溃。相反，我的cohesionCount为1.x百万，而alignementCount和splittingCount仍为0。这又对我完全没有意义。 cohesionCount不能大于boid的总数，该总数目前为1000(因此崩溃)。即使所有Boid都位于内聚范围内(距离
这只蜜蜂说，我如何迭代羊群有问题吗？
最佳答案
事实证明，我在这里提出的算法没有任何导致此问题的缺陷。内存泄漏发生在我不得不使用的Lua文件之一中，因为通过该引擎(因此也使用了该算法)。尽管如此，还是感谢大家的帮助!