Steering behaviours are doing it wrong

Update: you can now read part two of this series.

Steering behaviours have for a long time been a gateway drug of game AI. People like this (annoyingly pluralised) technique because its components are fun and easy to write, the framework code is very simple, requiring only some vector maths knowledge, and the end result is awesomely emergent.

For the uninitiated, a steering behaviours system is typically used to decide a direction and speed for an entity to move in, although it can be generalised as selecting a direction and strength in a continuous space of any dimensionality, not necessarily just spatial. The system contains many behaviours, each of which when queried returns a vector representing a direction and strength.

These vectors are then combined in some manner. The most simple combination strategy is averaging, but there are others that don’t really change the arguments I make here.

As an example, consider an entity moving through space avoiding obstacles and chasing a target. A collision avoidance behaviour may return a vector pointing away from nearby obstacles, and the chasing behaviour will return a vector pointing towards the target. If the obstacle is behind and the target in front, the entity can move towards the target unhindered. If an obstacle is to the left of the entity’s direction of travel, it will nudge its movement vector slightly to the right, moving it away from danger. Coding behaviour like this by hand would be much more complicated.

The strength of the returned vectors is proportional to how strongly the behaviour feels about this movement. For instance, when far from a target, the chase behaviour might return a long vector, to get him back into the hunt. When very near an obstacle, the collision avoidance behaviour might return a very long vector, to overwhelm over behaviours and get the entity to react quickly.

This all sounds great, right? Steering behaviour systems can be very effective, as long as you’re using it in the right situations. It gives coherent and pleasing results when given the numerical statistical advantage to hide its flaws. A massive flock of entities moves through obstacles in a convincing manner, but inspect one of those and you’ll find it sometimes behaves erratically, and without robust collision avoidance.

After all, the collision avoidance behaviour has no direct control over entity movement, and can just suggest directions to move in. If the chase behaviour also decides on a strong result, the two may fight and collision may be unavoidable.

When creating robust behaviours that work at the macro scale, with a small number of entities, these problems become very visible. The small component-based behaviours and lightweight framework are attractive but the system doesn’t scale. You can code around the edge cases, but the previously-simple behaviours soon become complex and bloated.

Consider an example. If our chasing entity picks a target that’s directly behind an obstacle, there will come a point where the vectors from the chase behaviour and the collision avoidance behaviour will cancel each other out. The entity will stop dead, even if there’s another near-by and unobstructed target that could be picked. The chase behaviour doesn’t know about the obstruction, so will never pick the second target.

To fix this, the first thing most people will try is to have the hunting behaviour path-find or ray-cast to the target. If it’s unreachable or obscured, the behaviour can pick another target. This is successful, and your system is more robust.

However 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. The whole point of a steering behaviours system implementation is to separate concerns, to reduce code complexity and make the system easier to maintain. However we had to break that constraint and have lost those benefits as a result.

This is the design flaw of steering behaviours. Each behaviour produces a decision, and all decisions are merged. If one behaviour’s decision (to chase a particular target) conflicts with another’s (to avoid a certain obstacle), the most intelligent merge algorithm in the world will still fail. There’s no way for it to know that two results conflict, and if there was there’s no way for it to know how to resolve the conflict successfully.

To do that the system needs not decisions, but contexts. It needs to understand how each behaviour sees the world, and only then it can produce its own correct decision.

In a context-based chasing entity, the target behaviour would return a view of the world contextualising that there are several potential targets, and how strongly the behaviour wants to chase each one. The obstacle avoidance behaviour would return a view that showed several obstacles, and how strongly the behaviour wants to avoid each one. When placed in the balanced target-behind-obstacle situation above, the obstacle and the target cancel each other out but all the other contexts remain, including other potential targets. The system can recover and choose a direction that’s sensible and coherent.

If computing and merging world contexts suggests generalised compromises and messy data structures, you’d be wrong. And I’ll tell you why in my next blog post.

What? Don’t look at me like that.

Update: continue reading the second post in this series now.

Advertisement

Reducing Memory Usage in Unity, C# and .NET/Mono

Unity on iOS uses an early version of Mono’s heap manager. This manager doesn’t do packing, so if you fragment your heap, it’ll just grab a new one for you. I am under the impression the Unity boffins are working on a new heap manager to get around this problem, but for now a game with no memory leaks can end up consuming ever-increasing amounts of memory. C# is a fun language that allows you to quickly write powerful code without sacrificing readability. However the downside to this is that writing natural C# code produces a lot of garbage collection. The only way around this is to eliminate or reduce your heap allocations. I’ve compiled a handy list ways to do this without reducing functionality. The end effect is that your C# code looks much more like C++, and so you lose some of that C# power, but such is life. As an added bonus, heap allocs are inherently more CPU-intensive than stack allocs, so you’ll probably save some frame time as well. To target your efforts, the Unity profiler can help you functions that make a lot of allocations. It’s not a lot of info, but it’s there. Open the profiler and run the game,  select the CPU profiler, and tap the GC Alloc column to sort by the worst offenders. Apply these guidelines to those functions first.

• Avoid using foreach(). It calls GetEnumerator() on your list type, which will allocate an enumerator on the heap just to throw it away. You’ll have to use the more verbose C++-style for(;;) syntax. EDIT: Unless you’re foreach-ing over an array. That causes no allocations. I guess that’s a special case that becomes syntactic sugar for a for(…){}? Thanks to Ian Horswill for pointing that out.

• Avoid strings. Strings are immutable in .NET and allocated on the heap. You can’t manipulate them in-place like C. For UI, use StringBuilders to build up strings in a memory-efficient manner, delaying the conversion to string until as late as possible. You can use them as keys because literals should point to the same instance in memory, but don’t manipulate them too much.

• Use structs. Struct types in mono are allocated on the stack, so if you have a utility class that won’t leave scope, make it a struct. Remember structs are passed by value, so you will have to prefix a parameter with ref to avoid any copy costs.

• Replace scope-bound fixed-size arrays with structs. If you have a fixed-size array that doesn’t leave scope, consider either replacing it with a member array that you can reuse, or create a struct with fields that mirror it. I replaced a Vector3[4] that was allocated every time you called our spline class with a ControlList struct that had four fields. I then added an this[] property for index-based access. This saved a ton of allocations because it was such a high-frequency function.

• Favour populating lists passed as ref parameters over returning new lists. This sounds like you’re not saving anything – you still need to heap-alloc the list you pass in, right? – but it allows us to, where necessary, make the next particularly ugly optimisation:

• Consider storing the scope-local storage of a high-frequency function as a member variable. If your function needs a big list every time it’s called, make that list a member variable so the storage persists between frames. Calling .Clear() on a C# list won’t delete the buffer space so you have no/less allocs to do next frame. It’s ugly and makes the code less readable so needs a good comment, but can make a big difference on heavy lifters.

• Avoid IEnumerable extension methods. It goes without saying that most Linq IEnumerable extension methods, as handy as they are, will create new allocations. However I was surprised that .Any(), called on an IList<>, which I expected to just be a virtual function to Count > 0, triggered an allocation. It’s the same for other funcs that should be trivial on an IList, like First() and Last(). If anyone can illuminate me on why this is I’d appreciate it. Because of this, and the foreach() restriction, I’d go as far as to say avoid the IEnumerable<> abstraction in your interfaces, and use IList<> instead.

• Minimise use of function pointers. Putting a class method in a delegate or a Func<> causes it to be boxed, which triggers an allocation. I can’t find any way to store a link to a method without boxing. I’ve left most of my function pointers in there because they’re a massive boon to decoupling, and I’ll just have to live with the allocs, but I’ve removed some.

• Beware cloned materials. If you get the material property of any renderer, the material will be cloned even if you don’t set anything on it. This material isn’t GC’d, and is only cleared up when you either change levels or call Resources.UnloadUnusedAssets(). Use myRenderer.sharedMaterial if you know you don’t want to adjust the material.

• Don’t use raw structs as keys in dictionaries unless... If you use a Dictionary<K,V> type, and your key value is a struct, fetching a value from the dictionary using TryGetValue() or the index accessor can, somehow, cause an allocation. To avoid this, implement IEquatable<K> for your struct. I guess the dictionary is creating some default equality comparer every time. Thanks to Ryan Williams for finding this one.

• 2014/5/8 Don’t overuse Enum.GetValues() or myEnumValue.ToString(). Enum.GetValues(typeof(MyEnum)) allocates an array with every call. Enum.GetNames() does something similar. If you’re like me, you’re probably using these heavily, along with .ToString() on enum variables, to do UI, as well as is other places. You can cache both these arrays easily, allowing you to do a for loop over enum values as well as cachedEnumNames[(int)myEnumValue]. This doesn’t work if your enum values are manually set, eg flags.

Feel free to add more in the comments.

Shamless plug: Easily add human-like and emergent decision making to your Unity3d game with DecisionFlex