Scanning for objects in a 2D array by drawing lines in random angles in C++

Question

I'm creating an organism simulator, and the organism objects are situated inside of a particle simulation. I want the organisms to be able to 'sense' the particles.

The particles exist inside of a 1920x1080 array. Currently, the organisms sort of 'draw' lines out from their current position, checking for non-null values in the array, and if any of the lines it draws intersect with a particle inside of the particle array, it senses the particle.

Here's an example of how it looks (green particles are detected by the organism): enter image description here

This method of sensory input is extremely realistic, as the probability of particle detection decreases as the particles get further away from the organism.

However, there's one huge problem. It's extremely CPU-intensive, and it runs slowly, because there are hundreds of organisms in a simulation at once, all performing the same CPU-intensive scanning process.

This is the code I'm currently using to draw lines and check for non-null points in the particle array (this code is called several times per simulation frame):

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

Is there a way to make this code use less CPU while maintaining roughly the same behaviour?

Maybe use a [different way of testing the intersection](http://stackoverflow.com/q/7050186/2065121)? — Roger Rowland, Dec 21 '13 at 10:14
I think any algorithmic method of intersection detection would require a test for every single particle in the simulation, which will probably be really slow because there can be millions of particles in a simulation. It would be really great if there could be a way to only run the intersection tests on the particles that are within a certain distance of the organism, but I can't think of any computationally-cheap way to do it. — Sosumi, Dec 21 '13 at 10:33
You need to look at the way graphics apps in general and games in particular handle this sort of testing. Take a look at [quad trees](http://en.wikipedia.org/wiki/Quadtree) for one common way of structuring data for collision detection (which is basically what you're doing). — Roger Rowland, Dec 21 '13 at 10:41

score 1 · Accepted Answer · answered Dec 21 '13 at 10:12

The first thing you can do to optimize your code is to move the calculation of the step vector from the angle out of your for loop. The angle doesn't change and the vector is the same all the time.

The second thing you can do is to switch to a faster line stepping algorithm like for example a bresenham line drawing

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

score 1 · Answer 2 · answered Dec 21 '13 at 10:47

Point 1:
It appears that you draw lines at random angles. This may result in un-even spread depending on the number of angles you generate and the random numbers generated. There will be times when the random number gets repeated.

Instead I suggest you iterate over small increments of angles from 0 to 2pi.

Point 2:
Also, as pointed out by @NikolausGradwohl, you should minimize the computation of sin and cosin since they are very expensive in terms of time.

float deltaX = cosf(angle)*(1.1);
float deltaY = sinf(angle)*(1.1);
for (int i = 0; i < distance; i++) {
    this->point->x += deltaX;
    this->point->y += deltaY;
    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
    }
}

score 1 · Answer 3 · answered Dec 21 '13 at 12:10

Your simulation could be viewed as the n-body problem, but you have "life interactions" instead of gravity between bodies.

The simulation of the nbody problem is hard, and is never achieved in your way. Normally its done thorugh extensive space partitioning (Through BSP trees, quadtrees, etc) and some probabilistic computations.

Scanning for objects in a 2D array by drawing lines in random angles in C++

3 Answers3