最小生成树的概念

最小生成树，即构造连通网的总代价（总权值）最小的树为最小生成树。

最小生成树的一些性质：

1. 最小生成树一定是连通的。
2. 如果去掉某条边，则最小生成树就不再连通。
3. 最小生成树的边数一定等于顶点数减1。
4. 一个连通图可以有多个生成树。
5. 生成树中不存在环。
6. 对于包含n个顶点的连通图，其最小生成树包含n-1条边。
7. 对于包含n个顶点的完全无向图，最多包含n^(n-2)条边。

图的概念

图（Graph）是由一组顶点(V)和一组能够将两个顶点相连的边(e)的非空有限集组成的。

例如：

定义一个图G=(V,E)，V={V1,V2,V3,V4},E={E1,E2,E3,E4,E5,E6}
E1=<V1,V2> E2=<V1,V3> E3=<V1,V4> E4=<V2,V3> E5=<V3,V2> E6=<V3,V3>

一些定义

基本概念

1. 有向边：一条边所代表的顶点是有序的，则为有向边，也称弧，例如< V1,V2 >和< V2,V1 >是不同的两个边或弧。
2. 无向边：一条边所带表的顶点是无序的，则为无向边，例如(V1,V2)和(V2,V1)是同一个边。
3. 弧的头尾：一条边从V1指向V2，则V1为弧尾，V2为弧头。
4. 度：一个顶点的度是指与它相连的边的数目，入度指入边数，出度指出边数。
5. 路径：从顶点V1到V2的路径是指从V1到V2的边所表示的顶点序列。
6. 权值：与图的边相关的数称为权值，带权值的图称为网。
7. 连通：若两个顶点之间存在路径，则称这两个顶点是连通的。

图的分类

1. 简单图：不存在顶点到自身的边且一条边不重复出现，这样的图称为简单图。
2. 无向图：图中任意一条边代表的顶点是无序的，则为无向图。
3. 有向图：图中任意一条边代表的顶点是有序的，则为有向图。
4. 完全图：图中任意两个顶点之间都存在边，则为完全图。
5. 连通图：图中任意两个顶点之间都存在路径，则为连通图，否则为非连通图。

树

树的定义

树是n(n>=0)个结点的有限集合，当n=0时，称为空树。在任意一棵非空树中：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集，每个集合本身又是一棵树，称为原树的子树。

准备工具

1.AssetStudio
2.游戏安装包
3.解压软件

AssetStudio是进行解包的工具，主要针对的是Uinty的游戏
Github链接：https://github.com/Perfare/AssetStudio
网盘链接：https://pan.baidu.com/s/1oPR8JQ_tKsrgV-dLxgF7Pg?pwd=f8m6
游戏安装包可以直接从官方网站下载，我会以崩坏2举例
解压软件任意，常用的解压软件一般都没什么问题

线性的数据结构

线性结构是指元素只有一个前趋和后继

线性的数据结构分为物理线性结构和逻辑线性结构

物理线性是元素在内存中的地址是连续的；逻辑线性在内存中的地址不一定是连续的，在逻辑上存在前趋和后继

常用的线性数据结构包括数组、链表、栈、队列

角色基本运动的实现

基础知识

角色的移动功能是通过Movement组件实现的，角色由Controller进行直接控制，主角由PlayerController控制

敌人则由AIController控制；其中对于主角，PlayerController可由键盘、鼠标、手柄等获取到玩家输入实现对

角色的控制。

GameMode包含了对游戏的诸多设置，PlayerController就在其中，我们可以在GameMode中设置自己写的PlayerController。

关于游戏框架，可以参考官方文档： https://docs.unrealengine.com/4.27/zh-CN/InteractiveExperiences/Framework/