WaveFront - Real-time GOAP Planning

Planning algorithms are a central part of just about any game's artificial intelligence system. Many games require players to plan out what they're going to do to accomplish some goal - for example, to win capture-the-flag they'll have to plan how to get past the defending team, take the flag, and capture it safely. If NPCs are to be competitive players or believable actors in creating an immersive experience, they must be capable of planning their way through the game in a similar fashion. This is where planning algorithms like GOAP (Goal Oriented Action Planning) come into the picture.

GOAP is one of many ways to create a good AI, and it's commonly used and well known. It's an intuitive way for programmers to create an AI - the solver takes a logical representation of the world (the world state), and a description of what actions the NPC can perform, what preconditions must be met for each action to be useable, and what effects each action produces. The solver is given a goal state, and if the NPC is able to reach that goal state the solver will produce the sequence of actions required to get the NPC from the starting state to the goal state. Going back to the capture the flag example, the starting state might be that the enemy flag is guarded by two players and the NPC is thirty yards away. The plan might be to rush into close quarters, fight through the two defenders, pick up the flag, and escape to reach the goal state of capturing the enemy flag.

GOAP does not specifically require that any particular solving algorithm be used to produce the solution, and there are several types of solvers in common use. The first type explores all possible solutions and chooses the "best" one. This is an extremely limited solver, however, as it can only plan for very small problems (5 or 6 actions at most) in realtime - the amount of time it takes to produce a solution increases factorially with the number of actions! In order to get around this, many advanced GOAP systems solve with the A* pathfinding algorithm, but this also poses difficulties as A* is formulated as an algorithm in 2 or 3 dimensional Euclidean space, and the assumptions that it relies on to efficiently produce good solutions may not hold in the general state spaces that GOAP works on.

A couple of years ago Daniel developed a new solver for GOAP problems called WaveFront. Unlike A*, WaveFront is defined on general state graphs, not Euclidean space, but like A* it's typically able to converge very rapidly on an optimal or near-optimal solution. Source code for the reference implementation is not available, but the algorithm is not patented and an open source reimplementation is planned for MyWorld's AI system. Detailed notes from a recent presentation Daniel gave on WaveFront's design and implementation are available here: WaveFront Presentation.