迭代器方法

简单写一个迭代器方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void Start()
{
    foreach (var e in Iterator())
    {
        Console.WriteLine(e);
    }
}

IEnumerable<int> Iterator()
{
    Console.WriteLine("00");
    yield return 1;
    Console.WriteLine("11");
    yield return 2;
    Console.WriteLine("22");
}

上面的迭代器方法，在内部，编译器会生成一个匿名类，代码如下：

• 仔细观察会发现，这个匿名类同时继承IEnumerator和IEnumerable，意味着它同时负责生产迭代器和迭代。
• 状态点数字的含义：-1代表正在执行/当前不处于挂起点；-2代表尚未枚举或者已经Dispose；大于等于0代表各个恢复点

边函数光栅化 (Edge Function Rasterization)

算法简介

边函数光栅化，又称 Pineda’s Algorithm，由 Juan Pineda 于 1988 年 SIGGRAPH 论文 A Parallel Algorithm for Polygon Rasterization 提出。它是现代 GPU 硬件光栅化的基础算法。

核心思想：多边形的每条边将平面划分为两个半平面，点在多边形内部当且仅当它在所有边的内侧半平面内。

数学本质

射线检测法

经常用于判断点是否在多边形内部，可用于处理非凸多边形，不要求顺时针逆时针，该算法的思路十分巧妙：

从目标点向任意约定方向，通常选 右侧（X 轴正方向） 发射一条无限长的水平射线，统计这条射线与多边形边的相交次数

• 奇数 → 点在多边形内部
• 偶数 → 点在多边形外部

不多介绍，下文主要说下算法的两个形式和优化变体。

稀疏集

SparseSet（稀疏集） 是一种专为有界整数 ID设计的高性能集合数据结构，核心优势是插入、删除、查询、清空均为 O (1) 时间复杂度，且遍历高效、缓存友好。它通过稀疏数组（sparse）+ 密集数组（dense）+ 元素计数（n） 实现，广泛用于游戏引擎（如 ECS）、编译器、图算法等场景。

核心结构

SparseSet 由三部分组成：

• dense[]（密集数组）：按插入顺序存储集合中的实际元素值，仅包含存在的元素，内存紧凑、遍历高效。
• sparse[]（稀疏数组）：以元素值为索引，存储该元素在 dense 数组中的下标位置；未存在的元素对应位置值无意义。
• count（元素计数）：记录当前集合中元素的总数，dense[0..count-1] 为有效元素。

算法图解

ORCA避障算法，出自2011年的一篇论文《Optimal Reciprocal Collision Avoidance》。该算法的思想不算复杂，但实现上有很多细节需要注意。网上已有很多对该算法的讲解，但是大多都比较粗略，很多细节并未详解，缺少很多图解来帮助理解，因此本文着重通过图解的形式，辅以文字，来剖析该算法的思想，并对关键源码进行解释。

速度障碍（VO, Velocity Obstacle）

如图所示，假设存在A、B两个对象，它们以图中的速度（速度是向量，包含方向和模大小）运动。

参数传递

Out参数

只用于输出结果

• 调用前不需要初始化
• 方法内部必须赋值
• 引用传递

In参数

粗筛阶段（Broad Phase）

SAP（扫描线算法）

不论碰撞体本身是圆形、OBB、多边形，都可以获得顶点集合的minPoint: (minX, minZ)和maxPoint: (maxX, maxZ)，得到最大外接矩形也就是AABB，将所有待检测对象的AABB投影到对应的轴上。每个对象在每个轴上都会得到一个线段，两个不同对象的线段如果在某一个轴上没有交集，就证明一定不存在碰撞，反之，在所有轴上都存在交集，则这两个对象的AABB一定发生了碰撞，如果对象本身就是AABB那就检测完毕，否则需要进一步判断两个对象是否实际碰撞。

算法

先从X轴开始，遍历每个对象，投影可以产生两个端点minValue, maxValue，将所有对象的投影端点都放入一个数组内，并按坐标从小到大进行排序。维护两个列表：活跃列表[]和重叠对列表[]。扫描线从左到右扫描这些端点。

Span

Span是 C# 7.2 引入的值类型，核心作用是零分配、高性能地表示连续的内存区域，可以直接操作数组、字符串、非托管内存等连续内存块，避免不必要的内存拷贝，大幅减少GC压力。
总的来说：Span就像一个 “内存视图”，不拥有内存，只是对已有内存的安全封装和高效访问。

1.1 核心用法

1.1.1 高性能内存操作，避免数组拷贝

传统方式处理数组子集时会产生拷贝，Span直接操作原内存：

1、固定托管对象的地址

.NET的GC在进行可达性遍历后会将所有使用到的内存进行压缩（Compact），空出一整块未使用的内存方便后续申请使用，这时候，原先代码里还在使用的内存就可能会变动位置，指针就会失效。所以fixed在这里的作用就是告诉GC不要compact我这个托管对象，常常配合指针进行较为底层的操作。

1
2
3
4
5
6
7
8
9
10

unsafe
{
    int[] arr = {1, 2, 3};

    fixed (int* p = arr)
    {
        // scope范围内arr会被pin住，GC不会移动它
        Console.WriteLine(p[0]);
    }
}

• 这种方式会有一定内存损耗，可能会影响GC产生内存碎片。
• fixed只用用于内建类型数组，别用自己引用类型元素数组，它是不会递归pin的

2、固定大小缓冲区字段fixed buffer

视角移动和缩放

假如你的游戏场景是在XZ平面的，而你的相机是俯视角的，你希望玩家可以拖动屏幕来移动视角，双指交互可以缩放视角。针对这个需求，在FGUI里，包含用户输入的组件：SwipeGesture和PinchGesture。拖动相机分成两个阶段：第一阶段，手指按下并拖动，此时要求场景完全跟随手指移动（跟手）；第二阶段，当手指松开后，根据松开前delta阈值，低于阈值则不进行惯性操作，否则需要根据松开前的速度进行惯性制动位移。

正交相机

正交相机的orthographicSize代表相机高度的一半对应的世界距离，将它乘以2再除以屏幕高度，就可以得到单位像素对应的世界距离。FGUI屏幕delta可以转化为unity屏幕像素delta，最终对应世界空间的delta。
通过这种映射关系，移动视角的第一阶段，可以算出世界空间的delta；移动视角的第二阶段，可以算出世界空间的velocity。

透视相机