14 replies to this topic

[burnthepc]

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.

[scgames]

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.

[burnthepc]

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...

[IADaveMark]

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).

[burnthepc]

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.)

[IADaveMark]

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.

[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!


Here's the behaviour as it stands at the moment
Starlings

[IADaveMark]

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!

[burnthepc]

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!

[scgames]

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.

[ShawnO]

burnthpc,
Your video looks really good.
I've been fascinated with flocking behavior for a long time. I'd like to make a screensaver that incorporates flocking behavior.
I've looked at the Boids sample and some other references, but I have never fully wrapped my head around the implementation. Is there any chance you might share your implementation?

Thanks,
Shawn

[IADaveMark]

Are you familiar with Craig Reynolds work on the subject? He's kinda the father of flocking (the shepherd?). Head over to red3d.com and the research section to find more information.

[burnthepc]

The closest 7 birds boils down to implementation... implementation... implementation :) I'll have another crack at updating this stuff next week.

ShawnO, as InnocuousFox said, it's all just Craig Reynolds. Added a little bit of global cohesion in there too. Not strictly within the rules, but I can reference my project tutor to back up the choice. She can hardly complain!

[ShawnO]

Thanks guys,
The name does sound familiar. I'll visit his site.

Thanks,
Shawn

[Giliam]

Hi everyone,

A while back, I wrote a boid implementation that originally did the same thing as Reynold's algorithm.
But what I didn't like about the original model was the boid's tendency to group into similarly sized flocks,
with the average flock size depending on the number of boids being searched for in the boid's direct neighborhood.

I ended up changing a few details of the algorithm and that allowed me to search for only for 3-4 boids, while supporting formation of larger flocks than before.
So I thought I'd share how.

The trick was not to change to original behaviour model (although I did some tweaking there as well), but to change the selection method of which boids are used to calculate the steering behaviours' responses from:
Pick the closest 2-3 neighbors (so I use a small fixed number, not a fixed max distance) AND 1 (distant) boid that is nearest to at least a couple of times (e.g. 6x) the distance of the closest neighbor.

Loosely, this means something like: be sure to respond to changes/problems in the direct vicinity, but also look for some other closeby flock you'd be interested to join over time if there's no immediate problem.

Another thing that helped my simulation was the addition of a some non-linearity in the behaviour's responses, making the responses less spring-like, and therefore less prone to ongoing natural oscillations.

A more elaborate explanation, as well as a video, the C++ source and binary can be found here:
www.decarpentier.nl/boids

Regards,
Giliam de Carpentier


A screenshot from the demo: