Boids colliding with each other

Question

I was looking at some pseudocode for boids and wrote it in C++. However, I am finding that boids will occasionally collide with each other. I thought that I had programmed it correctly, given how simple the psuedocode is. yet, when i display the locations of all the boids, some of them have the same coordinates.

The pseudocode from the link:

PROCEDURE rule2(boid bJ)

    Vector c = 0;

    FOR EACH BOID b
        IF b != bJ THEN
            IF |b.position - bJ.position| < 100 THEN
                c = c - (b.position - bJ.position)
            END IF
        END IF
    END

    RETURN c

END PROCEDURE

my code is:

std::pair <signed int, signed int> keep_distance(std::vector <Boid> & boids, Boid & boid){
    signed int dx = 0;
    signed int dy = 0;
    for(Boid & b : boids){
        if (boid != b){       // this checks an "id" number, not location
            if (b.dist(boid) < MIN_DIST){
                dx -= b.get_x() - boid.get_x();
                dy -= b.get_y() - boid.get_y();
            }
        }
    }
    return std::pair <signed int, signed int> (dx, dy);
}

with

MIN_DIST = 100;

unsigned int Boid::dist(const Boid & b){
    return (unsigned int) sqrt((b.x - x) * (b.x - x) + (b.y - y) * (b.y - y));
}

the only major difference is between these two codes should be that instead of vector c, im using the components instead.

the order of functions i am using to move each boid around is:

    center_of_mass(boids, new_boids[i]);                      // rule 1
    match_velocity(boids, new_boids[i]);                      // rule 3
    keep_within_bound(new_boids[i]);
    tendency_towards_place(new_boids[i], mouse_x, mouse_y); 
    keep_distance(boids, new_boids[i]);                       // rule 2

is there something obvious im not seeing? maybe some silly vector arithmetic i did wrong?

Answer 1

The rule doesn't say that boids cannot collide. They just don't want to. :)

As you can see in this snippet:

    FOR EACH BOID b
        v1 = rule1(b)
        v2 = rule2(b)
        v3 = rule3(b)

        b.velocity = b.velocity + v1 + v2 + v3
        b.position = b.position + b.velocity
    END

There is no check to make sure they don't collide. If the numbers come out unfavorably they will still collide.

That being said, if you get the exact same position for multiple boids it is still very unlikely, though. It would point to a programming error.

Answer 2

Later in the article he has this code:

ROCEDURE move_all_boids_to_new_positions()
    Vector v1, v2, v3, ...
    Integer m1, m2, m3, ...
    Boid b
    FOR EACH BOID b
        v1 = m1 * rule1(b)
        v2 = m2 * rule2(b)
        v3 = m3 * rule3(b)
        b.velocity = b.velocity + v1 + v2 + v3 + ...
        b.position = b.position + b.velocity
    END
END PROCEDURE

(Though realistically I would make m1 a double rather than an Integer) If rule1 is the poorly named rule that makes boids attempt to avoid each other, simply increase the value of m1 and they will turn faster away from each other. Also, increasingMIN_DIST will cause them to notice that they're about to run into each other sooner, and decreasing their maximum velocity (vlim in the function limit_velocity) will allow them to react more sanely to near collisions.

As others mentioned, there's nothing that 100% guarantees collisions don't happen, but these tweaks will make collisions less likely.