视角移动和缩放

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

正交相机

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

透视相机

阅读全文 »

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]));
}
}
阅读全文 »

1 优化位枚举

1.1 原生HasFlag问题

  • 原生的HasFlag方法会将枚举装箱为Enum类型,产生性能开销
  • Enum本身是一个引用类型,所有具体的枚举类型比如MyColor都是值类型,并且继承自Enum(特殊的继承规则,就像所有C#对象都继承自object,它也是引用类型)。当调用基类Enum的方法时,自身需要装箱成Enum,参数也需要传递给Enum flag,会进行两次装箱
  • HasFlagFast 用泛型值类型参数替代 Enum 引用类型参数,从根源上避免了装箱。Unsafe.As 只是进一步优化了类型转换的性能,而泛型值类型参数才是避免装箱的关键
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 原生判断函数是Enum的实例方法,Enum本身是抽象类(引用类型)
public bool HasFlag(Enum flag){
// ...
}

// 替换 HasFlag 方法,避免装箱,仅适用于Int32枚举
public static bool HasFlagFast<T>(this T flags, T value) where T : struct, Enum
{
if (Enum.GetUnderlyingType(typeof(T)) != typeof(int))
throw new ArgumentException($"枚举类型 {typeof(T).Name} 的底层类型不是 Int32,无法使用此方法", nameof(T));
var f = Unsafe.As<T, int>(ref flags);
var v = Unsafe.As<T, int>(ref value);
return (f & v) == v;
}

1.2 内部发生了什么

阅读全文 »

问题

新项目,在学习FairyGUI,看到官方Demo里的Window示例有这么一段代码

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
// 业务层BasicsMain
private Window _winA; // 实例变量
private Window _winB; // 实例变量
private void PlayWindow()
{
GComponent obj = _demoObjects["Window"];
obj.GetChild("n0").onClick.Add(() =>
{
if (_winA == null)
_winA = new Window1();
_winA.Show();
});

obj.GetChild("n1").onClick.Add(() =>
{
if (_winB == null)
_winB = new Window2();
_winB.Show();
});
}

// FairyGUI.EventListener.cs
public void Add(EventCallback0 callback)
{
_bridge.Add(callback);
}

// FairyGUI.EventBridge.cs
EventCallback0 _callback0;
public void Add(EventCallback0 callback)
{
_callback0 -= callback;
_callback0 += callback;
}

这个PlayWindow函数是每次点击对应按钮都会调用的,但是里面的注册回调却用的匿名函数,虽然内部会先对委托进行解绑再绑定,但是匿名函数,怎敢断定两次调用传入的是同一个函数的?我立马嗅到一丝内存泄漏的异味,但是实际并没有发生。

验证

阅读全文 »

介绍

红黑树(RBT, Red Black Tree)是一种自平衡的二叉搜索树,有如下定义:

  • 根叶黑:根和叶子节点是黑色的(红黑树里的叶子节点其实是空节点Nil)
  • 不红红:红色节点的两个子节点都必须是黑色。(即不能有两个连续的红色节点)
  • 黑同路:从任一节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点

在这种定义下确保从根到叶子的最长路径不会超过最短路径的两倍,从而保证了高效的查找、插入和删除操作。相较于AVL树的严格平衡,红黑树只求得一种弱平衡,因此它的插入/删除性能是优于AVL树的,但是查询性能则略逊于AVL树。C++里的set、map底层就是红黑树实现的。

插入

阅读全文 »

AVL介绍

平衡二叉树(BST, Balanced Binary Tree又称AVL Tree)是自平衡的二叉搜索树(BST, Binary Search Tree),二叉搜索树的问题是,如果插入顺序是有序的,会导致树退化为线性结构,查询的复杂度退化为$O(N)$。

定义

首先介绍平衡因子(BF, Balance Factor):$BF(T) = h_L - h_R$,其中$h_L$和$h_R$分别是$T$左右子树的高度。
由此可以进行AVL树的定义:

  • 空树
  • 任一节点的$|BF(T)|<=1$
阅读全文 »

概念

我们有一堆数据,希望能够支持快速的插入、删除、查询以及范围查询
我们都知道数组进行排序后,可以通过二分查找的方式快速定位数据,时间复杂度是$O(LogN)$,但是如果数组经常发生插入、删除操作,就需要进行大量平移,时间复杂度是$O(N)$。
那用平衡树呢?AVL树、红黑树都是经过深度优化的动态数据结构,他们的插入删除查找都可以在$O(LogN)$的时间内完成,但是他们实现起来较为复杂,且对于范围查询,还需要进行中序遍历,但至少比数组好多了。
那链表呢,链表的插入删除是很方便,但关键查询呢,它能进行二分查找吗?链表无法随机访问,怎么二分?很显然,直接对普通链表进行二分查找是困难的。1990年,Pugh发表论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》,创造性的提出了自己的解决方案:”如果不能在节点间跳跃,那就建造可以跳跃的桥梁吧!”,跳跃表(SkipList)正式被提出。
跳跃表是一种概率性的有序数据结构,通过建立多级索引来加速查找,可以看作是在链表基础上加了“快速通道”,变相了实现对链表的二分查找,并且,范围查找也能够很轻易的完成,只要找到目标,就可以沿着链条依次访问。
游戏里排行榜一般是采用Redis Sorted Set,它在数据规模较大时的底层数据结构就是跳跃表+哈希表。

  • 跳跃表:天然支持有序插入、删除和范围查询,时间复杂度O(log n)
  • 哈希表:用于快速查找特定用户的当前位置和分数(O(1))

示意图跳跃表的每个节点拥有一个前序指针和多层后继指针。每层后继指针都独立成链,每个节点在插入时,都会按照概率分配给它多少层后继指针(至少一层)。类似抛硬币,落到正面,就给它加一层后继指针,然后继续抛硬币;落到反面就结束。当然,硬币正面的概率不一定是50%(实际有论文提出,包括业内经验来看,25%的概率是对性能和内存占用权衡后的得到的较优选择)。实际上,作者最初考虑过确定性跳表,即第0层是全连接,第1层是隔1个连接,第2层是隔3个连接…但是这样会导致插入和删除需要进行大量调整,复杂度变高,从而引入随机性,不仅简化了插入和删除的操作,并且统计上仍然是接近二分的结构。

代码

阅读全文 »

YOLOv4

YOLOv4是在YOLOv3的基础上进行了一些改进,但是整个流程依旧是YOLOv3,比如正负样本的划分、忽略样本等等。
其中添加的改进主要有如下几点:

  • 跨阶段局部网络(Cross-Stage-Partial, CSP)作为主干网络进行特征提取
  • Mish激活函数(backbone)和Leaky ReLU(neck)
  • Mosaic数据增强、MixUP数据增强
  • 添加注意力机制模块
  • CIoU作为边框回归损失
  • 在neck中添加空间金字塔池化(Spatial Pyramid Pooling, SPP)提升感受野
  • 在原先YOLOv3 neck的特征金字塔网络(Feature Pyramid Netword, FPN)的基础上改进为路径聚合网络(Path Aggregation Network, PAN)

YOLOv5

YOLOv5并无论文,我以开源代码中的实现来说明(version 5.0)。

阅读全文 »

0 主干网络

YOLOv3采用DarkNet-53网络,结构如下图(DarkNet-53预训练于ImageNet,由于是1000类的分类,所以网络最后输出经过全连接层。但是目标检测不需要那个全连接层,因此实际上只使用了“DarkNet-52”,共52层卷积层):

YOLOv3 Backbone

  • BN为批归一化层,Acti为激活函数,YOLOv3采用LeakyReLU
  • 输入批次经过一个3X3卷积改变通道数为32,然后经过5个降残差块。每个降残差块包含一次步幅为2的3X3卷积加上一系列残差块。每个残差块包含一次1X1卷积降低通道数,再经过一次3X3卷积提升通道数,最后和残差边进行连接。
  • 整体主干网络清晰,每经过一个降残差块,通道数翻倍,特征图宽高减半。

1 预测分支网络

阅读全文 »

0. 说明

  • C++采用g++编译,C采用gcc编译。两者主要不同点是:C++编译考虑到函数重载,会将原函数“改名”(命名倾轧name mangling);而在C中不存在重载,函数名不会变动。
  • g++和gcc可以兼容C++和C的编译方式,但是默认情况下g++采用C++编译方式;而gcc采用C的编译方式
  • 注意:gcc编译C++文件时不会主动链接C++用到的库stdc++,需要手动指定链接选项-lstdc++
  • __cplusplus宏定义会在编译cpp文件以及用C++的方式编译时被包含,因此用gcc编译.cpp文件或者g++编译.c、.cpp文件都会有这个宏
  • 之所以用条件判断,因为gcc不认识extern "C",直接编译会报错

1. C++调用C

只需要声明时包含extern "C"即可。下面的代码中,func.h可以不动,在main.cpp调用时,直接extern "C" int func(int, int)也是可以的。只需要让编译器按照C的方式编译,不要改动函数名即可正确链接的函数符号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// func.h 不论.c还是.cpp文件调用,都不会出错
#ifndef FUNC_H
#define FUNC_H

#ifdef __cplusplus
extern "C" {
#endif // __cplusplus

int func(int, int);

#ifdef __cplusplus
}
#endif // __cplusplus

#endif
阅读全文 »
0%