Building a Game Bot with GOAP

In this article we'll take a detailed look at how to create a game AI using Goal-Oriented Action Planning in TypeScript.

GOAP is an approach to creating artificial intelligence that allows a bot to autonomously plan actions in a game. Instead of programming specific behavioral scenarios, we define individual actions that the bot combines into scenarios to achieve a goal. This makes the system more flexible and adaptive, allowing it to exhibit unique behavior that is difficult to predict in advance.

We applied this approach to the game LandLords, creating a bot that plans its actions independently. In this game victory depends on the ability to combine different strategies. The bot constantly analyzes the situation and adapts to the unpredictable decisions of its opponents, making it a challenging and interesting opponent. The generative nature of the map creates even more opportunities for tactical maneuvers, and resource trading also adds an element of unpredictability. The bot accomplishes all this with the help of a planner.

This planner is our bot, the action plan generator, the heart of the AI system. The planner is a pure function that takes the current state of the game world and a list of available actions as input and returns the optimal action plan for achieving a given goal. Let's now take a closer look at what this GOAP bot is. I'll use simple analogies about beer to make this clear. Cheers 🍻😄

Planning algorithm

The GOAP implementation is based on a planning algorithm, essentially a breadth-first search (BFS). BFS itself is fairly academic, so we won't go into detail. However, we will examine the other components in detail — though simple, they are crucial for understanding GOAP. I especially want to note that this planner works with numeric values, an advantage often missing in other implementations. Here are three key functions that form the basis of bot planning:

1. isGoalReached — whether the goal has been reached.
2. sortPlanQueue — sorting plans.
3. perform — performing a potential action.

1. isGoalReached

Any game state can be described as a set of facts: boolean or numeric values. To determine whether a goal has been achieved, we check whether the current game state matches the goal. The goal and state are represented as GoalFacts objects. The check is very simple: boolean values are compared directly and numeric values are compared as greater than or equal to.

type GoalFacts = Record<string, (boolean | number)>

const isGoalReached = (
  goal: GoalFacts,
  state: GoalFacts,
) => Object
  .entries(goal)
  .every(([key, value]) => (typeof value === 'number'
    ? state[key] as number >= value
    : state[key] as boolean == value))

We can't buy beer if we don't have enough money and proof of age with us :D

2. sortPlanQueue

Sorting is used to find the most profitable course of action. We sort the plan queue before processing a step to minimize the number of required steps and maximize their efficiency. If two plans are the same length, we prefer the one with the higher total “reward” — that is, the one that brings more benefit. Otherwise, the plan with the fewest steps is prioritized: we try to achieve the goal by the shortest route.

It sounds complicated but it's quite intuitive. If we need to buy beer, we'll go to the store where it's cheaper. And if the prices are the same in both stores, we'll go to the one that's closer :D

type ItemQueue = {
  state: GoalFacts
  plan: Action[]
  totalUtility: number
}

const sortPlanQueue = (a: ItemQueue, b: ItemQueue) => {
  return a.plan.length === b.plan.length
    ? b.totalUtility - a.totalUtility
    : a.plan.length - b.plan.length
}

3. perform

This function allows you to simulate the execution of an action and evaluate its impact on the game state. It's like a trial run of an action plan to ensure it will achieve the goal. The function doesn't apply the action directly, but rather calculates a new game state based on the estimated effects of each step in the plan.

const perform = (
  facts: GoalFacts,
  effects: GoalFacts,
): GoalFacts => {
  const result = { ...facts }

  for (const key in effects) {
    const value = effects[key]

    result[key] = typeof value === 'number'
      ? value + (result[key] as number ?? 0)
      : value
  }

  return result
}

Before going out for a beer, we imagine going to the store, paying for it, getting the beer, and updating our inventory :D

Actions

Next, let's look at actions, which are described by the Action type. An action is an atomic unit of work that a bot can perform to change the game state. An action is the basic building block, a “ladder segment”, that we use to create a scenario. Each action has preconditions, which determine when it can be executed, and effects, which change the game state. When sorting plans, we used the totalUtility field, which is a combination of two values: reward and priority. These fields are optional, but they help clearly express the reward. We could have used only the reward field, but priority acts as an additional influence factor: “This needs to be done very urgently, even if it yields few or no reward points.”

type Action = {
  name: string
  preconditions: GoalFacts
  effects: GoalFacts
  reward?: number
  priority?: number
}

All actions can be serialized in JSON, which guarantees declarativeness. However, I prefer the JavaScript/TypeScript notation, as it allows for the use of the + prefix for numeric effects. This notation better conveys intent and allows us to more intuitively perceive changes in the game state as additions or deductions of values.

const action: Action = {
  name: 'BuyBeer',
  preconditions: { hasDocument: true, money: 10 },
  effects: { beer: +1, money: -10 },
}

Goal 🎯

Finally, let's look at how to set a goal for the planner. The goal is the desired future state of the game world that must be achieved. The goal is described taking into account what already exists in the game state, without any additional interim details.

const state = { beer: 2 } satisfies GoalFacts
const goal = { beer: state.beer + 1 } satisfies GoalFacts

If you need to get 1 more beer 🍺
And you already have 2 beers 🍺🍺
Then your final goal is 3 beers! 🍺🍺🍺
Without mentioning documents and money :D

GOAP-solver

And that's all you need to create the bot's intelligence. I've prepared a source code repository github/13luck/goap-solver so you can explore everything yourself. The repository includes several tests demonstrating trading using the game LandLords, and of course, an example of buying beer. I've also published an NPM package goap-solver, which you can install and test yourself.

This scheduler works with number and boolean values. The key planner function is pure and predictable: it always builds the same plan for the same conditions. This makes it easy to test with unit tests.

Working with the planner looks like this:

import { planner, Action, GoalFacts } from 'goap-solver'

// define world state
const state = {
  hasDocument: false,
  money: 0,
  beer: 2,
} satisfies GoalFacts

// define what we want to achieve
const goal = { beer: state.beer + 1 } satisfies GoalFacts

// define available actions
const a: Action = {
  name: 'GetDocument',
  preconditions: { hasDocument: false },
  effects: { hasDocument: true },
  priority: 1,
}
const b: Action = {
  name: 'GetMoney',
  preconditions: { money: 0 },
  effects: { money: +10 },
  priority: 2,
}
const c: Action = {
  name: 'BuyBeer',
  preconditions: { hasDocument: true, money: 10 },
  effects: { beer: +1, money: -10 },
}

const actions = [c, b, a]
const plan = planner(state, goal, actions)
const result = plan?.map(({ name }) => name)

expect(result).toEqual(['GetDocument', 'GetMoney', 'BuyBeer'])

Demo

This is a simple interactive demonstration of the Goal-Oriented Planning (GOAP) algorithm. You see a small maze. You can change its structure by adding or removing walls by simply clicking on them.

Our agent's goal 😊 is to reach the beer mug 🍺. Each time the maze is modified the planner re-searches the optimal path from the start to the goal. Try building different maze configurations and see how the system finds solutions.

Performance

Regarding GOAP's complexity: the more facts and actions, the greater the variability. The algorithm actually enumerates all options, which can lead to very long calculations — the overall complexity is exponential due to the nature of the planning problem itself. To avoid this, it's best to stick to small spaces and a limited set of facts. Then, the calculations will be virtually instantaneous, and the planner will quickly find a solution without resorting to extensive search. In the game LandLords, economic relations are expressed minimally — literally in units — which is very well suited for GOAP.

The presented implementation is quite simple and has a clear bottleneck: sorting. You can improve this aspect yourself: the current version is more of an educational one, but it still handles the planning problem well.

LandLords game bot

One of the key challenges in online multiplayer games is ensuring players have enough players to play with. We spent a long time considering implementing a bot, but it wasn't immediately clear how to implement it — it was a difficult development challenge, since despite the simple gameplay, the bots' decisions must be strategic, not random.

Of course, we looked at Catanatron, the only open-source bot for Catan that, according to the developer, plays well. However, it wasn't suitable for us for several reasons: the difficulty of adaptation and the expensive support. It's much easier to write our own solution in GOAP, even if it's not initially designed for grandmasters, which is what we did.

Also, one of the reasons we abandoned Catanatron was the need for a specific server environment. It's easier to run the bot's calculations directly in the player's browser. However, calculating plans in the browser can be resource-intensive, which can lead to interface freezes. To solve this problem, we used Web Worker ⚙️, which allows calculations to be performed in a separate thread without blocking the main interface thread.

Yes, right now this is the beginning of a bot with a simple goal cascade, and it may seem a bit silly to a Catanist, but the bot already knows how to play and displays behavior resembling intelligence. A more comprehensive algorithmic framework for the bot's strategies can be implemented later; for now, we're satisfied with its flawless execution.

Conclusion

GOAP is a simple and powerful tool for creating autonomous agents that can be used in a wide range of fields, not just games. Its strength lies in the fact that you don't hardcode specific scenarios, but focus on combinable actions, leaving you more time for creativity. I hope I've been able to explain its principles clearly and in a friendly manner, and that this material will help you start creating your own bots, and that the beer analogies didn't confuse you at all. Cheers 🍻😄