Jump to content

  • Log In with Google      Sign In   
  • Create Account

sheep19

Member Since 20 Jul 2007
Offline Last Active Sep 06 2014 04:32 AM

Posts I've Made

In Topic: Review my portfolio

19 April 2014 - 12:09 PM

Hello again. I completely re-designed the site by myself. Now the back button works like it should :P

 

I have also updated its content. I would appreciate if you could take a look and post some comments about the design and about the content as well.

I also found a free host that contains my name in it.

 

http://minasmina.host22.com/


In Topic: [Flocking] How to improve performance?

14 April 2014 - 09:55 AM

Alright, I moved the array allocations in the Flock class's constructor. And in the rebuildKDTree function I do not create the array every frame.

The time dropped from ~46 ms to ~36 ms. That was pretty big. By the way, I had forgotten that Unity uses Mono and not .NET  tongue.png

 

About co-routines: Seems I do not have access to startCoroutine because the class that handles the updates does not derive from MonoBehavior. However I did it myself: I manually update only n boids every frame (basically what I do is set a flag in each behavior that indicates whether it will use its old value or calculate a new one).

 

This is my update function:

public override void Update(float dt)
    {
        if (Time.frameCount == currentFrame) return;
        currentFrame = Time.frameCount;

        //------------
        kdBuildTimer.Start();

        flock.RebuildKdTree();
        anchorFlock.RebuildKdTree();

        kdBuildTimer.Stop();
        //------------

        updateTimer.Start();

        for(int i = 0; i < entries.Count; ++i)
        {
            (((entries[i].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[0].behaviour as Separation).useOldValues = true;
            (((entries[i].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[1].behaviour as Cohesion).useOldValues = true;
            (((entries[i].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[2].behaviour as VelocityMatch).useOldValues = true;
        }

        int limit = (current + 100 < entries.Count ? current + 100 : entries.Count);
        for(; current < limit; ++current)
        {
            (((entries[current].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[0].behaviour as Separation).useOldValues = false;
            (((entries[current].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[1].behaviour as Cohesion).useOldValues = false;
            (((entries[current].behavior as PrioritySteering).Groups[1] as BlendedSteering).Behaviors[2].behaviour as VelocityMatch).useOldValues = false;
        }

        if( current == entries.Count )
            current = 0;

        // update birds and calculate the center of the flock
        for (int i = 0; i < entries.Count; ++i)
            UpdateSteering(dt, entries[i]);

        updateTimer.Stop();
        ++frameCount;
        Debug.Log("Time to build K-D tree: " + kdBuildTimer.ElapsedMilliseconds / (float)frameCount + ", Time to update: " + updateTimer.ElapsedMilliseconds / (float)frameCount);
    }


The k-d tree is built every frame however. I guess I can do something about that too - re-build it every x seconds (where x < 1.0 of course).

So now by having 500 boids and updating 100 every frame I get 25 fps (time to update is about 16ms) instead of 15 fps (and 34 ms to update).

But the motion of the boids is not the same when updating different number of boids every frame. But I guess this is expected. By the way isn't this "cheating"? That I'm not updating all every frame? Or is this a standard thing to do in AI?

Another thing: If I set more boids (5000 for example smile.png ) I still get very long update times even when I still update 100 boids per frame. This is because those that get updaded still do queries on a huge k-d tree... Can I do something about this? What I was thinking was having something that "remembers" where the closest neighbors were so that next time they won't be far away. But how can I know this without re-calculating everything?


In Topic: [Flocking] How to improve performance?

13 April 2014 - 01:47 PM

I see what you guys mean, but the problem is that alglib expects the array to be of this type. And even If allocate earlier it will still be re-allocated by alglib (that's why it takes the array by reference) as you can see below:

 

// get the results
alglib.kdtreequeryresultsxy(kdt, ref results);

 

Also as far as I'm aware dynamic memory allocation in C# is fast (I read it's just a pointer increment, not sure how it works).

I can't switch to C++, it's too late now :P Also Unity doesn't support C++ so...

 

The last not so obvious problem you might have is colliders. You wrote above you "disabled" physics on your agents. Does this mean you removed the RigidBody component or do you set it to isKinematic? Do you still have colliders attached to the objects?

The agents do have rigidbodies attatched to them because I use them to set the velocity of the agents. However they do not have colliders attatched to them.


In Topic: [Flocking] How to improve performance?

13 April 2014 - 02:27 AM

I have made some measurements using the StopWatch class of the .net framework.

 

When using the following steering behaviors I had the results below - using 500 boids.

Time to build K-D tree: 2.34ms. So this is not the problem.

 

Time to update boid steerings (all 500 boids, average time of N frames)

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 46.77ms

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 39.55ms

Behaviors used: Cohesion, Separation, VelocityMatch, ObstacleAvoidance => 24.44ms

 

So by not using some behaviors the time dropped significantly. The difference from not using VelocityMatch to not using Cohesion was bigger because Cohesion uses k = 30 for aknn while velocity match uses k = 10. When I set k = 10 for cohesion the time dropped as well.

 

This is the code that behaviors use to get k-nearest neighbors:

public class Flock
{
	List<Entity> boids;
	alglib.kdtree kdt;

	public Flock(params Entity[] _boids)
	{
		boids = new List<Entity>();

		Add(_boids);
	}
	
	public int GetNeighborhoodInfo(Entity character, int maxNeighbors, float maxDistance, float minDotProduct, double aknnApproxVal, out Vector3 center, out Vector3 avgVeL) 
	{
		var point = new double[3]{character.position.x, character.position.y, character.position.z};

		var results = new double[0, 0]; // the array containing the results (points of the k nearest neighbors)

		int neighbors = (maxNeighbors == 0 ? 0 : alglib.kdtreequeryaknn(kdt, point, maxNeighbors, aknnApproxVal));

		// get the results
		alglib.kdtreequeryresultsxy(kdt, ref results);

		center = avgVeL = Vector3.zero;

		// where is the character looking
		var look = character.transform.forward;

		int count = 0;
		for (int i = 0; i < neighbors; ++i)
		{
			var pos = new Vector3((float)results[i, 0], (float)results[i, 1], (float)results[i, 2]);
			var vel = new Vector3((float)results[i, 3], (float)results[i, 4], (float)results[i, 5]);

			if (pos == character.position)
				continue;


			if( Vector3.Distance(character.position, pos) <= maxDistance )
			{
				// check for angle
				if( minDotProduct > -1.0f )
				{
					var offset = pos - character.position;
					if( Vector3.Dot(look, offset.normalized) < minDotProduct )
						continue;
				}
				
				center += pos;
				avgVeL += vel;
				++count;
			}
		}

		center /= count;
		avgVeL /= count;


		return count;
	}
}

I think it's pretty straight-forward... So I guess the only solution is to search for another library for aknn? I read somewhere that akkn could be made more efficient when using octrees instead of k-d trees.


In Topic: [Flocking] Avoid many "sub-flocks" in Cohesion

13 April 2014 - 01:02 AM

It's pretty much mathematically provable that over time, your flocks will break into groups that are proportional to some degree with your k value. It's self-reinforcing. 

 

One method is to not use a hard-cap on k -- but rather use all neighbors within distance d. It's a subtle difference, but I think it would help.

 

I see, thank you.


PARTNERS