using Plugins.JNGame.Sync.Frame.AStar.Entity;

namespace Game.Plugins.JNGame.Sync.Frame.AStar.Util.Graph
{
    /// <summary>
    ///保存层次图以加快某些寻路查询的速度。
    ///
    ///一种需要非常快速的常见查询类型是“此节点可从其他节点到达吗”这种形式。
    ///例如，在选取路径的结束节点时使用。该结束节点被确定为离该结束点最近的节点
    ///可以从开始节点访问的。
    ///
    ///此数据结构的主要目的是跟踪每个节点包含在哪个连接的组件中，以便快速进行此类查询。
    ///
    ///参见:https://en . Wikipedia . org/wiki/Connected _ component _（graph _ theory）
    ///
    ///连通分量是一组节点，其中每对节点之间都有一条有效路径。
    ///因此，上面的查询可以简单地通过检查它们是否在同一个连接的组件中来回答。
    ///连接的组件在节点上作为《see cref=“寻路。graph node . Area“/》属性并使用《see cref =“get Area“/》方法对该类进行初始化。
    ///
    ///在下图（显示200x200网格图）中，每个连接的组件都使用不同的颜色进行着色。
    ///然而，实际的颜色并没有什么特别的意义，只是它们有所不同。
    ///【打开在线文档查看图像】
    ///
    ///在4.2版之前，连接的组件只是存储在每个节点上的一个数字，当图形更新时
    ///已完全重新计算连接的组件。这可以使用淹没填充相对有效地完成
    ///算法（参见https://en.wikipedia.org/wiki/Flood_fill）但是它仍然需要通过每个节点
    ///这对于较大的图形来说代价很高。
    ///
    ///相反，该类构建了一个小得多的图，但仍保持与原始图相同的连通性。
    ///此分层图中的每个节点代表大量的实际节点，这些节点是一个单一的连通组件。
    ///请看下图中的示例。在图像中，每种颜色都是一个单独的层次节点，黑色连接位于每个层次节点的中心之间。
    ///
    ///【打开在线文档查看图像】
    ///
    ///使用分层图，可以通过对分层图进行洪水填充来计算连通分量，而不是真实图。
    ///然后当我们需要知道一个节点属于哪个连通分量时，我们会查找该节点所属的层次节点的连通分量。
    ///
    ///好处不会立即显现。以上只是完成同一件事的更复杂的方法。然而，真正的好处出现在更新图表时。
    ///当图形被更新时，包含受更新影响的任何节点的所有分层节点被完全移除，然后一旦所有节点都被移除，新的分层节点在其位置被重新计算。
    ///一旦完成此操作，整个图的连接组件可以通过仅整体填充分层图来更新。由于层次图比真实图小得多，因此速度明显更快。
    ///
    ///【打开在线文档查看视频】
    ///
    ///最后，使用所有这些，可以在图形更新时非常快速地重新计算图形的连接组件。
    ///图形越大，这种影响越大，图形更新越小。通过这些优化，对1000x1000网格图进行小规模更新的速度大约快40倍。
    ///扫描图形或同时更新整个图形时，速度不会提高。事实上，由于额外的复杂性，它有点慢，但是在分析后，与扫描图形的其余成本相比，额外的时间似乎是微不足道的。
    ///
    ///【打开在线文档查看视频】
    ///
    ///请参见:《see cref=“寻路。path utilities . ispath possible“/》
    ///请参见:《see cref=“寻路。nn constraint“/》
    ///请参见:《see cref=“寻路。graph node . Area“/》
    /// </summary >
    public class HierarchicalGraph
    {
        
        GraphNode[] dirtyNodes = new GraphNode[128];
        
        /// <summary>  
        /// 当创建新的图节点时调用此方法。  
        /// </summary>  
        /// <param name="node">新创建的图节点。</param>  
        internal void OnCreatedNode(GraphNode node) {  
            // 检查新节点的索引是否超过了dirtyNodes数组的长度  
            if (node.NodeIndex >= dirtyNodes.Length) {  
                // 如果是，则创建一个新的数组newDirty，其长度是新节点索引加1与dirtyNodes数组长度两倍的较大值  
                // 这确保了新节点索引在newDirty数组的有效范围内，并且数组有足够的空间来容纳未来的节点  
                var newDirty = new GraphNode[System.Math.Max(node.NodeIndex + 1, dirtyNodes.Length * 2)];  
          
                // 将旧的dirtyNodes数组中的元素复制到新的newDirty数组中  
                dirtyNodes.CopyTo(newDirty, 0);  
          
                // 将dirtyNodes引用指向新的newDirty数组，以便后续添加新节点  
                dirtyNodes = newDirty;  
            }  
      
            // 将新节点添加到dirtyNodes数组中  
            // AddDirtyNode(node);  
        }
        
        // /// <summary>  
        // /// 将此节点标记为“脏”，因为其连接性或可通行性已发生变化。  
        // /// 在对节点进行任何连接性或可通行性更改后，节点类必须调用此方法。  
        // ///  
        // /// 请参见：<see cref="GraphNode.SetConnectivityDirty"/>  
        // /// </summary>  
        // /// <param name="node">要标记为“脏”的节点。</param>  
        // public void AddDirtyNode(GraphNode node) {  
        //     // 如果节点尚未被标记为层次化节点“脏”  
        //     if (!node.IsHierarchicalNodeDirty) {  
        //         // 将节点标记为层次化节点“脏”  
        //         node.IsHierarchicalNodeDirty = true;  
        //           
        //         // 当dirtyNodes数组保证足够大以容纳图中所有节点时  
        //         // 数组可能也包含许多已销毁的节点。在极少数情况下，这可能导致数组越界。  
        //         // 在那种情况下，我们需要遍历数组并过滤掉任何已销毁的节点，同时确保将其对应的层次化节点标记为“脏”。  
        //         if (numDirtyNodes < dirtyNodes.Length) {  
        //             // 如果dirtyNodes数组还有空余空间，则直接将新节点添加到数组中  
        //             dirtyNodes[numDirtyNodes] = node;  
        //             // 增加脏节点计数  
        //             numDirtyNodes++;  
        //         } else {  
        //             // 如果数组已满，则需要压缩数组以移除已销毁的节点  
        //             int maxIndex = 0;  
        //             for (int i = numDirtyNodes - 1; i >= 0; i--) {  
        //                 // 检查节点是否已销毁  
        //                 if (dirtyNodes[i].Destroyed) {  
        //                     // 如果是，则减少脏节点计数  
        //                     numDirtyNodes--;  
        //                     // 标记对应的层次化节点为“脏”  
        //                     dirty[dirtyNodes[i].HierarchicalNodeIndex] = 1;  
        //                     // 将最后一个有效节点移到当前位置  
        //                     dirtyNodes[i] = dirtyNodes[numDirtyNodes];  
        //                     // 将当前位置设置为null，表示该位置不再包含有效节点  
        //                     dirtyNodes[numDirtyNodes] = null;  
        //                 } else {  
        //                     // 如果节点未销毁，则更新maxIndex为当前节点索引和maxIndex中的较大值  
        //                     maxIndex = System.Math.Max(maxIndex, dirtyNodes[i].NodeIndex);  
        //                 }  
        //             }  
        //             // 检查是否成功压缩了数组。如果numDirtyNodes仍然大于等于dirtyNodes.Length，则抛出异常  
        //             if (numDirtyNodes >= dirtyNodes.Length)   
        //                 throw new System.Exception("Failed to compactify dirty nodes array. This should not happen. " + maxIndex + " " + numDirtyNodes + " " + dirtyNodes.Length);  
        //             // 再次尝试添加新节点，此时数组应该有足够的空间  
        //             AddDirtyNode(node);  
        //         }  
        //     }  
        // }
        
    }
}