数据结构

Posted on 2026-03-03 Edited on 2026-07-08 In Programming

AVL树

平衡树：一棵包含 N 个节点的平衡树，其树高 h 始终保持在 O(log N) 的量级。
AVL是平衡树的一种，平衡条件非常严格。它要求任何节点的左右子树高度差的绝对值不能超过1。

空二叉树是一个 AVL 树
如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 |ℎ(𝑙𝑠) −ℎ(𝑟𝑠)| ≤1，h 是其左右子树的高度
树高为 𝑂(log ⁡𝑛)

平衡因子：右子树高度 - 左子树高度

红黑树

首先，红黑树是一个二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK
通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡（最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，当从根节点到叶子节点的路径上黑色节点相同时，最长路径刚好是最短路径的两倍）

红黑树满足以下特性：

节点是红色或黑色
根是黑色
叶子节点（外部节点，空节点）都是黑色，这里的叶子节点指的是最底层的空节点（外部节点），即null节点才是叶子节点，null节点的父节点在红黑树里不将其看作叶子节点
红色节点的子节点都是黑色，红色节点的父节点都是黑色
从根节点到叶子节点的所有路径上不能有 2 个连续的红色节点
从任一节点到叶子节点的所有路径都包含相同数目的黑色节点

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素

并查集支持以下两种操作：

合并（Unite）：合并两个元素所属集合（合并对应的树）。
查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合。

路经压缩

如果查询过程中经过的每个元素都属于该集合，我们可以将其直接连到根节点以加快后续查询。

1
2
3

// assignment expression 
// size_t a; size_t b = (a = 10);
size_t dsu::find(size_t x) { return pa[x] == x ? x : pa[x] = find(pa[x]); }

kd 树（k-d tree）

数据驱动 (Data-Driven) 的空间划分。k-d树的分割线（或分割面）的位置，是由数据点本身的位置决定的，目标是让分割后的两个子空间包含大致相同数量的点。
每个节点按一个维度（2D：x 或 y，3D：x/y/z）把空间分成两半
节点保存一个点/对象，左子树保存该维度值更小的点，右子树保存更大的点

构建方式

选维度: 从 X 轴开始。
找到中位数: 在所有数据点中，找到 X 坐标的中位数。
划分: 以这个中位数点的 X 坐标为界，画一条垂直于 X 轴的分割线（平面）。
- X 坐标小于该值的点，归入左子树。
- X 坐标大于等于该值的点，归入右子树。
递归与交替维度:（3维的话是 x -> y -> z -> x -> …）
- 对左子树和右子树，重复上述过程，但这次切换到 Y 轴。
- 下一层再切换回 X 轴，如此循环，交替使用不同的维度进行划分。
结束: 直到每个子区域只包含一个点，或达到预设的叶子节点容量。

结果是一个平衡树，构建复杂度 O(N log N)

更新方式

插入

直接沿树下降，到叶子插入新点
不做重平衡，平均 O(log N)，但随着插入会变得不平衡

删除

可把节点标记为“已删除”
或用后继/前驱点替换当前节点并递归删除

动态维护

简单方案：批量更新后重建整个 kd 树
常见做法：周期性重建，或者在插入/删除累计到一定阈值后重建

适用场景

点集较静态或更新较少
适合近邻搜索、点查询

四叉树

空间驱动 (Space-Driven) 的划分。四叉树的分割方式是固定的，它只关心空间本身，而不管空间里有什么数据。
每个节点对应一个轴对齐的矩形/正方形区域，如果区域内点数超过阈值，则分成 4 个子象限
分割线永远是区域的正中线。最终划分出的子空间是大小可能不同、但形状永远是正方形的网格。

构建方式

定义边界: 从一个包含所有数据点的巨大正方形（根节点区域）开始。
划分: 将这个正方形均匀地分割成四个等大的子正方形（象限）：西北、东北、西南、东南。这四个子正方形成为根节点的四个子节点。
递归:
- 对于每个子节点，检查其中包含的数据点数量。
- 如果数量大于某个阈值（比如1），或者区域的尺寸还很大，就再次将其均分成四个更小的正方形。
- 如果数量小于等于阈值，或者区域已经很小，则停止分裂，该节点成为叶子节点。
数据归属: 每个数据点根据其坐标，被存储在完全包含它的、尺寸最小的那个叶子节点中。

更新方式

插入

找到点所属的叶节点并加入
若点数超阈值，分裂该叶节点

删除

从对应叶节点删除点
如果节点和兄弟节点合并后点数低于阈值，可回收子节点，合并成父节点

移动对象

先从旧格子删除，再重新插入新位置
若对象移动量不大，可使用“松散四叉树”（loose quadtree）减少频繁重插入

适用场景

2D 空间、区域查询、碰撞检测、动态场景
对于分布不均匀、局部聚集的点特别有效

BVH (Bounding Volume Hierarchy) / 包围盒层级

对单位按区域构建层级包围盒（AABB），按包围盒层级组织，适合先过滤远物体再精细排序
适合移动对象少、查询多的场景
查询时先过滤掉远离的盒子：如果这个盒子比当前队列（大顶堆）中的最远距离还要远，那么不考虑这个盒子

构建方式

准备叶子对象：每个对象先计算自己的AABB和中心点（centroid）
建根节点：根节点包围所有对象的总 AABB
递归分裂：
- 终止条件为对象数 <= leaf_size（如 4/8）或树深度到上限。
- 否则继续分裂：选最长轴 + 中位数切分（快，质量一般），或者 SAH 选轴和切分位置（慢些，但查询更快）。
生成子节点：左右子集分别求 AABB，继续递归
叶子存索引：叶节点保存对象索引范围（而不是拷贝对象）。
- “保存索引范围” 通常建立在 “构建时把对象重排成连续段”这个前提上
- 如果不重排，那就需要存一个显式索引列表（vector/list），代价是内存和访问局部性通常更差。

优点

全局唯一实例：单例模式确保在整个应用程序中只有一个实例存在，可以提供一个全局的访问点，方便对实例的管理和调用。
节省资源：由于只有一个实例存在，可以避免重复创建实例，节省了系统资源。
避免竞态条件：在多线程环境下，使用单例模式可以避免由于竞态条件而导致的问题，如资源争夺、数据不一致等。
实现了懒加载：某些单例模式的实现方式（如懒汉式）在需要时才创建实例，实现了延迟加载，节省了内存空间。
继承monobehaviour的单例有unity生命周期函数和也可以调用协程，可以用来控制没有继承monobehaivour的脚本组件

缺点

可能引入全局状态：由于单例模式提供了全局访问点，可能会导致多个部分之间共享了同一个状态，增加了系统的耦合性。
可能造成性能瓶颈：在高并发环境下，单例模式的实现需要考虑线程安全性，可能会引入锁机制，导致性能下降。
隐藏了依赖关系：单例模式的使用会隐藏类的依赖关系，增加了代码的复杂性和理解难度。
不利于扩展和测试：单例模式一般是通过静态方法获取实例，难以进行扩展和替换，也不利于单元测试。
可能造成内存泄漏：如果实例被长时间持有而不释放，可能会造成内存泄漏，特别是在移动端或长时间运行的服务中。

实例化方法

懒汉式（Lazy Initialization）：在第一次使用时创建实例。

public class Singleton {
    private static Singleton instance;
private Singleton() {}
public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }
}

饿汉式（Eager Initialization）：在类加载时就创建实例。

public class Singleton {
    private static final Singleton instance = new Singleton();
private Singleton() {}
public static Singleton getInstance() {
        return instance;
    }
}

事件和委托

Posted on 2026-02-11 Edited on 2026-03-04 In Programming

观察者模式

通过事件实现的观察者模式

using UnityEngine;
using System;
 
public class Publisher : MonoBehaviour
{
    // 声明一个事件
    public static event Action OnEventPublished;
 
    void Update()
    {
        if (Input.GetKeyDown(KeyCode.Space))
        {
            // 发布事件
            OnEventPublished?.Invoke();
        }
    }
}
 
public class Subscriber : MonoBehaviour
{
    private void OnEnable()
    {
        // 订阅事件
        Publisher.OnEventPublished += HandleEvent;
    }
 
    private void OnDisable()
    {
        // 取消订阅事件
        Publisher.OnEventPublished -= HandleEvent;
    }
 
    // 事件处理方法
    private void HandleEvent()
    {
        Debug.Log("Event received!");
    }
}

委托

委托是个类，分为Delegate自定义委托类型，Func有返回值的委托类型，Action无返回值的委托类型

Func和Action的底层原理便是用Delegate声明一个委托类型（有返回值和无返回值），并且通过泛型参数（最多十六个）来实现自定义参数类型和参数
其中，Func委托类型的最后一个参数为返回值

委托需要先定义后使用

1	delegate void IntMethodInvoker(int x);

如上定义了一个委托InMethodInvoker，这个委托可以指向一个 int类型参数，返回值为void 的方法

Action委托和 Func委托

Action委托引用了一个void返回类型的方法，T表示方法参数

Action
Action<in T>
Action<in t1,in t2>
Action<in t1,in t2,···,t16>

Func引用了一个带有一个返回值的方法，它可以传递0或者多到16个参数类型，和一个返回值类型

1
2
3

Func<out TResult>
Func<in t,out TResult>
Function<in t1,in t2,···,in t16,out TResult>

多播委托

前面是用的委托都只包含一个方法调用，但是委托也可以包含多个方法，这种委托叫做多播委托。使用多播委托可以按照顺序调用多个方法，多播委托只能得到调用的最后一个方法结果，一般我们把多播委托的返回值类型声明为void。
多播委托包含一个逐个调用的委托集合，如果通过委托调用的其中一个方法抛出异常，整个迭代就会停止。

使用匿名方法给委托赋值

前面使用委托都是先定义一个方法，然后把方法给委托的实例。但还有另外一种使用委托的方式，不用去定义一个方法，直接使用匿名方法（lambda expression）

Func<int,int,int> plus = delegate(int a, int b)
{
  int temp = a+b;
  return temp;
}
int res = plus(34,34)
Console.WriteLine(res);

//上述代码可以换成下面一行
Func<int, int, int> plus = (a, b) => { return a + b; };

事件

用event关键词修饰的字段，由观察者拥有，一种类型成员，有能力使一个类或者对象去通知其他类、对象们

事件是基于委托的，委托是事件的“底层基础”，事件是委托的“上层建筑”
委托类型定义了事件的有无返回值和参数类型，事件处理器必须和事件的有无返回值和参数类型一致，即双方都要遵守同一个约定（有无返回值和参数类型），我们把这叫做事件和事件处理器必须是匹配的

自定义事件

先声明该事件的委托类型，再声明事件

在声明委托类型的时候，如果这个委托，是为了声明某个事件而准备的委托，那么这个委托的名字，就要去使用：事件名+EventHandler的格式，由于委托是一种引用类型，所以事件名首字母要大写
在定义事件参数的时候，即在定义该事件的委托类型的参数的类型的时候，要遵循：类型名+EventArgs这个格式

事件声明示例

// 声明该事件的委托类型：事件名 + EventHandler
public delegate void OrderEventHandler(Customer customer, OrderEventArgs e);//声明一个委托类型

// 声明事件：访问修饰符 + event + 事件处理器（委托类型的实例、字段）+ 事件名称（一定要注意命名规范：On+事件名）
public event OrderEventHandler OnOrder;

微软提供了一个EventHandler委托类型

其中用来传递事件数据的类EventArgs，凡是用来传递事件数据的类，都是从这个类派生出来的
让自定义的传递事件数据的类继承EventArgs，就可以作为参数传入EventHandler委托类型了
将Object类型的变量转换为Customer类型的变量，我们可以用as操作符

1
2
3

public delegate void EventHandler(object? sender, EventArgs e);

Customer customer1 = _sender as Customer;

事件和委托的区别

事件其实是委托类型字段的包装器、限制器，限制外界对委托类型字段的访问。
外界只能通过“+=”和“-=”两个操作符对事件进行添加事件处理器和移除事件处理器的操作，并不能去赋值和触发事件。
事件是用来阻挡非法操作的“蒙版”，它绝对不是委托字段的本身
类似的情况有字段和属性，属性是字段的包装器。字段能做的，属性都能做；属性能做的，字段不一定都能做

总结：事件是用来“阉割”委托实例的，事件只能添加、删除事件处理器，不能赋值。外界只能用“+=”和“-=”去访问它，不能=，不能从外部触发事件，也就是说，事件包含了委托类型字段的所有功能，但只是对外部暴露了“+=”和“-=”操作符。

事件和委托的关系

委托类型规定了事件拥有者和事件响应者通知和接收的消息必须是同一类型的消息
约束了添加和移除事件时必须要使用与之匹配（同样类型）的事件处理器，即使用与之匹配（同样类型）的方法来处理响应这个事件

完整示例（顾客点单）

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
/// <summary>
/// 事件的拥有者：顾客
/// 事件：点单
/// 事件的响应者：服务员
/// 事件处理器：计算最后金额
/// 事件订阅（+=操作符）
/// </summary>
namespace EventDemo
{
    //声明一个委托类型
    public delegate void OrderEventHandler(Customer customer, OrderEventArgs e);

    class EventExample
    {
        public static Customer customer = new Customer();
        public static Customer customer2 = new Customer();
        public static Waiter waiter = new Waiter();
        static void Main()
        {
            customer.OnOrder += waiter.CalculateBill;
            customer2.OnOrder += waiter.CalculateBill;
 
            //使用事件，事件只能由事件拥有者触发，不能在外部去触发
            //顾客1点了超大杯摩卡15+6 = 21
            customer.Order("摩卡", 15, OrderEventArgs.CoffeeSizeEnum.Venti);
            //顾客1点了中杯拿铁20
            customer.Order("拿铁", 20, OrderEventArgs.CoffeeSizeEnum.Tall);
            //顾客2点了中杯卡布奇诺
            customer2.Order("卡布奇诺", 25, OrderEventArgs.CoffeeSizeEnum.Tall);
            customer.PayTheBill();
            customer2.PayTheBill();
 
            /*//如果使用委托，不使用事件，委托类型的字段可以在外部进行调用，意味着顾客2可以把自己点的东西记在顾客1的账单上
            //顾客1点了超大杯摩卡15+6 = 21
            OrderEventArgs e1 = new OrderEventArgs();
            e1.CoffeeName = "摩卡";
            e1.CoffeePrice = 15;
            e1.CoffeeSize = OrderEventArgs.CoffeeSizeEnum.Venti;
            customer.OnOrder(customer, e1);
            //顾客1点了超大杯拿铁20+6 = 26，并记在了倒霉蛋顾客1的账单上
            OrderEventArgs e2 = new OrderEventArgs();
            e2.CoffeeName = "拿铁";
            e2.CoffeePrice = 20;
            e2.CoffeeSize = OrderEventArgs.CoffeeSizeEnum.Venti;
            customer2.OnOrder(customer, e2);
            customer.PayTheBill();
            customer2.PayTheBill();*/
 
 
            Console.Read();
        }
    }

    public class Customer
    {
        //声明一个点单事件
        public event OrderEventHandler OnOrder;

        public float Bill { get; set; }
        public void PayTheBill()
        {
            Console.WriteLine("I have to pay : " + Bill);
        }

        /// <summary>
        /// 点餐（咖啡名称、价格、大小）
        /// </summary>
        /// <param name="coffeeName"></param>
        /// <param name="coffeePrice"></param>
        /// <param name="coffeeSize"></param>
        public void Order(string coffeeName,float coffeePrice, OrderEventArgs.CoffeeSizeEnum coffeeSize)
        {
            //语法糖：如果事件不为空（因为简略声明事件时委托类型的字段被隐藏了）
            if (OnOrder != null)
            {
                OrderEventArgs e = new OrderEventArgs();
                e.CoffeeName = coffeeName;
                e.CoffeePrice = coffeePrice;
                e.CoffeeSize = coffeeSize;
                //事件只能由事件拥有者触发：限制只能自己给自己点单
                OnOrder(this, e);
            }
        }
    }

    public class Waiter
    {
        //计算账单金额
        public void CalculateBill(Customer customer, OrderEventArgs e)
        {
            float finalPrice = 0;
            switch (e.CoffeeSize)
            {
                case OrderEventArgs.CoffeeSizeEnum.Tall:
                    finalPrice = e.CoffeePrice; //中杯，原价
                    break;
                case OrderEventArgs.CoffeeSizeEnum.Grand:
                    finalPrice = e.CoffeePrice + 3; //大杯：原价+3元
                    break;
                case OrderEventArgs.CoffeeSizeEnum.Venti:
                    finalPrice = e.CoffeePrice + 6; //超大杯：原价+6元
                    break;
            }
            customer.Bill += finalPrice;
        }
    }

    public class OrderEventArgs
    {
        // 咖啡是大杯、中杯还是小杯
        public enum CoffeeSizeEnum { Tall,Grand,Venti}//默认为静态
        public CoffeeSizeEnum CoffeeSize { get; set; }
        // 咖啡价格
        public float CoffeePrice { get; set; }
        // 咖啡名称
        public string CoffeeName { get; set; }
    }
}

Credits

https://blog.csdn.net/Hotgun2222/article/details/139901041

线性与非线性表

Posted on 2026-02-11 Edited on 2026-03-03 In Programming

线性：一头一尾，每个元素只有一个前驱和一个后驱，比如栈/队列
非线性：分支、分层关系，比如树/图

物理结构和逻辑结构

数组和链表可以看做物理存储的概念。
数组是用一段连续的内存存储，可以随机访问，支持随机访问（ O(1) ），但增删需移动元素（ O(n) ）。
链表不要求连续的内存，元素分散存储，通过指针连接，增删无需移动元素（ O(1) ），但不支持随机访问（ O(n) ）。

而数据结构都是逻辑层的概念，线性表，非线性表，栈，队列，树，图等等。
线性表这些逻辑层的概念，底层既可以用数组实现，也可以用链表实现。线性表用数组实现就叫做顺序表。

“顺序表是在计算机内存中以数组的形式保存的线中以数组的形式保存的线性表。” 简而言之，是线性表的一种实现方式。显然，这里的“数组”指物理结构，“线性表”指逻辑结构。这个解释应该还是合理的。

面向对象三大特性

封装 Encapsulation
将客观事物抽象为类，隐藏对象的内部属性和实现细节，只通过对外提供的公开接口（如 getter/setter）进行访问。
继承 Inheritance
一个类（子类/派生类）从另一个类（父类/基类）中继承属性和方法，同时可以扩展新的功能，实现代码复用减少冗余。
多态 Polymorphism
同一接口在不同情形下有不同的表现形式。简单来说，即父类指针或引用指向子类对象，并调用子类重写后的方法。
如果多个派生类同时实现了一个接口，通过实例化此接口也可以展现出多态的特性。

虚函数

当继承链中虚函数 >= 1，则在compile time编译时生成虚函数表vtable映射到虚函数
继承链中的每个包含虚函数的类都有一个属于自己的 vtable (虚函数表)
在runtime运行时，子类的构造函数中为vptr赋值指向vtable

父类指针调用虚函数时，子类复写的虚函数被调用
查询vtable找到虚函数的入口地址并执行
父类指针指向子类对象，或父类引用绑定子类对象，父类对象vptr变成子类对象vptr，查询子类vtable

virtual vs. new

Note: virtual + override are resolved at runtime (so override really overrides virtual methods), while new just create new method with the same name, and hides the old, it is resolved at compile time -> your compiler will call the method it ‘sees’.

HybridCLR简述

Posted on 2026-02-09 Edited on 2026-02-12 In Programming

HybridCLR扩充了IL2CPP的代码，使它由纯AOT Runtime变成“AOT+Interpreter“混合Runtime，进而原生支持动态加载Assembly，使得基于IL2CPP Backend打包的游戏不仅能在Android平台，也能在iOS、Consoles等限制了JIT的平台上高效地以AOT+interpreter混合模式执行。

通过 “Differential Hybrid dll” 技术，可以对 AOT dll 实现任意增删改，会智能地让 被修改或者新增的类和方法 以 Interpreter 模式运行，但 未被修改的类 以AOT方式运行，从而使 热更新的游戏逻辑 的运行性能基本达到原生AOT的水平。

基础原理

CLR，即Common Language Runtime，中文叫公共语言运行时，是让.NET程序执行所需的外部服务的集合，是.NET平台的核心和最重要的组件，类似于Java的JVM。

IL2CPP是Unity开发的跨平台CLR解决方案，诞生它的一个关键原因是Unity需要跨平台运行。但一些平台如iOS，这种禁止JIT并导致依赖JIT的官方CLR虚拟机无法运行，而是必须使用AOT技术将Mananged程序提前转化为目标平台的静态原生程序后再运行。而Mono虽然也支持AOT，但性能较差以及跨平台支持不佳。The IL2CPP backend converts MSIL (Microsoft Intermediate Language) code (for example, C# code in scripts) into C++ code, then uses the C++ code to create a native binary file (for example, .exe, .apk, or .xap) for your chosen platform.

IL2CPP方案包含一套AOT运行时以及一套DLL到C++代码及元数据的转换工具，使得原始的C#开发的代码最终能在iOS这样的平台运行起来。因为 IL2CPP 生成的 C++ 代码不是普通的 C++，它本质上还是在模拟 C# 的行为。很多 C# 特性在 C++ 里根本不存在，必须有额外代码来支撑。IL2CPP 只是把计算逻辑翻译成了 C++，但 C# 作为托管语言的那些”托管服务”，必须由运行时来提供。生成的 C++ 代码到处都在调用 il2cpp_xxx() 这类运行时 API，离开运行时根本跑不起来。

IL2Cpp运行时

Unity 在打包时就把 IL 代码转换成 C++ 源码，然后在开发者的机器上（或 CI 上）用目标平台的 C++ 编译器编译成 machinecode。最终交付给用户的已经是编译好的原生二进制，不是在用户设备上编译的。
所以用户设备上不需要安装 C++ 编译器，也不需要单独安装什么 IL2CPP runtime —— 它是随游戏一起打包分发的。

虽然代码本身已经变成了原生机器码，但 C#/.NET 的很多语言特性不只是代码逻辑，还依赖一个运行时环境。IL2CPP VM（更准确地说是 libil2cpp 运行时库）负责提供这些能力：

垃圾回收（GC）：C++ 没有自动内存管理，需要运行时提供 GC（IL2CPP 用的是 BoehmGC）
类型系统和反射：typeof、GetType()、Activator.CreateInstance() 这些反射操作需要运行时维护类型元数据
泛型的运行时支持：某些泛型实例化需要运行时处理
线程管理：对应 .NET 的线程模型
异常处理：C# 的异常机制需要映射到原生代码的异常处理
平台抽象层：提供统一的 API 来屏蔽不同操作系统的差异

可以把它理解为：IL2CPP 把”程序逻辑”编译成了原生代码，但 C# 程序运行时还需要一个”服务层”来提供 GC、反射、类型系统等基础设施。这个服务层就是 IL2CPP runtime（所谓的”VM”）。它不是传统意义上解释执行字节码的虚拟机，更像是一个原生运行时库，和你的游戏代码一起编译、一起打包、一起运行。
它的角色类似于 .NET 程序依赖的 CoreCLR runtime，只不过 IL2CPP 的版本更轻量，且不包含 JIT 编译器。

这个il2cpp runtime是由用户在目标设备上自行安装吗？还是随unity游戏项目一起打包？
如果是这样，当一个用户设备上有多个unity引擎制作的游戏，会有多个重复的il2cpp runtime吗？

IL2CPP runtime 是随每个游戏一起打包的，不需要用户自行安装。如果用户设备上装了 3 个 Unity 游戏，就会有 3 份 IL2CPP runtime，各自独立存在于各自的应用包内。

为什么不做成共享的系统级运行时？

这和 .NET Framework on Windows 的模式（系统全局安装一份，所有 .NET 程序共用）是完全不同的设计选择，原因包括：

版本耦合：每个游戏可能用不同版本的 Unity 构建，对应不同版本的 IL2CPP runtime。共享的话版本兼容性会是噩梦。
跨平台一致性：Unity 要支持 iOS、Android、主机等众多平台，不可能在每个平台上都推动安装一个系统级运行时。
自包含 = 可靠：游戏自带运行时，不依赖用户设备上装了什么，部署更可控。
体积可接受：libil2cpp 运行时库本身并不大（通常几 MB 级别），相对于游戏的贴图、音频等资源来说微不足道。

不只是 Unity，很多引擎和框架都这么做：

Unreal Engine 的游戏也是各自打包完整的引擎运行时
Electron 应用每个都自带一份 Chromium + Node.js
Go / Rust 编译的程序都是静态链接、自包含的

本质上就是用少量磁盘空间换取部署的简单性和可靠性，在现代存储容量下这是非常合理的取舍。

HybridCLR核心构成

IL2CPP是一个纯静态的AOT运行时，不支持运行时加载DLL，因此不支持热更新；不像Mono有Hybrid mode execution，可支持动态加载DLL。

目前Unity平台的主流热更新方案xLua、ILRuntime之类都是引入一个第三方VM（Virtual Machine），在VM中解释执行代码，来实现热更新。这里我们只分析使用C#为开发语言的热更新方案。这些热更新方案的VM与IL2CPP是独立的，意味着它们的元数据系统是不相通的，在热更新里新增一个类型是无法被IL2CPP所识别的（例如，通过System.Activator.CreateInstance是不可能创建出这个热更新类型的实例），这种看起来像，但实际上又不是的伪CLR虚拟机，在与IL2CPP这种复杂的CLR运行时交互时，会产生极大量的兼容性问题，另外还有严重的性能问题。

HybridCLR 对 IL2CPP运行时进行扩充，添加Interpreter模块，将它由AOT运行时改造为“AOT + interpreter”双引擎的混合运行时，进而实现Mono hybrid mode execution这样的机制。这样一来就能彻底支持热更新，并且兼容性极佳。对开发者来说，除了解释模式运行的部分执行得比较慢，其他方面跟标准的运行时没有区别，完美支持在iOS这种禁止JIT的平台上以解释模式无缝地运行动态加载的DLL。

与其他热更新方案对比

HybridCLR是原生的C#热更新方案。通俗地说，IL2CPP相当于Mono的AOT模块，HybridCLR相当于Mono的Interpreter模块，两者合一成为完整Mono。HybridCLR使得IL2CPP变成一个全功能的Runtime，原生（即通过System.Reflection.Assembly.Load）支持动态加载DLL，从而支持iOS平台的热更新。

正因为HybridCLR是原生Runtime级别实现，热更新部分的类型与主工程AOT部分类型是完全等价并且无缝统一的。可以随意调用、继承、反射或多线程，不需要生成代码或者写适配器。

其他热更新方案则是独立VM，与IL2CPP的关系本质上相当于Mono中嵌入Lua的关系。因此类型系统不统一，为了让热更新类型能够继承AOT部分类型，需要写适配器，并且解释器中的类型不能为主工程的类型系统所识别。特性不完整、开发麻烦、运行效率低下。

模型和动画

Posted on 2026-02-04 Edited on 2026-02-09 In Animation

关节坐标的定义和计算方法

绑定姿势：这是网格绑定到骨骼之前的姿势，通常是设计师在绑定模型时预设的。绑定姿势通常在一个T型姿势（T-Pose）下进行记录‌。
局部姿势：这是关节相对于父关节来指定的常见姿势。局部姿势存储为TQS格式，表示相对于父关节的位置、朝向和缩放。根关节的父节点可以认为是世界坐标系的原点。在数学上，关节姿势是一个仿射变换，由平移向量、旋转矩阵和对角缩放矩阵组成‌。

骨架由一系列具有层次关系的关节（骨骼）和关节链组成，是一种树结构，选择其中一个是根关节，其它关节是根关节的子孙，可以通过平移和旋转根关节移动并确定整个骨架在世界空间中的位置和方向。父关节运动能影响子关节运动，但子关节运动对父关节不产生影响，因此，平移或旋转父关节时，也会同时平移或旋转其所有子关节。

Unity动画系统

分为旧版动画系统和新版动画系统，即AnimationClip 与 Animator（Mecanim）

AnimationClip
Plays specific Animation Clips directly via script (e.g., Animation.Play(“Jump”)). It has no built-in state machine or visual graph.
Animator/Mecanim (New)
Attach a animator component to your GameObject. It requires an Animator Controller asset to function.
It uses a visual graph to manage states. You rarely tell it to “Play” a clip; instead, you change a parameter (e.g., animator.SetFloat(“Speed”, 5.0f)), and the state machine decides which animation to play.

3D模型

绑定 (Rigging)
指为3D模型创建内部骨骼、关节及控制器系统，定义运动逻辑，给角色搭建“骨架”和“控制系统”的过程，类似于给木偶安装操纵线。

目的：赋予模型生命，使动画师能方便地操纵复杂的几何体。
组成：包含骨骼（Joints）、控制器（Controllers）、IK/FK（逆向/正向动力学）链。
工作内容：放置关节、设置骨骼层级、添加IK把手、创建控制器。

蒙皮 (Skinning)
蒙皮是绑定完成后的步骤，将模型的顶点（Vertex）“绑定”到骨骼上。
目的：让骨骼驱动模型网格变形。当骨骼移动时，皮肤上的顶点会随之移动。
方法：

平滑蒙皮（Smooth Skinning）：顶点受多个骨骼影响，变形平滑自然（最常用）。
刚性蒙皮（Rigid Skinning）：一个顶点只受一个骨骼影响，变形较生硬。
关键概念——刷权重（Weighting）：定义顶点受特定骨骼影响的程度（0-1之间）。将Mesh网格的顶点与骨骼节点对应，从而决定模型的不同部位要跟着关节位移的程度

制作关键帧动画
IK骨（Inverse Kinematics，反向动力学）通过设置骨骼末端（如手、脚）的目标位置，计算系统会自动推算出其他关节（如手腕、肘部）的移动

IK骨不是被反推的骨头的子节点，而是以外的骨头（例如大腿->小腿->脚，此时IK骨则不为这三个骨头的子节点）
Chain Length：有多少根节点骨头要反算
Pole Target：被影响关节的朝向方向

着色器

Posted on 2025-09-18 Edited on 2025-09-29 In Graphics

顶点着色器 vs 片元着色器

One main difference is that a vertex shader can manipulate the attributes of vertices. which are the corner points of your polygons.
The fragment shader on the other hand takes care of how the pixels between the vertices look. They are interpolated between the defined vertices following specific rules.

白话：顶点着色器负责定位三角形位置！片段着色器负责修改像素颜色！！

顶点着色器(Vertex Shader)

顶点着色器是图形渲染管线中的第一个可编程阶段。它的主要任务是处理从CPU发送到GPU的顶点数据。每个顶点都会通过顶点着色器进行一次，通常用于执行以下操作：

变换：将顶点从模型空间转换到世界空间，然后进一步转换到视图空间和投影空间。这通常涉及到矩阵乘法运算，用于实现平移、旋转和缩放等变换。
光照计算（可选）：在某些情况下，顶点着色器也用于执行初步的光照计算，但这通常是在更简单的渲染场景中，或者作为更复杂的片元级光照计算的一个初步步骤。
传递数据：顶点着色器可以计算并传递额外的数据到后续的渲染阶段，如片元着色器。这些数据可以是颜色、纹理坐标或其他自定义属性。

片元着色器

片元着色器是图形渲染管线中处理像素级渲染的阶段。它接收由顶点着色器插值得到的片元（即屏幕上的像素或像素的候选者），并生成最终的颜色和其他与像素相关的数据。以下是片元着色器的一些主要用途：

纹理映射：从纹理中读取颜色信息，并应用到相应的像素上。这可以用于实现贴图、细节增强等效果。
光照计算：执行更详细的光照计算，如计算每个像素上的光照强度和颜色。这可以包括漫反射、镜面反射、环境光等多种光照模型。
颜色混合和特殊效果：实现各种颜色混合模式，以及应用如模糊、发光、深度测试等后处理效果。
输出最终颜色：基于上述计算，确定每个像素的最终颜色，并将其发送到渲染管线的下一个阶段（通常是帧缓冲区）。

Credits:

https://zhuanlan.zhihu.com/p/718015588

裁剪空间和NDC

Posted on 2025-09-05 Edited on 2026-02-04 In Graphics

Vertex Shader的输出在Clip Space，然后GPU自己做透视除法变到了NDC( 取值范围[-1, 1] )。

裁剪空间

裁剪空间变换的思路是，对平截头体进行缩放，使近裁剪面和远裁剪面变成正方形，使坐标的w分量表示裁剪范围，此时，只需要简单的比较x,y,z和w分量的大小即可裁剪图元。
完全位于这块空间内部的图元将会被保留，完全位于这块空间外部的图元将会被剔除，与这块空间边界相交的图元就会被裁剪。而这块空间就是由视椎体来决定的。

In clip space, clipping is not done against a unit cube. It is done against a cube with side-length w. Points are inside the visible area if each of their x,y,z coordinate is smaller than their w coordinate.

In the example you have, the point [6, 0, 6.29, 7] is visible because all three coordinates (x,y,z) are smaller than 7.

透视投影矩阵

此时我们就可以按如下不等式来判断一个变换后的顶点是否位于视椎体内

正交投影矩阵

判断一个变换后的顶点是否位于视椎体内使用的不等式和透视投影中的一样，这种通用性也是为什么要使用投影矩阵的原因之一。

NDC

齐次除法将Clip Space顶点的4个分量都除以w分量，就从Clip Space转换到了NDC了。
而NDC是一个长宽高取值范围为[-1, 1]的立方体，超过这个范围的顶点，会被GPU剪裁。也就是说，每个顶点的x，y，z坐标都应该在-1.0到1.0之间，超出这个坐标范围的顶点都将不可见。

透视投影除法

正交投影除法

细心一点会发现，齐次坐标对于透视投影空的裁剪空间变化更大，而对正交投影的裁剪空间没有影响（正交投影的裁剪空间中顶点的w已经是1了）。

视口变换(Viewport Transformation)

At this moment, we’re still in 3D space.How do we get to 2D space?

We need to transform our vertex from 3D NDC to 2D screen coordinates.

When initializing the Canvas, we are responsible for configuring its size. This size is used to convert our NDC coordinates to screen coordinates.

C# 依赖注入

Posted on 2025-08-28 Edited on 2026-03-24 In Programming

No Dependency Injection

不使用依赖注入，必须在依赖方(Dependent Class)中主动创建或者获取被依赖方(Denpendency Class)

public class ClassA
{
    private readonly ClassB _classB;

    public ClassA()
    {
        _classB = new ClassB(); //主动创建对象B
    }

    public void Process()
    {
        Console.WriteLine("Class A start process");
        _classB.DoSomething();
        Console.WriteLine("Class A finish process");
    }
}

public class ClassB
{
    public void DoSomething()
    {
        // ClassB performs some logic
    }
}

Denpendency Injection and IoC

使用依赖注入，不需要在依赖方的代码里主动创建或者获取被依赖方，反而，只需要在构造器参数里声明需要对象B的引用。

ClassA.cs

public class ClassA
{
    private readonly IInterfaceB _b;

    public ClassA(IInterfaceB b)
    {
        _b = b;
    }

    public void Process()
    {
        Console.WriteLine("Class A start process");
        _b.DoSomething();
        Console.WriteLine("Class A finish process");
    }
}

在使用依赖注入时，更多时候，对于依赖更提倡使用接口，这样解耦了接口和实现：ClassA不需要知道ClassB的内部，只需要知道IClassB有个叫DoSomething的方法可以调用
并且，业务代码中不需要主动实例化对象，即无需这样主动调用构造函数 new ClassA(new ClassB())

ClassB.cs

public class ClassB : IClassB
{
    public void DoSomething()
    {
        Console.WriteLine("class B is doing something ...");
    }
}

IClassB.cs

public interface IClassB
{
    void DoSomething();
}

Program.cs

internal class Program
{
    public static void Main(string[] args)
    {
        IHost host = Host.CreateDefaultBuilder(args)
                        .ConfigureServices((context, services) =>
                        {
                            services.AddSingleton<ClassA>();
                            services.AddSingleton<IInterfaceB, ClassB>();
                        }).Build();

        ClassA a = host.Services.GetRequiredService<ClassA>();
        a.Process();
    }
}

原本是在ClassA内部决定使用怎样的ClassB实例，使用了依赖注入设计后，这种控制关系（决定关系）变为由外部控制了，这就是所谓的“控制反转”(Inversion of Control)

Host 以及它内部的 Services可以理解为 C# 提供的依赖注入系统
通过 GetRequiredService 可以获得对应的实例并执行业务逻辑（此处为ClassA实例）

使用依赖注入系统实例化对象

如果我们想要达到不需要手动实例化ClassA的效果，可以新建一个类并实现IHostedService接口

DoSomethingHostedService.cs

public class DoSomethingHostedService : IHostedService
{
    private readonly ClassA _a;

    public DoSomethingHostedService(ClassA a)
    {
        _a = a;
    }

    public Task StartAsync(CancellationToken cancellationToken)
    {
        _a.Process();
        return Task.CompletedTask;
    }

    public Task StopAsync(CancellationToken cancellationToken)
    {
        return Task.CompletedTask;
    }
}

修改 Program.cs

internal class Program
{
    public static async Task Main(string[] args)
    {
        IHost host = Host.CreateDefaultBuilder(args)
                        .ConfigureServices((context, services) =>
                        {
                            services.AddSingleton<ClassA>();
                            services.AddSingleton<IInterfaceB, ClassB>();

                            services.AddHostedService<DoSomethingHostedService>();
                        }).Build();

        await host.RunAsync();
    }
}

IHostedService 是一个特殊的接口，实现这个接口的类通过在Host中的services里注册后，可以在Host运行时自动实例化并执行
services.AddHostedService<>() 用于注册要自动执行的类
await host.RunAsync() 运行Host实例

Credits:

https://zhuanlan.zhihu.com/p/592698341

AVL树

红黑树

并查集

路经压缩

kd 树（k-d tree）

构建方式

最近邻查询

更新方式

四叉树

构建方式

最近邻查询

更新方式

BVH (Bounding Volume Hierarchy) / 包围盒层级

构建方式

最近邻查询

优点

缺点

实例化方法

观察者模式

委托

Action委托 和 Func委托

多播委托

使用匿名方法给委托赋值

事件

自定义事件

事件和委托的区别

事件和委托的关系

Credits

物理结构和逻辑结构

面向对象三大特性

虚函数

virtual vs. new

基础原理

IL2Cpp运行时

HybridCLR核心构成

与其他热更新方案对比

关节坐标的定义和计算方法

Unity动画系统

3D模型

顶点着色器 vs 片元着色器

顶点着色器(Vertex Shader)

片元着色器

Credits:

裁剪空间

透视投影矩阵

正交投影矩阵

NDC

透视投影除法

正交投影除法

视口变换(Viewport Transformation)

No Dependency Injection

Denpendency Injection and IoC

使用依赖注入系统实例化对象

Credits:

Action委托和 Func委托