c++ - 通过在 C++ 中以随机角度绘制线来扫描二维数组中的对象

Question

我正在创建一个有机体模拟器，并且有机体对象位于粒子模拟内部。我希望有机体能够“感知”粒子。

粒子存在于 1920x1080 阵列中。目前，生物体从它们的当前位置“画”出线，检查阵列中的非空值，如果它绘制的任何线与粒子阵列内的粒子相交，它就会感应到粒子。

这是它的外观示例(有机体检测到绿色颗粒):

这种感觉输入的方法非常现实，因为随着粒子离生物体的距离越来越远，粒子检测到的概率会降低。

但是，有一个大问题。它非常占用 CPU，而且运行缓慢，因为一次模拟中有数百个生物体，它们都执行相同的 CPU 密集型扫描过程。

这是我目前用来画线和检查粒子数组中非空点的代码(每个模拟帧调用此代码多次):

float distance = 100.f;
float angle = 2.f*M_PI*randomNumber;
for (int i = 0; i < distance; i++) {
    this->point->addVectorFromAngle(angle, 1.1f); //this gets the next point in the line
    int x = static_cast<int>(this->point->x);
    int y = static_cast<int>(this->point->y);

    if (mainController->spaceTaken[x][y] != NULL) {
        return mainController->spaceTaken[x][y]; // Particle detected
    }
}

//this is a member function of the Vector class I use to handle co-ordinates
void addVectorFromAngle(float angle, float magnitude) {
 this->x += cosf(angle)*magnitude;
 this->y += sinf(angle)*magnitude;
}

有没有办法让这段代码使用更少的 CPU，同时保持大致相同的行为？

Answer 1

要优化代码，您可以做的第一件事是将步长 vector 的计算从角度移出 for 循环。角度不变， vector 始终相同。

您可以做的第二件事是切换到更快的线步进算法，例如 bresenham 线图

http://en.wikipedia.org/wiki/Bresenham 's_line_algorithm