Flocking Agent and the optimisation thereof

We were given a flocking simulation that needed to be optimised and customised for others (designers) to be able to use.

My first thought was to try and do a custom user interface screen where the different variables could be set, but this is not Unity, it is c++ and that is a hell of a task for me to try and do.

To start, I did have it set up so that the number of prey and predators could be input from the main screen before it processed the information and ran the simulation.

I decided that a csv file would be the best option for a budding developer to input the ranges of the variables that could be affected by this simulation.  Unfortunately, there was no way for me to hard code parameters for the variables to fall between.  I could have made it part of the csv file, but then they could be changed by the designer, by design or by accident.

I also wanted to set up pack behaviours for the predators so they would form their own groups and chase down the prey, working together.  As part of this, I would need to set up a Quadtree for all the flocking agents, in part to minimise the amount of calls to every other agent in the simulation.

This represented the first major problem of this challenge.  I could find plenty of various coding pieces and pseudo code to do the job, but I had no idea of how to implement it into my scene.

The other major problem was introducing collisions, whereby the predators would eat their prey once they caught up with them.  I struggled with these for the better part of  two weeks.  I was able to implement the collisions but had to drop the Quadtree because time was nearly up for delivery of this project.

My only optimisation was the standard oem threading that was implemented for a for loop that went through every prey and then looped through every prey again, checking for positions and group tendencies, but this had to be removed as it no longer became thread safe when I had the predators consume any prey that it caught.

The full features of my Flocking simulation can be seen in the above video.  The csv file to Initialise the simulation, the actual simulation, the csv file showing the 5 number summary of important information on closing the simulation and the heat map, generated by the simulation.

The feedback showed that this problem went into way more depth than I thought we were needing to go.  There were many more options for optimisation than I thought possible.  I could have gone through the code and replaced division, where applicable, with multiplication, for example, re-writing x/3 as x * 0.3.  Multiplication happens quicker than division.

I could have set up all if statements so that they ran as true for most occasions when entered.  If they run true the code carried on with what is loaded, whereas if they run false, new code needs to be loaded for the program to continue.

I could also have changed code regarding the checking of distances.  Instead of checking the distance between two vectors, I could have taken the sqrMagnitude of the two vectors, converted that into a float and checked if the float was less than a certainDistance * certainDistance.

For example:

float distanceApart = 5f;

float offset = (other.position – transform.position).sqrMagnitude;

if(offset < distanceApart * distanceApart)

{

//do stuff

}

The reason that this is quicker is because checking the distance between them will result in a Squared Root operation, which is slower than using the sqrMagnitude which is using and comparing variables that are multiplied.

It is unfortunate that I didn’t have another three weeks to work on this, but by the same token, I didn’t understand how much depth was required to “solve” most of this problem.  I thought implementing a Quadtree (or similar) and some form of threading would suffice.  If I had this to do again, I would have optimised the hell out of it, but without decent C++ skills, I would still struggle to implement a Quad tree.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s