cppGOAP

A fork of cpowell/cppGOAP

Goal Oriented Action Programming (GOAP) is a planning architecture used in video games and other real-time applications. It's best described by Jeff Orkin here.

Give the GOAP planner a start and a goal and a list of possible actions and it'll plan a sequence of actions to reach the goal. Defining actions can be simpler and more modular than defining transitions for a finite state machine, plus it allows for more emergent behaviour.

How to use

Set up

• Install CMake.
• Clone this repo.
• Navigate to a directory where you'd like to put build files.
• Decide whether you want to build the library on it's own, or together with the examples.
• Run cmake -DCMAKE_CONFIGURATION_TYPES="Debug;Release" -DCMAKE_GENERATOR_PLATFORM=x64 -G "Visual Studio 16 2019" -S <path to CMakeLists.txt> from the command line. Replace Visual Studio 16 2019 with whatever build tool you're using. Replace <path to CMakeLists.txt> with either the path to the "goap" directory of this repo to build the library, or the path to the root of the repo to build the examples too.
• Open the generated "cppGoap.sln" or build with your build tool.

Simple usage

Everything provided is in the goap namespace.

A plan needs a start and a goal. These are each given to the planner as a WorldState. A WorldState is a simplified representation of the world which maps a variable/subject pair to a Value. Each variable is an integer identifier, and each subject is just a void* which you're free to set to whatever you like, as long as it's unique. Each Value in the world state can be a BOOL, FLOAT, INT or COMPARABLE/ARITHMETIC.

goap::PlanningParameters params;

params.start.Set(HAS_NUMBER, nullptr, true);
params.start.Set(HAS_RECIPE, nullptr, true);
params.start.Set(HUNGRY, nullptr, true);

params.goal.Set(HUNGRY, nullptr, false);

A plan is a sequence of actions. An Action is given a goal state to act on, and produces effects given that preconditions are met. A SimpleAction class is provided that stores Effects and Preconditions, and SimpleEffect and SimplePrecondition implementations are provided for those. Each Action has an integer identifier and a cost.

goap::PlanningParameters params;

std::shared_ptr<goap::SimpleAction> order = std::make_shared<goap::SimpleAction>(ORDER, 1);
eat->AddPrecondition(new goap::SimplePrecondition(HAS_NUMBER, nullptr, true));
eat->AddEffect(new goap::SimpleEffect(HUNGRY, nullptr, false));

std::shared_ptr<goap::SimpleAction> cook = std::make_shared<goap::SimpleAction>(COOK, 5);
cook->AddPrecondition(new goap::SimplePrecondition(HAS_RECIPE, nullptr, true));
cook->AddEffect(new goap::SimpleEffect(HUNGRY, nullptr, false));

params.actions = { order, cook };

The Planner and SlicedPlan classes are used to calculate a plan.

std::vector<goap::ActionSummary> plan = goap::Planner::Plan(params);

Or

goap::SlicedPlan sliced(params);
sliced.RunToCompletion();
sliced.Finalize();
std::vector<goap::ActionSummary> plan = sliced.Result;

Finally the plan that is created is a list of ActionSummary in order of expected execution.

for (int i = 0; i < plan.size(); i++)
{
	goap::ActionSummary nextAction = plan[i];
}

Advanced usage

The Action abstract class can be extended to create complex and dynamic actions.

class CustomAction : public goap::Action
{
public:
    CustomAction()
        : goap::Action(999) {}

    virtual std::vector<goap::EvaluatedAction> Act(void* world, const goap::WorldState& goal) override
    {
    	goap::EvaluatedAction evaluated;
        evaluated.id = this->id_;
	evaluated.preconditions.Set(...);
	evaluated.effects.Set(...);

	if (<failure condition>)
	    return {};

        return { evaluated };
    }
};

Custom actions are able to evaluate the current goal state (this is not necessarily the final goal state of the desired plan), and a user-provided void* when generating actions. The example above produces 0 or 1 actions, but as the return type is a vector, any number of actions can be returned.

A DistanceFunctionMap can be passed to the planner to override the default distance between non-equal values. These distances functions inform the heuristic used to calculate an estimate between each state and a goal state. Providing a custom distance function can help the planner converge on an optimal plan faster, but be careful as a distance function that overestimates the distance between two values can cause the planner to produce non-optimal plans.

The EvaluatedActions returned by Action::Act can be given a void* which will be passed back as part of the formulated plan. This might be useful for cases where an action acts on a specific target or has varying behaviour depending its desired effects.

Examples

There are four examples included:

• simple
• entity
• maze
• currency

The simple example project demonstrates basic usage, based on the examples in Jeff Orkin's slides. It shows how to use the Planner, SimpleAction and SimplePrecondition/Effect classes.

The entity example project demonstrates entity-specific state using the subject concept. In the example, an Agent must reach a Target by opening two doors in the correct sequence. This is a good resource for seeing how custom Action implementations might work in your project.

The maze example project is less of an example, more of a stress test. It manipulates complex state and produces long plans, and ends up being slow and very memory intensive. It may be worth looking at to get an idea of how you might use the SlicedPlan class in a game loop, but in general I don't recommend GOAP for solving dynamic mazes.

The currency example project demonstrates usage of the Comparable and Arithmetic variable types. Running the example will generate a plan for giving the hard-coded amount specified in exact change.