I’ve intentionally split this post, to get you to think about the problem rather than being told the answer, so what this post covers:
- flocking behaviour
- a chance to herd sheep
- retrospective on how you did
- putting an algorithm to herding
- using AI to herd sheep
Background
I still fondly remember my childhood in the 80’s when “Computer & Video Games“, and “PCW” came out each month. Both magazines shaped me in some way. My handiwork appeared in C&VG, cheating games for readers (back in the days when folks knew what a poke was). I also spent many hours porting games from other computers, and obligatory debugging having keyed them in. PCW had a Z80 assembler section where they provide algorithm challenges with the least number of bytes, and the least clock cycles; something that developers generally are oblivious to given the modern gigabytes of ram and 4ghz clock speed!
I can’t be fully sure which one had a sheepdog trial game, featuring a handful of blocky sheep and a blocky dog. The idea was to herd the sheep into a pen. I think there were multiple levels (different blocky obstructions, 128×48 pixels limits things). It was more strategy than arcade from what I recollect.
Kind of like…
while (!endOfGame)
{
WaitForHumanToPressKey();
MoveDogBasedOnKeyPressed();
MoveSheepBasedOnDogPosition();
CheckForEndOfGame();
}
Today’s real-time / arcade equivalent would be Flock. I love what they did, but not enough to buy it.
That’s the background to this fun. I woke up one day wondering “what next?” in my AI/ML fun world, and the old game popped into my head. Back then it probably took me more time to type the game in and debug than actually play!
So here we go trying to make an AI herd sheep. That doesn’t sound difficult – right? Yeah, uh, well no – I can assure you that I found this a tad tricky. Maybe reinforcement learning might change my mind, but without it, I nearly tore what’s left of my hair out.
What Sheep?
First things first: where do I get my sheep from? I am glad you asked.
Given this blog intentionally has no advertising, and that the lottery win I am awaiting has not been forthcoming, a dog, a flock of real sheep and a large field are out of the question. That nearly kiboshed the idea.
I can hear you encouraging me with “never mind, create virtual sheep“. Great idea! Hmm, how do you do that?
We create… (please feel empowered to make your own before the SPOILER)
- a sheep object, give it a Move() and Draw() method. Done.
- a flock object, List<Sheep>, and a Move() method to move all the sheep. Done
- a dog object, give it a Move() and Draw() method. Done.
Do you have all those stubs methods set up? Great. How did you make the flock move? How did you make them run from the dog You didn’t, you’re waiting for me to tell you. Oh. I was hoping you were going to tell me…
Not to be put off, I came up with a few initial thoughts on sheep –
- they mostly tend to stick together, esp. in the presence of a dog – flocking is something they are known for
- I’m pretty sure they can’t walk through each other and nor can they move at 90 degrees without rotating and walking; because they cannot run thru each other when threatened they have to run in a similar direction in a time of trouble, and probably wander slowly the rest of the time
- if the dog gets too near the rear of the flock they start with the back most sheep pushing into the centre driving the sheep forwards as sheep after sheep do it. I am basing that on watching too many wildlife documentaries.
- put the dog in the middle, if they have any sense they all move away from it (leaving an arc of sheep), I have coined a new concept a “sheep-arc”. You read it here first.
You might think of additional things I might not have considered.
I thought I could probably get that to work before it crossed my mind, do I actually have any idea about sheep movement? Sheep and gazelles are different. When was the last time I watched someone herd sheep, and was I even paying attention? Ok, I accept I am not an authority on sheep, maybe I should check the internet.
After a bit of Googling about “flocking”, I came across “boids”. Folks have done some beautiful and cool stuff. It’s certainly not a new idea – we’re talking about the mid-80s! The person who pioneered the concept is Craig Reynolds. Kudos to Craig! I recommend learning more about swarming/flocking behaviour. It’s not my fault if you get hooked on it.
I don’t think my sheep observations were far wrong. I got virtual sheep working the same evening. Mine are not perfect. We’ll get to that, but they are good enough in my opinion, for a “herding challenge”.
Whilst searching, I found an academic paper on simulating sheep. They don’t provide the code, but they did provide a great write-up and is worth a look if my sheep are not accurate enough for you. My sheep move when they probably should be stationary, I blame stage fright. If you have improvements please let me know in the comments, and I’ll share them with everyone whilst attributing to you.
Here’s a “user-controlled” version of herding here on GitHub.
Try getting the sheep from the top left to the pen in the top right.
Now, you’ll probably miss something about what you just did – how quickly your human brain works out how to get the sheep to go where you want. Well done to you!
On your first go, you’re unlikely to have done it perfectly but you will manage. By the 2nd time, you’ll ace it!
It’s easy to not appreciate what you just did, but before you award yourself a medal, my 10-year-old son aced it with no problem whatsoever. (Although being a very high rank at HALO and many games this was a little insulting to his hand-eye coordination.)
Before the SPOILER (part 2), it’s a good time to have a quick think about how you managed to do it. Maybe do it several times and jot down your approach.
If you can’t be bothered to fetch the code, maybe think about how you expect the sheep to react and ask yourself how you counteract their non-compliant behaviour.
In part 2 we discuss algorithms followed by building one that trains.
