XNA Boids in a Quadtree

A demonstration of Boid flocking using a Quadtree for increased efficiency, in a little program called Rise of the Colossus.

Previously, the program could only handle around 200 boids before noticeable slowdown occurred. This video shows 700 with a smooth framerate.

The small pumpkins flock to their large pumpkin leader. The big object isn't forcing the pumpkins away, they're running away from it. It eats the slow ones to grow larger.

Source code available from http://www.momentstudio.co.nz/other .

Category:

Howto & Style

Tags:

• boids
• xna
• quadtree
• pumpkins

[fermixx]

a question from a beginner: do you use quadtrees instead of octrees because all objects are touching the floor? if they could fly all over the place, would you use an octree instead?

Questions appart, great engine you have ! runs smoothly and those shaders look cute

[BillOfficial]

@fermixx Basically yeah. A quadtree IS an octree, just in 2D instead of 3D, and these don't really have actual 3D movement - they just stick to the level of the ground.

[fermixx]

@BillOfficial question nº 2 (hope im not annoying you); how do you manage objects belonging to two nodes at the same time? I tryed adding them to both. But when the update comes in, they are updated twice.

On top of that, after updating, if they are outside the bounds, i reinsert them from the root. the problem is they get sometimes inserted in a node i've not updated yet, so they are updated ONCE AGAIN, making them fly all over the place :P

[BillOfficial]

@fermixx I'm not exactly an expert either; I adapted another existing quadtree implementation for this one. But each object should only belong to one quadrant at a time. I'm just taking the centre point of the objects to determine which quadrant they're in. It doesn't work perfectly because objects on the edges of two quadrants can (and sometimes do) overlap each other. There's probably a better way but that would fix your first problem. I'm not sure about your second problem.

[fermixx]

@BillOfficial thanks for your help and quick replies :) much appreciated