Context Behaviours Know How To Share

Last time we saw how steering behaviour systems are very useful when either behaviour integrity isn’t important, or if there are a large number of entities to help hide any irregularities.

We saw this is actually an unavoidable feature of steering behaviours. The heart of steering behaviour systems, the merging of decisions of several behaviours, is what makes it so straight-forward to explain and implement  However it is also a flaw. There is not enough information in the system for the decisions to be merged with integrity, and there never can be, as long as only a direction and magnitude  are returned from each behaviour.

For many applications, this may not even be an issue. If the game needs a large collection of entities moving as a flock, the user isn’t necessarily interested if one entity occasionally makes a bad choice. The user sees the flock move as a whole, and isn’t looking at individual behaviours.

flocking starlings

However if the application requires a small number of entities that interact individually with the player, like a racing game, then mistakes and collisions start to become very apparent. In fact they can be game-ruining if not dealt with properly.

7529582638_bdab334226_b

The only way to fix these problems without replacing the system is to make the behaviours aware of each other, so they can return decisions that are sensible in the surrounding context. This leads to stateful and complex behaviours, and increased coupling, and doesn’t scale well when adding new behaviours. Can’t this be fixed without losing simple stateless composable behaviours?

I’m going to explain my solution to this problem, which is a more advanced version of the steering system I wrote for a shipped AAA racing game. After replacing the previous behaviour system, there was a net loss of 4,000 lines of code and yet there was a massive boost in the playability and expressiveness of the AI opponents.

To enable a steering system to merge properly, behaviours need to return much more information. They need to give not a single decision, but a view of the world as it appears to them. This is the context in which the behaviour would make a decision, if it was acting alone. The context of each behaviour can be merged and then, with all the information available, the system can make a decision. A sensible decision that always respects every behaviour, never gets stuck, and still shows emergence.

A behaviour will represent its context by writing into a context map. A context map is a projection of the decision space of the entity onto a 1D array. If the application features entities moving on a 2D plane, a map could be represented by evenly spaced radials around the entity, each a direction the entity could travel in, and associated with a single slot in the array. If the application has race cars zooming around a track, each slot of the array is associated with a distinct position to the left or right of the racing line, representing where the car would like to place itself.

Demonstrating projection from a 2D plane to a context map

An entity’s view of a 2D plane projected into a 1D context map

The context behaviour system creates two of these context maps – one for danger, and one for interest. The behaviours will fill these out. A strong entry in the danger map means someone thinks going that way would be bad. A strong entry in the interest map means someone would love to go that direction. The system passes both maps to every behaviour, asking each to fill them in with its own context.

Context maps are not cumulative. When a behaviour wants to add strength to a slot, it is only written if it is stronger than the value already in the slot.

Behaviours themselves look similar to their steering behaviour counterparts. Consider a chasing behaviour that selects a target and returns a direction towards it. The context maps version would instead iterate through each target, evaluate how strongly it wanted to chase it, and add that strength to the interest map slot that points towards the target. Any criteria can be used here, just like steering behaviours. The behaviour might be more interested in dangerous targets, or have some complex utility expression tree for evaluating interest, but for this example the behaviour will be more interested the closer the target is.

A collision avoidance behaviour would work in a similar manner. It would iterate through all obstacles, decide how strongly it wants to avoid each, and write that strength into the danger map slot that points towards the target. Again for this example, closer obstacles will be more dangerous.

Multiple targets and obstacles writing into the interest and danger maps

Targets and obstacles write into the interest and danger maps respectively, with strength based on distance

These behaviours are stateless, small and easy to write. That advantage of steering behaviours has not been lost.

In practice, writing to a single slot is not very effective. The behaviour might not want to move directly towards an obstacle, but it might be good to avoid going anywhere near an obstacle as well. A similar thing applies for the chase behaviour – if the entity can’t move directly towards a target, it might be good to move in a direction that takes it a bit closer to it. For this reason when writing into the context maps it’s normally a good idea to write across a range of slots, with the strength ramping down the further the slot is from the target direction. There’s a lot of power and expression in how the strength in surrounding slots is created. Helper functions can help keep the behaviours small and clean while using this expressiveness.

Once the danger and interest context maps are fully populated, the system can process them and come up with a unique decision. The exact way the map is processed depends on the application. If there are simple entities moving on a plane, a suitable algorithm might be as follows: Find the slot with the lowest danger, or as will probably be the case the set of slots with the equal lowest danger. Look in the corresponding slots in the interest map and pick the slot with the highest interest. For a tiebreak, pick the slot that is closest to our current heading.

The result of the system is simply the direction of that slot coupled with the interest strength. The entity interprets this as a direction to move in, and takes the strength as proportional to the speed to travel. Because of this, an entity that has nothing but low-interest things to do might move quite slowly, but an obstacle chasing something highly interesting or dangerous would move quickly.

Now that the whole system has been explained, consider the problem from the previous article. There are two potential targets to chase, but what we would consider the best choice is obscured by an obstacle. A naive steering behaviours system implementation would lead to deadlock as the forces balanced out, or worse, oscillation. To avoid this, the chase behaviour (or some higher-level decision-making system) had to be aware of the collision avoidance system, so it could know to ignore the obscured target. The context of the collision avoidance system had bled into the chase behaviour and coupling has increased.

In the context behaviour system, there is interest pointing towards both targets, with more towards the best target. There is danger in the same region pointing towards the obstacle. The system evaluates the danger map first, taking only the least dangerous slots from the interest map. This leaves it with only the interest from the weaker target available, and that direction is chosen. The behaviours have remained lightweight and isolated, but the end result was a very complex decision.

Obstacle danger obscures most interesting target, so the less interesting target is chosen

Obstacle danger obscures most interesting target, so the less interesting target is chosen

Not only that but if a higher-level decision-making system is only concerned with choosing unobscured targets, it can now be removed. I found a lot of higher-level decisions in F1 – who to block, who to draft – could be left to the context behaviour system to work out without increasing coupling.

There are several ways this system can be extended to give nice results. Since the context maps are essentially one-dimensional images, they can be blurred to smooth out narrow troughs and spikes. Last frame’s context maps can be kept, and  this frame’s results blended with them to provide free hysteresis to every behaviour. To do a similar thing for steering behaviours would require custom stateful code in every behaviour! The processing of the maps is ripe for vectorisation or offloading to a GPU.

Implemented as-is, the results of the system will always be exactly the direction of one slot. In the diagrams above, the entity can only move in 8 directions. This can lead to juddery behaviour if there aren’t a lot of slots. Taking the image metaphor again, the fix for this is to implement a kind of sub-pixel rendering. By taking the strength of surrounding slots, and approximating the gradient, the between-slot direction that would have the best strength can be found.

Since the behaviours are providing so much more information than a steering behaviours system, this solution is in isolation unavoidably more processor intensive than a steering behaviour equivalent. The exact complexity depends on the application, but the entities on a place example above is linear to the size of the context maps, and that’s probably typical.

However unlike steering behaviours, this system lends itself well to Level Of Detail (LOD) changes. The slot count of the maps can be changed from frame to frame, ramping down as the entity is further from the camera or player. This will compromise the quality of the movement, but the integrity of movement will still be preserved. If the system is structured so the behaviours are ignorant of the context map size, they don’t even have to know about LOD changes. The ability to have this kind of granular control over LOD is very rare.

By writing danger and interest into context maps, a context behaviour system can fix many of the problems that come from using steering behaviours, leading to small, stateless and decoupled behaviours that are still just as emergent and expressive.

Thanks to Matt Simper (@MSimperGames) and Michael Deardeuff (@mdeardeuff) for their help proof-reading this post.

About these ads

14 thoughts on “Context Behaviours Know How To Share

  1. Pingback: Steering behaviours are doing it wrong « Andrew Fray
  2. Pingback: Context Behaviours Digest « Andrew Fray
  3. These two articles were fantastic, your effort is much appreciated. I’ve been approaching a related issue and encountering many issues you’ve mentioned. I switched to a pure vector field model for most avoidance and pathing, and I’ve been struggling to recapture the expressiveness of dumb steering ever since. This technique helped me consolidate my plans, and the whole endeavor seems far more approachable. Thanks!

  4. I enjoyed this post. (More so than the first in this series, see my comment there.) I once had tried simple experiments with an approach like this, dividing perception of a 2d environment into angular sectors to allow spatial reasoning, but I did not pursue it very far. So it is nice to read about your well thought out approach to steering based on this concept.

    However in the previous article, you described ways of addressing what you characterized as shortcomings of simple steering behaviors. Then you criticized those approaches by saying: “not only has your hunting behaviour become an order of magnitude more expensive, it’s also become aware that such a thing as obstacles exist.” So I am struck by the fact that (a) instead of returning one value, your context behaviors return 8 or 16, and (b) your behaviors are aware of both goals and dangers. I understand that the value 8(/16) is just an example, but in any case, it is about an order of magnitude more data to compute. Note also that in the context of 3d motion, the number of angular samples needs to be significantly higher, adding even more computational expense.

  5. If your context stores a danger and an interest map for each entity then I do not understand why you state your behaviours are stateless.
    You moved the states from the behaviours to a centralized system but it seems to me these are still behaviour states, nicely encoded to 1D arrays.

    • The maps are not state for the behaviours, because behaviours only need to write to maps, not read from them. The behaviours have input (world state) and output (danger and interest). This makes the majority of the behaviours small, functional, readable and maintainable.

      The behaviour controller has state, yes, but because it’s isn’t dealing with the specifics of the problem domain, just the generalities of the two maps, it too can be quite simple.

  6. Pingback: Game Dev | Annotary
  7. Pingback: The 1D Radial Height Field « Spare Time Indie

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