active-logic / xgoap Goto Github PK

View Code? Open in Web Editor NEW

73.0 8.0 9.0 190 KB

Goal oriented action planning beyond GOAP

License: MIT License

C# 97.02% Shell 2.98%

unity3d goap gamedev planning-algorithms game-ai

xgoap's Introduction

Pre-release - APIs are more likely to change during the pre-release period.

Beyond G.O.A.P

A fresh take on Goal oriented action planning.

In GOAP, actions have preconditions, effects, and a cost. Boilerplate? Have a look.

public Cost ChopLog(){
    if(!hasAxe) return false;  // Precondtion
    hasFirewood = true;        // Effect
    return 4;                  // Cost
}

Use A* or, if no cost function available, BFS.

Engine agnostic models - test without pain.
.NET Core compatible
Unity integration with UPM support
Demo project to help you get started
[COMING SOON] integration with the BT Framework of Awesome, Active Logic 🚀

Install

Clone the repository and add the package to your project as normal.

For Unity 3D:

Add xgoap/package.json via package manager > + > add package from disk.
Alternatively, add "com.activ.goap": "https://github.com/active-logic/xgoap.git" to Packages/manifest.json

Getting started

Planning requires a model and a goal; if available, also provide a heuristic. I will borrow Brent Owens' woodcutter example.

A woodcutter has the GetAxe, ChopLog and CollectBranches actions. Here is our implementation of the woodcutter planning model:

using Activ.GOAP;

public class WoodChopper : Agent, Clonable<WoodChopper>{

    public bool hasAxe, hasFirewood;
    Option[] opt;  // Caching reduces array alloc overheads

    public Option[] Options()
    => opt = opt ?? new Option[]{ ChopLog, GetAxe, CollectBranches };

    public Cost GetAxe(){
        if(hasAxe) return false;
        hasAxe = true;
        return 2;
    }

    public Cost ChopLog() => hasAxe ? (Cost)(hasFirewood = true, 4f) : (Cost)false;

    public Cost CollectBranches() => (hasFirewood = true, 8);

    // Clonable<WoodChopper>

    public WoodChopper Allocate() => new WoodChopper();

    public WoodChopper Clone(WoodChopper x){
        x.hasAxe      = hasAxe;
        x.hasFirewood = hasFirewood;
        return x;
    }

    // Override for correctness (don't compare refs) and faster hashes

    override public bool Equals(object other) => other is WoodChopper that
        && hasAxe == that.hasAxe && hasFirewood == that.hasFirewood;

    override public int GetHashCode() => (hasAxe ? 1 : 0)
                                       + (hasFirewood ? 2 : 0);

}

Run the model and get the next planned action:

var chopper = new WoodChopper();
var solver  = new Solver<WoodChopper>();
var next    = solver.Next(chopper, goal: (x => x.hasFirewood, null));

Parametric actions are supported; they are concise and type safe. Check the Baker example.

Quick and simple Unity integration via GameAI.cs - for details, read here.

Ready to GOAP? Follow the guide.

Getting involved

If you'd like to get involved, consider opening (or fixing) an issue. Your support is appreciated!

xgoap's People

Contributors

Stargazers

Watchers

Forkers

almahmudrony hengle r2d2m vortexlash jinminglee paulsrock painfulexistence nicojuicy hengtek

xgoap's Issues

Reclaim model states when possible

In the course of expanding actions states are generated, which may be discarded almost right away:

If a planning action fails its preconditions, the state is discarded.
Likewise if the resulting state is redundant, it is discarded.

This is impacting GC; eval perf overhead and review Clone API

Alt API for costing actions

Currently actions are costed by changing a cost value attached to the model/agent. Ideally:

Cost should be associated with search nodes
Cost of an action should be part of return value, as this makes it less likely a user would forgt to assign a cost.

Expressing cost as an attribute would be nice except for many actions cost depends on actual parameters so this is probably too restrictive.

Previously visited state may not be added to set

Pushing a fix momently

As seen on GDC talk h function can be measured via number of matching vars when comparing two states. Probably better than nothing.
Having said that, only applies to non-procedural goals, which aren't explicit right now (beyond GOAP there is no distinction between "procedural" and "non-procedural" goals)
Planned as an optional feature

Remove baker demo from package

'Actions' should be a function, not a property

A good strategy for evaluating planning actions avail consists in returning a predefined list; having Actions as a function would be neater; how it looks now:

Func<Cost>[] _actions;
Func<Cost>[] actions => _actions;

How it should look:

Func<Cost>[] actions;
Func<Cost>[] Actions() => actions;

Parametric actions should follow this pattern (methods => Methods() in Parametric)

Don't return solver status as next node

Solver status (not found, success or limit exceeded) should be returned separately from next node or path.
Bear in mind that, in production not every client needs to retrieve solver status

Ease custom hashing

When performance is needed, HashSet is too generic. A programmer would normally take advantage of their own model structure to optimize processing.

Design and implement a demo

Multithreading

`Agent` vs `Parametric`

Both Agent and Parametric are single-function interfaces which define possible ways a model can return its available planning actions.
There isn't a clear reason here why Agent is associated with the solver, whereas Parametric is not.
Dig.

Recheck examples before milestone

Add unity demo to VCS

Although Unity demo isn't visual for now, still a good thing

Add continuous integration

Do not map no-args via SendMessage

Instead of mapping via SendMessage, directly invoke the client object, if possible; will improve consistency with parametric mappings

Let user control planning frequency/replanning policy

Whether replanning at every step, or duration based, or after attempting to fully execute a plan... implies tradeoffs that should be controlled by the designer.
In some cases a plan can't execute correctly through re-planning. For an example, consider a "visit every square" goal. In this case knowledge of what's been covered or not is implicit to the solution - replanning would break that.

Validate and fix README

Some of the tutorial/quick-start looks out of date

Relax cost ordering

For many problems getting a solution that's 100% optimal cost-wise is not a requirement; so we use a precision value to limit accuracy; this is a sweet spot thing - if accuracy is too low the benefit of the heuristic erodes and performance decreases; if accuracy is too high, cycles are wasted spending more time sorting nodes.

Depress actions involved in failing plans?

When a sequence of actions fails to execute as planned, depressing implicated actions would promote alternatives, if any.
The idea here is to sharply depress actions after a failure, with a quick recovery but somewhat incomplete recovery, to introduce an adaptive/learning element over time.
Proposed as an optional feature

Should `Action` be `Function`?

Right now, looks like:
Action[] Parametric.Functions()

Whereas the actions list looks like:
Func<Cost>[] Agent.Actions()

Not very intuitive.

Ease visual/text feedback

Main requirement here is having a qualified API for clients who want to provide visual or non visual reports, either while planning is in progress, or after planning has completed.
As a simple example, in the sentinel demo we'd like to have reports showing what locations on the map have been visited and what actions have been tried.

Remove OneArg

This is not needed now since arbitrary client functions are supported

replace `log()` in `GameAI`

Print() is the better choice here

Is cloning via serialization effective?

Cloning via serialization may be slow. Depending on test results consider providing an API to make replacing the clone method easier

Stalled should be MaxIterExceeded

Document project

Allow planning actions to clone and return model state

A custom clone method is helpful; allowing planning actions to provide their own has advantages:

A planning action knows what state it modifies. With a well structured model planning action can return a shallow copy, with only relevant sections re-allocated (uses less memory)
In turn this makes equality compares much faster, because un-modified refs can be detected right away.

Fix CI sticker

CI sticker shows build instead of tests

Nuget support

Add a 'world update' phase to the planner

Structurally GOAP is not adversarial. Still many uses include an adversarial element, or at least the need to somehow project possible evolution of world state over time.

Add coverage

Review 'Baker' example

test.sh should clean even if tests fail

Setup .NET compatibility

Though a separate repo would be nice too, it should be possible to just process the repo, strip Unity-related files, and build a Nuget package.

Add per frame planning budget

Right now planning must complete within the current frame. Obviously this isn't practical except for really small stuff

Custom failure handler

Planning either completes (done, failed) or terminates (max iter, capacity overflow); minimally, need an inspector setting to decide what to do next.

Defer retrieving method name

Only need method name for planning actions actually mapped to a client action; get method from delegate is costly so, this is worthwhile.
Yes, maybe we also want method names when printing plans. So, JIT method names

How to address 'consequences'?

In many possible scenarios a short term plan can succeed, but with negative consequences for the agent after the plan has completed.
Clarify how this should be handled.

Ease custom clone method

Unless serialization is really effective (and even then) there shouldn't be a need to subclass Solver just to provide a custom clone method for the model

Separate GOAP 'driver' from GameAI interface (Unity integration)

We'd like to provide a custom editor for the solver (display stats, paths, ...) but the subclassing approach gets in the way. Delegate.

License should display as MIT

Although license is MIT this apparently isn't picked up by Github.
UPM wants a License.md file.
Github wants a License file (without extension)
Would prioritize showing license correctly on Github; also should probably open an issue since there's no particular reason to think the Github automation should choke on this.

'busy' should be a property or function

Path() should return actions, not nodes

Equality and hashing defaults

Desirable because poorly implemented Equals() leads to solvers exceeding maxIter and/or maxNodes, negatively impacting dev workflow.
One possible route is via structs, but this implies a design effort (mutable structs are probably a poor choice; readonly structs will have restrictions impacting action design.
As an alternative, consider providing generic equality and hashing