GOAP: Goal-Oriented Action Planning

0. La revolución de F.E.A.R.

En 2005 salió F.E.A.R. y los soldados enemigos hacían cosas que parecían magia: tiraban granadas para flanquear, se cubrían cuando recargabas, gritaban “covering fire” y se coordinaban. La prensa pensó que tenía la IA más sofisticada de la década. La realidad: usaba GOAP con apenas 3 goals y ~15 acciones.

GOAP separa qué quiere lograr de cómo lo logra. El designer escribe goals (“matar al jugador”) y acciones con preconditions/effects. El runtime busca con A* la secuencia óptima desde el estado actual. Si el mundo cambia (te cubrís, recargás, te alejás), el plan se rehace.

3 pasos · costo 9 · 14 nodos expandidos · 16 aristas↺ Reset

Editar estado inicial

tiene hachatiene armahacha cercaarma cercajugador en meleejugador a tirojugador vivoen coberturahp alto

Goal fijo: jugador vivo = false. El planner busca con A* la secuencia de acciones más barata. Toca los toggles del estado inicial: si quitás "hacha cerca" Y "arma cerca", el planner falla — el goal se vuelve inalcanzable.

Figura 1 — Goal: playerAlive=false. Modificá el estado inicial con los toggles y el planner busca otra ruta. Si quitás “hacha cerca” Y “arma cerca” simultáneamente, el goal se vuelve inalcanzable.

Lo usan F.E.A.R., Empire Earth, Just Cause 2, Shadow of Mordor, Tomb Raider 2013, Middle-earth: Shadow of Mordor.

1. Los tres conceptos

class WorldState:
    facts: Map<string, bool>     // hasGun, playerAlive, atCover...

class Action:
    preconditions: WorldState     // qué debe ser true antes
    effects: WorldState           // qué pasa a ser true después
    cost: number                  // peso para A*

class Goal:
    targetState: WorldState       // qué claves deben matchear al final

1.1 World state como bag de booleanos

El “mundo” no es una clase mountainosa: es un set de hechos discretos.

hasAxe: false
hasGun: true
gunNearby: false
playerInRanged: true
playerAlive: true
atCover: false

Para problemas chicos (~10 hechos, ~10 acciones), un Map<string, boolean> alcanza. Para problemas grandes hay representaciones más compactas (bitsets, STRIPS), pero la simplicidad gana en gamedev.

1.2 Acción = preconditions → effects

Una acción abstracta dice qué necesita y qué cambia. No dice cómo se ejecuta — eso es responsabilidad del game code.

attackRanged:
    preconditions: { hasGun: true, playerInRanged: true, playerAlive: true }
    effects: { playerAlive: false }
    cost: 3

approachPlayer:
    preconditions: { playerInRanged: false, playerAlive: true }
    effects: { playerInRanged: true, playerInMelee: true }
    cost: 4

El “cost” es para el planning, no es tiempo real — refleja “qué tan deseable” es esa acción. Una acción peligrosa tiene cost alto; una segura, cost bajo.

1.3 Goal: estado deseado

Un subset del world state que el NPC quiere lograr.

goal_kill_player: { playerAlive: false }
goal_get_safe:    { atCover: true, hpHigh: true }
goal_patrol:      { atWaypoint: true }

Los goals tienen prioridad: el NPC elige el más urgente y planifica para ese.

2. El planner: A* sobre estados

El planner busca el camino más barato desde el estado inicial al goal usando A*. La diferencia con A* clásico:

• Los nodos son estados del mundo (no celdas).
• Las aristas son acciones aplicables (no movimientos).
• El costo es el cost de la acción.
• La heurística es número de claves del goal aún no satisfechas (Hamming distance).

A* expande nodos en orden de f = g + h: costo acumulado más heurística (claves del goal aún no satisfechas). Los nodos en gris fueron explorados pero descartados; los nodos coloreados forman el plan óptimo. Notá cómo el goal "playerAlive=false" se alcanza con muy pocas expansiones porque la heurística guía bien.

Figura 2 — Espacio de estados explorado por A. Cada nodo es un estado; cada arista, una acción. El path coloreado es el plan óptimo; los grises son estados explorados pero descartados.*

function plan(initialState, goal, actions):
    open = priority_queue()
    open.push({ state: initialState, g: 0, f: h(initialState) })
    closed = set()

    while open not empty:
        cur = open.pop_lowest_f()
        if matches(cur.state, goal): return reconstruct(cur)
        if cur.state in closed: continue
        closed.add(cur.state)

        for action in actions:
            if not applicable(cur.state, action): continue
            next = apply(cur.state, action.effects)
            g2 = cur.g + action.cost
            f2 = g2 + h(next, goal)
            open.push({ state: next, parent: cur, action, g: g2, f: f2 })

    return null  # goal inalcanzable

2.1 Backward chaining (alternativa)

Algunos planners GOAP corren A* al revés: del goal hacia el estado inicial. La heurística cambia: número de claves del estado inicial que aún no se han logrado. La ventaja: desde el goal, el branching factor suele ser más chico (pocas acciones tienen effects que cubran una clave del goal).

F.E.A.R.’s Jeff Orkin describió ambas. En la práctica, forward está bien para problemas pequeños y es más fácil de entender.

2.2 ¿Cuándo es factible A*?

GOAP funciona si:

• N hechos relevantes ≤ ~30. Cada hecho duplica el estado posible; >30 y el espacio es ~10⁹.
• Plan típico ≤ ~10 pasos. Si necesitás 50 acciones para un plan, hay algo mal modelado.
• Re-plan en frecuencia baja (1× por segundo, no 60× por segundo). Una corrida típica tarda 1–10 ms.

Para problemas más grandes existen variantes (Hierarchical Task Networks, HTN), pero para gamedev clásico GOAP basta.

3. Re-planning: el corazón de la flexibilidad

replans: 0planificando inicial

Toggle hacha cercaToggle arma cercaToggle cobertura

El NPC va ejecutando el plan paso a paso. Cuando tocás un toggle del mundo (por ej. "quitar el hacha"), si el siguiente paso del plan ya no es aplicable, el planner se ejecuta otra vez y el NPC adopta la nueva ruta. Eso es lo que un BT no haría sin ramas explícitas para cada eventualidad.

Figura 3 — El NPC ejecuta su plan. Tocá los toggles del mundo en vivo: si quitás “hacha cerca” mientras el NPC iba a recogerla, detecta que el siguiente paso ya no es aplicable y replanifica desde cero. Esa es la magia.

function tick():
    if currentPlan is empty or not validForCurrentState():
        currentPlan = plan(currentState, currentGoal, actions)

    if currentPlan is empty:
        # goal inalcanzable; pickear otro goal o idle
        currentGoal = nextGoal()
        return

    nextAction = currentPlan.peek()
    if nextAction.preconditions match currentState:
        execute(nextAction)
        if completed: currentPlan.pop()
    else:
        # algo cambió mid-execution; replan
        currentPlan = []

El re-planning es lo que diferencia GOAP de un BT. Un BT con ramas hardcoded fallaría en combinaciones del mundo no anticipadas; GOAP busca dinámicamente.

4. GOAP vs Behavior Tree

✓ hacha cerca✓ arma cerca✓ hp alto✗ en cobertura

Cambia las condiciones del mundo. El BT (izquierda) tiene ramas explícitas hardcoded; cubre los casos típicos pero falla en combinaciones imprevistas. GOAP (derecha) replanifica desde cero cada vez — siempre encuentra una ruta si existe.

Figura 4 — Mismo escenario, dos enfoques. Tocá los toggles y observá cómo el BT cae en idle ⚠ cuando el dev no anticipó la combinación; GOAP siempre encuentra una ruta si existe.

Cuándo GOAP

• NPCs táctica: combate con mucha situacional dependency.
• Cuando el set de combinaciones de mundo es alto y diseñar BT exhaustivos sería tedioso.
• Re-planning frecuente ante cambios del mundo.
• Designers que entienden preconditions/effects pueden escribir nuevas acciones sin tocar el árbol completo.

Cuándo BT

• Comportamiento scripted con cinemáticas: cuando la secuencia es fija.
• Boss patterns: ataques predecibles, fases discretas.
• Equipos que no quieren hacer profiling de A* cada frame.
• Performance-critical: BT corre en O(profundidad árbol activo); GOAP corre A*.

Híbrido (lo que se usa en prod)

BT global como skeleton (estructura macro: combat / explore / cinematic). En la “hoja” de combate, en vez de tener 20 ramas más, llamás a GOAP para que planifique los próximos 3-5 pasos. Lo mejor de ambos.

5. Personalidad por goals y costs

soldado_ofensivo:
    goals: [
        { kill_player: priority 10 },
        { take_cover: priority 3 },
    ]
    actions: [...]  // costs estándar

soldado_defensivo:
    goals: [
        { take_cover: priority 8 },
        { kill_player: priority 5 },
    ]
    actions con cost ajustado:
        attackRanged.cost: 5  # más caro → menos preferido
        takeCover.cost: 1     # baratísimo

Mismo grafo, distinto comportamiento. Los designers expresan personalidad sin tocar código.

6. Pseudocódigo limpio

class GOAPPlanner:
    function plan(initial, goal, actions) -> Plan?:
        if matches(initial, goal): return []  # ya satisface
        open = pq([{ state: initial, g: 0, f: h(initial, goal), parent: null, action: null }])
        closed = set()

        while open not empty:
            cur = open.pop_min_f()
            if matches(cur.state, goal): return reconstruct(cur)

            ck = stateKey(cur.state)
            if ck in closed: continue
            closed.add(ck)

            for action in actions:
                if not stateMatches(cur.state, action.preconditions): continue
                next = apply(cur.state, action.effects)
                g = cur.g + action.cost
                f = g + h(next, goal)
                open.push({ state: next, g, f, parent: cur, action })

        return null

    function reconstruct(node) -> List<Action>:
        path = []
        while node.action:
            path.unshift(node.action)
            node = node.parent
        return path

function h(state, goal) -> int:
    count = 0
    for key, val in goal:
        if state[key] != val: count++
    return count

7. Implementación en Unity / C#

public class WorldState : Dictionary<string, bool> {
    public bool Matches(WorldState partial) {
        foreach (var kv in partial)
            if (!TryGetValue(kv.Key, out var v) || v != kv.Value) return false;
        return true;
    }

    public WorldState ApplyEffects(WorldState effects) {
        var next = new WorldState();
        foreach (var kv in this) next[kv.Key] = kv.Value;
        foreach (var kv in effects) next[kv.Key] = kv.Value;
        return next;
    }
}

public abstract class GOAPAction {
    public string id;
    public WorldState preconditions;
    public WorldState effects;
    public float cost = 1f;

    public abstract IEnumerator Execute(IAgent agent);
    public virtual bool IsRunnable(IAgent agent) => true; // chequeo extra runtime
}

public class GOAPPlanner {
    public List<GOAPAction> actions;

    public Queue<GOAPAction> Plan(WorldState initial, WorldState goal) {
        var open = new SortedSet<Node>();
        open.Add(new Node { state = initial, g = 0, f = Heuristic(initial, goal) });
        var closed = new HashSet<string>();

        while (open.Count > 0) {
            var cur = open.Min;
            open.Remove(cur);
            if (cur.state.Matches(goal)) return Reconstruct(cur);

            string key = StateKey(cur.state);
            if (closed.Contains(key)) continue;
            closed.Add(key);

            foreach (var a in actions) {
                if (!cur.state.Matches(a.preconditions)) continue;
                var next = cur.state.ApplyEffects(a.effects);
                float g = cur.g + a.cost;
                open.Add(new Node {
                    state = next, parent = cur, action = a,
                    g = g, f = g + Heuristic(next, goal)
                });
            }
        }
        return null;
    }

    int Heuristic(WorldState s, WorldState goal) {
        int h = 0;
        foreach (var kv in goal)
            if (!s.TryGetValue(kv.Key, out var v) || v != kv.Value) h++;
        return h;
    }
}

8. Errores comunes

1. Olvidar que effects pueden romper preconditions — una acción que setea playerAlive=false invalida cualquier acción que requiera playerAlive=true. Eso está OK, pero podés sorprenderte.
2. Goals competidores — si un NPC tiene goal “matar jugador” y “estar a salvo” y ambos suman, los planes se cancelan. Los goals deben ser mutex o jerarquizados.
3. Cost arbitrario — si todas las acciones tienen cost 1, el planner devuelve el plan más corto (menos pasos). Eso a veces no es lo que querés. Tunealo según preferencia táctica.
4. No replanning — si el agente ejecuta pickUpAxe y entre que decidió y ejecutó, otro NPC se la llevó, sin replan, falla silenciosa.
5. Demasiados hechos en world state — el espacio explota. Mantenélo a ~15-25 booleans en gamedev típico.
6. Acciones sin effects — si una acción no setea nada, no aporta al plan; el A* la ignora. Útil para “actions virtuales”, pero suele ser un bug.

9. Quiz

Pon a prueba lo que entendiste

Responde una por una. La explicación aparece al elegir, correcta o no.

1. ¿Por qué F.E.A.R. parecía tener IA tan avanzada con apenas 3 goals y ~15 acciones?

   • AEl planner combinaba acciones de formas que el dev nunca enumeró explícitamente.
   • BF.E.A.R. usaba aprendizaje automático.
   • CF.E.A.R. tenía pathfinding más rápido.

2. Tu NPC con BT cae en `idle` cuando el jugador hizo algo no anticipado por el dev. ¿Cómo lo arregla GOAP?

   • AGOAP busca dinámicamente cualquier secuencia que cumpla el goal, sin necesidad de ramas explícitas para cada caso.
   • BGOAP es más rápido que BT.
   • CGOAP tiene más acciones por defecto.

3. ¿Qué es la heurística h() típica en GOAP?

   • ANúmero de claves del goal que aún no están satisfechas (Hamming distance).
   • BDistancia geométrica entre NPC y jugador.
   • CSuma de costs de acciones disponibles.

4. Tu agente está ejecutando un plan de 5 pasos. En el paso 3, el mundo cambia y el siguiente paso ya no es aplicable. ¿Mejor approach?

   • ADetectar la invalidez (preconditions del próximo paso no se cumplen) y replanificar desde el estado actual.
   • BIgnorar el cambio y ejecutar el paso anyway; lidiar con el bug en runtime.
   • CCancelar el plan completo y entrar a estado idle.

10. Siguientes pasos

GOAP planifica acciones, pero asume que el NPC sabe el estado del mundo. ¿Cómo se entera de cosas como “el jugador está a 12m”? Esa es la última pieza: percepción. Visión, audio, memoria — los sentidos del NPC. Te toca el siguiente.