
Advertisement
Sign in to follow this
Followers
0
AI help  flocking behavior  C#
By
cdxrd
, in Artificial Intelligence
This topic is 3589 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.
If you intended to correct an error in the post then please contact us.
Recommended Posts
cdxrd 205
Well Regimus, you have peaked my curiosity.. and I've tried dividing R2 by the number of boids and it didnt seem to make too much of a difference, especially since i added in a velocity limiter.. they still flock wrong.. The pseudocode did seem a bit off to me, but since Im such a newb to this particular part of programming It felt off, but its been referenced by so many books and sites i figured I have to be doing something wrong.
I am thinking about rewriting parts of it to add a bool flag like currentUpdate or such and when its that boids turn to update, flip the flag and eliminate any possibility that the while if(b != fb) thing is causing troubles.. plus I wondered if the list isnt getting passed right, etc.. I might just tear the whole thing down and try rebuilding from scratch. This *IS* just a learning experience for me..
If you have some other ideas on implementing on flocking behavior, go right ahead.. im interested.. =)
I am thinking about rewriting parts of it to add a bool flag like currentUpdate or such and when its that boids turn to update, flip the flag and eliminate any possibility that the while if(b != fb) thing is causing troubles.. plus I wondered if the list isnt getting passed right, etc.. I might just tear the whole thing down and try rebuilding from scratch. This *IS* just a learning experience for me..
If you have some other ideas on implementing on flocking behavior, go right ahead.. im interested.. =)
0
Moomin 332
In rule 1 shouldnt
119. r1 = r1 / (count  1) ;
be just
119. r1 = r1 / count;
(As count is initialized to 0, and only increases for each boid velocity added.)
In rule 2 (line 146) I would have thought that the scaling is wrong, as the futher away another FlutterBy is(within the range 45), the faster you will move away from it.
Maybe something like this would be better. (btw psuedo code)
For rule 3 i suggest you perform it last, as although the current FlutterBy's velocity is taken into account, it is the last frame/ticks velocity and not the current accumulation from the other rules. (Though this probably won't be noticable.)
I also suggest you scale the ending velocity with the time delta (as remigius first suggested)
becomes
Apart from that, nothing stands out at me.
119. r1 = r1 / (count  1) ;
be just
119. r1 = r1 / count;
(As count is initialized to 0, and only increases for each boid velocity added.)
In rule 2 (line 146) I would have thought that the scaling is wrong, as the futher away another FlutterBy is(within the range 45), the faster you will move away from it.
Maybe something like this would be better. (btw psuedo code)
Vector2 direction = (b.Pos  fb.Pos).normalise();
float scale = 1.0f / ((b.Pos  fb.Pos).magnitude() + 1.0f);
r2 += direction * scale;
For rule 3 i suggest you perform it last, as although the current FlutterBy's velocity is taken into account, it is the last frame/ticks velocity and not the current accumulation from the other rules. (Though this probably won't be noticable.)
I also suggest you scale the ending velocity with the time delta (as remigius first suggested)
flutter.Pos += flutter.Vel;
becomes
flutter.Pos += flutter.Vel * elapsedFrameTime;
Apart from that, nothing stands out at me.
0
kindjie 290
Hey!
It actually doesn't look too bad. I think your problem is that you're not reflecting the velocity when they collide with the edge of the world, so your alignment rule will have them keep crashing into the wall and get stuck in the corner.
Another thing that I usually do is add multipliers for each rule, because it's pretty hard to control the flocking. One way is just to add 3 new member variables that you can tweak to your Flutterby class, then multiply them with what your rules return.
I didn't look too closely, but your alignment might be a lot higher than your separation. Usually that's ok, because alignment's the main way you stop them from colliding (if they all fly in the same direction, they won't hit each other), but you might run into issues when you hit a wall or approach a goal.
Once you have everything working, try having your rules affect their acceleration instead. You get more smooth, natural motion that way.
Hope that helps!
~kindjie
It actually doesn't look too bad. I think your problem is that you're not reflecting the velocity when they collide with the edge of the world, so your alignment rule will have them keep crashing into the wall and get stuck in the corner.
Another thing that I usually do is add multipliers for each rule, because it's pretty hard to control the flocking. One way is just to add 3 new member variables that you can tweak to your Flutterby class, then multiply them with what your rules return.
I didn't look too closely, but your alignment might be a lot higher than your separation. Usually that's ok, because alignment's the main way you stop them from colliding (if they all fly in the same direction, they won't hit each other), but you might run into issues when you hit a wall or approach a goal.
Once you have everything working, try having your rules affect their acceleration instead. You get more smooth, natural motion that way.
Hope that helps!
~kindjie
0
cdxrd 205
Really appreciate the thoughts everyone.. I am switching it over to a time based movement.. plus Moomin in rule 1, yes that should have been divided by count not count1.. but ive been playing for 2 days and was experimenting and that got left in.. thanks for noticing tho!
Kindjie, you said:
Another thing that I usually do is add multipliers for each rule, because it's pretty hard to control the flocking. One way is just to add 3 new member variables that you can tweak to your Flutterby class, then multiply them with what your rules return.
Ok, so what exactly do you mean by adding multipliers and adding 3 new member variables? such as what? Just a random int or better a random float value such as 0.6f for each 'rule' and multiply by those? of course having different random floats for each entity?
It would make things a little more interesting maybe, plus this way they couldnt end up in a 'formation' and flying around as such constantly.
I do plan to add in multiple goals and as each flutterby hits a goal there's a chance it will 'land' and 'sit' on the goal for x amount of time before taking off and joining the flock again.
Of course, this is just all to teach myself a few new tricks and I really reallly reallllly appreciate the help and input!
One more question if you dont mind there kindjie, your last statement about having the rules affect acceleration? sounds interesting, but as a newb how would you go about implementing that? even in pseudocode.. I'm trying to work it out in my head, but it aint working.. =)
Kindjie, you said:
Another thing that I usually do is add multipliers for each rule, because it's pretty hard to control the flocking. One way is just to add 3 new member variables that you can tweak to your Flutterby class, then multiply them with what your rules return.
Ok, so what exactly do you mean by adding multipliers and adding 3 new member variables? such as what? Just a random int or better a random float value such as 0.6f for each 'rule' and multiply by those? of course having different random floats for each entity?
It would make things a little more interesting maybe, plus this way they couldnt end up in a 'formation' and flying around as such constantly.
I do plan to add in multiple goals and as each flutterby hits a goal there's a chance it will 'land' and 'sit' on the goal for x amount of time before taking off and joining the flock again.
Of course, this is just all to teach myself a few new tricks and I really reallly reallllly appreciate the help and input!
One more question if you dont mind there kindjie, your last statement about having the rules affect acceleration? sounds interesting, but as a newb how would you go about implementing that? even in pseudocode.. I'm trying to work it out in my head, but it aint working.. =)
0
K_J_M 401
Best of luck with the code.
Just thought i'd post my Fish Flocking / Schoaling demo, it uses the Boids algorithm too.
http://www.kjmsoftware.co.uk/fish_flocking/fish.htm
You can modify it in run time to create different flocking behaviours.
Hope you like it.
KJM
Just thought i'd post my Fish Flocking / Schoaling demo, it uses the Boids algorithm too.
http://www.kjmsoftware.co.uk/fish_flocking/fish.htm
You can modify it in run time to create different flocking behaviours.
Hope you like it.
KJM
0
remigius 1172
Quote:
It actually doesn't look too bad.
Indeed it doesn't, I hope I haven't given you that impression. I recall my first experiments included boids happily dropping off the screen with NaN positions [wink]
Quote:
One more question if you dont mind there kindjie, your last statement about having the rules affect acceleration? sounds interesting, but as a newb how would you go about implementing that? even in pseudocode.. I'm trying to work it out in my head, but it aint working.. =)
This would have been the starting point of my 'realistic behavior' suggestion as well. Basically you could define a boid with the following properties:
class Boid
{
private Vector2 currentPosition;
private Vector2 currentVelocity;
public Vector2 currentAcceleration; // of course, this should be a property
public void Update(float elaspedTime)
{
// update the position
currentPosition += currentVelocity * elapsedTime;
// introduce some drag to cheaply limit velocity
currentVelocity *= (1  0.25f * elapsedTime);
// update our velocity
currentVelocity += currentAcceleration * elapsedTime;
}
}
Now, by changing the currentAcceleration you can indirectly influence the boid's movement behavior. This setup should allow your boid to react more realistically, so it won't for example change direction instantly but rather 'curve' towards the direction specified by the acceleration. The fudged drag is a cheap way of making sure the velocity vectors don't grow too large, so changes in acceleration are more noticable and it has the added benefit that the boid elegantly slows to a halt whenever there's no acceleration.
This is still pretty basic, but it may already give your simulation some more interesting behavior.
0
cdxrd 205
Ok, but where does the acceleration get updated? I would assume its in the move, but are you talking about passing the velocity and adding that to acceleration? or?
0
remigius 1172
You could start off by setting the accelaration like you were setting the velocity in your original boid code. That's nowhere near physically correct, but it should have the effect of the velocity converging to the direction you want the boid to move to. The only thing you'll need to pay extra attention to is that you'll probably want to shorten the accelaration vector a bit so the boids don't 'overshoot' their target too much.
Disclaimer
Remember, you asked for the next few paragraphs. I'm not particularly good at math or physics for that matter, so it's quite possible that this contains errors. I also tried to include unsolicited information on simulation and convergence, which shouldn't really be read by any sane person.
Enjoy [smile]
To make matters more correct (and sadly more complex), you'd have to reexamine your rules. Then you'll see each rule except rule 3 actually calculates distances and not velocities, let alone accelerations. Some basic physics teaches that accelaration (a) affects an objects position (x) over time (t) like this:
x(t) = x(0) + v(0) * t + 0.5 * a * t * t
The calculated distances by the rules represent x(t)  x(0), the boids current position subtracted from the boids target position (center of mass for rule 1, 'away from others' for rule 2 and the cursor position for rule 4). In an ideal situation, the boid will have moved the total distance calculated by the rules after some time t. Hopefully this picture can make things clearer:
So if we define r1 + r2 + r4 as R, meaning the distance we want the boid to travel or x(t)  x(0), we can write:
R = v(0) * t + 0.5 * a * t * t
Now we're facing an interesting problem, since we want to calculate the acceleration (a) a boid with starting velocity v(0) needs to move to the end of vector R over some time (t). Since we have two unknowns (a and t) and only one equation, this problem has infinitely many solutions, so that's not very helpful. Instead we'll define t ourselves, which is reasonable since then it would represent the time we'll allow for the boid to get into position.
If we go with t = 1 (for simplicities sake), we can calculate the acceleration (a) we need to give a boid with initial velocity v(0) to move to the end of vector R in one second. So we can write:
R = v(0) * 1 + 0.5 * a * 1 * 1
or
R = v(0) + 0.5 * a;
or
a = 2 * (R  v(0))
And there you have it, calculating an acceleration to make the boid obey rules 1, 2, and 4 after one second. Of course, this will only work perfectly in an ideal situation where all other boids are stationary. In your (and in fact most typical) situation however, the distance R we so conveniently used as a constant actually depends on the positions and hence the accelerations of the other boids over time. So in order to solve this problem perfectly, you'd need to venture into the dark wastelands of complex integrals and the dreaded differential equations.
If this feels like a bit of a letdown, don't worry. We'll use a 'trick' similar to which most, if not all physics simulators rely on. Instead of calculating a perfect solution each frame, we'll rely on the fact that most videogames are updated at at least 60Hz and our less perfect approach will at least converge to the ideal solution.
The catch here of course is that our approach may not converge and actually goes wild with huge acceleration vectors. This shouldn't put you off, the risk is only marginally higher than with your initial approach, which relies on the same 'trick'. Anyway, this is where the drag comes in, since it helps filter out the effects of errors over time.
An additional help in tweaking the behavior would be adjusting t, which influences how soon your boid should converge. Lower values for t (fractions of seconds) typically give faster convergence but are more instable, meaning they are more likely to generate huge accelerations to travel larger distances (R) in some short time t. Likewise, higher values for t obviously make the boid converge slower, but run less risk of spinning your simulation out of control.
There, with that settled, we have one last thing left to take care off. Since rule 3 gives back a velocity and we don't want to adjust our velocity directly, we have two options to still factor it in. We could calculate the acceleration needed to obtain the desired velocity and adjust our calculated acceleration accordingly. Or we can calculate the distance a boid with the desired velocity would travel over our chosen time t and add that to our R for calculating the required acceleration, like this:
R = r1 + r2 + r4 + r3 * t
Obviously for our t = 1, this means we can just sum it with the other vectors and be done with it.
One last word of caution: this approach calculates a new acceleration each frame, so you should set the acceleration on your boid, not add it to the existing one.
Hopefully this is somewhat helpful and/or correct. If anyone spots a glaring error, feel free to correct it, since I really have to get back to work now [wink]
Disclaimer
Remember, you asked for the next few paragraphs. I'm not particularly good at math or physics for that matter, so it's quite possible that this contains errors. I also tried to include unsolicited information on simulation and convergence, which shouldn't really be read by any sane person.
Enjoy [smile]
To make matters more correct (and sadly more complex), you'd have to reexamine your rules. Then you'll see each rule except rule 3 actually calculates distances and not velocities, let alone accelerations. Some basic physics teaches that accelaration (a) affects an objects position (x) over time (t) like this:
x(t) = x(0) + v(0) * t + 0.5 * a * t * t
The calculated distances by the rules represent x(t)  x(0), the boids current position subtracted from the boids target position (center of mass for rule 1, 'away from others' for rule 2 and the cursor position for rule 4). In an ideal situation, the boid will have moved the total distance calculated by the rules after some time t. Hopefully this picture can make things clearer:
So if we define r1 + r2 + r4 as R, meaning the distance we want the boid to travel or x(t)  x(0), we can write:
R = v(0) * t + 0.5 * a * t * t
Now we're facing an interesting problem, since we want to calculate the acceleration (a) a boid with starting velocity v(0) needs to move to the end of vector R over some time (t). Since we have two unknowns (a and t) and only one equation, this problem has infinitely many solutions, so that's not very helpful. Instead we'll define t ourselves, which is reasonable since then it would represent the time we'll allow for the boid to get into position.
If we go with t = 1 (for simplicities sake), we can calculate the acceleration (a) we need to give a boid with initial velocity v(0) to move to the end of vector R in one second. So we can write:
R = v(0) * 1 + 0.5 * a * 1 * 1
or
R = v(0) + 0.5 * a;
or
a = 2 * (R  v(0))
And there you have it, calculating an acceleration to make the boid obey rules 1, 2, and 4 after one second. Of course, this will only work perfectly in an ideal situation where all other boids are stationary. In your (and in fact most typical) situation however, the distance R we so conveniently used as a constant actually depends on the positions and hence the accelerations of the other boids over time. So in order to solve this problem perfectly, you'd need to venture into the dark wastelands of complex integrals and the dreaded differential equations.
If this feels like a bit of a letdown, don't worry. We'll use a 'trick' similar to which most, if not all physics simulators rely on. Instead of calculating a perfect solution each frame, we'll rely on the fact that most videogames are updated at at least 60Hz and our less perfect approach will at least converge to the ideal solution.
The catch here of course is that our approach may not converge and actually goes wild with huge acceleration vectors. This shouldn't put you off, the risk is only marginally higher than with your initial approach, which relies on the same 'trick'. Anyway, this is where the drag comes in, since it helps filter out the effects of errors over time.
An additional help in tweaking the behavior would be adjusting t, which influences how soon your boid should converge. Lower values for t (fractions of seconds) typically give faster convergence but are more instable, meaning they are more likely to generate huge accelerations to travel larger distances (R) in some short time t. Likewise, higher values for t obviously make the boid converge slower, but run less risk of spinning your simulation out of control.
There, with that settled, we have one last thing left to take care off. Since rule 3 gives back a velocity and we don't want to adjust our velocity directly, we have two options to still factor it in. We could calculate the acceleration needed to obtain the desired velocity and adjust our calculated acceleration accordingly. Or we can calculate the distance a boid with the desired velocity would travel over our chosen time t and add that to our R for calculating the required acceleration, like this:
R = r1 + r2 + r4 + r3 * t
Obviously for our t = 1, this means we can just sum it with the other vectors and be done with it.
One last word of caution: this approach calculates a new acceleration each frame, so you should set the acceleration on your boid, not add it to the existing one.
Hopefully this is somewhat helpful and/or correct. If anyone spots a glaring error, feel free to correct it, since I really have to get back to work now [wink]
0
cdxrd 205
Fun fun! lol.. I know I asked for it, so.. this should keep me busy for a little while. Its been a busy weekend and I needed something to study =) The only thing I got done this weekend was to add some code to convert my velocity and position and goal into vectors and into an angle so that I can rotate the boids to be facing the goal.. next up is the acceleration and keeping them from 'formation flying' like they do now.. going to start with landing, and work my way from there.
Looking forward to the read remigius!
[Edited by  cdxrd on April 29, 2008 12:00:44 PM]
Looking forward to the read remigius!
[Edited by  cdxrd on April 29, 2008 12:00:44 PM]
0
Sign in to follow this
Followers
0

Advertisement
Well, at first glance I'd say the distance calculations aren't entirely correct. You'd probably want to use something like this:
But that doesn't account for the strange behavior. I think the main problem lies in the 'scaling' of the velocity vectors you calculate. In rule 1 you divide the target velocity by the number of boids, while the total velocity of rule 2 has a far greater magnitude since it is not scaled like this. This would mean the velocity from r2 would easily be large enough to hide any behavior prompted by rule 1.
Depending on your setup code, this would most likely mean that the first boid is starting to move away from the flok, since rule 2 is so stong, with the rest cascading along in the same general direction. A quick and dirty way to fix this would probably be to divide the r2 velocity by the number of boids, so rule 1 and 2 have equal influences. In fact, I'd divide the result form rule 2 by a somewhat larger number to make rule 1 leading.
That said, I'm unfamiliar with original algorithm by Reynolds, but the implementation suggested by the pseudocode feels a bit backwards to me. Obviously the choice is up to you, but I'd try and start with the general movement behaviors of the boids and then implement the flocking rules against these. The restrictions implied by realistic movement behavior typically make for a much more interesting simulation.
But I'll spare you a treatise on this unless you're really interested [smile]
Share this post
Link to post
Share on other sites