Sign in to follow this  
cdxrd

AI help - flocking behavior - C#

Recommended Posts

Ok, so I thought that next on my list was tackling some AI. I was looking at Boids Psuedocode for a flocking setup. Well, I set up a new project, got a background and some sprites. Im populating the list, and displaying the sprites, then with a short delay it starts updating. Problem is, as far as I can see I implemented it properly but all the sprites move to the bottom right. For some reason my Velocity vector keeps ending up with values like 568, 492.. not sure where exactly im going wrong on this, so thought I would see if anyone wants to look at it and see if you can tell where im going wrong. game1.cs flutterby.cs Project source if you have xna 2.0 installed - Zipped - 597kb Download Anyone see where im going wrong? I think i've gone cross eyed.. [Edited by - cdxrd on April 24, 2008 10:52:54 PM]

Share this post


Link to post
Share on other sites

The function for rule one (lines 77-104), you're returning the center of mass position as the velocity to use. This should be (centerOfMass - boid.Position), to actually get the required velocity for the boid to move to the center of mass. This is also detailed in the pseudocode as (pcJ - bJ.position) .

You might also want to multiply the combined velocity by the elapsed time from the last frame (you can get this from the GameTime object supplied by the overridden Update function in your Game class). This way line 63 would become:

63. flutter.Pos += flutter.Vel * elapsedFrameTime;

I think this should reduce the position increase to acceptable levels (so the calculated velocity is actually used as units/second) and the behavior of your objects no longer depends on your framerate, which is generally considered bad practice.

Hope this helps :)

Share this post


Link to post
Share on other sites
Thanks regimus, I havent played with it yet but Ill go back over it today after work. I knew I had to be doing something not quite right, but I thought I had it all the way it should have been. thanks for taking a look!

Share this post


Link to post
Share on other sites
Ok regimus, i fixed Rule 1 where I overlooked that, but that still doesnt solve the troubles. Right now I have added a rule4 which guides them all to a predetermined point which is controlled by WASD right now. The problem Im encountering right now is that I usually get 2-3 butterflies that DO migrate to that point, but I get 3-4 that always seem to migrate to the bottom right.

Its Rule 2 that Im having the problem in, as soon as I make it return a 0,0 vector they all flock to the point they are supposed to, they just dont keep a distance from each other like rule 2 is supposed to provide. Any insights?

ATM Im not worried about updating distance based on the elapsedtime since this is only a demo project, I'd rather get the behaviors correct and then move on to moving them based on the elapsed time. Ive included a link to a youtube video here to show the current mucked up behaviors. I've also updated the source zip to include the latest changes.

New Game1.cs

New FlutterBy.cs

New Zip file

Youtube Behavior Video

Share this post


Link to post
Share on other sites

Well, at first glance I'd say the distance calculations aren't entirely correct. You'd probably want to use something like this:


Vector2 distVector = (otherBoid.Pos - thisBoid.Pos);
bool tooClose = distVector.Length() < range;


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

Share this post


Link to post
Share on other sites
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)

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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 count-1.. 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.. =)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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 re-examine 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 let-down, 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]

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this