• Create Account

# Boids - reasonable neighbourhood

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

14 replies to this topic

### #1burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 29 July 2009 - 10:45 PM

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.

### #2scgames  Members   -  Reputation: 1931

Like
0Likes
Like

Posted 30 July 2009 - 12:48 AM

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.

### #3burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 30 July 2009 - 01:14 AM

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

### #4IADaveMark  Moderators   -  Reputation: 2059

Like
0Likes
Like

Posted 30 July 2009 - 02:24 AM

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).
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #5burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 30 July 2009 - 04:45 AM

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

### #6IADaveMark  Moderators   -  Reputation: 2059

Like
0Likes
Like

Posted 30 July 2009 - 06:05 AM

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.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #7burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 30 July 2009 - 06:19 AM

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

### #8IADaveMark  Moderators   -  Reputation: 2059

Like
0Likes
Like

Posted 30 July 2009 - 07:19 AM

Quote:
 Original post by burnthepcyeah 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!

Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #9burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 30 July 2009 - 10:22 PM

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!

### #10scgames  Members   -  Reputation: 1931

Like
0Likes
Like

Posted 31 July 2009 - 12:48 AM

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.

### #11ShawnO  Members   -  Reputation: 145

Like
0Likes
Like

Posted 31 July 2009 - 01:24 AM

burnthpc,
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

### #12IADaveMark  Moderators   -  Reputation: 2059

Like
0Likes
Like

Posted 31 July 2009 - 02:56 AM

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.
Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

### #13burnthepc  Members   -  Reputation: 109

Like
0Likes
Like

Posted 31 July 2009 - 04:41 AM

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!

### #14ShawnO  Members   -  Reputation: 145

Like
0Likes
Like

Posted 03 August 2009 - 06:33 AM

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

Thanks,
Shawn

### #15Giliam  Members   -  Reputation: 144

Like
2Likes
Like

Posted 13 December 2011 - 05:48 AM

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:

www.decarpentier.nl - developer blog | @decarpentier_nl - twitter

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS