技能树闭环检测问题：CanDisableSkill函数逻辑异常修复求助

问题根源 #

原逻辑在检测闭环时，仅通过简单的路径回溯判断是否能回到起点，未严格区分节点是否属于完全由已激活节点构成的强连通分量（SCC）。当存在内嵌小闭环时，遍历路径会误将连接到大闭环的非闭环节点判定为处于闭环内，导致错误允许关闭本不应操作的节点。

修复思路 #

采用强连通分量（SCC）检测算法（如Tarjan算法），仅针对已激活节点构建子图，精准识别闭环：

• 若待关闭节点所在的强连通分量大小≥2（即存在有效闭环），则允许关闭；
• 若所在分量大小为1（无闭环），则不允许关闭。

具体代码实现 #

替换原CanDisableSkill函数逻辑，以下是基于Tarjan算法的可落地示例：

using System.Collections.Generic;
using UnityEngine;

public class SkillTreeManager : MonoBehaviour
{
    // 技能节点核心结构（根据项目实际定义调整）
    public class SkillNode
    {
        public bool isActive;
        public List<SkillNode> connectedNodes; // 技能节点间的双向/单向连接
        public int uniqueId; // 节点唯一标识，用于SCC检测
    }

    private int _traversalIndex;
    private Dictionary<SkillNode, int> _nodeIndexMap;
    private Dictionary<SkillNode, int> _lowLinkMap;
    private Stack<SkillNode> _nodeStack;
    private HashSet<SkillNode> _nodesOnStack;
    private List<List<SkillNode>> _sccCollection;

    public bool CanDisableSkill(SkillNode targetNode)
    {
        // 未激活节点直接禁止关闭
        if (!targetNode.isActive)
            return false;

        // 初始化SCC检测工具
        _traversalIndex = 0;
        _nodeIndexMap = new Dictionary<SkillNode, int>();
        _lowLinkMap = new Dictionary<SkillNode, int>();
        _nodeStack = new Stack<SkillNode>();
        _nodesOnStack = new HashSet<SkillNode>();
        _sccCollection = new List<List<SkillNode>>();

        // 仅遍历已激活节点构建子图
        List<SkillNode> activeNodes = CollectAllActiveNodes();
        foreach (var node in activeNodes)
        {
            if (!_nodeIndexMap.ContainsKey(node))
                TarjanTraverse(node);
        }

        // 查找目标节点所属的SCC并判断是否允许关闭
        foreach (var component in _sccCollection)
        {
            if (component.Contains(targetNode))
            {
                return component.Count >= 2;
            }
        }

        return false;
    }

    private void TarjanTraverse(SkillNode node)
    {
        _nodeIndexMap[node] = _traversalIndex;
        _lowLinkMap[node] = _traversalIndex;
        _traversalIndex++;
        _nodeStack.Push(node);
        _nodesOnStack.Add(node);

        // 仅处理已激活的相邻节点
        foreach (var neighbor in node.connectedNodes)
        {
            if (!neighbor.isActive)
                continue;

            if (!_nodeIndexMap.ContainsKey(neighbor))
            {
                TarjanTraverse(neighbor);
                _lowLinkMap[node] = Mathf.Min(_lowLinkMap[node], _lowLinkMap[neighbor]);
            }
            else if (_nodesOnStack.Contains(neighbor))
            {
                _lowLinkMap[node] = Mathf.Min(_lowLinkMap[node], _nodeIndexMap[neighbor]);
            }
        }

        // 提取完整的强连通分量
        if (_lowLinkMap[node] == _nodeIndexMap[node])
        {
            List<SkillNode> component = new List<SkillNode>();
            SkillNode currentNode;
            do
            {
                currentNode = _nodeStack.Pop();
                _nodesOnStack.Remove(currentNode);
                component.Add(currentNode);
            } while (currentNode != node);

            _sccCollection.Add(component);
        }
    }

    // 辅助函数：收集所有已激活的技能节点
    private List<SkillNode> CollectAllActiveNodes()
    {
        // 替换为项目中获取所有技能节点的实际逻辑
        List<SkillNode> allNodes = new List<SkillNode>();
        List<SkillNode> activeNodes = new List<SkillNode>();
        foreach (var node in allNodes)
        {
            if (node.isActive)
                activeNodes.Add(node);
        }
        return activeNodes;
    }
}

关键细节说明 #

• 激活节点子图限定：仅对已激活节点做SCC检测，排除未激活节点对闭环判定的干扰；
• 精准闭环识别：内嵌小闭环会被识别为独立的SCC，不会误判外部连接节点处于闭环内；
• 连接方向适配：若技能树是单向激活逻辑（如父节点→子节点），需调整connectedNodes的遍历方向，确保检测的是激活路径上的闭环。

内容的提问来源于stack exchange，提问作者RiP Hunt