A Simulation of Sheep Herding - Part 1

January 3, 2022

For the past year (off and on) I've been working on a large scale simulation of sheep using Unity. My goal was to get over 1000 concurrent sheep moving over a realistic terrain on a reasonably good PC. While I've had eyes on making this a full game, I want to share what I'm doing before I get to a final decision on that. It's fun to play with even in this early state, and who knows there it will end up. So here we go!

Why?

Well, as you can see from some other posts on here, and from the title of the site, I am really interested in emergent behavior. The interactions of individuals acting in their own self interest is responsible for so many phenomena we see very day. It's like playing with water - it never gets old even if it's totally familiar. I feel like being able to create this stuff on the computer is super interesting and can lead to a lot of crazy surprises.

Then I was watching the film Howl's Moving Castle with my family, and I came across this shot:

It just hit me how interesting and beautiful flocks of sheep are. I could see how to do it. So I jumped in.

Getting Educated

It turned out to be a deep well. Humans and sheep have a very long and mature relationship so there's quite a bit of information and knowledge out there. One of the most useful resources was this simple site on raising sheep. I love that it was built in Dreamweaver.

http://www.sheep101.info

There are also academic papers with super complicated analyses of sheep behavior that are more meant for industry. I felt like starting with Boids would work.

Boids

A flock, whether it's birds, sheep, or fish, can be represented by a well known and elegant algorithm called Boids (Reynolds 1986). 

In the Boids algorithm, we determine the movement of each individual agent by observing its neighbors to calculate forces. These forces represent the agent's desire to stay close to other agents (cohesion), but not TOO close (separation). At the same time, each agent wants to move in the same direction as those around them (alignment). Once we balance these three fundamental forces we get interesting and natural behavior out of simple rules. 

After the basic forces are set up, most implementations add avoidance so that the agents don't run into obstacles. However, I was most interested in them escaping from a predator such as a dog. After all, that's the basis for herding.

So I put together a basic implementation in Unity. This had cohesion, alignment, and separation and then after all that was summed up, the escape vector was thrown in. There was no avoidance but since these were rigidbodies, they gracefully slid along the walls and it worked. This also was fine with a few dozen sheep, but as the calculations for boids are O(n^2) it wasn't viable as the final algorithm. I wanted to have hundreds going at once.

Up Front Optimizations

The next step was to figure out how to get the numbers of sheep I wanted. The obvious thing was to make the logic multithreaded using Unity's Jobs System. This works by doing the boids forces calculations in a job so that it can be distributed across the CPU's cores. But there turned out to be a lot more to it than that.

There are bunch of performance intensive functions that needed attention:

1. Neighbor Finding using Overlap Sphere
2. Ground detection using a raycast
3. World sensing via raycasts
4. Physics
5. Time slicing updates