I have a quadtree implementation that works well with what I need for handling collisions between enemies, projectiles, and heroes.

However, most of these types of entities are pointbased, with varying radius but that's about it.

I have a weapon idea for lazer or ray weapon that's essentially a line. How does something like that fit in to working with something like a quadtree? Normally when we have a quadtree, we are essentially letting that data structure handle point masses to figure out which subset of objects we need. How then might we handle something like a line?

The dumb way to do it is to just query the enemies and do something like a circle line intersection test on all the enemy objects. This is obviously not efficient especially when we already have a quadtree.

One idea i have are to just put some dummy projectile object along the line and submit those to the quadtree. Then if we get any returned objects from those dummies, then we can use the circle line intersection test on it.

Any ideas pertaining to how to use ray weapon that requires some line intersection test with a quadtree would be appreciated. Thanks.


1 Answer 1


you could something like the following, that would at least limit the enemy-ray tests to quads that only intersect the line:

void process_sub_quads(Quad q,Ray r) {
    for(int sq=0; sq<4; ++sq) { // query sub quads
        Quad sub_quad = q.sub_quad(sq)
        if(ray_box_intersection(r,sub_quad)) {
            if(sub_quad == lowest_quad) {
                // test ray against enemies, perform appropriate actions
            } else {

if(ray_box_intersection(r,top_quad)) {

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .