BehaviorTree.h

Go to the documentation of this file.

/**
 * @file BehaviorTree.h
 * @brief Data-driven behavior tree system for AI decision making
 * @author Nicolas Chereau
 * @date 2025
 * @version 2.0
 * 
 * @details
 * This file implements a behavior tree system for creating complex AI behaviors.
 * Behavior trees are hierarchical structures that make decisions based on conditions
 * and execute actions based on those decisions.
 * 
 * Key features:
 * - Composite nodes: Selector (OR), Sequence (AND)
 * - Decorator nodes: Inverter, Repeater
 * - Condition nodes: State checking (health, target, etc.)
 * - Action nodes: Behaviors (move, attack, patrol, etc.)
 * - JSON-based tree definitions
 * - Per-entity tree execution
 * 
 * @note Behavior Tree purpose: Data-driven behavior tree system for AI decision making.
 * 
 * @example
 * @code
 * // Load behavior tree from JSON
 * BehaviorTree::LoadTreeForEntity(npcEntity, "Blueprints/BehaviorTrees/Patrol.json");
 * 
 * // Update tree each frame
 * BehaviorTree::UpdateEntity(npcEntity, deltaTime);
 * @endcode
 */
 
#pragma once
 
#include "../ECS_Entity.h"
#include "../vector.h"
#include <vector>
#include <string>
#include <cstdint>
#include <map>
#include <algorithm>
#include <set>
 
// Forward declarations
struct AIBlackboard_data;
 
/**
 * @enum BTNodeType
 * @brief Behavior tree node types
 * 
 * Defines the different types of nodes that can exist in a behavior tree.
 */
enum class BTNodeType : uint8_t
{
    Selector = 0,       ///< OR node - succeeds if any child succeeds
    Sequence,           ///< AND node - succeeds if all children succeed
    Condition,          ///< Leaf node - checks a condition
    Action,             ///< Leaf node - performs an action
    Inverter,           ///< Decorator - inverts child result
    Repeater,           ///< Decorator - repeats child N times
    Root,               ///< Phase 38b: Root node - entry point of behavior tree (green, fixed position)
    OnEvent,            ///< Phase 38b: OnEvent root - event-driven entry point (orange, event-triggered)
    SubGraph = 8        ///< Phase 39: SubGraph - external graph reference (recursive BT or ATS)
};
 
/**
 * @enum BTStatus
 * @brief Behavior tree node execution status
 * 
 * Represents the current state of a behavior tree node.
 */
enum class BTStatus : uint8_t
{
    Idle = 0,           ///< Node waiting for execution (not yet started)
    Running = 1,        ///< Node is currently executing
    Success = 2,        ///< Node completed successfully
    Failure = 3,        ///< Node failed
    Aborted = 4         ///< Node execution interrupted (e.g., entity destroyed)
};
 
/**
 * @enum BTConditionType
 * @brief Built-in condition types for behavior trees
 * 
 * Predefined conditions that can be checked during tree execution.
 */
enum class BTConditionType : uint8_t
{
    TargetVisible = 0,              ///< Can see target entity
    TargetInRange,                  ///< Target within specified range
    HealthBelow,                    ///< Health below threshold
    HasMoveGoal,                    ///< Movement goal is set
    CanAttack,                      ///< Attack is available
    HeardNoise,                     ///< Detected noise
    // NEW: Wander behavior conditions
    IsWaitTimerExpired,             ///< Wait timer expired?
    HasNavigableDestination,        ///< Navigable destination chosen?
    HasValidPath,                   ///< Valid path calculated?
    HasReachedDestination,          ///< Reached destination?
    // Catalog aliases for better readability
    HasTarget = TargetVisible,          ///< Alias for HasTarget condition
    IsTargetInAttackRange = TargetInRange  ///< Alias for range check
};
 
/**
 * @enum BTActionType
 * @brief Built-in action types for behavior trees
 * 
 * Predefined actions that can be executed during tree execution.
 */
enum class BTActionType : uint8_t
{
    SetMoveGoalToLastKnownTargetPos = 0, ///< Move to last seen target position
    SetMoveGoalToTarget,                  ///< Move towards current target
    SetMoveGoalToPatrolPoint,             ///< Move to next patrol waypoint
    MoveToGoal,                           ///< Execute movement to goal
    AttackIfClose,                        ///< Attack if in range
    PatrolPickNextPoint,                  ///< Select next patrol point
    ClearTarget,                          ///< Clear current target
    Idle,                                 ///< Do nothing
    // NEW: Wander behavior actions
        WaitRandomTime,                       ///< Initialize random timer (param1=min, param2=max)
        ChooseRandomNavigablePoint,           ///< Choose navigable point (param1=searchRadius, param2=maxAttempts)
        RequestPathfinding,                   ///< Request pathfinding to moveGoal via MoveIntent
        FollowPath,                           ///< Follow the path (check progression)
        SendMessage,                          ///< Emit event to EventQueue (param1=EventType enum)
        // Catalog aliases for better readability
        MoveTo = MoveToGoal,                  ///< Alias for MoveTo action
        AttackMelee = AttackIfClose           ///< Alias for melee attack
    };
 
/**
 * @struct BTNode
 * @brief Represents a single node in a behavior tree
 * 
 * Can be a composite, decorator, condition, or action node.
 * Stores node type, parameters, and child references.
 */
struct BTNode
{
    BTNodeType type = BTNodeType::Action;   ///< Node type
    uint32_t id = 0;                        ///< Unique node ID within tree
    
    // For composite nodes (Selector, Sequence)
    std::vector<uint32_t> childIds;         ///< IDs of child nodes
    
    // For condition nodes
    BTConditionType conditionType = BTConditionType::TargetVisible;  ///< Condition type (enum)
    std::string conditionTypeString;         ///< Condition type as string (for flexible conditions like CheckBlackboardValue)
    float conditionParam = 0.0f;            ///< Generic parameter for conditions
    
    // For action nodes
    BTActionType actionType = BTActionType::Idle;  ///< Action type
    float actionParam1 = 0.0f;              ///< Generic parameter 1 for actions
    float actionParam2 = 0.0f;              ///< Generic parameter 2 for actions
    
    // For decorator nodes
    uint32_t decoratorChildId = 0;
    int repeatCount = 1;                    // For Repeater decorator
    
    // Debug info
    std::string name;
 
    // Editor positioning (for visual layout in BehaviorTree editor)
    float editorPosX = 0.0f;                ///< Horizontal position in editor canvas (pixels)
    float editorPosY = 0.0f;                ///< Vertical position in editor canvas (pixels) - used for execution order sorting
 
    // Flexible parameters (for new condition/action types that need structured data)
    std::map<std::string, std::string> stringParams;  ///< String parameters
    std::map<std::string, int> intParams;             ///< Integer parameters
    std::map<std::string, float> floatParams;         ///< Float parameters
 
    // Phase 38b: Event-driven execution fields
    std::string eventType;                  ///< Event type listener (e.g., "Olympe_EventType_AI_Explosion")
    std::string eventMessage;               ///< Optional event message filter (for future event filtering)
    uint32_t onEventRootIndex = 0;          ///< Index into BehaviorTreeAsset::m_eventRootIds for backreference
 
    // Phase 39: SubGraph support
    std::string subgraphPath;               ///< Path to external .bt.json or .ats file
    std::map<std::string, std::string> subgraphInputs;   ///< Input bindings: "childVar" → "parentVar"
    std::map<std::string, std::string> subgraphOutputs;  ///< Output bindings: "childVar" → "parentVar"
 
    // Helper methods for parameter access
    std::string GetParameterString(const std::string& key, const std::string& defaultValue = "") const
    {
        auto it = stringParams.find(key);
        return (it != stringParams.end()) ? it->second : defaultValue;
    }
    
    int GetParameterInt(const std::string& key, int defaultValue = 0) const
    {
        auto it = intParams.find(key);
        return (it != intParams.end()) ? it->second : defaultValue;
    }
    
    float GetParameterFloat(const std::string& key, float defaultValue = 0.0f) const
    {
        auto it = floatParams.find(key);
        return (it != floatParams.end()) ? it->second : defaultValue;
    }
};
 
/**
 * @struct BTValidationMessage
 * @brief Validation message for behavior tree structure checking
 */
struct BTValidationMessage
{
    enum class Severity : uint8_t
    {
        Info = 0,
        Warning = 1,
        Error = 2
    };
    
    Severity severity = Severity::Info;
    uint32_t nodeId = 0;
    std::string message;
};
 
// --- Behavior Tree Asset ---
struct BehaviorTreeAsset
{
    uint32_t id = 0;                        // Unique tree ID
    std::string name;
    std::vector<BTNode> nodes;
    uint32_t rootNodeId = 0;
 
    // Phase 38b: Event-driven execution roots (separate from main Root)
    std::vector<uint32_t> m_eventRootIds;   // IDs of OnEvent root nodes
 
    // Helper: get node by ID
    BTNode* GetNode(uint32_t nodeId)
    {
        for (auto& node : nodes)
        {
            if (node.id == nodeId)
                return &node;
        }
        return nullptr;
    }
    
    const BTNode* GetNode(uint32_t nodeId) const
    {
        for (const auto& node : nodes)
        {
            if (node.id == nodeId)
                return &node;
        }
        return nullptr;
    }
 
    // Get children of a node sorted by Y-position (execution order)
    // Returns vector of child IDs sorted by editorPosY (lowest Y = executes first = index 1)
    std::vector<uint32_t> GetChildrenSortedByY(uint32_t parentId) const
    {
        const BTNode* parent = GetNode(parentId);
        if (!parent) return {};
 
        // Create pairs of (editorPosY, childId)
        std::vector<std::pair<float, uint32_t>> childrenWithY;
        for (uint32_t childId : parent->childIds)
        {
            const BTNode* child = GetNode(childId);
            if (child)
            {
                childrenWithY.push_back({child->editorPosY, childId});
            }
        }
 
        // Sort by Y-position (ascending: top node = first to execute)
        std::sort(childrenWithY.begin(), childrenWithY.end(),
                  [](const std::pair<float, uint32_t>& a, const std::pair<float, uint32_t>& b)
                  {
                      return a.first < b.first;
                  });
 
        // Extract sorted child IDs
        std::vector<uint32_t> sortedIds;
        for (const auto& pair : childrenWithY)
        {
            sortedIds.push_back(pair.second);
        }
        return sortedIds;
    }
 
    // Get execution index of a child within its parent (1-based)
    // Returns 0 if not found or parent is not composite
    uint32_t GetChildExecutionIndex(uint32_t parentId, uint32_t childId) const
    {
        std::vector<uint32_t> sortedChildren = GetChildrenSortedByY(parentId);
        for (size_t i = 0; i < sortedChildren.size(); ++i)
        {
            if (sortedChildren[i] == childId)
            {
                return static_cast<uint32_t>(i + 1);  // 1-based indexing
            }
        }
        return 0;  // Not found
    }
 
    // Validation methods
    std::vector<BTValidationMessage> ValidateTreeFull() const;
    bool DetectCycle(uint32_t startNodeId) const;
 
    // Phase 38b: Ensure a Root node exists (auto-create if missing)
    void EnsureRootNodeExists();
 
    // Editor CRUD operations
    uint32_t AddNode(BTNodeType type, const std::string& name, const Vector& position);
    bool RemoveNode(uint32_t nodeId);
    bool ConnectNodes(uint32_t parentId, uint32_t childId);
    bool DisconnectNodes(uint32_t parentId, uint32_t childId);
    uint32_t GenerateNextNodeId() const;
};
 
// --- Phase 39: SubGraph Call Stack ---
// Tracks active SubGraph paths to prevent infinite recursion and cycles
struct SubGraphCallStack
{
    std::vector<std::string> pathStack;     ///< Stack of active subgraph paths
    int depth = 0;                          ///< Current recursion depth
 
    static const int MAX_DEPTH = 32;        ///< Maximum recursion depth limit
 
    /// Push a subgraph path onto the stack
    void Push(const std::string& path)
    {
        pathStack.push_back(path);
        depth++;
    }
 
    /// Pop a subgraph path from the stack
    void Pop()
    {
        if (!pathStack.empty())
        {
            pathStack.pop_back();
            depth--;
        }
    }
 
    /// Check if a path is already on the stack (cycle detection)
    bool Contains(const std::string& path) const
    {
        for (const auto& p : pathStack)
        {
            if (p == path)
                return true;
        }
        return false;
    }
 
    /// Check if maximum depth has been reached
    bool IsFull() const
    {
        return depth >= MAX_DEPTH;
    }
 
    /// Clear the stack
    void Clear()
    {
        pathStack.clear();
        depth = 0;
    }
 
    /// Get current depth
    int GetDepth() const
    {
        return depth;
    }
};
 
// --- Behavior Tree Manager ---
// Singleton manager for loading and caching behavior tree assets
class BehaviorTreeManager
{
public:
    static BehaviorTreeManager& Get()
    {
        static BehaviorTreeManager instance;
        return instance;
    }
    
    // Load a behavior tree from JSON file
    bool LoadTreeFromFile(const std::string& filepath, uint32_t treeId);
    
    // Reload a behavior tree from JSON file (hot-reload support)
    bool ReloadTree(uint32_t treeId);
    
    // Validate a behavior tree structure
    bool ValidateTree(const BehaviorTreeAsset& tree, std::string& errorMessage) const;
    
    // Get a loaded tree by ID
    const BehaviorTreeAsset* GetTree(uint32_t treeId) const;
    
    // Clear all loaded trees
    void Clear();
    
    // NEW: Get tree ID from path (for prefab instantiation)
    uint32_t GetTreeIdFromPath(const std::string& treePath) const;
    
    // NEW: Check if tree is already loaded by path
    bool IsTreeLoadedByPath(const std::string& treePath) const;
    
    // NEW: Get loaded tree by path
    const BehaviorTreeAsset* GetTreeByPath(const std::string& treePath) const;
    
    // NEW: Enhanced lookup that tries multiple strategies
    const BehaviorTreeAsset* GetTreeByAnyId(uint32_t treeId) const;
    
    // NEW: Get tree path from ID (reverse lookup)
    std::string GetTreePathFromId(uint32_t treeId) const;
    
    // NEW: Debug method to list all loaded trees
    void DebugPrintLoadedTrees() const;
 
    // Phase 39c Step 6: SubGraph Validation
    // Validates that a SubGraph path points to a valid, loadable .bt.json file
    bool ValidateSubGraphPath(const std::string& path) const;
 
    // Phase 39c Step 6: Detects circular references by checking if SubGraph creates a cycle
    // Returns true if circular dependency detected, false otherwise
    // graphId: ID of the parent graph, nodeId: ID of the SubGraph node
    bool DetectCircularDependencies(uint32_t graphId, uint32_t nodeId, const BehaviorTreeAsset* parentTree, std::set<std::string>& visited);
 
    // Phase 39c Step 6: Collect all validation errors for a specific graph
    // Returns vector of error strings describing all validation issues
    std::vector<std::string> GetValidationErrors(uint32_t graphId);
 
private:
    BehaviorTreeManager() = default;
    std::vector<BehaviorTreeAsset> m_trees;
    
    // NEW: Registry to map file paths to tree IDs
    std::map<std::string, uint32_t> m_pathToIdMap;
};
 
// --- Behavior Tree Execution ---
// Execute a single node of a behavior tree
BTStatus ExecuteBTNode(const BTNode& node, EntityID entity, AIBlackboard_data& blackboard, const BehaviorTreeAsset& tree);
 
// Execute built-in condition nodes
BTStatus ExecuteBTCondition(BTConditionType condType, float param, EntityID entity, const AIBlackboard_data& blackboard);
 
// Execute built-in action nodes
BTStatus ExecuteBTAction(BTActionType actionType, float param1, float param2, EntityID entity, AIBlackboard_data& blackboard);
 
// Phase 38b: Process EventQueue events and activate matching OnEvent root nodes
// Called once per frame for each entity with active behavior tree
// Scans EventQueue for events matching OnEvent nodes' eventType field
// Executes matching OnEvent roots in parallel with main Root node
void TickEventRoots(class EventQueue& eventQueue, const BehaviorTreeAsset& tree, EntityID entity, AIBlackboard_data& blackboard);