Event Sequencing

With the release of the long promised strategic planning AI for Heroes V around the corner, it is time to have a look at the tech that drives this AI and makes it special.

Heroes of Might & Magic III developed by New World Computing

When I began working on Heroes V in 2006 I had the good fortune to read and assess the C++ code for the AI that made Heroes III special, originally written by Gus Smestad, and as Greg Fulton told me, which was based on the work Phil Steinmeyer did for Heroes II.

While fairly old from our perspective, Heroes II was released in 1996, the craftmanship was impeccable and it contained an ingenious centerpiece of code. Technically it compared the different paths from which you could arrive at a given tile on the map, and selected the best one. Knowing which is the best path isn't trivial, so naturally there was much more going on under the hood. How all the required parts were crafted into a highly performant streamlined algorithm, was where the true ingenuity resided.

Paths are made up of events

If you look at the state of a system, or at a gameworld, it changes continuously with the interactions that occur in it. I prefer to view these interactions as events that are happening. In the case of our paths, these are made up of events that occur while travelling along it. The term event feels more natural, you have major events, random events, irrelevant events and such, though the term interaction is technically accurate.

Algorithmically you start processing from a root event, usually the position an entity currently has in the gameworld. In this case its topology is presented by a tilemap. Then you project paths to all events in range from the current position. When a path arrives at an event, you add its value to the path, i.e. each path has an aggregated value that is the sum of all events visited so far by this path. This aggregated value is a key, it not only tells you which is the best path when processing is complete, it is also used to select the path that is continued on further from any event. Typically from many paths that arrive at an event only one or a select few paths are processed further.

Conceptionally the entire processing is recursive. An event with a path that needs processing further is called an active event and placed in a suitable container, a priority queue is a good choice for this. In each step the highest ranking event is popped from the container, the paths leading from it are processed and the events the newly projected paths lead to become active events if they are improved. Processing continues until there are no more active events or a termination condition is reached.

Control of the order of processing

The choice of a priority queue as a container gives you more control than for instance a FIFO list, because you can prioritize the processing of the shorter paths, which in turn avoids the processing of longer path sequences that would be replaced if a shorter path with a better value supersedes an earlier path to the same event in the longer sequence. Finding the most efficient order, i.e. which path segments to process first, is paramount for performance and in practice makes a difference of many orders of magnitude in terms of computation required. A proven best practice is to perform the processing in stages, e.g. turns in TBS or 1s increments in real-time, which allows you to find the most relevant paths in each increment and then use these as input for the next stage.

Valuation is a key

The aggregated value that is a key for the processing of the paths deserves special attention. It is rarely a scalar. Typically it has multiple parameters, for example an actor can be described by current army strength which might be impacted by events, the strategic value of the events performed, and by the travel cost incurred so far. The latter is significant to gauge the quality of paths, which usually is based on value vs cost.

Summary

This is in a nutshell an overview how event sequencing works. It requires a well designed thought-through evaluation function for each event, and a framework that ensures that the most relevant paths are projected and processed. There are a lot of things to learn, and it requires diligence and experience to work out how to get the best performance out of such a system. You find typical evaluation strategies in the ShortPath example of my earlier C++ coding practice. Additionally you find practical considerations about the significance of order in processing and some insights for writing a high-performance pathfinder in my previous post.

If you go this route you are rewarded with a powerful tool that gives the actors you write AI for awareness of their environment. They adapt to what they find in their vicinity and also do some planning ahead. For example they will forgo picking up a less valuable resource if they need the time to reach something of much higher value, a safe place or something they deem decisive instead.

Additionally, you get a good number of tools to shape the behaviour, how you design the evaluation function, what paths you prioritize, and the partition of the processing into stages, so that you can create fairly different behaviours, from an actor that beelines to an important location, over collectors that visit each attractive event, to actors that strike a strategic balance. Likewise you can design characters that are drawn to brute strength and battles, or alternatively avoid combat to build up a base or do smart scouting.

The above picture gives you an impression of the density of events in Heroes III. The green arrows that mark the plotted path of one of the heroes give you an idea how big a tile on the map is. New World Computing, the developer of Heroes III, managed to process a lookahead, technically the limit to which paths are processed, of roughly 75 tiles in each direction.

The Heroes V mod that I published in 2011 processes more than double this limit, which required significantly improved algorithms and massive performance optimizations. While a doubling of the range means four times the events, the permutations of the possible paths grow exponentially.

Event sequencing is a universal concept

While events can be mapped to locations on a map, the technique can be applied also to other kinds of interactions, for example the sequence of actions in a souls-like combat.

While so far finite state machines (FSM) and behaviour trees (BTs) are the tool of choice to implement the behaviour of a combatant, event sequencing has some advantages.

In principle a FSM can be designed to account for the state of the AI-controlled actor as well as for the state of the opponent. Refining the behaviour, in particular to employ and react to specific sequences of actions, i.e. combos, attack followed by a defence stance and so on, with a suitable responding action sequence is labour-intensive and requires the designer or programmer to think the consequences through.

In contrast event sequencing can string together actions and probe their outcome automatically, by comparing the aggregated value of different action sequences and selecting the best one. It cannot be stressed enough how much this changes the approach. The AI only needs to know what interactions can happen, all the work programmers/designers do for defining FSM and BTs behaviour becomes redundant. That is you get FSM and BTs fully automatically, these are created by the AI, which means changes to the interactions, game mechanics, items and so on are adapted to by simply pressing rebuild. The AI figures out the best approach how to react in each situation based on its knowledge what can happen and doing a lookahead of suitable depth.

In brief, event sequencing can improve the efficiency of the development process. The properties of actors can be fully parametrized, for example UE Blueprints can be used to set the health, strength, armor and other parameters. Even the evaluation function can be made editable, to achieve different behaviours. New weapons, shields and skills can be added by the designer by specifying their effects, like the timing, impact on health, added armor, cooldown and so on. Event sequencing takes all the variables into account and builds the necessary states, transitions and graphs accordingly. It processes a behaviour that adapts to any situation automatically. Whereas FSM and BTs need to be reworked to address changes that alter the actions a combatant can take significantly.

Both approaches, FSM and BTs on the one hand and event sequencing on the other, have their uses. Knowing both adds more versatility to your toolbox as an AI programmer.

Progress on AI

I appreciate very much the good fortune that introduced me to the AI code crafted originally by New World Computing. I took the opportunity to look in more depth at the theoretical foundation of AI in games. Understanding how the AI in Heroes III truly works and formulating the concept of event sequencing as a valuable tech helped me a lot.

But since then a lot has happened, and my research and affinity to the Heroes of Might & Magic source led me to a grander vision: an AI engine that simulates all actors and entities in a gameworld and predicts their behaviour accurately.

In a grand strategy game the entities of a faction need to behave synergistically while competing with the entities of opposing factions. In a way this is almost a universal conceptional challenge, questioning how entities in such a sandbox should behave. If you can solve this, you can potentially design any AI application you can imagine.

The key to solve this was for me strategic planning, this infinitely recursive give-and-take of competing factions to maximize their standing, to acquire, employ and leverage the resources they could get hold of.

It is fascinating in more ways than the chess-like drive to win, because factions and actors can have much more nuanced goals, they can support each other or cause friction. Different goals mean different valuation. If you put this into the context of event sequencing, it becomes clear that valuation and lookahead need a deeper understanding, that you question how these work.

It is this critical mindset that drove me all these years.

What's around the corner now is the next AI for Heroes V, sort of a grand experiment that incorporates a lot of new, highly-innovative, cutting-edge technologies that have been developed step by step to give actors and factions a grasp of what matters. The technological foundation is advanced, solutions for context-sensitive valuation, adaptive lookahead and high-performance ordering of processing that haven't been tried in this world so far.

What remains is some engineering effort to complete this new AI for Heroes V. Once we have it we can try it out. I am curious. I hope you are too.