The AI initially took an average of around 7ms per tick to process. Though the AI only runs on the server, and our server tick rate is 30hz, this would still have severely limited the amount of games we could run on one machine. As a side note, the amount of time spent on AI didn’t vary much with the amount of AI-controlled players, because the heaviest state was Ball Ownership, and only one bot can hold the ball at any time.

I spent a couple of days on optimizing and brought the AI tick down to below 1ms on average and 3-4ms peak:

Shared AI Cache

Each bot has access to a shared cache that can be queried for information like lists of alive players, players with active status effects (“stunned”, etc.), players’ current stamina, bumper positions, the current ball owner, etc. etc. The cache is updated once per tick and stays valid throughout the tick.

Over time, the cache evolved to cover pretty much all information about the game world that the AI is interested in, to the point where it made the AI so self-contained that it would probably be pretty trivial to offload the AI onto its own thread (which could eventually be valuable for offline gameplay).

Batched Position Evaluation

The position evaluators we use for our influence maps were originally written to process single positions and calculate the influence of nearby players, bumpers etc. on the assigned scores. Since the much more common case is that we want to evaluate many positions at once and find the one with the best score, I refactored the relevant methods to operate on Lists of Vectors, which produced a sizeable speed up.

Note that depending on your application, it might actually be your best strategy to implement influence maps as an actual spatial grid that you “render” once per frame and share among many agents. About ten years ago, I wrote AI for a Flash game that actually implemented influence maps by blitting gradients into a texture with various blend modes and sampling pixels from there (circumventing the sluggishness of ActionScript 2).

In Steel Circus, we just sample a small to medium number of pseudo-random positions around the bots, as the position scores depend very much on factors individual to each bot, we don’t have a lot of bots, and we’re typically not interested in scores for faraway points on the map.

Simplified Collision System

As I mentioned, the Ball Ownership state turned out to be our most expensive state by far: The AI constantly samples potential passes and goal shots and simulates several shots per tick. These simulations happen in slices of around 0.3 seconds, to best determine the odds of an enemy or friendly player intercepting the ball before it reaches its destination.

I originally had the AI simulate the ball using our physics engine (we use “Jitter” to be independent of Unity on the server), but it quickly became clear that that was way overblown and too costly for my needs. I spent about 5 hours writing a super-simple 2D collision system that could load our arena’s colliders and convert them to circles and polylines. It could do raycasts against these colliders and reflect rays against collision normals. Since sphere casts for the ball were the only real use-case for the collision system, I simply shrunk/expanded every imported collider by the ball’s radius and thus had a lightning-fast system for simulating ball movement.

The downsides of the system are that it doesn’t handle bumpers well (it simply treats them as static circles/cylinders), and it doesn’t scale well for future features (e.g. handling dynamic obstacles) or game mechanics. But it got us to release the AI on time, and it’s easy to swap out for something more scaleable, so I consider it time well-spent.

Micro-Optimization

I’m not going to go into much detail here. I just want to state that, as someone who has often been outspoken against premature optimization throughout our project, the AI and particularly ball prediction was absolutely a case where things like micro-optimizing math, unrolling loops, inlining functions etc. made a difference. I profiled thoroughly, found methods that were called many thousands of times per tick and hand-optimized them.

Future Work

We have a long list of things we want to improve on the AI, and most of them are pretty specific to “Steel Circus”. A few items are more generally applicable, so I want to finish by listing some of them here:

• Obstacle avoidance: Our position evaluators discourage positions close to bumpers to nudge the AI towards navigating around them, but the bots still frequently get stuck against them (or other players) for brief periods. I believe adding a steering layer on top of the position evaluation would make the AI move much more fluidly and could also be a good basis for adding code to avoid dynamic obstacles (such as Cap’s “Barrier” skill).
• Aim smoothing: the AI can instantly change its aim direction, resulting in inhuman flick-shot ability.
• Avoiding enemy skill areas of effect: the AI currently has no concept of the different champions’ special skills. While making it react to each of them efficiently would be a major task, the influence maps could simply penalize AoEs of enemy skills that are either active or currently being aimed.

Part 1: Overview
Part 2: The FSM and Ball Ownership
Part 3: Other States
Part 4: Optimization and Future Work