Specialisation - Utility AI

After working alot with tools during the latest game projects, I felt inclined to go into a more gameplay oriented direction for my specialisation. I felt inspired and motivated by our recently finished AI-course and after watching some GDC talks by Rez Graham and Mike Lewis (and others) I felt inspired to create some sort of goal oriented AI decision making. I did some reading and stumbled upon something called utility system which felt like it could easily turn into be a fun, five-week, project.

  • Utility AI system complete with utility functions
  • 5 weeks half time
  • The Game Assembly's in-house game engine TGA2D
  • Written in C++

In video game AI, a utility system, or utility AI, is a simple but effective way to model behaviors for non-player characters. Using numbers, formulas, and scores to rate the relative benefit of possible actions, one can assign utilities to each action. A behavior can then be selected based on which one scores the highest "utility" or by using those scores to seed the probability distribution for a weighted random selection. The result is that the character is selecting the "best" behavior for the given situation at the moment based on how those behaviors are defined mathematically.

Preparation and Re-evaluation

I knew that I wanted to make something fun and non-combat, hence I, quite early in the process, came up with the idea of simulating a simplified restaurant. However, it was not until the first week of this project that I started doing some proper research of utility systems. This led me to be very ambitious with the project scope; I planned on generating a tile map in order to use A*-pathfinding along with the possibility for the AI to have complex, hierarchical states containing behaviour trees. Both ideas had to be scrapped very early on as I realised that 1. the behaviours will not be complex enough to need behaviour trees and 2. after an insightful conversation with our mentor from the game industry, I realised that the main focus of this project was to demonstrate that I have indeed created a fully functioning utility system.

My new focus made structuring the project more straightforward as, in order to demonstrate the functionality of the system, I would need to focus on:

  • choose varied enough actions for the different AI,
  • decide how to visualise the AI going between these actions,
  • finding appropriate utility functions for the various actions,
  • and how to integrate the utility system with the AI.

The plan of simulating a little restaurant would now be used as a tool to demonstrate the system insted of being the main focus of the projects.

The AIs' Goals

Since the utility system is a form of goal oriented behaviour, the actors will need to have goals to fulfill. In order to fullfill any of the goals, the AI will have to take actions which are in turn provided by the environmet. I decided to have two different actors: a guest and a waiter.

The waiter's goals are to

  • satisfy their need to clean,
  • please guests
  • and socialise.

The guest's goals are to

  • satisfy their hunger
  • and socialise.

A goal will contain a value that represent the urgency of said goal. This value is, in my case, a number between 0 and 100. If a guest's "eat" goal has a low value, such as 10, it will make the guest appear hungry as it tries to choose actions that will increase this "eat"-value.

Utility Functions

To understand how the goals and actions correlate to one another, we must first visit the concept of utility. When my actors in my simulation consider an action, I want it to be dependent on the states of their goals. If a guest AI is really hungry, I want the utility returned from the eat-action to be quite large so that it appears attractive to the decision-making system. The utility system would look at this value and see that it will be beneficial to one of the actor's goals. Likewise, if the guest AI is full, the eat-action would return a low utility. Therefore, I need simple mathematical functions to help evaluate the utility as a function of current goal values.

Here are the functions that were used in the simulation. These can be combined in ways such that certain actions can seem attractive to the AI given a certain goal, while simultaneously impacting other goals negatively. Above, in the Goal-struct, you can see a function called GetDiscontentment(). This function is used in the utility system to calculate how unattractive a specific action is. The utility system sums the output from all inputted utilities, one for each goal, attained from a specific action and the result is a measure for the attractiveness of said action. A low discontentment value for an action is attractive to the utility system.

Actions and Decision Making

As mentioned previously, actions are presented from the environment. If a plate is introduced in the world, an action of "pick up plate" will present itself to the actors. This forces the system to constantly pay attention to the environment. I used an event manager-system (like a postmaster but particularly dedicated to the AI-system) to send messages to the UtilitySystem class which would in turn update its available actions. The UtilitySystem loops over all the actions and determines the most appropriate action to take (the one that results in the least discontentment) and returns this action to a StateMachine-class that then controls the actor's behaviour.

In the Action-class, you may see that every action contains a list of utility functions for the relevant goal types. For more flexibility, I added a multiplier which can be applied to the utility, and a list of conditions, that would have to be checked before returning the utility. If the conditions are not fulfilled, the utility's value will be the goal value - 1 so that it appears unattractive to the utility system.

Here you can see the action of type "pick up plate" being added to a plate's list of active actions. In this case, the plate has just been spawned in the restaurant. The utility function chosen for the goal-type "please" is the square decrease-function with a multiplier of 0.8. I chose this because I wanted the waiters to choose this action if their "please"-goal is low, and not choose it if it is high. My reasoning being to add a bit of drama to the plot, so that the guests have time to become annoyed and start complaining. I also added the condition that actors may not hold another plate to perform this action.

Result

It took me a lot of tweaking and perhaps some hacks to be able to present (in my opinion) a fully working and relatively flexible utility system. The final result can be seen in the video displayed at the top.

I took the freedom of messing around a little bit and tested what would happen if I gave the guests the goal of cleaning and the waiters the goal of eating. This resulted in that the guests would be served their food, and if the waiter was not fast enough to grab their empty plate, they would carry the plate themselves to the kitchen to be disposed of. The waiters were not so lucky in their eating-fulfillment. The only case they were able to grab some food, was if a plate got served to someone else and they were quick enough to grab it before the guest. I did catch both cases for everyone's viewing enjoyment.

Take Aways

I am quite proud of what I managed to achieve; I have never in my life used so many lambda-expressions, never used std::function and I believe I never fully understood what it meant to build utility AI. However, I reckon I managed to build a relatively stable base for a utility system. I knew there would be a lot of tweaking of the parameters ("which utility function for what action and goal?", "should I use a multiplier?" and so on), but ultimately, it was surprisingly straight forward. Once I grasped the concept of "if my AI is not hungry, it should not want to go to the plate and this utility function would be perfect for representing that", I never had to do major changes to my parameters. I could not have done this without our AI course book, Artificial Intelligence for Games by Ian Millington and John Funge, or without articles like this one (Alastair Aitchison, 2013).

I truly believe I created a system with the potential to handle growth, therefore, here are some points that I would have liked to explore more, if I had more time:

  • Make the application of goals to the AI data driven through e.g. json-files
  • Make the creation of actions, its utility functions and multipliers data driven through e.g. json-files
  • Make the steering behaviours nicer so that the AI would not walk over each other
  • Give the AI even more goals and actions by making the environment more sophisticated (perhaps introduce payments).

Below, I show some of my progress. The first week of the project was spent conducting research. The following week consisted of some slow progress, until week four, where everything fell into place. Enjoy!

Progress GIFs