虚幻的反射

反射是虚幻引擎中的基础技术，虚幻中的细节面板、序列化、垃圾回收、蓝图与C++交互等功能都依赖于反射。但原生C++并不支持反射，因此虚幻拥有一套自己的反射系统。

本文将对虚幻的反射机制进行浅析，更多信息可以查看工程文件中的generated和Marcos源码文件，里面有对反射更详细的解释。

反射的简要机制

Unreal Build Tool(UBT)和Unreal Header Tool(UHT)两个协同工作来生成运行时反射需要的数据。UBT通过扫描头文件，记录任何至少有一个反射类型的头文件的模块。如果其中任意一个头文件从上一次编译起发生了变化，那么UHT就会被调用来利用和更新反射数据。UHT分析头文件，创建一系列反射数据，并且生成包含反射数据的C++代码,放到每一个模块的generated文件中，使用标记宏标记的数据编译后可以在generated文件中看到，使用了一些宏对数据进行包装。

用生成的C++代码来存储反射数据的一个最大好处就是，它可以保证跟二进制做到同步,不会加载陈旧或者过时的反射数据，因为它是跟引擎的其它代码同时编译的，并且它会在程序启动的时候使用C++表达式来计算成员偏移等，而不是通过针对特定平台/编译器/优化的组合中进行逆向工程。

反射的概念

允许程序运行时获取类内部信息，并且能操作对象的内部属性和方法。

但C++本身并没有反射的概念，需要通过第三方库来实现。

反射的目标：

1. 类对象反射。
2. 类成员数据反射。
3. 类成员函数反射。

注册时成员为public作用域
通过注册宏实现反射功能

归并排序

算法思想：先将需要排序的元素分开，在合并的过程中将元素进行排序，最终得到一个有序数组。
分开方法：逻辑二分。

模拟：将数组拆分为单个元素

选择排序

每次从乱序区中选择一个最小的排序
分为简单选择排序和堆排序

简单选择排序

每次遍历都找到一个最小的元素，放在乱序区的第一个位置。

1
2
3
4
5
6
7
8
9
10
11
12

void SelectSort(int arr[], int n)
{
    for(int i=0;i<n;i++){
        int Min=i;
        for(int j=i+1;j<n;j++){
            if(arr[j]<arr[Min]){
                Min=j;
            }
        }
        swap(arr[i],arr[Min]);
    }
}

交换排序

基于比较的排序算法，通过不断交换元素的位置，使得排序的元素达到有序。
主要有冒泡排序和快速排序。

冒泡排序

冒泡排序思路与实现都很简单，通过不断比较两个相邻的元素，如果第一个元素比第二个元素大，则交换两个元素的位置，这样循环一轮下来，最大的元素就浮到了最右边。

同样将数组分为待排区和有序区，实现如下：

1
2
3
4
5
6
7
8
9
10

void BubbleSort(int* arr, int n) 
{
    for(int i=0;i<n-1;i++){
        for(int j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1]){
                swap(arr[j],arr[j+1]);
            }
        }
    }
}

有关排序的一些概念

时间复杂度：一个算法执行所耗费的时间。
空间复杂度：运行完一个程序所需内存的大小。
原地排序：空间复杂度为 O(1)，不需要申请额外的空间。
内部排序：待排序的元素全部存放在内存中。
外部排序：待排序元素很多，需要从外存中读取元素。
稳定性：排序前后两个相同元素的相对位置不变。

拓扑排序

一些概念

1. 有向无环图：有向说明图的路径是有方向的，无环说明图的路径不能成环。
2. 拓扑序列：设一个具有n个顶点的有向图，其中顶点序列V1—Vn满足一条路径，若Vi必须在Vj之前，则称这个顶点序列为拓扑序列。
3. 拓扑排序：按照顶点的依赖关系进行排序，使得没有前驱的顶点排在最前，没有后继的顶点排在后面，直到所有节点都被移除。

算法思想

它的思路总结起来只有两步：

1. 在有向图中选择一个没有前驱的顶点并输出。
2. 删除该顶点和以它为尾的弧。
3. 重复上述两步直到所有顶点都被输出，或者当前图中不存在无前驱的顶点为止。

蒙太奇动画

在UE中可以使用蒙太奇动画完成一些效果，完成人物的一些特俗运动，比如攀爬、跳跃、技能等等。
使用蒙太奇的动画只需要创建一个蒙太奇动画，插入一个slot和section，便可以在动画蓝图涨使用，我们可以不关心蒙太奇动画的实现细节而达到很好的表现效果。

散列表定义

散列表（HashTable，也叫哈希表），是根据关键码值(Key)而直接进行访问的数据结构。也就是说，它通过把键值映射到整数的方法(Value=f(Key))，来访问记录，这加快了查找速度。

在存储散列表时，通过散列函数来确定每个键值对应的存储位置，当我们要查找一个Key时，便可以通过散列函数直接找到Value的位置。

散列冲突：查找时可能会出现f(Key1)=f(Key2)这种情况，即两个不同的Key，通过散列函数计算出来的值相同，这种现象称为散列冲突。

关于最短路径的一些概念

源点：路径起始的第一个顶点。
终点：路径终止的最后一个顶点。
最短路径：对于无权图来说，就是从源点到终点经过的边数最少的路径；对于带权图来说，就是路径上权值之和最少的路径。

常用的最短路径算法有：SPFA算法、Dijkstra算法、Bellman-Ford算法、SPT算法、Floyd算法，将介绍Dijkstra算法和Floyd算法。