Lizq的个人博客

发表于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

边函数光栅化 (Edge Function Rasterization)

算法简介

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

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

数学本质

阅读全文 »

发表于 更新于 本文字数： 2.2k 阅读时长 ≈ 8 分钟

射线检测法

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

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

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

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

阅读全文 »

发表于 更新于 本文字数： 1.5k 阅读时长 ≈ 5 分钟

稀疏集

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

核心结构

SparseSet 由三部分组成：

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

发表于 更新于 本文字数： 11k 阅读时长 ≈ 38 分钟

算法图解

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

速度障碍（VO, Velocity Obstacle）

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

两个即将碰撞的对象

阅读全文 »

发表于 本文字数： 1.3k 阅读时长 ≈ 5 分钟

参数传递

Out参数

只用于输出结果

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

In参数

阅读全文 »

发表于 更新于 本文字数： 4.6k 阅读时长 ≈ 17 分钟

粗筛阶段（Broad Phase）

SAP（扫描线算法）

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

算法

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

阅读全文 »

发表于 更新于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

Span

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

1.1 核心用法

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

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

阅读全文 »

发表于 更新于 本文字数： 1.5k 阅读时长 ≈ 6 分钟

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

阅读全文 »

发表于 更新于 本文字数： 1.2k 阅读时长 ≈ 4 分钟

视角移动和缩放

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

正交相机

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

透视相机

阅读全文 »

发表于 更新于 本文字数： 800 阅读时长 ≈ 3 分钟

NPC平滑运动

NPC被赋予一组路线比如List，NPC按照路线行进。当遇到转角时，如果直接改变朝向，NPC会显得过于程序化，必然是不可取的。该篇博客尝试了两种方法，分别是“转角圆弧”和“惰性转向”

1 转角圆弧

在转角时，根据预留量（可以设定与速度线性相关）提前脱离路径转弯，转弯的圆弧是两组边的内切圆。此时NPC的转弯角速度可以根据运动速度、预留量，转角的角度，精确求得。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
using System.Collections.Generic;
using UnityEngine;

public class ArcMove : MonoBehaviour
{
    public float TurnTriggerDistance = 5f;  // 预先转向保留距离
    public float MoveSpeed = 20f;           // 匀速朝向前运动

    private float _angularSpeed = 0f;       // 本次转向的转向速度
    private float _remainingTurnTime = 0f;  // 本次转向的转向时间
    private int _currentNodeIndex = 0;

    private List<Vector3> _route = new()
    {
        new Vector3(10,0,-10),
        new Vector3(-10,0,-10),
        new Vector3(10,0, 0),
        new Vector3(10,0,10),
        new Vector3(-10,0,10),
    };

    private void Start() => ResetState();

    void Update()
    {
        // ECS里的控制系统
        var curPos = transform.position;
        if (_remainingTurnTime <= 0 && _currentNodeIndex == _route.Count - 2)
        {
            var curPoint = _route[_currentNodeIndex];
            var arrivePoint = _route[_currentNodeIndex + 1];
            if (Vector3.Dot(arrivePoint - curPoint, arrivePoint - curPos) < 0)
                ResetState();
        }
        if (_remainingTurnTime > 0)
        {
            _remainingTurnTime -= Time.deltaTime;
            if (_remainingTurnTime <= 0) _angularSpeed = 0;
        }
        else
        {
            var haveNextPoint = _currentNodeIndex + 1 < _route.Count;
            var haveNextNextPoint = _currentNodeIndex + 2 < _route.Count;
            var handled = false;
            if (haveNextNextPoint)
            {
                var curPoint = _route[_currentNodeIndex];
                var nextPoint = _route[_currentNodeIndex + 1];
                var nextNextPoint = _route[_currentNodeIndex + 2];
                var inVector = nextPoint - curPoint;
                var outVector = nextNextPoint - nextPoint;
                var clampTurnTriggerDistance = Mathf.Min(TurnTriggerDistance, Mathf.Min(inVector.magnitude, outVector.magnitude) / 2);
                var nowRemainDist = (curPos - nextPoint).magnitude;
                if (nowRemainDist <= clampTurnTriggerDistance)
                {
                    ++_currentNodeIndex;
                    handled = true;
                    // 脱离
                    var angle = Vector3.SignedAngle(inVector.normalized, outVector.normalized, Vector3.up);
                    var absoluteAngle = Mathf.Abs(angle);
                    if (absoluteAngle < 1f) return; // 角度太小，Tan会很大，安全起见，直接当直线跑
                    var inCircleRadius = nowRemainDist / Mathf.Tan(absoluteAngle * Mathf.Deg2Rad / 2);
                    var arcLength = 2 * Mathf.PI * inCircleRadius * absoluteAngle / 360;
                    _remainingTurnTime = arcLength / MoveSpeed;
                    _angularSpeed = angle / _remainingTurnTime;
                }
            }
            if (haveNextPoint && !handled)
            {
                var curDir = transform.rotation * Vector3.forward;
                var targetDir = _route[_currentNodeIndex + 1] - curPos;
                var diffAngle = Vector3.SignedAngle(curDir.normalized, targetDir.normalized, Vector3.up);
                _angularSpeed = diffAngle * MoveSpeed; // 朝向收敛与速度正相关
            }
        }

        // ECS里的Movement系统
        transform.rotation *= Quaternion.Euler(0, _angularSpeed * Time.deltaTime, 0);
        transform.position = transform.position + MoveSpeed * Time.deltaTime * transform.forward;
    }

    private void ResetState()
    {
        _currentNodeIndex = 0;
        transform.SetPositionAndRotation(_route[_currentNodeIndex], Quaternion.LookRotation(_route[1] - _route[0]));
    }
}
阅读全文 »
0%