Hi guys. I've put together a boids simulation for the final year project of my degree. I'm trying to work out if I've chosen a reasonable neighbourhood distance for the calculations. At the moment it's set at a radius of 44 units (overall world space is a 4000 unit cube). I guess the best judge is if the behavour looks right, and it does. I just wondered if anyone had any opinion on if this was way too small or too large.

The units really only have meaning relative to the other parameters in the simulation - world size (which you mentioned), the size of the boids, the number of boids, the speed with which they move, their turning radius, their fields of view, etc. So I would say that if it looks right, and if the performance is acceptable, then it is right.

Thanks, jyk. I thought as much. Just wanted confimation that there's not a general rule / thought on the matter. If it looks right and runs fast enough...

One thing you would definitely want to consider is your proposed separation distance. That directly implies how many other boids would be included once the flock was together. If your distance was 44, but your proposed separation distance was 40, any given boid would not have many neighbors to align with - only 1 layer deep, so to speak. If your separation distance was 5, however, you could be looking at 8 layers deep and is serious overkill. The reason for this is that the farther layers (i.e. 2-8) are already aligning with each other so you are receiving redundant information from them. There is too much overlap.

Shoot for a value that looks at 2-3 layers deep of boids using this rudimentary formula. So, if your seperation distance was 10, set your neighborhood to about 25. That way, it will pick up neighbors who aren't at that proposed distance (10), and yet may pick up a second layer of boids outside the first (e.g. 20).

Wow thanks. Without knowing it, I think you've solved a mayor issue I had with big flocks. (I'm too embarrassed so say what my separation distance is...low single digits.)

Incidentally, I believe there was a link to a study that claims that flocking starlings tend to keep track of about 7 neighbors total.

Remember that complexity theory and combinatorial explosions can actually be your friends in this case. It's how ants know what to do when (collect food, repair nest, defend nest) when all the information is passed through contact with a relatively small number of other ants. If each ant passes information to only a few others, the spread of the news is fairly rapid.

The same can be said for your boids. If you only are keeping track of the nearest 8 flock members, you are, by proxy, keeping track of the aggregate of their connections as well. Alignment will then happen as a group over time.

yeah I read that study too. Keeping track of 7 birds seemed a bit hard to do, particularly with the optimisation technique I've used. But I'll test out that increased separation force and hope it brings dividends!


Here's the behaviour as it stands at the moment

"> Starlings

Quote: Original post by burnthepc
yeah I read that study too. Keeping track of 7 birds seemed a bit hard to do, particularly with the optimisation technique I've used. But I'll test out that increased separation force and hope it brings dividends!

I'm confused. You say that you have a very large search area, but that you are having difficulty keeping track of 7 neighbors? I would think that in a flock such as the one in your video, that would be an adequate target there. Maybe 5-10 neighbors. Remember that much of the information passing is bi-directional - e.g. "distance to me is distance to you."

Also, remember that your other axis on the calculation overhead is update frequency. You don't have to update every boid every frame. In fact, you can spread the updates around per boid. To generate a more organic feel, you can even randomize the next update for each boid somewhat... that way they don't end up in patterns because certain neighborhoods of boids are in sync (m + x) and others are in (n + x). If you were to update each boid's neighborhood information every approximately every 5 frames, you could randomize its next update as (ThisFrame + [3..7]). On average, you are still updating the information every 5 frames, but every one is slightly different. Even the same boid is updating at irregular rates.

Obviously, you would still want to update their position every frame but they are working with only their most recent information. By the way, you can probably get away with something along the lines of 300-500 ms between informational updates and still get good-looking performance. In fact, having that lag time in there is slightly realistic anyway.

Quote: Here's the behaviour as it stands at the moment

"> Starlings

Decent video, btw!

Quote: I'm confused. You say that you have a very large search area, but that you are having difficulty keeping track of 7 neighbors?

Mostly, the issue is that to take the first 7 neighbours would take a standard order from my array that contains the birds. Or I'd need to calculate and keep track of all distances and pick the closest 7. All in all, sounds like added complexity to result in less information about the flock.

Fiddling with the update frequencies and groups sounds like a good idea. I'm updating 30 times per second (overkill I know but I set my ideals as 60fps for graphics and 30 updates for AI a second).

Now I'm itching to start coding and I'm on holiday (without a compiler) for a week!

Quote: Mostly, the issue is that to take the first 7 neighbours would take a standard order from my array that contains the birds. Or I'd need to calculate and keep track of all distances and pick the closest 7.

I may be misunderstanding here (please ignore this if that's the case), but the typical solution to the problem of finding the closest n boids would be to use some sort of spatial subdivision.

In this particular case, I think a regular grid might be a good choice.