GoapPlanner.cs

Source file unity-csharp/game-ai/goap/GoapPlanner.cs from the GDnD code examples. Download raw file

// GDnD wiki example
// Demonstrates: an A* planner that searches over world states, with actions as the edges
// Related pages: [[goal-oriented-action-planning]], [[pathfinding-algorithms]]
 
using System.Collections.Generic;
 
// Pathfinding A* searches over places; this A* searches over world states.
// Node = a world state. Edge = an action whose preconditions hold in that state.
// g = total action cost so far. h = number of goal facts still unmet.
// Returns the cheapest action list, or null when no plan exists.
public static class GoapPlanner
{
    private class Node
    {
        public WorldState State;
        public Node Parent;
        public GoapAction Action;   // the action that led here
        public float G;
        public float F;
    }
 
    public static List<GoapAction> Plan(WorldState start, Dictionary<string, bool> goal,
                                        List<GoapAction> actions, int maxExpansions = 1000)
    {
        var open = new List<Node> { new Node { State = start, G = 0, F = start.CountUnmet(goal) } };
        var bestCost = new Dictionary<string, float> { [start.Key()] = 0 };
 
        for (int i = 0; i < maxExpansions && open.Count > 0; i++)
        {
            // Take the open node with the lowest f = g + h. A plain list keeps this
            // readable; a priority queue is the usual upgrade for bigger action sets.
            Node current = open[0];
            foreach (Node n in open) if (n.F < current.F) current = n;
            open.Remove(current);
 
            if (current.State.Satisfies(goal)) return BuildPlan(current);
 
            foreach (GoapAction action in actions)
            {
                if (!current.State.Satisfies(action.Preconditions)) continue;
 
                WorldState next = action.ApplyTo(current.State);
                float g = current.G + action.Cost;
                string key = next.Key();
 
                // Skip states we have already reached at least as cheaply.
                if (bestCost.TryGetValue(key, out float known) && known <= g) continue;
                bestCost[key] = g;
 
                open.Add(new Node { State = next, Parent = current, Action = action,
                                    G = g, F = g + next.CountUnmet(goal) });
            }
        }
        return null;
    }
 
    // Walk back from the goal node to the start, then reverse into execution order.
    private static List<GoapAction> BuildPlan(Node node)
    {
        var plan = new List<GoapAction>();
        for (; node.Action != null; node = node.Parent) plan.Add(node.Action);
        plan.Reverse();
        return plan;
    }
}