Why is it so hard to find an algorithm that deals with a specific instance of a problem instead of solving everything at once? I’ve looked at various pathfinding and flocking algorithms, but nothing fits the bill so far. What I have is a bunch of sheep running around, and I would like to see them avoid corners but still move around objects gracefully. It’s a simple task, but not really simple in reality. And I really don’t want any involved path-planning in all of this, so advanced algorithms are right out.

The sheep have two modes of self-initiated transport: walking and running. When they walk, they’re intended to be pretty random and can go everywhere. Previously I added constraints that they prefer to be within a certain distance of each other – flocking behaviour - but it wasn’t really noticeable. When they run, on the other hand, they have a goal: get away from the dog’s bark. In other words, they have a destination angle and they move along this angle. That’s when they can bump into objects and get stuck in corners; and in the latter case, how should the dog get them out if the bark only makes them go farther into the corner?

So far I’ve gone through these attempts:

1. Just let the sheep run straight ahead; who cares about avoiding objects? This version sucked.
2. When a sheep runs forward, add vectors according to this simple algorithm:
   
   The red lines are vectors from the objects to the sheep; the blue line is the initial destination vector; the green line is a vague approximation of the resulting current vector.
   
   * Create a temporary vector of the sheep’s destination angle.
   * See if an object is close enough. If not, disregard it.
   * Add to the temporary vector a shortened version of the vector from the object to the sheep. This is in order to make the sheep move around it.
   * Do this for all objects. The final result is the current angle that the sheep will run to. This worked surprisingly well, and the sheep moved smoothly around objects. However, the sheep got stuck in corners despite this. They moved away, and then immediately walked back to the corner when they could.
3. In my next attempt I tried to change the destination vector along with the current angle change. The destination was moved a little bit to where the current angle was pointing. I.e., in an attempt to make the sheep change running destination when they current angle was pointing away for a while. This looked very silly when it came to avoiding common objects in the way: the sheep avoided it by running in another direction instead of just moving around it.
4. Fed up with vectors I went back to my old friend potential fields.
   The red parts show the intensity of the field; sheep will want to avoid red areas.This is the current method I’m using, but I made a very simple version of it. Basically, the sheep predict if the block that it’s going into has a potential greater than 1 (marked as the lightest tone in the image). If so, it decides that this won’t do. It checks the surrounding blocks of the destination block, selects the one with the least potential, and goes in that direction.

This last method works reasonably well for getting the sheep around stuff, and it also makes the sheep very reluctant to get into corners. It’s good enough, but I’m considering adding some vector additions to this to make things even smoother.

It’s rather ridiculous that I’m spending this much time on a simple problem like this. But I really want the sheep to run smoothly and be nice to the player!

This entry was posted on Wednesday, October 25th, 2006 at 3:08 pm and is filed under Indie Games, Sheeplings. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.