Utility-based AI for Games

Finite-State Machines (FSM) are the bread-and-butter of game AI due to their simplicity (both in implementation and theory) and effectiveness. As such, FSMs are the topic of many tutorials and guides. Unfortunately, most of them focus on the States part of FSM. After all, they are called Finite-State Machines, so you expect that states are the critical part.

Well, no. The critical part is the other: transitions.

Transitions can make or break your AI independently of how carefully crafted the states are. In other words, intelligence is in change, and the element of change in an FSM is represented by transitions.

Unfortunately, transitions in real-world examples are more complex than in FSMs tutorials. For example, suppose we have a simple character in a shooting game and assume we have three states: shootflee, and heal. The first will make the character attack the player, the second will make the character run away from the player, and the third will make the character run toward the nearest healing spot.

That’s sound. However, how do we transition between the states? The simplest thing would be to write three boolean conditions, as usual.

The character will flee when their HPs are less than 50%, and we are close to the player, and they will heal when their HPs go under 25%.

It seems fine at first. But then we realize that there are some ambiguous situations. For example, the character can be near the player with less than 25% HP. Will they flee or not?

Depends. Is the health location closer than the player’s? How much HP does the character have? Are they at 24% or at 1%? Because at 24%, the NPC may risk rushing to the health location, while at 1%, it will be suicide.

There are many decisions here. Unfortunately, none of them is easy to encode with an if-then-else rule. What if we use a smoother approach?

Introducing Utility Functions

So imagine you are working on your game. You lose track of time, and suddenly, you feel uncomfortable. You are hungry. And thirsty. Where do you go? You go to grab a bite by walking to the kitchen, or you get your water bottle inside a fridge on the opposite side? (Yes, you really botched the setup of your working place)

Depends. Are you more hungry or more thirsty? What are the things that you need to address with more urgency? Or, said in another way, what action will provide you with the most utility?

You can imagine having some hidden “utility trackers,” translating every urgency/utility into a numeric value. So that you can make a decision. For instance, you can simply compare the “thirst utility” and “hunger utility” numbers and choose to go toward the greater utility.

Let’s try to code this. I’ll write this in a small Pico8 demo.

First, we set up a small scene with three objects: a burger, a glass of water, and our character. The following code initializes the state of these objects.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27  function _init() initplayer() initburger() initwater() end function initwater() water={} water.x=0 water.y=9*8 end function initplayer() player={} player.x=5*8 player.y=9*8 player.hunger=0 player.thirst=0 player.idle=1 player.state="idle" end function initburger() burger={} burger.x=11*8 burger.y=9*8 end 

Next, we initialize the draw function. This is just basic Pico8 stuff. Don’t worry. It is not required to understand the AI. We are just rendering the three sprites for the hamburger, water, and player, plus writing the value of the hunger and thirst utility trackers.

  1 2 3 4 5 6 7 8 9 10  function _draw() cls() map(0,0,0,0,16,16) spr(3, player.x, player.y) spr(17, burger.x, burger.y) spr(18, water.x, water.y) print("hunger "..player.hunger, 0, 0, 7) print("thirst "..player.thirst, 0, 10, 7) print("state: "..player.state, 0, 20, 7) end 

Now, during the update step, we need to do two things: update the world state and trigger the AI.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  function _update() updatestate() ai() end function updatestate() player.hunger+=0.01 player.thirst+=0.02 if (abs(player.x-burger.x)<10) then player.hunger=0 end if (abs(player.x-water.x)<10) then player.thirst=0 end end 

The updatestate function is elementary. We increase the player’s hunger and thirst at every frame by a small value. Then, we check if the player is near the burger or the water, and we zero the corresponding bodily sensation (if I eat a burger, I have zero hunger; if I drink water, I have zero thirsts).

Finally, let’s look at the AI.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17  function ai() -- This could by any utility-generation function. -- But we just use the values as-is for now. utility_vector = {player.hunger, player.thirst, player.idle} max_idx = maxArg(utility_vector) if max_idx == 1 then player.x+=1 player.state="fetch food" end if max_idx == 2 then player.x-=1 player.state="fetch water" end if max_idx == 3 then player.state="idle" end end 

As you can see, it is pretty simple. We can summarize it in a few steps:

1. Compute the Utility Vector

The Utility Vector maps states and utilities. So, its length is equal to the number of possible states. In our example, we have three states: fetch foodfetch water, and idle. Therefore, our utility vector will contain 3 values: the utility for bringing food ($$u_f$$), the utility for fetching water ($$u_w$$), and the utility of for being still ($$u_i$$).

In our example, we use hunger as the utility for fetching food ($$u_f = hunger$$), thirst as the utility for fetching water ($$u_w = thirst$$), and constant 1 as the utility for being still ($$u_i = 1$$). However, you can use any function you like.

For instance, imagine we want the weather temperature to influence the behavior of the AI. We may wish to tweak the utility so that, in hot environments, we prioritize getting water. We can just add something proportional to the temperature to the utility for fetching water ($$u_w = thirst + k\cdot temperature$$). Simple as that.

2. Select the state corresponding to the maximum utility

In our example, we use a maxArg function to return the array’s index of the maximum value. This is usually good enough.

3. Run the AI for that state

Once we have the state with the most utility, we run such a state.

Example in Action

You can see the embedded demo here, or use the png cartridge on your environment as a starting point for further experiments.