broccoli 3.4.0

broadphase collision detection algorithms
Documentation

Broccoli

Crates.io docs.rs Crates.io

Broccoli is a broad-phase collision detection library.

The base data structure is a hybrid between a KD Tree and Sweep and Prune.

Checkout it out on github and on crates.io. Documentation at docs.rs. For a report on the algorithm used as well as analysis on the crate in general, see the broccoli book.

Screenshot

Screen capture from the inner demo project.

Other crates

The broccoli-ext crate contains some more functionality but relies on unsafe.

Example

use broccoli::prelude::*;
use broccoli::tree::{bbox, rect};
fn main() {
    let mut inner1 = 0;
    let mut inner2 = 0;
    let mut inner3 = 0;

    //Rect is stored directly in tree,
    //but inner is not.
    let mut aabbs = [
        bbox(rect(00, 10, 00, 10), &mut inner1),
        bbox(rect(15, 20, 15, 20), &mut inner2),
        bbox(rect(05, 15, 05, 15), &mut inner3),
    ];

    //This will change the order of the elements
    //in bboxes,but this is okay since we
    //populated it with mutable references.
    let mut tree = broccoli::tree::new(&mut aabbs);

    //Find all colliding aabbs.
    tree.colliding_pairs(|a, b| {
        **a.unpack_inner() += 1;
        **b.unpack_inner() += 1;
    });

    assert_eq!(inner1, 1);
    assert_eq!(inner2, 0);
    assert_eq!(inner3, 1);
}

Name

If you shorten "broad-phase collision" to "broad colli" and say it fast, it sounds like broccoli. Broccoli are also basically small trees and broccoli uses a tree data structure.