Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


Separation


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.

  • You cannot reply to this topic
2 replies to this topic

#1 sheep19   Members   -  Reputation: 413

Like
0Likes
Like

Posted 16 September 2013 - 02:51 AM

I'm trying to implement the Separation behaviour.

 

The author of AI for games describes it as:

The separation behavior is common in crowd simulations, where a number of char-
acters are all heading in roughly the same direction. It acts to keep the characters from
getting too close and being crowded.

 

So what he does is loop through each target, check if it's within the threshold distance and if it is, make some changes to the character's linear velocity (using inverse square).

 

This is the pseudocode:

def getSteering():

	# The steering variable holds the output
	steering = new Steering

	# Loop through each target
	for target in targets:

	# Check if the target is close
	direction = target.position - character.position
	distance = direction.length()
	
	if distance < threshold:

		# Calculate the strength of repulsion
		strength = min(decayCoefficient * distance * distance, maxAcceleration)

		# Add the acceleration
		direction.normalize()
		steering.linear = strength * direction

	# We’ve gone through all targets, return the result
	return steering

He also says that:

Where there are multiple characters within the avoidance threshold, the steering
is calculated for each in turn and summed. The final value may be greater than the
maxAcceleration, in which case it can be clipped to that value.

 

I don't see anything being summed in the code above. Maybe is that a mistake?

I guess it is, so what I did was to change:

steering.linear = strength * direction

to
 

steering.linear += strength * direction

And outside the loop I check if its length is larger than maxAcceleration and if its, I normalize it and multiply by maxAcceleration.

 

So I did a small test. I added three agents (birds) that are first moving in a straight line parallel to each other, and by pressing a button I make them to want to separate each from the other two.

So Bird_0 wants to separate from Bird_1 and Bird_2, Bird_1 wants to separate from Bird_0 and Bird_2 and Bird_2 wants to separate from Bird_0 and Bird_1.

 

The result seems a bit strange. All birds orbit around each other. I have uploaded a video that shows it.

 

Am I doing something wrong or is that the way separation works?



Sponsor:

#2 LorenzoGatti   Crossbones+   -  Reputation: 2779

Like
0Likes
Like

Posted 16 September 2013 - 04:50 AM

You are perfectly right about summing forces instead of using one at random (the last in the for loop).

 

Probably, your birds orbit each other because the force is attractive: direction points towards the other bird, and so does strength*direction.  The sum of the two contributions points somewhere between the two other birds.

strength = min(decayCoefficient * distance * distance, maxAcceleration)

This is suspect: strength should decrease at larger distances. The presumably wrong formula has an additional confinement effect, of course.

 

Clipping should also be applied to the final steering force: the worst case for N+1 birds is N*maxAcceleration rather than maxAcceleration.


Produci, consuma, crepa

#3 sheep19   Members   -  Reputation: 413

Like
0Likes
Like

Posted 16 September 2013 - 05:44 AM

Thank you for you help.

 

Probably, your birds orbit each other because the force is attractive: direction points towards the other bird, and so does strength*direction.

So I changed it to: var direction = character.Transform().position - target.Transform().position;

 

It seems to be working now - the birds steer away from each other.

 

This is suspect: strength should decrease at larger distances. The presumably wrong formula has an additional confinement effect, of course.

I guess I can use the linear version too: var strength = maxAcceleration * (threshold - distance) / threshold;

 

Clipping should also be applied to the final steering force: the worst case for N+1 birds is N*maxAcceleration rather than maxAcceleration.

This is what I do:

var steering = new SteeringOutput();
		
			bool noSteering = true;
			
			foreach(var target in targets)
			{
				// check if the target is close
				var direction = character.Transform().position - target.Transform().position;
				var distance = direction.magnitude;
				
				if( distance < threshold )
				{
					var strength = Math.Min(decayCoefficient / (distance * distance), maxAcceleration);
					//var strength = maxAcceleration * (threshold - distance) / threshold;
					
					direction.Normalize();
					steering.linearVel += strength * direction;
					
					noSteering = false;
				}
			}
			
			if( steering.linearVel.magnitude > maxAcceleration )
			{
				steering.linearVel.Normalize();
				steering.linearVel *= maxAcceleration;
			}
			
			// face in the direction we want to move
			character.Transform().LookAt(character.Transform().position + character.Velocity());
			
			if( noSteering )
				return SteeringOutput.None;
			
			return steering;

I do the clipping at the end, but do not allow N*maxAcceleration for steering.linearVel. Do you mean that I should allow it to be that large? (or maybe I didn't understand correctly). If I allow it though, the acceleration would be really big if a lot of targets where near, which is something I don't want to happen. I want maxAcceleration to be the mas acceleration, independently of how many targets are close.


Edited by sheep19, 16 September 2013 - 05:49 AM.





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