冲击秋招

Lua与热更新

打包函数

BuildPipeline.BuildAssetBundles("AssetBundles", BuildAssetBundleOptions.ChunkBasedCompression, BuildTarget.Android);

打包策略和方案

1. 按文件夹打包：Bundle数量少，首次下载块，但是后期更新补丁大
2. 按文件打包：Bundle数量多，首次下载较慢，更新补丁小
3. 整包：完整更新资源放在项目中，下载时间长，首次更新少
4. 分包：大部分热更资源放在服务器上，进入游戏后下载到热更目录，安装包下，但是首次更新下载时间久。

简述热更新

热更新原理

Unity 游戏热更新包含两个方面，一个是资源的更新，一个是脚本的更新。
Unity 提供可以热更的方案就是 AssetsBundle（后面简称 AB）。资源、代码都可以打成 AB 包，放到服务器上，然后比对版本，进行热更。Unity3D 的热更新会涉及 3 个目录：游戏资源目录、数据目录、网络资源地址。
游戏资源目录：游戏的安装目录，如下所示:
Mac OS 或 Windows：Application.dataPath + “/StreamingAssets”;
IOS:Application.dataPath + “/Raw”;
Android: jar:file://“ + Application.dataPath + “!/assets/“

数据目录：由于“游戏资源目录”在 Android 和 IOS 上是只读的，不能把网上的下载的资源放到里面，所以需要建立一个“数据目录”，该目录可读可写。不同平台下，“数据目录”的地址也不同，LuaFramework 的定义如下：
Android 或 IOS：Application.persistentDataPath + “/LuaFramework”
Mac OS 或 Windows：C:/LuaFramework/
调试模式下：Application.dataPath + “/StreamingAssets/

网络资源地址：又名服务器地址，是用来存放游戏资源的网址

热更步骤如下：

1. 第一次开启游戏后，程序将“游戏资源目录”的内容复制到“数据目录”中。（这个步骤只会执行一次，下次再打开游戏就不复制了）。
2. 游戏开启后，程序会从“网络资源地址”下载一些更新的文件到数据目录。
3. 游戏过程中的资源加载，都是从“数据目录”中获取解包。

热更新流程

热更的基本流程分为两部分：
导出热更资源
（1） 打包热更资源的对应的 md5 信息（涉及到增量打包）
（2） 上传热更 ab 到热更服务器
（3） 上传版本信息到版本服务器

游戏流程热更
（1） 启动游戏
（2） 根据当前版本号，和平台号去版本服务器上检查是否有热更
（3） 从热更服务器上下载 MD5 文件，比对需要热更的具体文件列表
（4） 从热更服务器上下载需要热更的资源，解压到热更资源目录
（5） 游戏运行加载资源，优先到热更目录中加载，再到母包资源目录加载
更新注意：
（1） 要有下载失败重试几次机制
（2） 要进行超时检测
（3） 要记录更新日志，例如哪个资源导致了整个更新流程失败

版本号管理

客户端版本号是 4 位来标识，假设是 X.Y.Z.W
X：【巨大版本号】这一位其实就是 1，没事一般不会动他，除非有太巨大的变化
Y：【整包更新版本号】：我们游戏一般一个月会有一个比较大的版本迭代，这种版本会走商店，每次提交 Y 值+1；
Z：【服务器协议版本号】，一个月度版本周期内，万一 SDK 有问题或者 C#层有发现 bug，需要更新商店，这一位会+1，这里单独留一个 Z 处理这种商店版本号，是因为不想影响 Y 值，而商店提交新包要求版本号必须有增加，buildNum 也是商店要求必须要升的；
W：【编译版本号\热更版本号】，每次热更都+1 。
【第 2 位加 1 之后，3、4 位全部清 0】

table

基本原理：
table是一种特殊的容器，可以向数组一样按照索引存取，也能按照键值对存取。

local mytable = {1,2,3} --相当于数组
local mytable = {[1]=1,[2]=2,[3]=3} --和上面等价
local mytable = {1,2,3,[3] = 4} --隐式赋值会覆盖掉显式赋值
local mytable = {1,2,5,a=9,b="bo"} --支持索引存储，也支持键值对存储
print(mytable[4])--输出为nil，键值对存储不能用索引访问
print(mytable.a) --正确访问方式
mytable.id = "1001" --不用事先定义，使用的时候直接赋值，类似python
--我们收数据的时候只用收table一种数据类型就可以了，约定好里面有什么数据后直接取即可
mytable.userdata = {atk = 15, def = 20} --table可以存放很多数据类型，并且可以嵌套
function mytable:test(p)
  print(p)
  print(mytable[1])
end

for i,v in  pairs(mytable) do  --遍历方式，输出的是索引和内容，或者键值对，忽略nil项
  print(i)
  print(v)
end
for i,v in ipairs(mytable) do  --遍历方式，输出的是索引和内容，并且不能遍历键值对，并且遍历索引时遇到nil会停止输出
  print(i)
  print(v)
end
if next(mytable) == nil then --next第二个参数是索引位，判断索引位的下一位，如果为空就判断第一位
  print("为空")
end

print(#mytable)  --判断table长度，但注意table里面不能有nil，否则长度计算会在遇到nil的地方停止

底层实现：
table：底层实现分数组部分和哈希表部分。数组部分，从 1 开始做整数数字索引，这可以提供紧凑且高效的随机访问；数组部分存储在 TValue *array 中，其长度 信息存储在 int sizearray 中。哈希表存储在 Node *node，哈希表的大小用 lu_byte lsizenode 表示，lsizenode 表示的是 2 的几次幂，而不是实际大小，因 为哈希表的大小一定是 2 的整数次幂。哈希冲突后，采取开放地址法，应对 hash碰撞。每个 Table 结构，最多会由三块连续内存构成：
(1) 一个 table 结构
(2) 一块存放了连续整数索引的数组
(3) 一块大小为 2 的整数次幂的哈希表

string底层

Lua 中的字符串（string）底层实现使用了一种叫作”短字符串优化”（Short String Optimization）的策略。该策略基于以下两种情况来存储字符串：

短字符串：长度小于等于 40 字节的字符串会直接存储在 Lua 内部的字符串对象中，而不需要额外的内存分配。这种情况下，字符串的数据会被直接存储在字符串对象的数据字段中。

长字符串：长度超过 40 字节的字符串则会分配额外的内存空间来存储字符串数据。Lua 使用一个单独的内存块来存储长字符串的数据，并在字符串对象中存储指向该内存块的指针。

无论是短字符串还是长字符串，Lua 的字符串都是不可变的（immutable）。这意味着一旦创建了一个字符串，就不能再修改它的内容。如果需要对字符串进行修改，必须创建一个新的字符串。

Lua 的字符串实现具有一些优点和注意事项：

• 节约内存：短字符串直接存储在字符串对象中，无需额外的内存分配，节约了内存空间。长字符串使用单独的内存块存储，可以避免字符串占用过多的 Lua 内存。

• 高效性能：由于字符串不可变，可以在多个 Lua 值之间共享相同的字符串对象，避免了重复的字符串复制操作，提高了性能。

• 注意拼接操作：由于字符串不可变，每次对字符串进行拼接操作都会创建一个新的字符串对象。如果需要频繁进行字符串拼接操作，可能会导致大量的内存分配和对象创建，影响性能。在这种情况下，可以使用 Lua 中的字符串缓冲区（如 table.concat 函数）或者考虑使用 LuaJIT 提供的 FFI 接口来进行高效的字符串拼接。

元表

local mytable = {1,2,3}
local mymetatable = {
  __index = {b=6,c="c"}  
}
mytable = setmetatable(mytable, mymetatable)  --元表扩展了普通表的功能
getmetatable(mytable)  --获取元表
print(mytable.c)  --table里面没有的话会查找元表中的index来调用


local mymetatable = {
  __index = function(table,key)   --访问table中没有的元素调用元表中的index
              if key == "b" then
                return "hello"
              else
                return nil
              end
              end  --如果index是一个方法
  __newindex = function(table,key)    --给table和元表中没有的数组元素赋值或给一个变量赋值会执行newindex
                  print("被调用")
                  return "NoValue"
                  end
  __call = function(mytable, newtable)  --把元表当做方法（函数）使用的时候调用call
              sum = 0
              for i = 1, #mytable do 
                sum = sum + mytable[i]
                end
              for i = 1, #newtable do 
                sum = sum + newtable[i]
                end
              return sum
            end
  __tostring = function(mytable)     --想要直接输出这个表的时候调用
                return #mytable
                end
  __add = function(mytable, newtable)  --两个表进行相加操作的时候调用
      for i = 1, table.maxn(newtable) do
         table.insert(mytable, table.maxn(mytable)+1,newtable[i])
      end
      return mytable
   end



  
}
mytable = setmetatable({1,2,3}, mymetatable)
function mytable:test(p)
  print(p)
end
print(mytable.b)  --会调用index里面的方法输出hello
mytable.c = 10    --设置没有定义的变量会触发__newindex，一般里面做一些报错提醒
mytable[1] = 6    --已经存在的数组元素，不会触发__newindex
mytable[5] = 666  --不存在的数组元素，会触发__newindex
newtable = {10,20,30}
print(mytable(newtable))  --调用__call
print(mytable)       --调用__tostring
mytable = mytable + newtable
print(mytable)

---查找和赋值不调用index和newindex函数的方法
print(rawget(mytable ,mytable.w))  --输出的是nil
rawset(mytable,"w",1)   --设置不存在的变量不会调用newIndex



mytable:test(5)           --这两种调用方式等价，冒号是一个语法糖
mytable.test(mytable,5)

模块

一个文件想要用另外一个文件的变量，就要用到require。但是如果我们不想每次使用都require，我们可以把lua文件定义成module，这样只需要require一次加载进来，就能在所有文件中访问这个文件的变量。
普通用法

require("math_func")
local ret = math_abs(-7)
print(ret)

定义Module的方式：

module("device",package.seeall)

function get_device_name()
  return "guest9527:
end

local name = device.get_device.name()

接口

如果我们不想把一个lua文件中的所有变量都暴露出去，我们可以在文件中定义一个table作为接口，把所有变量设为local，把想要暴露的添加到table中，然后返回即可。

function math_abs(value)
  if(value < 0) then
    return -value
  end
  return value
  
end
function math_vec_length_2(vec)
  return vec.x * vec.x + vec.y - vec.y
end
function _test_func(...)
  print("test")
end
local list = {
  abs = math_abs,
  lenth = math_vec_length_2,
  test_func = _test_func,
}

return list

lua的数据类型

table
function
nil
boolean
number：包括整数，浮点数等
string

userdata：userdata类型主要用来表示在C/C++中定义的类型，即用来实现扩展lua，这些扩展代码通常是用C/C++来实现的。对lua 虚拟机来说userdata只是提供了一块原始的内存区域，可以用来存储任何东西，并且在lua中userdata没有任何预定义的操作。注意这块分配的额外内存是由Lua垃圾收集器来管理的，无须关心起释放等情况。
thread：线程
注意：数据类型不是固定了，一个数据赋值了整型之后，也可以赋值字符串。
注意：函数也是变量的一种，可以随意赋值给变量
注意：字符串之间的拼接用..

local a = 5
print(type(a))  --打印类型
foo2 =function foo(x)  --函数的赋值
      print(x)
      end
foo2(x)
 

点和冒号的区别

冒号隐式地传递了一个调用这个函数的表的示例进去，可以省略一个参数。

local a = {}
--下面两个函数等同
function a.test(self,a,b)  --这里self必须传进去本身才行
  print("atest",self)
end
function a:test(a,b)
  print("atest",self)  --冒号包含了self机制
end

两者不能混着用，如果定义的是冒号，用的时候是点，就会导致找不到self而报错。

闭包

语法域：函数可以嵌套在另一个函数中，内部函数可访问外部函数的局部变量，这样可以用来实现面向对象的编程
闭包：lua编译一个函数的时候，会生成一个原型prototype，包含了函数体对应的虚拟机指令，函数体中的常量，调试信息。运行的到函数的时候会创建一个新的数据对象，对象中包含了响应函数原型的引用和一个数组，包含了所有upvalue的引用（传进来的值），这个数据对象称为闭包。
注意：lua支持函数有多返回值

function f1(n)
  local fuction f2()
    print(n)
  end
  return f2
end
 
g1 = f1(2021)
g1()
g2 = f1(2022)
g2()

function create(n)
  local function foo()
    local function foo1()
      print(n)
    end
    local function foo2()
      n = n + 10
    end
    return foo1,foo2
  end
  return foo
end
f0 = create(2021)
f1,f2 = f0()
g1,g2 = f0()
f1()
f2()
g1()
g2()
f1()

--闭包可以作为高阶函数的参数
table.sort(t,function(t1,t2) return t1.param > t2.param end)
--重写（类似面向对象）,可以用来添加验证
local oldOpen = io.open
local accessOk = function(filename,mode)
                    --方法体
                    end
io.open = function(filename,mode)
              if accessOk(filename,mode) then
                return oldOpen(file,mode)
              else
                return nil,"校验失败"
              end
          end

--实现迭代器
function values(t)
  local i = 0
  return function() i=i+1 return t[i] end
  end
t = {1,2,3,4,5,6}
iter = values(t)
print(iter())
print(iter())
print(iter())

C#和lua的相互调用

c语言可以和lua直接通信，lua就是c语言开发的，C#要和lua通信，需要先调用C语言，C语言再调用lua，Xlua插件封装了C#调用C语言的接口。
C 调用 Lua 实际上是：由 C 先把数据放入栈中，由 Lua 去栈中取数据，然后返回数据对应的值到栈顶，再由栈顶返回 C。
Lua 调 C 也一样：先编写自己的 C 模块，然后注册函数到 Lua 解释器中，然后由Lua 去调用这个模块的函数。
Lua虚拟栈：从底往上是1到n，从顶往下时-1到-n，lua里面用到的数据类型都可以入栈

Lua实现只读表

local readOnly
readOnly = function(t)
  for k,v in pairs(t) do
    if type(v) == "table" then
      t[k] = readOnly(v)
    end
  end
  local nt = {}
  local mt = {
    __index = t,
    __newindex = function(t,key,value)
      error("this is a readonly table")
      end
  }
  setmetatable(nt,mt)
  return nt
end

local a = {x=1,y=2}
a = readOnly(a)
a.x = 3 --错误

当我们对readOnly的table进行赋值会调用newIndex函数，从而抛出错误

Lua GC

从Lua 5.1开始，采用三色增量标记清除算法。好处：它不必再要求GC一次性扫描所有的对象，这个GC过程可以是增量的，可以被中断再恢复并继续进行的。3种颜色分类如下：

白色：当前对象为待访问状态，表示对象还没有被GC标记过，这也是任何一个对象创建后的初始状态。换言之，如果一个对象在结束GC扫描过程后仍然是白色，则说明该对象没有被系统中的任何一个对象所引用，可以回收其空间了。

灰色：当前对象为待扫描状态，表示对象已经被GC访问过，但是该对象引用的其他对象还没有被访问到。

黑色：当前对象为已扫描状态，表示对象已经被GC访问过，并且该对象引用的其他对象也被访问过了。当GC完后被重置为白色。
伪代码：

每个新创建的对象颜色为白色
 
//初始化阶段
遍历root节点中引用的对象，从白色置为灰色，并且放入到灰色节点列表中
 
//标记阶段
当灰色链表中还有未扫描的元素：
    从中取出一个对象并将其标记为黑色
    遍历这个对象关联的其他所有对象：
        如果是白色：
        标记为灰色，加入灰色链表中
 
//回收阶段
遍历所有对象：
    如果为白色：
        这些对象都是没有被引用的对象，逐个回收
    否则：
        重新加入对象链表中等待下一轮的GC检查

设计模式

静态和单例模式

单例模式的本质就是类成员中有一个对象实例

public class Animal{
  public static string Title = "Animal" // 类成员
  public string Name; // 对象成员
  public const float Pi = 3.14f; // 类成员
  public readonly float Pi2 = 3.14f // 对象成员
  public static readonly Animal animal; //类成员
  private static Animal Instance;  //实例
  public static Animal Instance{
    get{
      if(instance == null){
        instance = new Animal();
      }
      return instance;
    }
  }

  // 类构造函数
  static Animal(){
      animal = new Animal();
  }
  // 对象构造函数
  public Animal(){

  }
}

注意：

1. 我们也可以把整个类static来当做单例
2. 使用单例时，我们把构造函数私有可以防止被人new，在类前加上seal防止被继承

观察者模式

多人开发的时候，每个人开发不同的功能，每个人代码风格不一样，但是要用到别人提供的功能，别人还没有写对应的功能，这时候我们要用到事件，关心的人订阅这个事件即可，完全不用关心其他人的代码。我们可以用到C#里面的Action函数。
这样的订阅功能我们可以用一个EventManager来管理，包含至少以下方法：订阅事件，取消订阅事件，触发事件， 移除事件，我们可以通过一个字典来进行管理，键是对应的命名（可以用枚举），值就是对应的Action(可以封装一下)。

外观模式

把一个功能的细节全部封装起来，只对外暴露使用者关心的部分。例如一场战斗开始之前我们需要初始化各个系统，有网络系统，团队系统，背包系统，AI系统等等，但是我们都把它封装到一个函数当中调用即可，对外只暴露一个初始化战斗的函数，战斗时候的更新同理，我们也可以把各个系统的更新集成到一起。
定义：为子系统定义一组统一的接口，这个高级接口让子系统更容易被使用。

状态模式

枚举是关键。怪物的状态机是一个例子。不同的状态有不同的初始化动作，不同的更新动作，更新的时候有状态转移条件。

工厂模式

概念：工厂模式（Factory Pattern）是一种创建型设计模式，它提供了一种将对象的创建和使用分离的方式。工厂模式通过定义一个创建对象的接口，但将具体的对象创建过程延迟到子类来完成。这样，客户端代码就不需要知道具体的对象创建细节，只需要通过工厂方法获取所需的对象。工厂模式的主要目的是封装对象的创建过程，使客户端与具体的对象类解耦，从而提供更大的灵活性和可维护性。
例子：MMORPG中输入网络端的信息即可调用对应的接口创建对应的角色。
工厂模式通常涉及以下角色：

抽象工厂（Abstract Factory）：定义了创建对象的接口，它是工厂方法模式的核心，具体工厂类实现了这个接口。

具体工厂（Concrete Factory）：实现抽象工厂接口，负责创建具体的产品对象。

抽象产品（Abstract Product）：定义了产品的接口，描述了产品的特性和功能。

具体产品（Concrete Product）：实现抽象产品接口，是被创建的对象。

工厂模式的工作流程如下：

客户端通过调用抽象工厂的方法创建产品对象，而不直接实例化具体产品类。

抽象工厂根据客户端的请求，选择合适的具体工厂来创建产品对象。

具体工厂根据客户端的请求，创建具体的产品对象，并将其返回给客户端。

工厂模式的好处在于当新增一个类的时候我们不会对原来的代码进行修改，只新增类本身及其工厂。

策略模式

根据不同的条件需求，构建不同的实例，并且在策略模式内 封装具体的自定义行为接口
应用场景
例如: 游戏设置界面，根据GPU品质，批量设置群组显示效果

命令模式

命令是对命令的封装，每一个命令都是一个操作，请求方发出请求，接收方接收请求，并执行操作。命令模式解耦了请求方和接收方，命令模式属于行为型模式
有执行队列的需求，且支持撤销需求
应用场景
例如: 比如FPS 输入模块，需要存储某些输入指令时
优点：
通过引入命令的抽象接口，实现了命令请求与实现的解耦
扩展性良好，可以很容易的增加新命令

面向对象的设计原则

1. 单一职责原则：一个类只做一件事情
2. 开放-封闭原则：对于扩展是开放的，对于更改是封闭的
3. Liskov替换原则：子类必须能替换基类
4. 依赖倒置原则：依赖于抽象，在依赖之间定义一个抽象的接口使得高层模块调用接口，而底层模块实现接口的定义，以此来有效控制耦合关系，达到依赖于抽象的设计目标。
5. 接口隔离原则：使用小的专门接口，不要使用大的总接口

行为树和状态机的区别

有限状态机系统：是指在不同阶段会呈现出不同的运行状态的系统，这些状态是有限的、不重叠的。这样的系统在某一时刻一定会处于其所有状态中的一个状态，此时它接收一部分允许的输入，产生一部分可能的响应，并且迁移到一部分可能的状态。

1. 基本节点是状态：他包含了一系列运行在该状态的行为以及离开这个状态的条件。
2. 状态可以任意跳转,实现简单,但是对于大的状态机很难维护.状态逻辑的重用性低.
3. 每一个状态的逻辑会随着一些新状态的增加而越来越复杂。维持状态的数量和状态逻辑复杂性是一个很大的难点。需要合理的分割以及重用状态。
4. 状态机状态的复用性很差，一旦一些因素变化导致这个环境发生变化。你只能新增一个状态，并且给这个新状态添加连接他以及其他状态的跳转逻辑。
5. 状态机的跳转条件一旦不满足，就会一直卡在某一个状态。

行为树：一个流行的 AI 技术，涵盖了层次状态机，事件调度，事件计划，行为等一
系列技术。

1. 高度模块化状态，去掉状态中的跳转逻辑，使得状态变成一个“行为”。
2. “行为”和”行为”之间的跳转是通过父节点的类型来决定的。比如并行处理两个行为，在状态机里面无法同时处理两个状态。
3. 通过增加控制节点的类型，可以达到复用行为的目的。
4. 行为树具有树状结构，节点之间的连接关系可以灵活组合和修改。在Unity中，可以使用行为树编辑器进行可视化编辑和调整，可以快速修改和调试行为树的逻辑。这使得开发人员可以快速迭代和调整角色的行为逻辑，提高开发效率。

数据结构

这一部分参考以前的文章《Unity游戏开发基础知识》

哈希表

哈希表代表了键值对集合，使用键访问集合中的元素。用法比较简单。
HashMap和Hashtable都是基于哈希表实现的Map接口的实现类，但是它们采用的哈希算法和数据结构有所不同。

Hashtable ht1 = new Hshtable();
ht1.Add("1",99);
ht1.Clear();
if(ht1.ContainsKey("1")){
  Debug.Log("包含键为“1”的数据");
}
ht1.Remove("1");
Debug.Log(ht1["1"]);   //读取
ht1["1"]=99;           //修改
ICollection key = ht1.Keys;
foreach(var k in key){      //遍历
  Debug.Log(ht1[k]);
}

和字典的不同在于可以存储任何类型的变量，不需要提前定义，但需要拆箱装箱。
哈希表本质上是通过数组储存的，一般把Key输入哈希函数中，计算出哈希值，把用这个哈希值作为数组的索引来读取和修改Value。
如果不同的Key计算出了同一个哈希值，称为发生了哈希冲突（哈希碰撞），因此设计合适的哈希函数很重要（直接定址法，数字分析法，折叠法，随机数法和除留余数法等等）

hash函数

直接定址法
取关键字或者关键字的某个线性函数为 Hash 地址，即address(key) = a * key + b; 如知道学生的学号从2000开始，最大为4000，则可以将address(key)=key-2000(其中a = 1)作为Hash地址。

平方取中法
对关键字进行平方计算，取结果的中间几位作为 Hash 地址。如有以下关键字序列 {421，423，436} ，平方之后的结果为 {177241，178929，190096} ，那么可以取中间的两位数 {72，89，00} 作为 Hash 地址。

折叠法
将关键字拆分成几部分，然后将这几部分组合在一起，以特定的方式进行转化形成Hash地址。如图书的 ISBN 号为 8903-241-23，可以将 address(key)=89+03+24+12+3 作为 Hash 地址。

除留取余法
如果知道 Hash 表的最大长度为 m，可以取不大于m的最大质数 p，然后对关键字进行取余运算，address(key)=key % p。这里 p 的选取非常关键，p 选择的好的话，能够最大程度地减少冲突，p 一般取不大于m的最大质数。

随机数法
  选择一个随机函数，取关键字的随机函数值作为它的哈希地址，即H(key)=random(key)，其中random为随机函数。通常用于关键字长度不等时的场合。

hash冲突

解决哈希冲突的方法有开放寻址法（一个位置被占了就一直找下一个位置），拉链法：通过在数组的位置上额外存放一个指针指向另外的一个位置（相当于链表），然后去下一个位置看是否有冲突，有冲突就继续走向这个位置指针的下一个位置，以此类推。
当哈希表被占领的位置过多（例如超过70%），就会触发扩容机制，创建一个新的数组，长度为原来的两倍，并且重新利用哈希函数计算位置。

hashmap(哈希映射)

HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

HashMap存数据的过程是：

HashMap内部维护了一个存储数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。

链表

C#中是有前驱和后驱的双向链表。链表在内存中是离散的，不连续。通过两个指针指向上一个存储位置和下一个存储位置。
链表在删除和插入的时候效率比列表和数组快，但查找的时候只能靠遍历，比较慢。

链表可以分为单向和双向。

LinkedList<int> linList = new LinkedList<int>();
LinkedListNode<int> node;  
node = linList.AddFirst(1); //第一个节点
linlist.AddAfter(node,2); //添加在某节点后面+具体值
linlist.AddBefore(node,0); //添加在某节点前面+具体值
Debug.Log(linList.Count);
Debug.Log(linList.First.Value); //第一个值
Debug.Log(linList.Last.Value); //最后一个值
Debug.Log(node.Previous.Value); //节点前一个值
Debug.Log(node.Next.Value); //节点后一个值

反转链表

链表逆序（反转链表）的方法：
方法一：就地逆序
方法二：递归法
方法三：插入法

就地逆序：

def reverseList(self,head: Optional[ListNode]) -> Optional[ListNode]:
  pre = None
  cur = head
  while cur:
    nxt = cur.next
    cur.next = pre
    pre = cur
    cur = nxt
  return pre

插入法：
从链表的第二个结点开始，把遍历到的结点插入到头结点的后面，直到遍历结束。假如原链表为head->1->2->3->4->5->6->7，在遍历到2的时候，将2插入到头结点的后面，链表变为head->2->1->3->4->5->6->7，同理head->3->2->1->4->5->6->7等等。

def insertReverse(head):
	# 特殊情况：头节点为空，或者只有单个节点
    if head is None or head.next is None:
        return
    # 操作头节点, 2次指针操作,头节点head.next赋值给cur, 由于头节点最终要成为尾结点,其指向为空
    cur = head.next
    head.next = None
    # 操作第二个及之后的节点,每次遍历到的节点都放到头节点处
    while cur:
        nex = cur.next
        cur.next = head
        head = cur
        cur = nex
    return head

判断链表有环

首先从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节点ID和此节点之前所有节点ID(即重新遍历len-1步)依次作比较。如果发现新节点之前的所有节点当中存在相同节点ID，则说明该节点被遍历过两次，链表有环；如果之前的所有节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。
例如这样的链表：A->B->C->D->B->C->D， 当遍历到节点D的时候，我们需要比较的是之前的节点A、B、C，不存在相同节点。这时候要遍历的下一个新节点是B，B之前的节点A、B、C、D中恰好也存在B，因此B出现了两次，判断出链表有环。
方法一、穷举遍历

struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
};
 
bool detectCycle(ListNode *head) {
    ListNode *tem = head,*temp;
    int len = 0;
    while(tem){
        *temp = head;
        for(int i=0;i<len;i++)
        {
            if(temp==tem) return true;
            temp = temp->next;
        }
        len++;
        tem = tem->next;
    }
    return false;
}

class Solution1:
    """
    思路分析:
    判断一个单链表是否有环,
    可以用 set 存放每一个 节点, 这样每次 访问后把节点丢到这个集合里面.
    其实 可以遍历这个单链表, 访问过后,
    如果这个节点 不在 set  里面, 把这个节点放入到 set 集合里面.
    如果这个节点在  set 里面 , 说明曾经访问过, 所以这个链表有重新 走到了这个节点, 因此一定有环.

    如果链表都走完了, 把所有的节点都放完了. 还是没有重复的节点, 那说明没有环.

    """

    def hasCycle(self, head):

        mapping = set()

        flag = False

        p = head

        while p:

            if p not in mapping:
                mapping.add(p)
            else:
                flag = True
                break
            p = p.next

        return flag

方法二、哈希表/set 缓存
哈希表：首先创建一个以节点ID为键的HashSet集合，用来存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节点。每遍历到一个新节点，就用新节点和HashSet集合当中存储的节点作比较，如果发现HashSet当中存在相同节点ID，则说明链表有环，如果HashSet当中不存在相同的节点ID，就把这个新节点ID存入HashSet，之后进入下一节点，继续重复刚才的操作。

set集合：还可以用 set 遍历链表，把节点放入set里，每次访问下个节点时，如果set长度不变，则跳出，说明有环。否则set长度+1，继续遍历。

ListNode *detectCycle(ListNode *head) {
        set<ListNode* node> s;
        while(head){
             if(s.size()==s.push(head)) return true;
              head = head->next();
        }
        return false;
    }

二叉树

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点：

• 每个结点最多有两棵子树，即二叉树不存在度大于2的结点。
• 二叉树的子树有左右之分，其子树的次序不能颠倒。
• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
• 二叉树的顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

性质

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1) 个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h- 1.

3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为 n2,则有n0＝n2＋1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=Log2(n+1). (ps：Log2(n+1)是log以2为
   底，n+1为对数)

5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为i的结点有：

   • 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
   • 若2i+1<n，左孩子序号为2i+1，2i+1>=n否则无左孩子
   • 若2i+2<n，右孩子序号为2i+2，2i+2>=n否则无右孩子

链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面课程学到高阶数据结构如红黑树等会用到三叉链。

// 二叉链
  struct BinaryTreeNode
  {
   struct BinTreeNode* _pLeft; // 指向当前节点左孩子
   struct BinTreeNode* _pRight; // 指向当前节点右孩子
   BTDataType _data; // 当前节点值域
  }
  // 三叉链
  struct BinaryTreeNode
  {
   struct BinTreeNode* _pParent; // 指向当前节点的双亲
   struct BinTreeNode* _pLeft; // 指向当前节点左孩子
   struct BinTreeNode* _pRight; // 指向当前节点右孩子
   BTDataType _data; // 当前节点值域
  }；

遍历

参考：https://blog.csdn.net/chinesekobe/article/details/110874773
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。
NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。相当于从顶部开始，逆时针绕圈。
LNR：中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。相当于从左往右排序，每个父节点都在其左右子节点的中间。
LRN：后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。相当于从左往右，一次从叶子节点取一个元素下来，依次取到顶部。

深度优先遍历：似于先序遍历。
广度优先遍历：按每一层从上到下，从左到右进行遍历。

//	先序遍历
void ShowXianXu(BitTree T)			//		先序遍历二叉树
{
	if(T==NULL)						//	递归中遇到NULL，返回上一层节点
	{
		return;
	}
	printf("%d ",T->data);
	ShowXianXu(T->lchild);			//	递归遍历左子树
	ShowXianXu(T->rchild);			//	递归遍历右子树
}
//	中序遍历
void ShowZhongXu(BitTree T)			//		先序遍历二叉树
{
	if(T==NULL)						//	递归中遇到NULL，返回上一层节点
	{
		return;
	}
	
	ShowZhongXu(T->lchild);			//	递归遍历左子树
	printf("%d ",T->data);
	ShowZhongXu(T->rchild);			//	递归遍历右子树
	
}
//	后序遍历
void ShowHouXu(BitTree T)			//		后序遍历二叉树
{
	if(T==NULL)						//	递归中遇到NULL，返回上一层节点
	{
		return;
	}
	
	ShowHouXu(T->lchild);			//	递归遍历左子树
	ShowHouXu(T->rchild);			//	递归遍历右子树
	printf("%d ",T->data);
}

前序非递归遍历：
这里使用栈来实现，首先将根放进栈中然后定义一个循环，循环条件是栈不为空，首先将栈顶元素弹出，并用一个结点保存，如果栈顶的元素不是空，就输出栈顶元素的数据，然后看它的左右子树，先把右子树压入栈中，再压左子树，（因为栈后进先出，先要访问左子树，所以左子树后进入），每次进入循环如果栈顶为空的化就不进行操作，直接进行操作，如果栈顶不为空的话再进行下面操作。直到所有结点都被遍历。
中序非递归遍历：
还是利用栈，因为先访问最左边的结点，所有我们先定义一个循环一直向左走把左边的所有结点压入栈中，这时候栈顶就是最左侧得结点，我们要将这个接单弹出，然后输出它的值，下来输出的是它的根结点，所以先要把它的右子树都压入栈中，最后再保存根结点就能保证先输出根结点再输出它右侧元素了。
后序非递归遍历：
还是利用栈，和中序非递归类似，先找到最左边的结点，并把这条路径上所有的结点按照找的顺序压入栈中，然后将最左侧结点的数据打印出来，然后判断当前节点是不是栈顶结点的左子树，如果是要先访问右结点才能访问根结点，否则将当前结点置成空，下一次就会输出当前结点的根结点，然后重复上述操作。

#前序
def preorder(root): 
  res=[] 
  if not root:  
    return [] 
  stack=[root] 
  while stack: 
    node=stack.pop() 
    res.append(node.val) 
    if node.right: stack.append(node.right) 
    if node.left: stack.append(node,left) 
  return res
#中序
def inorder(root): 
  stack=[] 
  node=root 
  res=[] 
  while stack or node: 
    while node: 
      stack.append(node) 
      node=node.left 
    node=stack.pop() 
    res.append(node.val) 
    node=node.right 
  return res
# 后序
def laorder(root): 
  stack=[root] 
  res=[] 
  while stack: 
    node=stack.pop() 
    if node.left: stack.append(node.left) 
    if node.right: stack.append(node.right) 
    res.append(node.val) 
  return res[::-1]

void PreOrder(BiNode *bt) { //树的前序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			visit(p->data);//访问根结点
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

void MidOrder(BiNode *bt) { //树的中序遍历
	SqStack s;
	s = InitStack();
	BiNode *p = bt;
	while (p != NULL || StackEmpty(&s) != 1) { //当p为空，栈也为空时退出循环
		while (p != NULL) {
			Push(&s, p); //将指针p的节点压入栈中
			p = p->Lchild; //遍历左子树
		}
		if (StackEmpty(&s) != 1) { //栈不为空
			p = Pop(&s); //根结点出栈,相当于回退
			visit(p->data);//访问根结点
			p = p->rchild; //遍历右子树
		}
	}
	DestroyStack(&s);
}

void PostOrder(BiNode *bt) { //树的后序遍历
	SqStack s;
	s = InitStack_1();
	BiNode *p = bt;
	element elem;
	while (p != NULL || StackEmpty_1(&s) != 1) { //当p为空，栈也为空时退出循环
		if (p != NULL) {//第一次入栈，访问左子树
			elem.ptr = p;
			elem.flag = 1; //标记flag为1，表示即将第一次入栈
			Push_1(&s, elem); //将指针p的结点第一次压入栈中
			p = p->Lchild;
		} else {
			elem = Pop_1(&s); //出栈
			p = elem.ptr; //p指向当前要处理的结点
			if (elem.flag == 1) {
				//flag==1时，说明只访问过左子树，还要访问右子树
				elem.flag = 2;
				Push_1(&s, elem); //结点第二次压入栈中
				p = p->rchild;
			} else {
				//flag==2时，左右子树都已经访问过了
				visit(p->data);
				p = NULL; //访问后，p赋为空，确保下次循环时继续出栈（相当于回退）
			}
		}
	}
	DestroyStack_1(&s);
}

反转二叉树

将每个节点的左右节点互换，也就是遍历每一个节点然后交换它们的左右节点，这里就可用到二叉树的各种遍历方法，只是将保存节点值的过程转换为交换左右节点。（中序遍历不能使用，会将某些节点反转两次）

//前序遍历解决问题
public TreeNode invertTree(TreeNode root) {
    if(root==null) return null;
    //反转左右孩子
    TreeNode temp=root.left;
    root.left=root.right;
    root.right=temp;
    invertTree(root.left); //左
    invertTree(root.right); //右
    return root;
}

排序二叉树找第k大节点

题目：

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
 
限制：
1 ≤ k ≤ 二叉搜索树元素个数

答案：

class Solution {
public:
    int kthLargest(TreeNode* root, int k) {
        //右根左降序遍历
        stack<TreeNode*> s;
        while(root || !s.empty())
        {
        	while(root)
        	{
        		s.push(root);
        		root = root->right;
        	}
        	root = s.top();
        	s.pop();
        	k--;
        	if(k==0)
        		return root->val;
        	root = root->left;
        }
        return -1;
    }
};

在这段代码中，使用右根左的遍历顺序是为了实现降序遍历二叉搜索树（Binary Search Tree）。降序遍历意味着按照节点值的降序来访问节点。
对于二叉搜索树而言，中序遍历可以实现升序遍历，即从小到大访问节点。而右根左的遍历顺序是中序遍历的逆序，所以可以实现从大到小访问节点，即降序遍历。
在这个特定的问题中，要找到二叉搜索树中第 k 大的元素。通过降序遍历，我们可以依次访问每个节点的值，并在第 k 个节点时返回对应的值，即为第 k 大的元素。
使用栈来辅助遍历的过程，可以实现迭代方式的降序遍历。从根节点开始，先将右子树的节点依次入栈，然后弹出栈顶元素，进行相应的处理（比如减小 k 的值，判断是否为第 k 大的元素），然后将左子节点作为下一个要处理的节点。
因此，使用右根左的遍历顺序是为了满足降序遍历的需求，并能够有效地找到第 k 大的元素。

平衡二叉树

二叉树能提高查询的效率 O(logn)，但是当你插入{1,2,3,4,5,6} 这种数据的时候，你的二叉树就像一个链表一样，搜索效率变为 O(n)

所以一般的二叉搜索树在进行数据的存储时可能会使工作的时间复杂度并未降低太多，这时便需要我们将二叉树的高度尽可能的降低，使二叉树的高度降低为log(n)，这样我们就得到了一个高度平衡的二叉搜索树，使对于数据的一系列操作的时间复杂度稳定在 O(logn)。
红黑树就是一颗自平衡的二叉树。

跳表

跳表（Skip List）是一种用于实现有序集合的数据结构，它通过在一个有序链表的基础上添加多层索引来提高数据的查找效率。跳表允许快速地按照元素的键值进行查找、插入和删除操作。
跳表的核心思想是通过建立多级索引层次，使得较大范围的元素可以通过跳过一些节点来进行快速搜索。每一级索引都是原始链表的一个子集，且比前一级索引稀疏，即包含更少的节点。最底层的索引就是原始的有序链表。
在跳表中，每个节点包含一个键值对，键用于按照有序方式进行排序，值则是具体存储的数据。每个节点还包含指向下一级索引节点的指针，使得可以在不同层次的索引之间进行快速的跳跃。

查找：从顶层往下，如果下一个指向的节点索引大于我们需要查找的索引，那么就跳到下一层。
插入：当我们在跳表中插入数据的时候，我们通过选择同时将这个数据插入到部分索引层中，如何选择索引层，可以通过一个随机函数来决定这个节点插入到哪几级索引中，比如随机生成了k，那么就将这个索引加入到，第一级到第k级索引中。
删除：和链表插入删除一致，不过是多了几层

public Node find(E e) {
    if (empty()) {
        return null;
    }
    return find(e, head, curLevel);
}

private Node find(E e, Node current, int level) {
    while (level >= 0) {
        current = findNext(e, current, level);
        level--;
    }
    return current;
}

//返回给定层数中小于e的最大者
private Node findNext(E e, Node current, int level) {
    Node next = current.next(level);
    while (next != null) {
        if (e.compareTo(next.data) < 0) {
            break;
        }
        //到这说明e >= next.data
        current = next;
        next = current.next(level);
    }
    return current;
}

跳表的查询效率是时间复杂度是 nlogn

红黑树（难）

参考：https://blog.csdn.net/xiaofeng10330111/article/details/106080394
红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在插入和删除操作后能够自动调整树的结构，保持树的平衡性。红黑树是在普通二叉搜索树的基础上增加了一些附加的规则和性质来确保平衡。

红黑树的特点包括：

1. 根节点是黑色的。
2. 每个叶子节点（NIL 节点，空节点）是黑色的。
3. 如果一个节点是红色的，那么它的两个子节点都是黑色的。
4. 对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数量的黑色节点。

这些特性保证了红黑树的关键性质，包括：
任意节点到其每个叶子节点的路径长度相等或差至多为1，因此树的高度是对数级别的，保持了较好的平衡性。
查找、插入和删除操作的时间复杂度为 O(log n)，保持了较高的操作效率。

旋转操作
在分析插入和删除操作前，先说明一下旋转操作，这个操作在后续操作中都会用得到。旋转操作分为左旋和右旋，左旋是将某个节点旋转为其右孩子的左孩子，而右旋是节点旋转为其左孩子的右孩子。

1. 如果插入节点位置是根部，节点为黑色，其他位置是红色

总共就会有12种情况，其中四种情况满足红黑树的性质，8种情况不满足红黑树性质。
parent 为黑色节点。四种情况不需要做任何额外的处理。
parent 为红色节点（ Double Red ），其中左面4种属于B树节点上溢的情况（一个4阶B树节点中最多存放三个数，这四种情况本来已经有3个了，又插入了1个，变成了4个，超出了4阶B树节点的容量范围，这种情况称为上溢）。这八种情况需要进行额外的处理。

算法

时间复杂度

$O(1)$

void func1(int n){
    int count = 100;
    count++;
}
void func2(int n){
    int count = 100;
    for(int i = 0; i < count;i++){

    }
}
int func3(int n){
    return n;
}

$O(n)$

void func1(int n){
    int count = 100;
    for(int i = 0; i < n;i++){
        count++;
    }    
}

$O(n^2)$

void func1(int n){
    int count = 100;
    for(int i = 0; i < n;i++){
        for(int j = 0;j < n;j++){
            count++;
        }
    }    
}

$O(nm)$

void func1(int n,int m){
    int count = 100;
    for(int i = 0; i < n;i++){
        for(int j = 0;j < m;j++){
            count++;
        }
    }    
}

$O(\log n)$

void func1(int n){
    int i = 1;
    while(i < n){
        i *= 2;
    }  
}

$O(n \log n)$

void func1(int n){
    int i = 1;
    for(j = 0; j < n; j++){
        while(i < n){
            i *= 2;
        }  
    }
}

空间复杂度

$O(1)$

void func1(int n){
    int a = 1;
    a++;
    int b = 2;
    b++;
}

$O(n)$

void func1(int n){
    int[] array = new int[n];
    for(int i = 0;i < n; i++){
        array[i] = i;
    }
}

int sum(int n){
    int a;
    if(n == 0) return 0;
    return n + sum(n - 1);
}

$O(n^2)$

void func1(int n){
    int[,] array = new int[n,n];
}

int sum(int n){
    int[] array = new int[n];
    if(n == 0) return 0;
    return n + sum(n - 1);
}

稳定性和冒泡排序

稳定性：当需要排序的序列中存在相同关键字的元素，排序后的相对次序保持不变，则算法稳定，稳定的排序算法会保留数值项顺序的表达意义。
冒泡排序：

int [] array = new int[]{2,5,6,7,1,3}
void bubbleSort(int[] arr, int n){
    int temp;
    int i,j;
    for(i = 0;i< n - 1; i++){
        for(j = 0; j < n-1-i; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

时间复杂度为$O(n^2)$，空间复杂度$O(1)$

改进版：

int [] array = new int[]{2,5,6,7,1,3}
void bubbleSort(int[] arr, int n){
    int temp;
    int i,j;
    bool flag = false;   
    for(i = 0;i< n - 1; i++){
        for(j = 0; j < n-1-i; j++){
            flag = false;
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if(!flag){
            break;
        }
    }
}

选择排序

void arr_sort(int *p,int n)
{
    int i,j;
    int min = 0;
    for(i = 0;i < n - 1;i++)//排序次数
    {
        min = i;
        for(j = i + 1;j < n;j++)
        {
            if(p[j] < p[min])
            {
                min = j;//记录交换的元素下标值
            }
        }
        if(i != min)
        {
            int temp = p[i];
            p[i] = p[min];
            p[min] = temp;
        }  
    }
}

插入排序

int [] array = new int[]{2,5,6,7,1,3}
void printArray(int[] arr){
    ls = "";
    foreach(var r in arr){
        ls += r + ",";
    }
    Debug.Log("轮次" + index++ + "数组" + ls);
}
void insertSort(int[] arr, int n){
    for(i = 0;i< n; i++){
        for(j = i; j > 0 && arr[j-1] > arr[j]; j--){
            int temp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = temp;
        }
        printArray(arr);
    }
}

时间复杂度为$O(n^2)$，空间复杂度$O(1)$

希尔排序

希尔排序是对插入排序的优化。

int [] array = new int[]{2,5,6,7,1,3}
void printArray(int[] arr){
    ls = "";
    foreach(var r in arr){
        ls += r + ",";
    }
    Debug.Log("轮次" + index++ + "数组" + ls);
}
void shellSort(int[] arr, int n){
    int i = 0;
    int j = 0;
    int temp;
    for(int step = n / 2; step > 0; step = step / 2){
        for(i = step; i < n; i++){
            temp = arr[i];
            for(j = i; j >= step && temp < arr[j - step]; j -= step){
                arr[j] = arr[j - step];
            }           
            arr[j] = temp;
        }
        printArray(arr);
    }
}

时间复杂度$O(n^2)$，空间复杂度$O(1)$，稳定性是不稳定的

堆排序

堆是一颗完全的二叉树，堆中某个节点的值总是不大于（大顶堆）或不小于（小顶堆）其父节点的值

void heapSort(int[] list){
    // 构建初始堆
    for(int i = list.Length / 2 - 1; i >= 0; i--){
        AdjustHeap(list,i,list.Length);                // O(n)
    }
    // 进行n-1次循环，完成排序
    for(int i = list.Length - 1; i > 0; i--){         // O(nlogn)
        // 交换堆顶（最大数）到最后，并把这个节点从二叉树去掉
        int temp = list[i];
        list[i] = list[0];
        list[0] = temp;
        // 只有堆顶不确定是不是最大，只调整堆顶即可
        AdjustHeap(list, 0, i);
    }
}
public void AdjustHeap(int[] array,int parent ,int Length){
    int temp = array[parent];    // 父节点
    int child = 2 * parent + 1;  // 左子节点
    while(child < Length){
        // 找最大的子节点
        if(child + 1 < Length && array[child] < array[child + 1]){
            child++;
        }
        if(temp >= array[child])
            break;
        // 如果子节点较大，交换父子节点
        array[parent] = array[child];
        // 子节点作为父节点，进行下一轮比较
        parent = child;
        child = 2 * child + 1;
    }
    array[parent] = temp;
}

时间复杂度$O(n\log n)$，空间复杂度$O(1)$，稳定性是不稳定的

二叉树排序

二叉排序树：空树或满足以下条件

1. 如果左子树不空，左子树上的所有节点值均小于根节点的值。如果右子树不空，右子树上的所有节点均大于根节点的值。
2. 左、右子树分别为二叉排序树。
   遍历顺序：
   中序遍历（左根右）、先序遍历（根左右）、后序遍历（左右根）
   我们采用中序遍历，也就是说，二叉排序树从小到大的遍历顺序是从最后最左的子节点开始，往上遍历，遍历到父节点的时候，再从下往上，从左往右遍历右子节点，如此往复，遍历完左右节点。

   public class BinarySortTreeNode{
       public int Key{get;set;}
       public  BinarySortTreeNode Left{get;set;}
       public BinarySortTreeNode Right{get;set;}
       public BinarySortTreeNode(int key){
           Key = key;
       }
       public void Insert(int key){
           var tree = new BinarySortTreeNode(key);
           if(tree.Key <= Key){
               if(Left == null){
                   Left = tree;
               }
               else{
                   Left.Insert(key);
               }
               else{
                   if(Right == null){
                       Right = tree;
                   }
                   else{
                       Right.Insert(key);
                   }
               }
           }
       }
       // 遍历方法（妙啊）
       public void InorderTraversal(){
           Left?.InorderTraversal();
           Debug.Log(Key);
           Right?.InorderTraversal();
       }
   }
   
   public static void BinaryTreeSort(int[] array){
       var binarySortTreeNode = new BinarySortTreeNode(array[0]);
       for(int i = 1; i < array.Length; i++){
           binarySortTreeNode.Insert(array[i]);        
       }
       binarySortTreeNode.InorderTraversal();
   }
   

   时间复杂度$O(n\log n)$，空间复杂度$O(n)$，稳定性是不稳定的

快速排序

参考：https://blog.csdn.net/qq_40941722/article/details/94396010

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end)
        return;
    int tmp = arr[begin];
    int i = begin;
    int j = end;
    while(i != j){
        while(arr[j] >= tmp && j > i)
            j--;
        while(arr[i] <= tmp && j > i)
            i++;
        if(j > i){
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
    arr[begin] = arr[i];
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);
    Quick_Sort(arr, i+1, end);
}

function Sort(list, leftIndex, rightIndex)
  if(leftInfex >= rightIndex) then
    return
  end
  local i = leftIndex
  local j = rightIndex
  local baseValue = list[leftIndex]

  while i < j do
    while i < j and list[j] >= baseValue do
      j = j - 1
    end
    while i < j and list[i] <= baseValue do
      i = i + 1
    end
    if j > i then
      t = list[i];
      list[i] = list[j];
      list[j] = t;
    end
  end
  list[leftIndex] = list[i];
  list[i] = baseValue;
  Quick_Sort(list, leftIndex, i-1);
  Quick_Sort(list, i+1, rightIndex);
end

快速排序最优时间复杂度为O(nlogn)，不稳定

归并排序

参考：https://www.bilibili.com/video/BV1Pt4y197VZ/

function sort(arr, startIndex = 0, endIndex = arr.length - 1) {
    // 递归结束条件：startIndex大于等于endIndex的时候
    if (startIndex >= endIndex) {
        return;
    }

    // 折半递归
    let midIndex = parseInt((startIndex + endIndex) / 2);
    sort(arr, startIndex, midIndex);
    sort(arr, midIndex + 1, endIndex);
    // 将两个有序的小数组，合并成一个大数组
    merge(arr, startIndex, midIndex, endIndex);
}

function merge(arr, startIndex, midIndex, endIndex) {
    // 新建一个大数组
    let tempArr = [];
    let p1 = startIndex;
    let p2 = midIndex + 1;
    let p = 0;

    // 比较两个有序小数组的元素，依次放入大数组中
    while (p1 <= midIndex && p2 <= endIndex) {
        if (arr[p1] <= arr[p2]) {
            tempArr[p++] = arr[p1++];
        } else {
            tempArr[p++] = arr[p2++];
        }
    }

    // 右侧小数组已排序完毕，左侧小数组还有剩余，将左侧小数组元素依次放入大数组尾部
    while (p1 <= midIndex) {
        tempArr[p++] = arr[p1++];
    }
    // 左侧小数组已排序完毕，右侧小数组还有剩余，将右侧小数组元素依次放入大数组尾部
    while (p2 <= endIndex) {
        tempArr[p++] = arr[p2++];
    }

    for (let i = 0; i < tempArr.length; i++) {
        arr[i + startIndex] = tempArr[i];
    }
}

let arr = [4, 5, 8, 1, 7, 2, 6, 3];
sort(arr);
console.log(arr);

时间复杂度是O(nlogn)，稳定

排序算法的使用场景

1. 游戏中得分排行榜
2. 英雄战力榜列表等

拓扑排序

拓扑排序（Topological Sorting）是一种对有向无环图（Directed Acyclic Graph, DAG）进行排序的算法。在拓扑排序中，节点表示图中的任务或事件，有向边表示任务间的依赖关系。
拓扑排序的目标是将图中的节点按照一定的顺序线性排列，使得所有的依赖关系都得到满足。也就是说，在排序结果中，若存在一条从节点 A 到节点 B 的有向边，那么节点 A 在排序中必须出现在节点 B 之前。
通俗讲解：当同时存在很多件事情需要完成，但是有些事情的完成依赖于另外若干件事情的完成，拓扑排序需要我们排列出事情完成的顺序，这个顺序往往不止一种。

拓扑排序的算法通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来实现。在实际应用中，如果图中存在环路（即有向图中存在回路），则无法进行拓扑排序，因为无法满足所有的依赖关系。因此，拓扑排序算法通常要求应用于有向无环图。

步骤

1. 构建图：根据给定的有向图的边关系，构建表示图的数据结构。通常使用邻接表或邻接矩阵表示图。
2. 统计节点入度：对于每个节点，统计它的入度（即指向该节点的边的数量）。可以通过遍历图的边关系，记录每个节点的入度。
3. 初始化队列：创建一个队列（可以使用队列数据结构），用于存储入度为0的节点。
4. 入度为0的节点入队：遍历所有节点，将入度为0的节点加入队列。
5. 拓扑排序：从队列中取出一个节点，输出该节点（或保存到结果序列中），并将其相邻节点的入度减1。若某个节点的入度减为0，则将其加入队列。
6. 重复步骤5，直到队列为空。如果输出的节点数量与图中的节点数量相同，则拓扑排序成功；否则，图中存在环路，无法进行拓扑排序。
7. 输出结果：按照拓扑排序的顺序输出节点，即为拓扑排序的结果。

int topological_sort(LGraph G)
{
    int i,j;
    int index = 0;
    int head = 0;           // 辅助队列的头
    int rear = 0;           // 辅助队列的尾
    int *queue;             // 辅组队列
    int *ins;               // 入度数组
    char *tops;             // 拓扑排序结果数组，记录每个节点的排序后的序号。
    int num = G.vexnum;
    ENode *node;
 
    ins  = (int *)malloc(num*sizeof(int));  // 入度数组
    tops = (char *)malloc(num*sizeof(char));// 拓扑排序结果数组
    queue = (int *)malloc(num*sizeof(int)); // 辅助队列
    assert(ins!=NULL && tops!=NULL && queue!=NULL);
    memset(ins, 0, num*sizeof(int));
    memset(tops, 0, num*sizeof(char));
    memset(queue, 0, num*sizeof(int));
 
    // 统计每个顶点的入度数
    for(i = 0; i < num; i++)
    {
        node = G.vexs[i].first_edge;
        while (node != NULL)
        {
            ins[node->ivex]++;
            node = node->next_edge;
        }
    }
 
    // 将所有入度为0的顶点入队列
    for(i = 0; i < num; i ++)
        if(ins[i] == 0)
            queue[rear++] = i;          // 入队列
 
    while (head != rear)                // 队列非空
    {
        j = queue[head++];              // 出队列。j是顶点的序号
        tops[index++] = G.vexs[j].data; // 将该顶点添加到tops中，tops是排序结果
        node = G.vexs[j].first_edge;    // 获取以该顶点为起点的出边队列
 
        // 将与"node"关联的节点的入度减1；
        // 若减1之后，该节点的入度为0；则将该节点添加到队列中。
        while(node != NULL)
        {
            // 将节点(序号为node->ivex)的入度减1。
            ins[node->ivex]--;
            // 若节点的入度为0，则将其"入队列"
            if( ins[node->ivex] == 0)
                queue[rear++] = node->ivex;  // 入队列
 
            node = node->next_edge;
        }
    }
 
    if(index != G.vexnum)
    {
        printf("Graph has a cycle\n");
        free(queue);
        free(ins);
        free(tops);
        return 1;
    }
 
    // 打印拓扑排序结果
    printf("== TopSort: ");
    for(i = 0; i < num; i ++)
        printf("%c ", tops[i]);
    printf("\n");
 
    free(queue);
    free(ins);
    free(tops);
    return 0;
}

其中G是有向图，结构可能如下：

struct ENode
{
    int ivex;                   // 该边所指向的顶点的位置
    struct ENode *next_edge;    // 指向下一条弧的指针
} ;

struct VNode
{
    char data;                  // 顶点的数据
    ENode *first_edge;          // 指向第一条依附该顶点的边的指针
} ;

struct struct
{
    VNode vexs[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum;                 // 顶点数量
    int edgenum;                // 边数量
} ;

操作系统和编译原理

进程与线程

概念：进程是操作系统分配资源的单位，线程是调度的基本单位，线程之间共享进程资源。

进程如何分配线程和内存

进程是运行application的载体，客户端，服务器都是application，每个application会创建一个进程，在创建进程的时候，系统会在内存创建代码段，数据段，堆，栈。和其他三个不同，栈是每个线程独享的，其他三个是公共的。
代码段：进程会读取可执行文件（exe），这个文件本质上是操作CPU的二进制指令（程序编程成汇编语言之后最后会变成二进制的机器语言），这些指令在内核态就装载好了。然后进程就会至少创建一个主线程出来，可以基于这个线程创建更多线程，进程是线程的容器，然后线程调度CPU执行我们的任务（调度CPU是基于线程的），上面所说的就是进程创建代码段，代码段只能读取不能修改。二进制指令文件（exe)在内核态装载完成后，就会调到main入口（已经确定内置地址），开始执行第一条指令。
数据段：负责全局变量，单例中的静态变量等的存放。
堆：用来做动态内存分配，例如创建对象的时候就是在堆创建出来，系统会从堆上分配一个满足要求大小的内存。如果不用了需要主动调用系统的free API来释放内存，但很多编程语言都内置垃圾回收器（GC），判断这个数据对象是垃圾，所以会主动回收，但是这会消耗系统性能，所以我们才需要尽可能减少GC。

栈：每个线程有独立的栈，存放代码执行中函数的参数等局部变量，并为函数跳转，返回提供服务，原理是栈临时存储了函数中的变量或引用，并在这个函数的顶部入栈了一个函数的形参，返回地址，前一个栈底地址（%ebp），以便函数调用完成后恢复原来的地址，并设置栈底(%esp)为当前栈顶值，调用完成后返回值压入EAX（如果返回值超过EAX宽度，高位放在EDX中）中并恢复现场。栈的大小有限制（默认几十k，可修改），超出会导致栈溢出，导致系统杀掉进程。
参考：https://blog.csdn.net/qq_27161565/article/details/110210030

虚拟内存和物理内存，动态内存分配

每个进程都会创建一个虚拟内存空间，只有这个进程能够访问，不同进程就算修改同一地址，指向的也不是同一个内存。虚拟内存不代表分配了真实内存，只是划了一个范围。只有在实际用到的时候予以分配，系统会划出一段地址，分配一些物理内存页（例如4K为一个映射单元），如果内存页不够，就会把长期不用的保存到磁盘从而释放内存页，当需要使用磁盘中的内存页的时候再交换回来，但这样会导致系统开销变大，CPU占用率高。数据是保存到映射的物理页的。
内存释放的时候，先释放对应的虚拟内存空间，再释放物理内存页，这样就能给其他进程或这个进程的其他虚拟内存地址使用。
动态分配的时候，出现out of memory的错误，有两种情况，一种是虚拟内存都分配完了，第二种是关闭了物理内存的交互功能或操作系统不堪重负死机了。
Tips：进程可以创建另外一个进程，相当于把代码段，数据段，堆重新创建一遍，但是子进程能访问主进程的函数，这是因为它们映射到的是同一个物理内存页，除非装载了新的代码。

内存碎片

内存碎片是对于堆来说的，只有堆的大小是动态的。
导致内存碎片的原因是反复请求与释放大小不一的内存空间，从而使得中间产生了很多段不能使用的空白内存。
解决方法：

1. 分配大小统一的内存空间
2. 设定对象池，循环反复利用

内存泄露

概念：虚拟的可用的内存地址空间越来越少
原因：分配的内存空间没有任何指针指向，但是又没有释放。
解决方法：

1. C/C++传统方式：分配内存的时候提前想好释放时机，并写代码执行
2. 采用系统托管的垃圾回收机制，拥有垃圾回收的语言所有的对象都继承自Object这样的东西，每当有赋值操作的时候（内部有重载），里面的引用计数就会+1，如果原来的变量=null，引用-1，引用计数为0的时候，调用系统的内存释放API。垃圾回收的时候，可以启用一个垃圾回收线程，也可以在主线程的特定时候调用。垃圾回收机制在内存分配的时候，看有没有同类型的垃圾对象，有的话直接返回，没有再申请内存

追踪内存泄露：
内存泄露检测工具：原理是接管了分配释放内存的malloc,free函数，判断哪里调用了malloc但是没有free。

1. 手动管理：重载new，delete，malloc的时候把对象添加到表中，free的时候从表中删除。如果一个对象长时间在表中，可能发生泄露
2. 自动管理：由于代码逻辑问题，有变量指向一个内存，但是你没有发现。
   tips：不断打开文件，忘记关闭也会导致系统越慢

GC性能优化

1. 减少new的次数
2. 调节GC参数，调节垃圾回收时机
3. 避免GC峰值：避免大量消耗和创建对象，确实需要的时候可以分配处理（每帧处理少量） 。

操作系统如何调度线程

操作系统需要分配CPU核心来执行线程的任务（代码指令），为了充分利用CPU资源，所谓的六核十二线程，一个CPU的物理核心模拟成两个逻辑核心，同时处理两个线程的任务（超线程技术）。
线程的两个状态：

1. 就绪状态：可被调度，放在就绪队列
2. 挂起状态：等待某个条件对象，如文件IO结束，睡眠结束，操作系统不会调度这些线程

Windows，Linux，Unix都是抢占式多任务管理系统：如果线程可以一直执行就一直占用CPU直到系统分配的时间片（根据线程的优先级分配）用完，然后才会放回就绪队列，等待重新被调度。
调度过程：CPU核心把此时寄存器的数据保存到内存中，然后从内存中读取要调度的线程上一次保存的寄存器数据，就能继续执行线程。
由于线程随时有可能被调度出去然后执行其他线程，所以一些全局变量有可能随时被修改。

系统调度线程的开销：

1. 内核决定哪个线程被调度
2. 被调度出去的需要保存现场环境
3. 重置调度进来的线程的现场环境

锁

锁是针对多线程编程而言。能保证线程安全。
同一个进程的线程之间共用数据段，堆，同时访问，使用的时候可能会发生冲突，所以需要加锁。加锁的时候，当其他线程想要操作加锁的对象的时候，我们让它挂起。直到这个锁被释放，线程才能处于就绪状态。
开销：

1. 线程切换的开销
2. 影响并发的进度，所以有其他办法的话尽可能不用

死锁

原因：多线程，因并发，导致了线程争用的安全问题
条件：互斥条件、不可剥脱条件、请求与保持条件、循环等待条件
说明：一个线程都保持着一个锁，但是又请求着另外一个锁住的资源。另外一个线程锁住了这个资源，同时请求原来线程锁住的资源。n个线程满足这种循环等待的条件即可形成死锁。
解决方法：

1. 请求锁的顺序要一致，并且后lock的先释放
2. 不允许在占用一个资源的时候请求另外的资源
3. 当请求资源被拒绝的时候要先释放自己占有的资源。

进程之间的通信

1. 文件通讯

2. socket通讯

3. 管道通讯
   管道：其实就是一个进程将数据写到内核中，另一个线程从内核中读取数据。

• 单向：无格式的流并且大小受限；先进先出；管道这种通信方式效率低，不适合进程间
  频繁地交换数据；
• 匿名管道：匿名管道是只能用于存在父子关系的进程间通信
• 命名管道：可以在任何的进程之间使用，因为使用命名管道的前提，需要在文件系统创
  建 个类型为 p 的设备文件，那么毫无关系的进程就可以通过这个设备文件进行通信

线程之间的通信

共享数据，全局变量，堆
需要保证线程安全，保证唯一性，有必要的话要加锁

地址、字节、内存对齐（感觉都差不多）

地址对齐

什么是地址对齐？
现代计算机中内存空间都是按照字节(byte)划分的，从理论上讲似乎对任何类型的变量的访问可以从任何地址开始，但实际情况是在访问特定变量的时候经常在特定的内存地址访问，这就需要各类型数据按照一定的规则在空间上排列，而不是顺序的一个接一个的排列，这就是对齐。

为什么要地址对齐？
对 齐的作用和原因：各个硬件平台对存储空间的处理上有很大的不同。一些平台对某些特定的类型的数据只能从某些特定的地址开始存取。其它平台可能没有这些限 制，但是最常见是的如果不按照适合其平台的要求对数据存储进行对齐，会在存取效率上带来损失。比如有些平台每次读都是从偶数地址开始，如果一个 int 型（假设是 32 位）如果存放在偶数地址开始的地方，那么一个时钟周期就可以读出。而如果是存放在一个奇数地址开始的地方，就可能会需要 2 个时钟周期，并对两次读出的结果的高低字节进行拼凑才能得到该 int 型数据。显然在读取效率上下降很多。这也是空间和时间的博弈。

对齐的实现
通常,我们写程序的时候，不需要考虑对齐的问题。编译器会替我们选择适合目标平台的对齐策略。当然，我们也可以通知给编译器传递预编译指令而改变指定数据的对齐方式。但是，正因为我们一般不需要关心这个问题，又因为编译器对数据做了对齐处理。但我们不了解的话，常常会对一些问题感到迷惑。最常见的就是结构体(struct)的 sizeof() 结果，出乎意料。为此，我们需要对对齐算法有所了解。

字节对齐

大多数计算机使用 字节（8 位的数据块）作为最小可寻址的存储器单位 ，而不是访问存
储器中单独的位。存储器的每一个字节都由唯一的数字标识，称为该字节的地址，所有可能地
址的集合称为存储器空间。
举例来说，ARM 处理器工作状态有如下两种：
l ARM 状态：执行字对齐的 32 位 ARM 指令。
l Thumb 状态：执行半字对齐的 16 位 Thumb 指令

内存对齐

有些 CPU 可以访问任意地址上的任意数据，而有些 CPU 只能在特定地址访问数据，因此不同硬件平台具有差异性，这样的代码就不具有移植性，如果在编译时，将分配的内存进行对齐，这就具有平台可以移植性了
CPU 每次寻址都是要消费时间的，并且 CPU 访问内存时，并不是逐个字节访问，而是以字长（word size）为单位访问，所以数据结构应该尽可能地在自然边界上对齐，如果访问未对齐的内存，处理器需要做两次内存访问，而对齐的内存访问仅需要一次访问，内存对齐后可以提升性能。

结构体的内存对齐规则

C 语言的对齐规则与 Go 语言一样，所以 C 语言的对齐规则对 Go 同样适用：

1. 对于结构体的各个成员，第一个成员位于偏移为 0 的位置，结构体第一个成员的偏移量(offset)为 0，以后每个成员相对于结构体首地址的 offset 都是该成员大小与有效对齐值中较小那个的整数倍，如有需要编译器会在成员之间加上填充字节。
2. 除了结构成员需要对齐，结构本身也需要对齐，结构的长度必须是编译器默认的对齐长度和成员中最长类型中最小的数据大小的倍数对齐。

虚拟机

虚拟机为了解决跨平台的问题，每个平台对应的二进制指令模板不一样。
虚拟机负责读取字节码，解释执行，调用本地CPU硬件，我们编写的代码转换成字节码，加上虚拟机，就能在任意平台运行，不同的平台只需要生成不同虚拟机的runtime就可以了。
有两种类型：

1. 解释执行字节码（机器码），例如：Java虚拟机，.net虚拟机
2. 直接解释代码，性能会差一些，例如：JS虚拟机

虚拟机设计：

1. 定义虚拟机的字节码指令模板，设计寄存器架构，偏硬件
2. 编写虚拟机的runtime程序，安装到目标平台（系统），或者随着app一起打包
3. 定义一门编程语言，设计如何用其开发代码，并有配套的开发工具，一般提供垃圾回收。
4. 制作编译工具，编译成字节码，由runtime来解释执行
5. 提供SDK，例如：直接写好的代码，如何调系统接口等。

Tips：虚拟机解释执行字节码，所以有性能问题

web浏览器是如何实现的

1. 内置JS解释器（chrome —v10）
2. 内置一个网页引擎（IE,webkit（chrome,safria））
3. 定制浏览器界面（应用功能，设置功能）

微信小游戏其实就是用web技术实现的游戏网页，微信app内置一个浏览器。

性能问题

运行解决：JIT(Just In Time)，虚拟机运行时检查代码性能，如果某段代码调用较多，运行时直接编译成机器码。

静态解决：运行之前解决，将影响性能的代码用native代码（C++）实现，然后用虚拟机调用。一般游戏引擎用C++控制OpenGL来渲染对象，再开放给脚本语言使用。也可以直接把字节码转换成native代码打包发布，但每个平台都需要打一个包。典型代表是Unity使用的IL2CPP，将.net字节码转换成C++代码再编译，从而获得更好的性能。

IOS不支持虚拟机

IOS没有Java和.net的虚拟机，不允许热更新，不允许Flash。
原因是虚拟机有成为平台的潜力，可以绕过苹果的审核，绕过苹果付费，影响苹果生态，同时也有不安全的问题。

静态链接和动态链接

静态链接和动态链接是两种不同的链接方式，用于将程序的模块（如函数、库等）与程序主体进行连接，使得程序能够正确执行和运行所需的代码和数据。

静态链接（Static Linking）：
静态链接是指在编译时将所有的程序模块和库文件的代码和数据复制到最终的可执行文件中。在静态链接的过程中，编译器将程序所依赖的静态库文件的代码和数据全部复制到可执行文件中的特定部分，使得可执行文件成为一个完全独立的实体。当程序运行时，操作系统加载整个可执行文件到内存中，并直接执行其中的代码。

静态链接的特点：
可执行文件独立性高：可执行文件包含了所有需要的代码和数据，无需依赖外部的库文件。
执行速度相对较快：由于代码和数据已经全部包含在可执行文件中，程序的执行速度较快。
文件较大：由于静态链接会将所有模块和库文件的代码和数据都复制到可执行文件中，因此可执行文件的大小较大。

动态链接（Dynamic Linking）：
动态链接是指在程序运行时，程序所依赖的库文件的代码和数据并不被复制到可执行文件中，而是在需要时由操作系统动态加载到内存中，并与程序主体进行链接。在程序编译时，只会包含对库文件的引用，而不会将库文件的实际代码和数据包含在可执行文件中。

动态链接的特点：
共享库的重用性：多个程序可以共享同一个动态链接库（Shared Library），节省了系统资源和存储空间。
可执行文件较小：由于不包含所有库文件的代码和数据，可执行文件的大小较小。
运行时灵活性：动态链接使得程序在运行时可以动态加载和卸载库文件，增加了灵活性。
运行时依赖性：程序运行时依赖于所需的库文件，如果某个库文件缺失或版本不兼容，可能会导致程序无法运行。
需要注意的是，动态链接需要操作系统提供相应的支持，并且在程序运行时需要确保所依赖的库文件能够正确地被系统找到和加载。

代码编写优化

CPU指令缓存：CPU硬件内部有指令缓存，并非每次都需要从内存取指令执行，而是一次性取多条，这样速度会快得多。

CPU指令跳转：包括if，while,for,函数调用等。每次跳转的时候可能会打乱缓存，例如调用函数的时候要放弃原来的指令，重新装载函数内部的指令。这样会影响执行效率。

优化方法：

1. 性能核心的代码要尽量避免这些跳转，尽量顺序执行。
2. 尽量把if else语句写到命中cache的部分，例如：执行if里面的代码的情况应该更多，跳转到else执行的情况应该更少。
3. for循环的时候也尽可能少写跳转与打断。

函数调用开销：

1. 指令跳转开销
2. 跳转之前，要保存栈的情况
3. 传递参数会导致参数的拷贝
4. 返回的时候要恢复栈的数据，要保存返回值

优化原则是你需要证明这个地方存在性能问题，并且代码要优雅，不能为了优化而优化。

递归调用对函数调用的开销很大，如果问题规模很深很大容易栈溢出，但是写代码的逻辑简单。

系统设计要有鲁棒性，随着问题规模的增长，你的开销是稳定的，开销的变化，到了某个规模是无法承受的，递归是一种不稳定的开销。

C#部分

程序集

程序集（Assembly）是在 .NET Framework 和 .NET Core 等微软的托管环境中使用的基本部署单元。它是一种逻辑和物理上的封装，用于组织、版本控制、部署和执行代码。

程序集包含了执行特定任务所需的所有代码（包括可执行代码、类型定义、资源、元数据等），并提供了一种将代码组织为逻辑单元的机制。在 .NET 环境中，程序集是面向对象的，可以包含一个或多个相关的类型。

程序集有两种类型：
可执行程序集（.exe）：包含一个入口点（Entry Point），可以直接运行。当你启动一个可执行程序时，操作系统会加载该程序集，并执行其中的入口点。
动态链接库（.dll）：是一个可被其他程序引用和调用的代码模块。它可以包含各种可被其他程序共享使用的类型、方法和资源。

程序集还包含元数据，其中包括有关类型、成员、引用和其他相关信息的描述。这些元数据使得程序集具有自描述的特性，使得在运行时能够进行反射和动态加载。
程序集还支持版本控制和部署。通过为程序集指定版本号，可以确保在更新程序集时，应用程序能够正确地使用所需的版本。程序集可以被部署到本地文件系统、Global Assembly Cache (GAC)、网络位置等。

抽象函数和虚函数的区别

1. 抽象方法是只有方法名称，没有方法体，即没有方法的具体实现，子类必须重写父类抽象方法才能实现具体功能；虚函数有方法名称也有方法体，但是子类可以覆盖，也可不覆盖。
2. 抽象方法是一种强制派生类覆盖的方法，否则派生类将不能被实例化。
3. 抽象方法只能在抽象类中声明，虚方法不是。

委托原理

委托是是一种引用类型，表示对具有特定参数列表和返回类型的方法的引用。委托可以把函数做为参数传递，其实际意义便是让别人代理你的事情。委托可以看做是函数的指针。例如，当任务完成的时候，任务管理器写一个委托，在调用这个委托，但是不用具体关心这个委托做了什么。别人在需要用到的时候，订阅这个委托，实现对应的方法即可。例如任务完成的时候，奖励物品，升级等，可以由不同的管理器订阅这个委托，实现对应的方法。

委托和直接调用函数的区别：用委托就可以指向任意的函数，哪怕是之前没定义的都可以，而不用受限于哪几种。

使用的时候可以用Func，delegate，Action。Func是通用委托，delegate使用繁琐一些，Action使用简单，但是只能用在没有返回值的函数上。
Unity中用法：

// 定义一个参数为Quest，返回值为void的委托
public UnityAction<Quest> onQuestStatusChange;
// 调用
if (onQuestStatusChange != null)
    onQuestStatusChange(result);

在别的程序中订阅：

void Start()
{
    QuestManager.Instance.onQuestStatusChange += this.OnQuestSelected;
}

private void OnQuestSelected(Quest q){
  // 具体逻辑
}

重载和重写的区别

1. 重载在同类中，重写在父子类中
2. 重载和重写虽然方法名一样，但是重载参数列表不同，重写相同
3. 重载是相同对象以不同参数调用，重写是不同对象以相同参数调用
4. 重载编译时多态，重写运行时多态

GC（垃圾回收）

C# 的垃圾回收器基于“代”的概念，使用了分代垃圾回收策略。具体的垃圾回收过程如下：

分代堆：堆被划分为三个代：0代、1代和2代。新创建的对象首先分配在0代中，如果经过一次垃圾回收后仍然存活，将被提升到下一代。这样，较新的对象更有可能被回收，而存活更久的对象则会逐渐晋升到更高的代中。

标记阶段：垃圾回收器从根对象（如全局变量、活动线程栈中的引用）开始，通过可达性分析算法（通常是使用标记-清除算法或标记-整理算法），遍历对象图，并标记所有可达的对象。被标记的对象将被视为存活对象。

清除阶段：在标记阶段之后，垃圾回收器会遍历堆中的所有对象，清除未被标记的对象。被清除的对象所占用的内存将被回收，并可以再次用于分配新的对象。

压缩阶段（可选）：在某些情况下，垃圾回收器可能会执行压缩操作。在压缩阶段，存活的对象将被整理，使它们在内存中连续排列，以便更好地利用内存空间。

装箱拆箱

装箱：装箱就是把值类型转换为 object 类型或由此值类型实现的任何接口类型
拆箱：就是把装箱后的引用类型转换为值类型

装箱和拆箱操作会引入一定的性能开销，因为涉及数据的复制和类型转换。

协程

协程是一种迭代器，每执行一次返回一个值，yield是语法糖，会生成实际的迭代器类。第一个yield是第一个状态，第二个yield是第二个状态。

迭代器：里面包含一个个包含返回值函数，迭代器依次执行每一个函数，把返回值存到一个Current变量中。每一次执行迭代器的MoveNext方法，就会执行一个函数，并把位置移到下一个函数。
yield：每一个yield相当于给迭代器增加一个函数，函数的内容是这一个yield到上一个yield之前的部分。

在Unity中，协程每次在LateUpdate的时候被调用。所以代码逻辑太过复杂的时候会卡住主线程。
自己实现协程：

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

class ClassWaitForTime {
    private float total;
    private float now;
    public ClassWaitForTime(float time) {
        this.total = time;
        this.now = 0;
    }

    public void Update(float dt) {
        this.now += dt;
    }

    public bool isOver() { 
        return (this.now >= this.total);
    }
}

public class Game : MonoBehaviour {

    private IEnumerator e = null;
    IEnumerator start_Coroutine() {
        Debug.Log("1111111111");
        yield return 1;

        Debug.Log("Hellword");
        yield return "abc";

        Debug.Log("我要睡5秒，别叫醒我");
        yield return new ClassWaitForTime(5);        
        Debug.Log("我醒了");

        yield break; // 终止结束了； 
    }

	// Use this for initialization
	void Start () {

        this.e = this.start_Coroutine();


#if TEST
        // step1 创建一个IEnumerator
		IEnumerator e = this.temp_Coroutine();

        // step2: 启动一个协程
        this.StartCoroutine(e);
#endif

	}


    IEnumerator temp_Coroutine() {
        for (int i = 0; i < 10; i++) {
            Debug.Log("i = " + i);
            // yield return null; // 终止协程，只到下一个帧开始;
            yield return new WaitForSeconds(2); // 终止协程，只到2秒结束以后再继续执行
        }
    }
	// Update is called once per frame
	void Update () {
        
	}

  void LateUpdate() {
      if (this.e != null) {
          if (this.e.Current is ClassWaitForTime) {
              ClassWaitForTime wt = this.e.Current as ClassWaitForTime;
              wt.Update(Time.deltaTime);
              if (!wt.isOver()) {
                  return; // 如果时间没有到，你就不要往后面执行了;
              }
          }

          if (!this.e.MoveNext()) {
              this.e = null;
          }
      }
  }
}

Unity协程应用：
自定义一个协程，只需要新增一个 class，继承自 CustomYieldInstruction 并实现 KeepWating

IEnumerator Do2(){  //Unity中每帧调用一次
  yield return new WaitForMouseButtonDown(5); //这里可以不new,找对象池要一个，优化性能
  Debug.Log("Done");   
}

public class WaitForMouseButtonDown: CustomYieldInstruction//自定义协程基类
{
  private int curr;
  private int max;
  public WaitForMouseButtonDown(int max)
  {
    this.max = max;
  }
  public override bool keepWaiting => CheckState();
  public bool CheckState(){
    if(curr >= max){
      print("达到点击次数")
    }
    else{
      if(Input.GetMouseButtonDown(0)){
        curr += 1；
        Debug.Log("点击了一次鼠标");
      }
      return true;
    }
  }
}

类和对象的内存占用

一个类被实例化后，就会开辟一块内存存放数据成员，这块空间不仅包括数据本身的大小，而且包括编译器数据对齐的消耗，对象头。而它的成员函数并不是这个时候放在内存的，而是一开始就放在代码段中，并且会记录这个函数在代码段的位置（偏移）

对象头包括两部分信息：

• 第一部分用于存储对象自身的运行时数据，如哈希码（HashCode）、GC 分代年龄、锁状态标志、线程持有的锁、偏向线程ID、偏向时间戳等。这部分数据的长度在32位和64位的虚拟机（未开启压缩指针） 中分别为32个比特（4字节）和64个比特（8字节），但8个字节只有后面4个字节会被使用
• 另外一部分是类型指针，即对象指向它的类元数据的指针，虚拟机通过这个指针来确定这个对象是哪个类的实例。
• 如果对象是一个 java 数组，那么在对象头中还有一块用于记录数组长度的数据。

实例数据部分是对象真正存储的有效信息，即我们在程序代码里面所定义的各种类型的字段内容，无论是从父类继承下来的，还是在子类中定义的字段都必须记录起来。HotSpot虚拟机默认的分配顺序为longs/doubles、ints、shorts/chars、bytes/booleans、oops（Ordinary Object Pointers，OOPs），从以上默认的分配策略中可以看到，相同宽度的字段总是被分配到一起存放，在满足这个前提条件的情况下，在父类中定义的变量会出现在子类之前。而且编译器会知道每个数据相对于对象实例地址的偏移。

对齐填充起着占位符的作用。 由于很多64位虚拟机的自动内存管理系统要求对象起始地址必须是8字节的整数倍，换句话说就是任何对象的大小都必须是8字节的整数倍。 对象头部分已经被精心设计成正好是8字节的倍数（1倍或者2倍），因此，如果对象实例数据部分没有对齐的话， 就需要通过对齐填充来补全。

反射

C#反射是一种功能强大的机制，它允许程序在运行时动态地检查类型、访问和操作类型的成员（如字段、方法、属性等），以及创建、使用和销毁对象，而无需事先知道这些类型的具体信息。

任意一个类，包括我们自己定义的类，都可以转换为这样一种描述：

1. 内存块大小，和数据成员有关
2. 类的数据成员的信息，通过数组等其他形式保存：
   {“age”,type int,偏移0个字节}
   {“sex”,type int,偏移1个字节}
   {“name”,type string,偏移8个字节}
3. 类的成员函数：
   {“func1”, type 成员函数（静态）, 代码段偏移}
   {“func2”, type 成员函数, 代码段偏移}
   {“func3”, type 成员函数, 代码段偏移}

编译的时候，每个类都会生成这样的描述实例（Type类型）来存这些信息，这些信息存入.exe文件。然后底层就可以根据这些信息构建类的实例，调用方法和成员了。
实例化的时候，底层就会根据信息分配内存块大小，然后调用构造函数（也在描述中）。
这个过程其实叫反射。

实际运用的时候，获取这样的描述实例的方式很简单，调用API即可：
Type t = System.Type.GetType(“类型的名字”)
Type t = typeof(T)
这个Type实例中包含着数据成员信息FieldsInfos，成员函数信息MethodInfos。然后我们根据这个Type实例就能通过反射创建一个对象：

instance = Activator.CreateInstance(t);

由于Type里面已经储存了数据成员的偏移，大小，所以可以从对象的内存中读取，设置成员的数据。

FieldInfo[] fields = t.GetFields();
FieldInfo ageInfo = t.GetField("age");
ageInfo.SetValue(instance, 4);   // 设置数据成员

MethodInfo m = t.GetMethod("test3");
System.Object[] funcParams = new System.Object[3];
funcParams[0] = 1;
funcParams[1] = 2;
funcParams[2] = "good";
System.Object ret = m.Invoke(instance,funcParams); // 执行对应成员函数，获取返回值

反射的价值在于用统一的方式处理任意的类型，任意新建的类都可以调用到，可以同同一种方式创建所有类的实例，而不用在底层做修改。

Unity部分

Unity底层如何处理C#

重点：.net，Mono，IL2CPP

Unity的历史里为什么会选择Mono?
Mono是微软在.net标准开放以后，开发的一个跨平台的.net项目，Unity使用Mono来开发游戏引擎，打包发布我们的游戏产品app，也具有跨平台的特性，为了这个特性而使用了Mono

为什么Unity后来选择了IL2CPP？

1. 基于.net的Mono具有版权的问题
2. Mono虚拟机解释执行.net字节码，存在一定的效率问题
3. 有些平台（IOS）不允许内置mono .net虚拟机。
4. 如果出现新的平台，mono不支持，Unity就失去了部分的跨平台能力，并且如果自己动手也不好移植，会与Mono的主干分开，维护麻烦。

IL2CPP的优势？
概念：IL指的是.net字节码，cpp指的是C++代码，这项技术可以把.net字节码转换为C++的代码（里面包含了C++没有的垃圾回收等支持），然后通过开发一个跨平台的Runtime和对应的工具一起编译来生成对应目标平台的应用程序。因此我们开发的时候还是用Mono，但是打包发布的时候使用的是IL2CPP。因为通过各个平台的C++编译器直接生成了机器码，也就是在你发包的时候已经是机器码了，所以很快。

好处：

1. 解决了跨平台可移植问题，解决了.net版权问题
2. 运行效率获得提升

为什么 Unity 中很少用多线程？多线程和协程都是非阻塞的，两者的优劣？

协程依然运行在主线程，只是逻辑上是非阻塞的而已。Unity 引擎本身是多线程的，只是 C#脚本是运行在同一个线程中的。因为游戏引擎是主循环结构，逻辑更新和画面更新时间点要求有确定性，如果逻辑更新和画面更新中引入了多线程，就需要做同步，而这加大了游戏的开发难度。

Unity 的内存分配机制

Unity 实际上可以看作是一个使用 C++开发的游戏引擎，它使用.net 的脚本虚拟机。Unity 从虚拟内存中给原生（C++）对象和虚拟机分配内存，同样，第三方插件的内存分配也都是在虚拟内存池中。原生内存（Native Memory ）是虚拟内存的一部分，它用来给所有需要的对象分配内存页面，包括 Mono 堆（Mono Heap）。如上所说，Mono 堆是出于虚拟机的需要而专门分配的本机内存的一部分。它包含了所有由 C#分配的托管的内存类型，而这些内存的托管对象就是垃圾收集器（Garbage Collector），简称 GC。

Unity 内部有几个专门的分配器，它们负责管理虚拟内存的短期和长期分配需求。所有的 Unity 资产（Assets）都是存储在原生内存中的。但这些资产会被轻量的包装成 Class，以供逻辑访问和调用。也就是说，如果我们用 C#创建了一张Texture，那么它的大部分原始数据（RawData）存在于 Native 内存中，并且会有很小的一个 Class 对象进入到虚拟机中，也就是 Mono 堆中。

死锁会因为资源抢占引起，说说 unity 有哪些资源

死锁这里的资源占用，是指一切对象
Unity 中的资源有：GameObject、Component、AudioClip、AnimationClip、AniamtionController、各种 Asset

unity 是怎么管理 resources 的

Resources 本质上就是一个默认 Assetbundle，Resources 文件夹下的文件都会打入整个 AB 包，并且在游戏启动时就加载整个 AB 包

NGUI UGUI 渲染顺序

不同的 Camera 的 Depth，值越大越后渲染
相同 Camera 下的不同 SortingLayer
相同 SortingLayer 下的不同 Z 轴/Order in Layer
Camera 模式下渲染顺序：基于同 Layer 同 OrderInLayer，因为渲染顺序优先级是：camera 的 depth>Layer>OrderInLayer>Z 轴，注意 UI 的渲染顺序最后是
OrderInLayer>transform 的层级

如何用 NavMesh 动态寻路

（1）烘焙导航网格
（2）需要导航的物体添加 NavMeshAgent 组件
（3）运行时候使用 NavMeshAgent.SetDestination 函数进行导航

profiler与stats

Stats

点开Unity Game窗口中的stats可以看到游戏运行时的参数：
重要参数：
Graphics：
CPU：主逻辑消耗时间
render thread：渲染消耗时间
Batches：场景中的物体分几批绘制，每次绘制需要一个drawCall
Saved by batching：被合批到一起的总物体数，由显卡决定，显卡越好，能够一次性合批在一起的物体数越多。
Tris：总绘制的面数
Verts：总绘制的顶点数
Screen：屏幕分辨率，占用内存
SetPass Call：配置渲染管道的shader等参数的次数，非常消耗性能。
Shadow Casters：阴影开销，打开阴影会增大batches，main，render thread。
Visable Skinned Meshes：人物的蒙皮网格数量。
Animation：动画数量。

Profiler

打开方式：Ctrl+7
点击CPU Usage:
上面是一副曲线图，绘制了每个时刻代码，物理引擎，渲染等消耗

下面的表格从高到低列举了调用某个函数的耗时，Total指整个函数的耗时百分比，而Self指的是除了调用其他函数的部分的耗时百分比，Calls指的是每一帧调用这个函数的次数，函数举例：
WaitForTarget：CPU休眠的时间
Camera Render：渲染时间
OverHead：不明确的时间消耗。
Behaviour Update：Update函数的时间消耗
GUI Paint：OnGUI函数的时间消耗

点击Rendering，下面会显示对应的渲染参数：
上面会显示三种合批方式，参数如下：
Batched Draw Calls：合批的个数
Batches：分为多少批

点击Memory显示的是内存相关信息

动态批，静态批，GPU Instancing合批

静态批：游戏引擎会将能够合批的(同一个材质球)标记为静态的物体合批到一起，提交给GPU。游戏引擎会预先合并静态物体的网络，提交给GPU。因为静态批会增加合并后的内存开销，有的情况我们必须关闭静态批，例如渲染1000颗树，如果合批，网格会导致内存暴涨。静态批通过预处理阶段合并顶点数据，并生成新的合并后的网格。在Project Setting中开启。

动态批：CPU计算能合批频繁变化物体（材质相同）的网格，然后提交给GPU绘制，相当于给动态合批的物体重新建模。动态批会消耗CPU性能。动态合批是引擎自动处理的，引擎会有一个顶点数量的限制。动态批需要在运行时动态合并，并在每帧或每次渲染前进行数据传输。在Project Setting中开启。

GPU Instancing合批：允许多个相同的渲染对象在GPU上以单个渲染调用的形式进行渲染。提交一个物体，GPU能绘制N个实例到不同的位置。每一批能够绘制的数目和GPU性能相关。可以在Shader中开启。

Unity是如何绘制3D物体

每一个模型都由无数个面构成，每一个面都是三角形，每一个形状的面都能分成若干个三角形，而三角形由三个顶点构成。

1. 顶点初始化，CPU把模型的顶点数据（位置，法线，纹理坐标…）放到GPU
2. 顶点shader做坐标变换，把模型数据变换到世界坐标，再变换到以摄像机为基准的坐标系。
3. 从摄像机的角度绘制画面，相当于在摄像机的位置摆放一个手电筒，然后在物体背后的一面墙上成像。墙到摄像机的距离固定，我们需要通过物体的三维坐标计算二维的投影点，这是一个数学问题。
4. 在把模型的三角形面投影到2D之后，再把三个顶点的颜色做插值，然后给三角形内部按照这个插值上色填充。

我们可以编写代码进行干预的是顶点shader和片源着色shader。

MeshRenderer/SkinnedMeshRenderer绘制3D物体流程

1. MenshRenderer会找到MeshFilter组件，把顶点数据装载的内存
2. MenshRenderer装载配置好shader，材质，渲染管道。
3. MenshRenderer绘制的时候需要将内存的顶点数据放到显存
4. MenshRenderer提交变化矩阵相关数据，材质中的数据给shader

动画组件就是根据动画文件来改变模型的顶点，从而改变模型的形状。

SetPass Call是配置渲染管道的shader等参数的次数，非常消耗性能。跟shader数目有关，也跟分批绘制情况有关，我们需要把同一个shader绘制的物体给分到同一批绘制，从而减小SetPass Call。

千人战场性能优化

1. 阴影关掉
2. 选择modile里面性能比较好的shader
3. 把SkinnedMeshRenderer转换成MeshRenderer，需要用到 AnimMapBaker插件，连动画组件都能优化掉，使用shader来实现动画的效果。这个工具只支持Animation动画。原理是通过离线采用，将每一帧的顶点位置存到贴图中。通过shader播放出来。
4. 开启instancing合批，限制比较宽松，但不支持SkinnedMeshRenderer，每个shader都有，勾选上就行。同一个shader，同一个网格，参数可以不一样，就能合批。根据GPU的性能来决定分批的数量（因为GPU每一次绘制的三角形数目有上限）

Tips：有两个DrawCall是系统自带的，代表天空盒和清理屏幕。其他的才是我们的物体决定。

DrawCall优化

概念：游戏场景的物体，CPU分几批提交给GPU绘制，就有几个DrawCall，Unity Game窗口中Stats下的Batches属性就是DrawCall的数量。默认有背景和天空盒两个DrawCall。
分析：隐藏节点，观察DrawCall的变化。

UGUI的DrawCall

UGUI影响两个物体合批的条件：

1. 模型是否相同（矩形）
2. shader是否相同（UI/Default）
3. 纹理参数是否相同（Image）
   一般1，2点容易满足，主要在第三点。
   解决方法：
   把小图片资源做成一张图集（整图）。
4. 点击Edit->Project Settings->Editor-Sprite Packer，里面的Mode调节为Always Enabled。
5. 新建一个图集的名字tag（在图片属性里面设置Packing Tag），把需要打包的图片放到一个文件夹下，以文件夹的名字作为图集名字
6. Window->Sprite Packer，点击Pack，就能看到图集，图集在Library文件夹中的AtlasCache中。

UGUI合批之后，合批的数量不会统计在Saved by batching内。

Text对DrawCall的影响

1. 和图片不同，Text的纹理图集是不一样的。但是，在运行的时候会根据文字的内容生成文字图集，所以看起来文字很多且不同，但实际上都在一个图集里面。
2. Unity在不影响层级关系的情况下，合并text的DrawCall（即使文字打乱了图片的DrawCall）。但是有的时候按照场景树来说，我们设定的文字打乱drawCall，并且影响了层级关系，Unity就不能帮我们合并drawCall。
3. 如果字体库不一样，DrawCall也会增加。

Image和RawImage

Image优点：简单，并且可以合并DrawCall，但不能修改UV。UV参数可以调节图片显示的部分。
RawImage优点，可以修改纹理贴图的UV，但是即使图片在一个图集也不能合并DrawCall。

OnGUI对DrawCall的影响

OnGUI每绘制一个文本或图片，DrawCall都会增加1（同一个图集不能合批），且非常消耗性能。

Mask和RectMask2D

区别1:Mask主要处理不规则图形遮罩效果，RectMask2D只能做矩形遮罩.
区别2:Mask需要一个Image来当作遮罩区域,子节点在Image渲染区域才会显示，RectMask2D以自身RectTransform为裁剪区域,子节点在RectTransform区域内显示
区别3：性能优势，Mask导致的2个drawcall, 而RectMask2D只会在显示图片上有一个drawcall，本身不会有drawcall。
Tips：渲染层级、材质相同，纹理相同的才能合批，如果两个UI重叠，那么不属于一个层级

mask底层

通过渲染器（Renderer）和模板缓冲区（Stencil Buffer）实现
gpu为每个像素点分配一个称之为stencil buffer的1字节大小的内存区域，这个区域可以用于保存或丢弃像素的目的。

当一个UI元素包含了Mask组件时，它会在渲染时将自己的遮罩范围绘制到模板缓冲区中，同时禁用裁剪。遮罩范围使用模板缓冲区中的特定值来表示，可以看作是一个临时的遮罩层。在绘制其他UI元素时，会检查模板缓冲区的值。如果当前像素位于遮罩范围内，就继续渲染；否则，将该像素裁剪掉。在完成遮罩元素的渲染后，还原裁剪状态，以便正常渲染后续的UI元素。

纹理

压缩格式

纹理尺寸

约束：单个散图超过 512像素，不打图集，图集最大2048像素的尺寸
打图集的约束
注意合理划分纹理尺寸的大小比如说: 能用 512*512尺寸的搞定的，就不要使用 1024 * 1024，处理不当内存翻4倍

Read/Write逐像素可修改的参数

图集有什么用

1. 减少渲染批次：在游戏或应用程序中，渲染大量单独的图片会增加渲染调用的次数，从而影响性能。通过将多个图片打包到一个图集中，可以减少渲染批次，因为可以同时渲染图集中的多个图片，从而提高渲染效率。
2. 减小内存开销：单独的图片文件需要存储文件头、元数据等信息，而每个图集只需要存储一份这些信息，可以大大减小内存开销。此外，图集还可以通过使用图片压缩算法来减小存储空间。
3. 提高纹理显存利用率：图集中的图片在显存中是连续存储的，这样可以提高纹理显存的利用率。相比于单独的图片，图集可以更高效地利用显存，并减少显存碎片化。
4. 方便管理和使用：使用图集可以更方便地管理和使用游戏或应用程序中的图片资源。在游戏开发中，可以使用图集编辑器工具将多个相关的图片打包成一个图集，并为每个图片指定在图集中的位置信息（如纹理坐标），便于在游戏中使用。
5. 支持动画和精灵表：图集常用于创建动画和精灵表。通过在一个图集中按顺序排列不同帧的图片，可以实现动画效果。而精灵表是一个包含游戏中各种角色、道具、UI元素等的图集，通过切换显示不同的图集区域来实现不同元素的渲染。

描述游戏动画有几种，以及其原理

主要有关节动画、单一网格模型动画(关键帧动画)、骨骼动画。
关节动画把角色分成若干独立部分，一个部分对应一个网格模型，部分的动画连接成一个整
体的动画，角色比较灵活 Quake2 中使用了这种动画。
单一网络模型动画由一个完整的网格模型构成， 在动画序列的关键帧里记录各个顶点的原位
置及其改变量，然后插值运算实现动画效果，角色动画较真实。
骨骼动画，广泛应用的动画方式，集成了以上两个方式的优点，骨骼按角色特点组成一定的
层次结构，由关节相连，可做相对运动，皮肤作为单一网格蒙在骨骼之外，决定角色的外观。
皮肤网格每一个顶点都会受到骨骼的影响，从而实现完美的动画。（骨骼动画是由关节动画
发展而来的，如今基本都使用骨骼动画来实现角色动画）

性能优化

这部分内容可以参考：MMORPG-Part4，特别是资源优化部分
这一部分的知识点，在Unity、操作系统与编译原理章节有所涉及，这里会做更系统的描述：
性能优化，主要聚焦在 内存、 CPU、GPU 三大方向上。 粗略划分：
（1）内存：资源内存占用、引擎模块自身内存占用、托管堆内存占用等
（2）CPU：引擎模块性能开销、自身代码开销
（3）GPU: OverDraw、显存带宽等 优化方案

资源优化

性能优化方向：内存占用、大小容量、运行效率

资源优化是首要优化任务

资源精细程度适可而止，不要占用太大空间，满载需求即可。
基础类型：模型、动作、纹理、声音、字体
综合资源类型：场景（地形、光影）、UI(图集)、粒子系统
其中基础资源前三个是优化重点
方法：
制作前要指定合理规范：例如规定模型最大面数、UV、LOD，规定贴图最大尺寸和格式，动作时长帧率。其中一些基本规范为美术风格（写实、卡通、像素），视角（2D、3D、2.5D、固定、自由），场景（无缝大地图、超大规模）、玩法。使用九宫格、图集等。
使用规范：模型导入优化（模型压缩、网格优化、可读写、Lightmap UV、动作导入）、动作导入优化（动画压缩、Rig-优化游戏对象）、纹理导入优化（纹理格式、POT、可读写、Mipmap、纹理大小、压缩选项）、场景优化（资源组织、引用和依赖、资源复用）、多平台优化（Standalone、IOS、Android）
优化流程自动化：使用代码进行检查

模型资源

检查参数
Model选项卡中：
MeshCompression：网格压缩，减少模型精度来降低大小，启动压缩后每个模型看看有没有问题，没有问题可以打开
Read/Write Enable：可以读写，如果代码没有对模型进行读写可以关闭。
Optimze Mesh：优化网格
Rig选项卡：
Optimize Game Objects：可以优化模型中的子物体数量，可以变成一个，大大减小遍历时间。
Animation选项卡：
Import Animation：不带动画不要选，否则产生冗余消耗。
Anim Compression：动画压缩，可能会使动画出现问题，出现问题就关掉

纹理资源

导入前图片格式要对：Png、TGA等，否则不支持转换成UI资源，导致没有办法压缩。
Max Size：设置图片最大尺寸
Compression：可以压缩图片，一般选High Quality
Compressor Quality：如果没问题就往小的调
Generate MipMaps：没有特殊情况保持打开，这样在距离较远时图片的像素会变小
注意：NPOT和POT的占用大小完全不同

代码处理

Unity有一个AssetPostprocessor类，可以继承它进行处理，具体查资料。

using UnityEngine;
using UnityEditor;
using System.IO;

namespace PostProcessor{
    public class UTexturePreprecessor: AssetPostprocessor{
        public static bool IsHD = false;

        void OnPreprocessTexture(){
            TextureImporter textureImporter = (TextureImporter0)assetImporter;
            texureImporter.isReadable = false;
            if(assetPath.StartsWith("Assets/UI")){
                textureImporter.mipmapEnabled = false;
                textureImporter.textureType = TextureImporterType.Sprite;
            }
            else if(assetPath.StartWith("Assets/Units")){
                textureImporter.textureFormat = TextureImporterFormat.AutomaticCompressed;

            }
            else if(assetPath.StartsWith("Assets/FX/Textures")){
                if(textureImporter.textureFormat == TextureImporterFormat.AutomaticTruecolor
                || textureImporter.textureFormat = TextureImporterFormat.Automatic16bit
                || textureImporter.textureFormat = TextureImporterFormat.ARGB16
                || textureImporter.textureFormat = TextureImporterFormat.RGB24
                || textureImporter.textureFormat = TextureImporterFormat.RGBA32
                || textureImporter.textureFormat = TextureImporterFormat.ARGB32
                || textureImporter.textureFormat = TextureImporterFormat.RGB16
                || textureImporter.textureFormat = TextureImporterFormat.RGBA16){
                    textureImporter.textureFormat = TextureImporterFormat.AutomaticCompressed;
                }
            }
        
        }
    }
}

只有这个脚本在项目中（例如Editor文件夹中），这样导入的时候，就会自动执行，不用手动改了。

内存优化

在 Unity 中， 前置堆内存分配，尽量降低碎片化；查验内存泄露；资源预处理；字符串拼接、配置表优化、对象池等等

内存的开销无外乎以下三大部分：
1.资源内存占用；2.引擎模块自身内存占用；3.托管堆内存占用。

对于目前绝大多数基于 Unity 引擎开发的项目而言，其托管堆内存是由Mono 分配和管理的。“托管” 的本意是 Mono 可以自动地改变堆的大小来适应你所需要的内存，并且适时地调用垃圾回收（Garbage Collection）操作来释放已经不需要的内存，从而降低开发人员在代码内存管理方面的门槛。但是这并不意味着研发团队可以在代码中肆无忌惮地开辟托管堆内存，因为目前 Unity 所使用的 Mono 版本存在一个很严重的问题，即：Mono 的堆内存一旦分配，就不会返还给系统。这意味着 Mono 的堆内存是只升不降的。

同时我们要对自身 Log 的输出进行严格的控制。

CPU优化

在 Unity 中，采用 静态批处理、动态批处理、遮挡剔除、远近剔除、AOI、合理划分图集、动态图集、美术模型顶点控制、特效面数控制、GPU Instanceing、UGUI 使用的注意事项等等，来控制DrawCall; 业务代码执行效率优化等等。

目前的 Unity 移动游戏而言，CPU 方面的性能开销主要可归结为两大类：引擎模块性能开销和自身代码性能开销。其中，引擎模块中又可细致划分为渲染模块、动画模块、物理模块、UI 模块、粒子系统、加载模块和 GC 调用等等。

GPU优化

OverDraw是指在渲染过程中重复绘制相同像素的现象。它会导致 GPU 不必要地进行多余的工作，消耗额外的性能资源，降低游戏的帧率和性能表现。

GPU 与 CPU 不同，所以侧重点自然也不一样。GPU 的瓶颈主要存在在如下的方面：
（1） 填充率，可以简单的理解为图形处理单元每秒渲染的像素数量。
（2） 像素的复杂度，比如动态阴影，光照，复杂的 shader 等等
（3） 几何体的复杂度（顶点数量）
（4） 当然还有 GPU 的显存带宽
那么针对以上 4 点，其实仔细分析我们就可以发现，影响的 GPU 性能的无非就是 2 大方面，一方面是顶点数量过多，像素计算过于复杂。另一方面就是GPU 的显存带宽。那么针锋相对的两方面举措也就十分明显了。
（1） 减少顶点数量，简化计算复杂度。
（2） 压缩图片，以适应显存带宽。

MipMap

Mipmap 中每一个层级的小图都是主图的一个特定比例的缩小细节的复制品。因为存了主图和它的那些缩小的复制品，所以内存占用会比之前大。但是因为可以根据实际情况，选择适合的小图来渲染。所以，虽然会消耗一些内存，但是优化了显存带宽，为了图片渲染的质量（比压缩要好），这种方式也是推荐的。

网络

TCP

参考：https://zhuanlan.zhihu.com/p/86426969

三次握手

三次握手（Three-way Handshake）其实就是指建立一个TCP连接时，需要客户端和服务器总共发送3个包。进行三次握手的主要作用就是为了确认双方的接收能力和发送能力是否正常、指定自己的初始化序列号为后面的可靠性传送做准备。实质上其实就是连接服务器指定端口，建立TCP连接，并同步连接双方的序列号和确认号，交换TCP窗口大小信息。
刚开始客户端处于 Closed 的状态，服务端处于 Listen 状态。

进行三次握手：

第一次握手（SYN）：客户端向服务器发送一个同步（SYN=1）报文，表示客户端请求建立连接。该报文中包含客户端的初始序列号ISN=x，用于后续数据传输的顺序标识。客户端处于 SYN_SEND 状态。

第二次握手（SYN + ACK）：服务器接收到客户端的请求后，会回复一个同步(SYN=1)-确认（SYN-ACK）报文。该报文中包含服务器的初始序列号(seq=y)和确认号（ACK=ISN+1），确认客户端的请求，并为后续数据传输做好准备。此时服务器处于 SYN_REVD 的状态。

第三次握手（ACK）：客户端收到服务器的回复后，会发送一个确认（ACK=y+1）报文，表示接收到服务器的确认。服务器收到客户端的确认后，建立连接，双方可以开始进行数据传输。此时客户端处于 ESTABLISHED 状态。服务器收到 ACK 报文之后，也处于 ESTABLISHED 状态，此时，双方已建立起了连接。ACK报文段可以携带数据，不携带数据则不消耗序号。

发送第一个SYN的一端将执行主动打开（active open），接收这个SYN并发回下一个SYN的另一端执行被动打开（passive open）。

在socket编程中，客户端执行connect()时，将触发三次握手。

为什么需要三次握手，两次不行吗

第一次握手：保证客户端的发送能力、服务端的接收能力是正常的。
第二次握手：保证服务端的发送能力、客户端的接收能力是正常的。但是服务端不知道客户端的接收能力是否正常。
如果只有两次握手，将会出现下面情况：
客户端发出连接请求，但因连接请求报文丢失而未收到确认，于是客户端再重传一次连接请求。后来收到了确认，建立了连接。数据传输完毕后，就释放了连接，客户端共发出了两个连接请求报文段，其中第一个丢失，第二个到达了服务端，但是第一个丢失的报文段只是在某些网络结点长时间滞留了，延误到连接释放以后的某个时间才到达服务端，此时服务端误认为客户端又发出一次新的连接请求，于是就向客户端发出确认报文段，同意建立连接，不采用三次握手，只要服务端发出确认，就建立新的连接了，此时客户端忽略服务端发来的确认，也不发送数据，则服务端一致等待客户端发送数据，浪费资源。
因此意义如下：

1. 防止已失效的连接请求被误认为是新的连接：如果只有两次握手，客户端发送连接请求后，可能由于网络延迟或其他原因导致该请求长时间滞留在网络中，然后在一段时间后到达服务器。此时，服务器可能已经清除了之前的连接状态，无法正确识别该连接请求的有效性。通过增加第三次握手，客户端在收到服务器的确认后，可以确保之前的请求已经成功到达服务器，并避免了这种混淆。
2. 防止服务器资源浪费：在两次握手的情况下，客户端发送的连接请求可能因为某种原因未能到达服务器，但服务器仍然为该连接分配了相应的资源。如果服务器长时间等待客户端的确认，这些资源将被浪费。通过增加第三次握手，服务器在收到客户端的确认后，可以确信客户端已经成功接收到了服务器的连接请求，避免了资源的浪费。
3. 确保双方都愿意建立连接：三次握手中的第三次握手是客户端向服务器发送确认报文，表示客户端愿意正式建立连接。这样可以确保双方都同意建立连接，避免了无意义的连接建立。

四次挥手

建立一个连接需要三次握手，而终止一个连接要经过四次挥手（也有将四次挥手叫做四次握手的）。这由TCP的半关闭（half-close）造成的。所谓的半关闭，其实就是TCP提供了连接的一端在结束它的发送后还能接收来自另一端数据的能力。
刚开始双方都处于 ESTABLISHED 状态，假如是客户端先发起关闭请求。四次挥手的过程如下：

1. 客户端发送一个FIN报文（FIN=1,seq=u），用于关闭它的发送能力，进入FIN_WAIT_1状态。
2. 服务器收到FIN报文后，发送一个ACK报文(ack=u+1,seq=v)作为应答，确认收到FIN，并进入CLOSE_WAIT状态。
3. 服务器发送完剩下的数据，然后发送一个FIN报文（FIN=1,ack=u+1,seq=w），用于关闭它的发送能力，进入LAST_ACK状态。
4. 客户端收到FIN报文后，发送一个ACK报文（ack=w+1）作为应答，进入TIME_WAIT状态。这个状态会持续2MSL（Maximum Segment Lifetime，最大报文生存时间）时间，等待可能出现的延迟报文。需要过一阵子以确保服务端收到自己的 ACK 报文之后才会进入 CLOSED 状态，服务端收到 ACK 报文之后，就处于关闭连接了，处于 CLOSED 状态。

在socket编程中，任何一方执行close()操作即可产生挥手操作。

为什么挥手需要四次

当服务端收到FIN报文时，很可能并不会立即关闭SOCKET，所以只能先回复一个ACK报文，告诉客户端，“你发的FIN报文我收到了”。只有等到我服务端所有的报文都发送完了，我才能发送FIN报文，因此不能一起发送。故需要四次挥手。

TCP为什么稳定

它提供了 乱序重排、应答确认、报文重传和流量控制 四种机制。乱序重排、应答确认都跟序号有关。由于网络或“多线程”等因素，接收方收到的数据段很可能是乱序的，不过，因为每个 TCP 封装都有序号，接收方重组起来非常容易。
TCP 的报文重传有两种独立的办法。 一种是超时重传，发送方收不到确认的时候用。我们都知道网速 并不是稳定的，传输时的每个报文的延时也不一样。TCP 会根据报文 的往返时间（RTT）自动调整超时重传时间（RTO）。发送方每发一 个报文段都会开始计时，如果时间超过 RTO 还没收到这个报文段的确 认，就重传该报文段。另一种方法是快速重传，发送的数据在路上丢失的时候用。接收方收到序号 1后，回复确认号 2，希望下次收到序号 2 的报文 段，但却乱序收到比序号 2 大的 3、4、5 报文段，于是连续发出确认 号为 2 的报文段。如果发送方连续三次收到重复的确认号，立即重发 该报文段，而不管是否超时。
window 还有一个很重要的作用，那就是 流量控制。 首先要明白一点，应用程序不论发送还是接收数据，都会先把数据放入缓冲区，再从缓冲区中发出或读取数据。 这个缓冲区大小，反映了应用程序一次能处理数据的能力。如果接收方应用程序处理速度比发送方的发送速度慢，就会造成接收方缓冲区“溢出”。实际上，发送方发送速度和接收方处理速度很难一致。 这就需要 window 来调整了。 TCP 在三次握手建立连接时，会协商双方缓冲区 window 大小。如果因 为接收方处理速度较慢，接收方会通过 window 告知发送方，实现动态调整，避免“溢出”。发送方会根据接收方确认报文中的 window 值来调整每次发出多少报文，这叫“滑动窗口”。

TCP/IP五层及其作用

计算机网络模型有七层：物理层，数据链路层，网络层，传输层，回话层，表示层，应用层。但这里简化为五层。
（1）物理层：负责光电信号传递方式。集线器工作在物理层。以太网协议。
（2）数据链路层：负责设备之间的数据帧的传输和识别。交换机工作在数据链路层。例如网卡设备的驱动，帧同步，冲突检测，数据差错校验等工作。
（3）网络层：负责地址管理和路由选择。路由器工作在网络层。
（4）传输层：负责两台主机之间的数据传输。
（5）应用层：负责应用程序之间的沟通。网络编程主要针对的就是应用层。

为什么要有 TIME_WAIT 这个状态

1. 可靠终止 TCP 连接。如果最后一个 ACK 报文因为网络原因被丢弃，此时 server 因为没有收到 ACK 而超时重传 FIN 报文，处于 TIME_WAIT状态的 client 可以继续对 FIN 报文做回复，向 server 发送 ACK 报文。
2. 保证让迟来的 TCP 报文段有足够的时间被识别和丢弃。连接结束了， 网络中的延迟报文也应该被丢弃掉，以免影响立刻建立的新连接。

TCP的流量控制

TCP的流量控制是通过滑动窗口机制实现的，主要目的是确保发送方和接收方之间的数据传输速率匹配，防止发送方发送速度过快导致接收方无法及时处理或数据丢失。
具体来说，TCP的流量控制包括以下要点：

1. 滑动窗口大小：每个TCP连接都有一个滑动窗口，表示接收方当前可接收的字节范围。发送方根据接收方的窗口大小来确定发送数据的数量。

2. 接收方通告窗口大小：接收方通过TCP报文段中的窗口字段通告发送方自己的窗口大小。发送方根据接收方通告的窗口大小来调整发送数据的数量。

3. 滑动窗口的滑动：随着接收方处理已接收数据，窗口向前滑动，为新的数据腾出空间。

4. 停止-等待流量控制：当发送方发送的数据超过接收方的窗口大小时，接收方会将窗口设置为0，停止接收数据，发送方必须等待接收方通告新的窗口大小后才能继续发送数据。

5. 慢启动和拥塞避免：TCP的拥塞控制机制与流量控制密切相关。拥塞控制通过动态调整拥塞窗口大小来控制发送速率，避免网络拥塞。慢启动阶段发送方逐渐增加拥塞窗口的大小，拥塞避免阶段则以一种更渐进的方式增加窗口大小。

总的来说，TCP的流量控制机制通过接收方通告窗口大小，发送方根据窗口大小调整发送数据的数量，确保发送速率与接收方的处理能力相匹配。这样可以避免数据的丢失和网络拥塞，保证可靠的数据传输。

TCP的拥塞控制

TCP的拥塞控制是一种机制，用于避免过多的数据流量拥塞网络，导致网络性能下降或数据丢失。它是为了保持网络的稳定性和公平性而设计的。
TCP的拥塞控制主要包括以下几个方面：

1. 慢启动（Slow Start）：在连接刚建立时，发送方先以较小的拥塞窗口开始发送数据，然后每经过一个往返时间（RTT），窗口大小就会加倍，以此逐渐增加发送速率。

2. 拥塞避免（Congestion Avoidance）：一旦拥塞窗口达到一个阈值（拥塞窗口大小的一半），发送方将以一种线性增加的方式增加拥塞窗口的大小，以更稳定的速率发送数据。

3. 快速重传（Fast Retransmit）：当接收方发现某个报文段丢失时，它会立即发送重复确认（duplicate ACK）给发送方。当发送方连续收到多个重复的ACK时，它会认为有一个报文段丢失，而不是等待超时后再进行重传，从而快速恢复丢失的数据。

4. 快速恢复（Fast Recovery）：在快速重传的基础上，发送方将拥塞窗口减半，并进入快速恢复状态。在快速恢复状态下，发送方继续以较小的速率发送数据，直到再次达到拥塞窗口的阈值。

通过这些机制，TCP可以根据网络的拥塞程度来动态调整发送速率，以避免网络拥塞的发生并保持网络的稳定性。拥塞控制使得TCP在不同网络条件下都能提供可靠的数据传输，并且在网络出现拥塞时能够自适应地减少发送速率，从而减轻网络的负载。

断线重连逻辑

当检测到客户端断线时，断开当前客户端 Socket；重新根据 IP 和端口号重建新的 Socket。当连接上服务器网关后，携带 token，向服务器发送断线重连协议。

TCP/UDP 的区别，用在什么场景

1. 基于连接 vs 无连接
   a. TCP 是面向连接的协议
   b. UDP 是无连接的协议。UDP 更加适合消息的多播发布，从单个点向多个点传输消息
2. 可靠性
   a. TCP 提供交付保证，传输过程中丢失，将会重发
   b. UDP 是不可靠的，不提供任何交付保证（网游和视频丢包情况）
3. 有序性
   a. TCP 保证了消息的有序性，即使到达客户端顺序不同，TCP 也会排序
   b. UDP 不提供有序性保证
4. 数据边界
   a. TCP 不保存数据边界。虽然 TCP 也将在收集所有字节之后生成一个完整的消息，但是这些信息在传给传输给接受端之前将储存在 TCP 缓冲区，以确保更好的使用网络带宽。
   b. UDP 保证。在 UDP 中，数据包单独发送的，只有当他们到达时，才会再次集成。包有明确的界限来哪些包已经收到，这意味着在消息发送后，在接收器接口将会有一个读操作，来生成一个完整的消息。
5. 速度
   a. TCP 速度慢
   b. UDP 速度快。应用在在线视频媒体，电视广播和多人在线游戏
6. 发送消耗
   a. TCP 是重量级
   b. UDP 是轻量级。因为 UDP 传输的信息中不承担任何间接创造连接，保证交货或秩序的的信息。这也反应在包头大小。
7. 报头大小
   a. TCP 头大。一个 TCP 数据包报头的大小是 20 字节。TCP 报头中包含序列号，ACK 号，数据偏移量，保留，控制位，窗口，紧急指针，可选项，填充项，校验位，源端口和目的端口。
   b. UDP 头小。UDP 数据报报头是 8 个字节。而 UDP 报头只包含长度，源端口号，目的端口，和校验码。
8. 流量控制
   a. TCP 有流量控制。主要目的是确保发送方和接收方之间的数据传输速率匹配，防止发送方发送速度过快导致接收方无法及时处理或数据丢失。
   b. UDP 不能进行流量控制

TCP用于状态同步，例如 MMORPG，使用 TCP 状态同步
UDP用于帧同步，例如MOBA游戏，使用 UDP 帧同步

数据链路层和传输层有什么区别

数据链路层和传输层的主要区别是：他们的功能和作用不一样。 数据链路层负责建立和管理节点间的链路。主要功能是通过各种控制协议，将有差错的物理信道变为无差错的、能可靠传输数据帧的数据链路。传输层是通信子网和资源子网的接口和桥梁。主要任务是：向用户提供可靠的端到端的差错和流量控制，保证报文的正确传输。 另外传输层的环境比数据链路层的环境要复杂得多。这是由于传输层的环境是两个主机以整个子网为通信信道进行通信，并且传输的数据是报文。而数据链路层的环境是两个分组交换结点直接通过一条物理信道进行通信。传输的数据是信息帧。

http原理

参考：https://zhuanlan.zhihu.com/p/24913080
HTTP，全称为 HyperText Transfer Protocol，即为超文本传输协议。是互联网应用最为广泛的一种网络协议，所有的 www 文件都必须遵守这个标准。HTTP 一般构建于 TCP/IP 协议之上，默认端口号是 80
HTTP 定义了在与服务器交互的不同方式，最常用的方法有 4 种，分别是 GET，POST，PUT， DELETE。URL 全称为资源描述符，可以这么认为：一个 URL 地址，对应着一个网络上的资源，而 HTTP 中的 GET，POST，PUT，DELETE 就对应着对这个资源的查询，修改，增添，删除4个操作。
特点：

1. 无连接性：每个HTTP请求都是独立的，服务器不会保留客户端的状态信息，每次请求都需要重新建立连接。
2. 无状态性：HTTP协议本身不会对请求和响应之间的状态进行保持，每个请求都是独立的，服务器不会记住之前的请求信息。
3. 基于请求-响应模型：客户端发送一个HTTP请求到服务器，服务器接收并处理请求后，返回一个HTTP响应给客户端。
4. 简单可读的文本协议：HTTP协议使用文本格式进行数据交换，易于理解和调试。
5. 支持多媒体内容：HTTP协议可以传输各种类型的数据，包括文本、图像、音频、视频等。

https 为什么安全？https 传输过程是怎样的？为什么需要证书？使用https 会被抓包么

为什么安全？
因为 HTTPS 保证了传输安全，防止传输过程被监听、防止数据被窃取，可以确认网站的真实性。
传输过程
客户端发起 HTTPS 请求，服务端返回证书，客户端对证书进行验证，验证通过后本地生成用于改造对称加密算法的随机数，通过证书中的公钥对随机数进行加密传输到服务端，服务端接收后通过私钥解密得到随机数，之后的数据交互通过对称加密算法进行加解密。

为什么需要证书？
防止”中间人“攻击，同时可以为网站提供身份证明。
会被抓包么？
会被抓包，HTTPS 只防止用户在不知情的情况下通信被监听，如果用户主动授信，是可以构建“中间人”网络，代理软件可以对传输内容进行解密。

端口号划分

0-1023：知名端口号，HTTP,FTP,SSH 这些广为使用的应用层协议，他们的端口号都是固定的：
HTTP:80
HTTPS：443
SSH：22
FTP:21
Telent：23

1024-65535：操作系统动态分配的端口号，客户端程序的端口号，就是由操作系统从这个范围分配的。

如何判断当前机器是大端还是小端

大端（存储）模式，是指数据的低位保存在内存的高地址中，而数据的高位保存在内存的低地址中。
小端（存储）模式，是指数据的低位保存在内存的低地址中，而数据的高位保存在内存的高地址中。

int i = 1;
byte[] buf = BitConverter.GetBytes(i);

if(buf[0] == 1){
  Console.WriteLine("小端");
}
else{
  Console.WriteLine("大端");
}

详细讲讲在服务器计算和在客户端计算的优缺点

服务器计算

1. 可靠性和安全性：服务端拥有更大的计算资源和更强的安全控制能力，可以进行复杂的计算和数据处理，确保数据的准确性和安全性。
2. 数据集中管理：服务端负责整个系统的核心业务逻辑和数据管理，可以实现数据的集中存储和管理，提高数据一致性和可靠性。
3. 减轻客户端负担：服务端进行计算和处理，可以减轻客户端的计算负担和网络传输压力，提升客户端的响应速度和用户体验。

缺点：

1. 延迟：客户端需要等待服务端的计算结果返回，可能会增加请求的响应时间和延迟。
2. 服务器压力：服务端需要处理大量的客户端请求，需要具备足够的计算资源和扩展能力来应对高并发情况。

客户端计算
优势释放服务器端压力，将计算量移到了客户端。并提高了用户的响应速度和实时性。
劣势是数据不可靠，可能会导致外挂。多个客户端进行独立计算可能导致数据的一致性问题，需要额外的同步和数据校验机制来保证数据的一致性。

网络同步中可以进行哪些优化

表现优化、延迟对抗、丢包对抗、带宽优化以及帧率优化

表现优化

（1） 差值优化
内插值的目的是解决客户端离散信息更新导致的突变问题，外插值的目的是解决网络延迟过大或者抖动导致间歇性收不到数据而卡顿的问题，两种方案并不冲突，可以同时采用。在具体应用时，我们可以使逻辑帧与渲染帧分离，这样在客户端没有收到新数据的时候还可以继续更新渲染位置（只对渲染的模型位置信息进行插值）。
（2） 客户端预先执行+回滚
预测的目的是让玩家能在本地操作后立刻收到反馈，提升游戏体验，回滚是为了保证服务器的权威性。客户端预测包括位置预测以及行为预测两种，位置预测需要高频率的执行，因为移动在每帧都可能发生，而其他行为预测则相对低频一些，包括开枪、扔手雷、释放技能等。另外，对于延迟不太敏感的游戏（比如 MMO），可以放宽校验条件（超过一定误差再纠正），这样即使降低服务器帧率客户端也不会有什么感觉。

延迟对抗

（1） 延迟补偿
服务器（注意是服务器而不是客户端）记录一段时间内所有玩家的位置历史，在发生伤害计算时根据延迟对所有玩家角色进行位置的回滚与处理，可以尽量还原当时的场景。
（2） 命令缓冲区
把远端的数据缓存在一个 buffer 里面，然后按照固定频率从 buffer 里面取，可以解决客户端卡顿以及网络抖动问题。不过缓冲区与延迟是有冲突的，缓冲区越大，证明我们缓存的远端数据就越多，延迟就越大。
（3）从具体实现的技巧上对抗延迟
客户端操作加一个前摇时间，释放技能等行为前有一个播放动画表现的时间来抵消掉同步 RTT 的延迟。比如角色释放无敌技能在进入无敌状态前做一个过度动画，客户端播放动画后进入无敌，但是服务器可以在收到指令后直接进入无敌状态从而抵消延迟。在游戏 Halo 中，有很多类似的例子，如在客户端玩家扔手雷的时候，我们可以在本地立刻播放扔手雷的动画并发送请求到服务器，然后服务器收到后不需要播放动画立刻生成手雷并同步，这样客户端真正扔出手雷的表现就是 0 延迟的

丢包对抗

1. 使用 TCP 而不是 UDP。由于 TCP 不会丢包，对于延迟不敏感的游戏还是优先采取TCP 来对抗丢包
2. 冗余 UDP 数据包
   一次性发送多个帧的数据来对抗丢包。UDP 同步数据时经常容易丢包，我们虽然可以使用上层实现 UDP 的可靠性，但是像帧同步这种同步数据量比较小的游戏可以采用冗余 UDP 的方案，即后续的 UDP 包会冗余一定量的前面已发送的 UDP 包，这样即使丢失了部分包我们也能保证拿到完整的远端数据。

带宽优化

带宽优化的目的是减小客户端以及服务器的同步压力，避免大量数据同时传输造成处理不过来，排队甚至是丢失。带宽优化是非常灵活且多变的，我们需要根据游戏的玩法来调整我们的优化行为。

1. 同步对象裁剪。核心目的是根据相关性剔除那些不需要同步的对象（这里都是指在同一个服务器内），比如一个玩家距离我很远，我们的行为彼此不会影响，所以就不需要互相同步对方的数据。裁剪方式有非常多，常见的 SOI（Spheres of Influence），静态区域（把场景划分为 N个小区域，不在一个区域不同步），视锥裁剪（更多用于渲染），八叉树裁剪等。相关性还可能会涉及到声音等其他因素，需要根据自己项目来决定。这里着重提一点 AOI ( Area Of Interest) ，即根据玩家的位置维护一个动态的视野列表，视野外的对象会被完全忽略（能大幅的减少同步对象的遍历与比较）。其基本思想也是判断相关性，实现方式有很多，
   其中基于格子的空间划分算法是网络游戏中常见的实现方案。在虚幻引擎中，大世界同步框架
   ReplicationGraph的核心思想也是如此。不过要注意的是，对于 MMO 这种可能有大量角色同时进行连续移动的游戏，视野列表频繁的增删查操作也可能对服务造成一定的压力。
2. 分区，分房间
   对于大型 MMO 来说，这是常见的手段，将不同的玩家分散到不同的场景内（不同的服务器），这样减小服务器处理数据的压力，减小延迟。对于大世界游戏而言，不同服务器可能接管同一个地图不同区域的服务，其中的跨服数据同步比较复杂。
3. 数据压缩与裁剪
   坐标与旋转是我们常见的同步内容，但是很多数据其实是不需要同步的。比如对于大部分 3D 游
   戏角色的 Pitch 以及 Roll 是不会改变的，我们只要同步 Yaw 值即可。对于非第一人称游戏，我们可以接着把四个字节 float 类型的 Yaw 压缩到两个字节的 uint16 里面，玩家根本不会有什么体验上的差异。类似的方法可以应用到各种同步数据里面。此外，在状态同步里面，我们可以采用增量发送来减少数据量，即第一次发送完整的数据信息后只发送哪些发生过变化的数据，这可以大大减少网络同步的流量。
4. 减少遍历以及更细力度的优化在 Halo 以及虚幻引擎里面都会对同步对象做优先级划分，发送频率调整等。在状态同步中，我们还需要合适的手段来快速定位发生变化的数据，如属性置脏、利用反射减少非同步属性的遍历等。进一步的，我们还可以根据客户端的类型以及信息作出更细致的同步信息过滤以及设置优先级，比如对同步属性进行优先级划分等（目前还没有见到过粒度如此细致的，但理论上是可行的）

帧率优化

帧率优化是一个重要且复杂的难题，涉及到方方面面的技术细节，这里主要针对网络同步相关内容做一些分析。相比单机游戏，网游需要同时考虑客户端与服务器的帧率，这并不是单纯地提升帧率的问题，如何优化与平衡是一个很微妙的过程。

1. 提升帧率
   这个不用多说，帧率低就意味着卡顿，玩家的体验就会很差。不同游戏的性能瓶颈都可能不一样，包括内存问题（GC、频繁的申请与释放）、IO（资源加载、频繁的读写文件，网络包发送频率过大，数据库读取频繁）、逻辑问题（大量的遍历循环，无意义的 Tick，频繁的创建删除对
   象，过多的加锁，高频率的 Log）、AI（寻路耗时）、物理问题（复杂模拟，碰撞次数过多）、语言特性（脚本语言比较费时）等，客户端相比服务器还有各种复杂的渲染问题（Drawcall 太多，半透明，动态阴影等）。这些问题需要长期的测试与调试，每个问题涉及到的具体细节可能都有所不同，需要对症下药才行。
2. 保持帧率稳定与匹配
   假如你的客户端与服务器帧率已经优化到极致，你也不能任其自由变化。首先，要尽量保持服务器的帧率稳定（减少甚至是消除玩家比赛时的所有潜在的卡顿问题），考虑一款对延迟比较敏感的射击游戏，如果你的客户端在开枪时遇到了服务器卡顿，那么就可能造成校验失败，导致客户端看到的行为与服务器行为不一致。其次，还要保持客户端与服务器的帧率匹配。对于延迟不敏感的游戏，考虑到玩家的体验以及服务器的压力，客户端的帧率可以高于服务器多倍，但是这个比例是需要通过实际的测试来调整。而对于延迟敏感的游戏，我们一般需要尽量让服务器的帧率接近客户端，这样服务器才能更及时的相应，减少延迟带来的误差。此外，我们也不能让客户端的帧率无限提高，对于某些同步算法，客户端与服务器过高的帧率差异可能造成不断的拉回卡顿。所以，很多游戏会采取锁帧的方式来保证游戏的稳定性。
3. 计算压力分担
   对于 MMO 这种服务器压力比较大的游戏，我们通常会考虑把一部分计算资源转交给客户端去计算（甚至是计算后再返还给服务器），比如物理运算、自动寻路、AI 逻辑计算等。其实将这种方式使用到极致的例子就是帧同步，服务器只做一些简单的校验即可。

IO 多路复用，select vs poll，epoll vs poll&select

IO多路复用是一种网络编程技术，用于在单个线程中管理多个网络连接。它通过使用操作系统提供的特定API（如select、poll、epoll等）来监听多个文件描述符（通常是套接字），以实现同时监测多个I/O事件的能力。

参考：https://blog.csdn.net/v123411739/article/details/124699602
Socket：对网络中不同逐级上的应用程序之间进行双向通信的端点的抽象，相当于客户端服务器通信的入口。
FD(file desriptor)linux 中的一切资源都可以通过文件的方式访问和管理。而 FD 就类似文件的索引（符号、指针），指向某个资源，内核（kernel）利用 FD 来访问和管理资源。我们调用内核函数创建 socket 后，内核返回给我们的是 socket 对应的文件描述符（fd），所以我们对 socket 的操作基本都是通过 fd 来进行。

核心交互流程如下：

1）服务器端通过 socket、bind、listen 对 socket 进行初始化，最后阻塞在 accept 等待客户端请求到来。

2）客户端通过 socket 进行初始化，然后使用 connect 向服务端发起连接请求。此时客户端会和服务端进行 TCP 三次握手，三次握手完成后，客户端和服务端建立连接完毕，开始进入数据传输过程。

3）客户端发起 write 系统调用写入数据，数据从用户空间拷贝到内核空间 socket 缓冲区，最后内核将数据通过网络发送到服务器。

4）数据经过网络传输到达服务器网卡，接着内核将数据拷贝到对应的 socket 接收队列，最后将数据从内核空间拷贝到用户空间。

5）客户端和服务器完成交互后，调用 close 函数来断开连接。

同步阻塞IO：当应用程序发起 read 系统调用时，在内核数据没有准备好之前，应用程序会一直处于阻塞等待状态，直到内核把数据准备好了返回给应用程序
大致流程如下：
1）服务端进行初始化：新建 socket、绑定地址、转为服务端 socket
2）服务端调用 accept，进入阻塞状态，等待客户端连接
3）客户端新建 socket，向服务端发起连接
4）服务端和客户端通过 TCP 三次握手建立连接
5）服务端继续执行 read 函数，进入阻塞状态，等待客户端发送数据
6）客户端向服务端发送数据
7）服务端读取数据，执行逻辑处理

总结
单线程：某个 socket 阻塞，会影响到其他 socket 处理。
多线程：当客户端较多时，会造成资源浪费，全部 socket 中可能每个时刻只有几个就绪。同时，线程的调度、上下文切换乃至它们占用的内存，可能都会成为瓶颈。

同步非阻塞IO

大致流程如下：
1）服务端调用 accept，数据未就绪，内核返回-1
2）服务端调用 accept，数据未就绪，内核返回-1
3）服务端调用 accept，数据未就绪，内核返回-1
4）客户端新建 socket，向服务端发起连接
4）服务端调用 accept，服务端和客户端通过 TCP 三次握手建立连接
5）服务端执行后续逻辑处理

提供了非阻塞调用的方式，从操作系统层面解决了阻塞问题。单个 socket 阻塞，不会影响到其他 socket 但是需要不断的遍历进行系统调用，有一定开销。

select
核心流程
1）应用程序首先发起 select 系统调用，传入要监听的文件描述符集合
2）内核遍历应用程序传入的 fd 集合，如果遍历完一遍后发现没有就绪的 fd 则用户进程会进入阻塞状态，如果有就绪的 fd 则会对就绪的 fd 打标，然后返回
3）应用程序遍历 fd 集合，找到就绪的 fd，进行相应的事件处理

优点：不需要每个 FD 都进行一次系统调用，解决了频繁的用户态内核态切换问题
缺点：

• 单进程监听的 FD 存在限制，默认1024
• 每次调用需要将 FD 从用户态拷贝到内核态
• 不知道具体是哪个文件描述符就绪，需要遍历全部文件描述符
• 入参的3个 fd_set 集合每次调用都需要重置

poll
poll 函数基本同 select，只是对 select 进行了一些小优化，一个是优化了1024个文件描述符上限，另一个是新定义了 pollfd 数据结构，使用两个不同的变量来表示监听的事件和就绪的事件，这样就不需要像 select 那样每次重置 fd_set 了。

epoll
核心流程
1）应用程序调用 epoll_create，内核会分配一块内存空间，创建一个 epoll，最后将 epoll 的 fd 返回，我们后续可以通过这个 fd 来操作 epoll 对象
2）应用程序不断调用 epoll_ctl 将我们要监听的 fd 维护到 epoll，内核通过红黑树的结构来高效的维护我们传入的 fd 集合
3）应用程序调用 epoll_wait 来获取就绪事件，内核检查 epoll 的就绪列表，如果就绪列表为空则会进入阻塞，否则直接返回就绪的事件。
4）应用程序根据内核返回的就绪事件，进行相应的事件处理

epoll 直接将 fd 集合维护在内核中，通过红黑树来高效管理 fd 集合，同时维护一个就绪列表，当 fd 就绪后会添加到就绪列表中，当应用空间调用 epoll_wait 获取就绪事件时，内核直接判断就绪列表即可知道是否有事件就绪。

LT：Level-triggered，水平（条件）触发，默认。epoll_wait 检测到事件后，如果该事件没被处理完毕，后续每次 epoll_wait 调用都会返回该事件。
ET：Edge-triggered，边缘触发。epoll_wait 检测到事件后，只会在当次返回该事件，不管该事件是否被处理完毕。

优点
解决了 select 和 poll 的缺点，高效处理高并发下的大量连接，同时有非常优异的性能。

缺点

• 跨平台性不够好，只支持 linux，macOS 等操作系统不支持
• 相较于 epoll，select 更轻量可移植性更强
• 在监听连接数和事件较少的场景下，select 可能更优

时间处理模式reactor和proreactor区别(待续)

https://www.bilibili.com/video/BV12U4y167sf

Reactor和Proactor是两种常见的事件处理模式，用于处理异步事件和I/O操作。它们在编程领域中被广泛应用于实现高性能、可扩展的系统。下面是它们的区别：

Reactor（反应器）模式：
Reactor模式基于事件驱动，使用一个事件循环（Event Loop）来等待和分发事件。
在Reactor模式中，所有的I/O操作都是同步的，当有一个I/O请求到达时，事件循环会通知相应的处理程序进行处理。
Reactor模式适用于处理少量的并发连接，并且处理程序通常是单线程的。它的主要优势在于简单性和低延迟。

Proactor（主动器）模式：
Proactor模式也是基于事件驱动的，但与Reactor模式不同，Proactor模式下的I/O操作是异步的。
在Proactor模式中，I/O操作的发起和完成是分离的。当一个I/O请求被发起后，程序可以继续执行其他任务，当I/O操作完成后，系统会通知相应的处理程序进行处理。
Proactor模式适用于处理大量的并发连接，特别是在高负载和高并发的情况下。它的主要优势在于并发性和可扩展性。
总的来说，Reactor模式适用于处理少量的连接和低延迟的场景，而Proactor模式适用于处理大量的连接和高并发的场景。选择使用哪种模式需要根据具体的应用需求和性能要求来进行评估。

帧同步为什么要自研物理引擎

物理引擎内部是由浮点数参与计算的，而浮点数在不同平台产生的结果也不一样，就导致了结果有所浮动，且不一致，所以会造成不同步。因此就衍生出了定点数。而帧同步为了保证各平台同步的情况下，则必须使用定点数物理库。

帧同步如何反外挂

多人竞技的帧同步比较容易反挂，王者也是通过客户端上传关键数据的hash 投票找出作弊玩家。如果要对单机，双人等人数较少的帧同步游戏反挂，可以结算之后服务器再加速跑一边录像做验证，例如刀塔传奇。

帧同步如何做预表现

预测就是将玩家的输入立即应用到本地状态，而无需等待服务端返回。但是由于延迟的存在，服务端的同步总是滞后的，所以你总是被拉回之前的位置，所以看到的抖动和拉扯。归根到底，是服务端同步过来的状态与本地预测的状态不一致，所以我们需要 “和解” 它们

如果使用的是状态同步，和解过程是：
（1） 收到服务端同步来的 权威状态
（2） 将本地状态立即设为此权威状态
（3） 在权威状态的基础上，应用当前所有 预测输入

如果使用的是帧同步，和解过程是：
（1） 收到服务端同步来的权威输入
（2） 将本地状态立即 回滚 至 上一次的权威状态
（3） 将权威输入应用到当前状态，得到此次的 权威状态
（4） 在权威状态的基础上，应用当前所有 预测输入
由此可见，状态同步和帧同步只是网络传输的内容不同，但它们是完全可以相互替代的 —— 最终目的都是为了同步权威状态。

帧同步中，逻辑渲染如何分离

多人实时游戏，通常会划分为表现层和逻辑层。 表现层指游戏画面的显示和用户输入的获取； 逻辑层指渲染无关的、只关注状态变化和计算的玩法逻辑。

逻辑层本质上就是一个状态机。在实现逻辑层的过程中，有几个重要的点需要关注：
（1） 无输入，不变化：状态变更仅发生在输入时刻，没有输入时状态不会改变
（2） 状态计算应该没有任何外部依赖，例如 Data.now()、Math.random()等，所有这些都应该显式成为输入的一部分
（3） 结果的一致性：在相同的状态和输入下，得到的新状态应该是一致的

像随机数这类场景，可以通过伪随机数生成器实现，在相同的种子输入下，随机结果应该是一致的。

帧同步中产生不同步的原因以及解决方案

首先我们要弄清楚帧同步中的不同步是指什么?帧同步的原理是客户端计算，服务器转发给所有客户端，客户端表现一致。这机制就导致了服务器是不知道具体的计算逻辑的，如果客户端在进行逻辑运算时，在某一帧的变量不一致，随着时间的推移，会将这个差异扩大化，形成雪球效应，最后各个客户端得到的结果不一致。总结就是各个客户端无法保证输入以及计算的一致性，就无法保证输出结果的唯一性，因而就产生了不同步的情况。
（1） 数值的随机性。格斗类游戏中的事件随机性是它的一大魅力所在。例如闪避机制，暴击伤害等。由于帧同步中的逻辑都在客户 端进行，每个客户端对这类事件进行计算，就没有唯一
性。举例 玩家 A 的暴击几率是 80%，假设在第 200 帧中，玩家A 进行了一次 平 A 攻击，客户端 A 计算得到这次攻击产生了暴132击伤害 300，而客 户端 B 计算得到的结果是暴击伤害 280。这就导致了伤害不一致，随着战斗的进行两边客户端的差距会越来越大，得到不同的战斗结果。而帧同步就需要解决这类事件，保证两边随机结果的一致性。解决方案是客户端做伪随机算法。战斗开始时，服务器给客户端下发一个随机种子，通过自定义随机算
法，保证每次的随机结果都是可控且一致的。

（2） 逻辑执行顺序不一致。我们项目中用到了很多第三方的插件（例如 PlayMaker、NGUI）,这些插件的 Update 是没法由帧同步去控制的，各个客户端可能执行某个计算片段的时间并不是在同一逻辑帧内导致出现不同步的情况。unity 的物理系统，动画系统也是如此。解决方案就是不使用第三方插件，使用成熟稳定的开源插件或者自己实现，保证每个 update 都是自主可控的。避免出现不可控导致的不同步的情况出现。

（3） 数学计算中的精度丢失。精度丢失的情况主要是出现在浮点运算中。不同的硬件环境下浮点数的运算结果可能是不一致的。可能在一帧中的差异性很小，但随着时间推移造成的雪球效应会导致客户端得到不同的结果。要保证在不同的硬件环境下，运算结果的一致性就需要使用定点数替代浮点数，根据需求定一个比值参数（我们项目采用的是万分比）进行定点数和浮点数的转换。这样就保证了不会出现计算中的精度丢失问题。

（4） 接收网络数据不一致。因为 UDP 的不可靠性以及复杂的网络环境，在出现网络波动的情况下，接收端接收到的消息是无序的，客户端在接收服务器发送的消息时，后发的消息可能会比先发的消息还要先接收到，如果这时候客户端不进行处理的话，就会出现客户端先处理后一条消息，再处理前一条消息的情况，这样就会造成客户端对于操作输入的顺序不一致，也是会造成最终的不同步的。解决方案就是对每一个发出的消息做一个自增的编号，根据编号的连续性确定消息的顺序，就算先收到后面的消息，也可以等待前面的消息收到之后进行顺序传入游戏逻辑中。

数学

三个矩阵的顺序

旋转矩阵，平移矩阵，缩放矩阵，三个动作的先后顺序（出自腾讯、网易）
先平移、然后旋转、最后缩放。

欧拉角的万向节死锁和四元数

在三维空间中，欧拉角是一种常用的表示物体旋转的方法，它由三个旋转轴和对应的旋转角度组成。然而，欧拉角存在一个问题，即当旋转角度接近某些特定值时，会导致旋转轴发生奇异性，从而使得物体的旋转过程出现异常。例如y轴旋转90度会导致x的旋转和z轴重合导致失去一个轴的自由度。这是因为欧拉角的旋转是相对于初始姿态来说的，并且是先旋转x再旋转y再旋转z。
x,y,z的旋转顺序不可改变，否则会导致姿态不一致，如果在y或z调整完了以后调整x轴，你想象中x的旋转发生在最后，实际上x的旋转会被加到一开始x的旋转变量上，所以导致了实际情况和直觉不符。这导致了死锁的发生。这会导致动画插值过渡的问题。

四元数是解决万向节死锁的方法，用四个数代表物体的旋转。四元数（Quaternions）是一种表示三维空间旋转的数学工具。它可以通过四个实数（a, b, c, d）来表示，常见的表示形式为 q = a + bi + cj + dk。其中，a 是实部，(b, c, d) 是虚部，而 (i, j, k) 则是三个相互正交的单位虚数。

四元数表示旋转的基本思想是利用一个单位四元数来表示旋转轴和旋转角度的组合。具体步骤如下：

定义旋转轴：选择一个单位向量 (x, y, z) 作为旋转轴，表示物体绕该轴进行旋转。

定义旋转角度：选择一个角度 θ，表示旋转的大小。

构造单位四元数：根据旋转轴和旋转角度构造一个单位四元数。常用的方式是通过旋转轴 (x, y, z) 和旋转角度 θ，计算出四元数的虚部 (b, c, d)。

b = x * sin(θ/2)
c = y * sin(θ/2)
d = z * sin(θ/2)

实部 a 的值通常为 cos(θ/2)。

执行旋转：将要旋转的点（向量）表示为四元数的虚部（0, x’, y’, z’），其中 (x’, y’, z’) 是点的坐标。

进行旋转：通过四元数的乘法运算将旋转应用于要旋转的点。乘法操作为：

q’ = q * p * q^(-1)

其中 q 是旋转的四元数，p 是要旋转的点（四元数表示），q^(-1) 是 q 的逆四元数。

最后得到的四元数 q’ 的虚部（0, x’’, y’’, z’’）即为旋转后的点的坐标。

三维旋转就是四维旋转的一个特例，就像二维旋转是三维旋转的一个特例一样。说是特例其实不准确，准确的说是一个子集或者subgroup。为了进行三维旋转运算，汉密尔顿首先在四维空间里划出了一块三维空间。汉密尔顿定义了一种纯四元数（pure quaternion），其表达式为qw=(0,wx,wy,wz)。纯四元数第一项为零，它存在于四维空间的三维超平面上，与三维空间中的三维向量一一对应。然后，就有了我们常见的q∗qw∗q−1这种左乘单位四元数，右乘其共轭的表达式。。简单的说，当对一个三维向量进行三维旋转后，我们希望得到的是一个三维向量。那么这个左乘单位四元数，右乘其共轭的运算保证了结果是一个在三维超平面上中的纯四元数。

点乘和叉乘

点乘（内积）的结果是一个数，反应了两个向量在方向上的相似度，方向相同值越大，反之值越小，范围为-a到a，a就是两者模的乘积。
叉乘（外积）的结果是一个向量，以三维举例，模长和两个向量组成的平行四边形的面积相等，方向垂直与两个向量组成的平面，当a在b顺时针方向则向上，反之向下。可以利用这个性质判断物体在左边还是右边，如果外积之后y为正，则a在b的右边，反之在左边，如果a和b在同一直线上，则外积为零向量。
叉乘：a×b = （y1z2-z1y2, z1x2-x1z2, x1y2-y1x2）
如果在二维上 a×b = x1y2 - y1x2，看起来是一个数，实际上方向在第三个轴上，这个数的正为正a在b的右边，反之在左边。

如何判断一个点在三角形内

面积法：
如果P点在三角形ABC内，则三角形面积等于：ABP+ACP+BCP的面积
求一个三角形的面积可以用叉乘，叉乘的结果可以求两个向量组成的平行四边形面积，三角形的面积是平行四边形的一半，因此通过向量PA，PB，PC就能求出三个三角形面积，AB，AC能求出大三角形面积。

射线和平面求交算法

垂直于平面的线与射线垂直。

点到直线的距离

如果存在一条直线ax+by+c=0，那么点(x0,y0)到直线的距离为：
$$
d = \frac {|ax_0 + by_0 +c|}{\sqrt{a^2 + b^2}}
$$

判断二维凸包

可以想象在平面中有一些点，这些点的集合为 X，拿一个橡皮圈撑到最大，尝试套住所有的点，待橡皮圈绷紧后，它会成为一个多边形，这个多边形所有顶点组成的集合便为集合 X 的凸包。
Gift wrapping算法：

（1） 找到一个一定在凸包中的初始点，比如最左下的点
（2） 计算剩下的所有点与初始点正向下方向之间的角度，取最小的角度的点加入凸包
（3） 对于最新加入凸包的点，取前一个点指向该点的方向作为初始方向，遍历剩下的点，取剩下的点和该点的连线与初始方向夹角最小的点加入凸包
（4） 重复 3，直到找到的下一个点是初始点

碰撞检测GJK算法、

GJK 算法可以在 O(M+N)的时间复杂度内，检测出碰撞，算法在每次迭代的过程中，都会优先选择靠近原点的方向，因此收敛速度会很快。
通俗的讲，GJK 算法就是沿着某个方向，从两个多边形上取相距最远的两个点计算差值；然后将方向取反，再次取两个点计算出差值。如果两个多边形发生碰撞，则这两个差值必然有一个大于 0，一个小于 0。如果不相交，则两个差值是同为正或同为负。

碰撞检测四叉树

四叉树就是一种优化方法，能够帮助我们对元素按照区域进行划分，减少检测数量。需要说明的是，四叉树只是一种「减少碰撞候选者」的算法，在利用四叉树得到碰撞候选元素后，还需要检测这些候选元素与目标元素是否发生碰撞。
假如在我们要在游戏中对 200 个物体进行碰撞检测，按照常规的碰撞检测方式，每帧每个物体都要对其他 199 个物体进行物理碰撞检测，则需要进行 200*199=39800 次检测。这样的检测效率，很容易对低端手机的性能造成一定的影响。

方法：
我们把游戏屏幕看做一个区域，不断放置圆点进去。假设我们设定每个区域只能容纳 4 个物体，只要超过这个数量，就分割该区域。如下图，当区域内的圆点数达到 4 个，这个时候再想加入第 5 个，就必须先将当前区域分割为 4 个区域，再将第 5 个放入左上区域。如果物体处在交界的区间内，那么把物体放在上一层次的区域内，不然就放在该层。

步骤：

• 创建四叉树，区域为整个屏幕，并将树保存为全局变量；
• 插入需要做碰撞检测的目标元素；
• 检索目标元素的待检测碰撞对象，返回碰撞候选元素组；
• 清除四叉树中的元素，以方便下次继续检测

AABB（轴对称矩形边界框）

AABB-box 简单点说就是垂直于坐标轴的包围盒，搞过物体识别的标注的童鞋都知道，这种包围盒不会旋转（当物体旋转的时候，就用更大的包围盒去包围它），因此使用起来非常简单。
AABB-box 对应的是 OBB-box, OBB-box 会跟着物体的朝向一起旋转，而大小不会改变，相对来说比 AABB-box 更加准确，但是检测碰撞的运算量会比AABB-box 大一点。
到采用包围盒之后简化了需要检测碰撞的模型，用其它更加简单的形状去做粗校验，避免采用更复杂的多边形去检测碰撞。

松散四叉树，BVH，BS，KD 树的特性以及适用情况

松散四叉树

参考：https://zhuanlan.zhihu.com/p/180560098
四叉树是一种将二维空间划分为四个象限的树结构，每个节点可以有最多四个子节点。松散四叉树相比于传统的四叉树在节点分割和合并的策略上有所不同，它在一些情况下可以减少树的深度和节点数量，从而提高查询效率。

松散四叉树的特点是：

节点的子节点不一定都存在。如果某个节点的四个子节点都为空且该节点中存储的对象数量很少，可以考虑将该节点与其相邻的同级节点合并，从而减少树的深度和节点数量。
节点的划分和合并策略是动态的。根据对象的插入、删除和移动等操作，动态地进行节点的划分和合并，以保持树的平衡性和性能。

松散四叉树/八叉树中，是指出口边界比入口边界要宽些（虽然各节点的出口边界也会发生部分重叠），从而使节点不容易越过出口边界，减少了物体切换节点的次数。问题在于如何定义出口边界的长度。因为太短会退化成正常四叉树/八叉树，太长又可能会导致节点存储冗余的物体。经过前人的实验表明出口边界长度为入口边界2倍最佳。

层次包围盒 BVH（待完善）

这部分是目前渲染器中最困难的部分，但是可以是渲染器更加高效，所以我们需要花上一点时间去重构之前的代码。

寻找射线与物体的交点是渲染器主要耗时的地方之一，而且时间消耗随着场景内物体的数量递增。

我们要做的是使用二分法对场景内的物体进行搜索，而不是遍历所有物体。

二叉空间分割 BSP

BSP（Binary Space Partitioning）是一种二叉空间分割数据结构，用于对三维空间进行分割和表示。它是一种递归的树结构，每个节点表示一个空间分割平面，将空间划分为两个子空间。
BSP树的构建过程是通过递归地选择一个空间分割平面，并将空间划分为两个子空间。通常选择的分割平面可以是平面、线段或者点。在构建过程中，根据空间中的物体位置，将物体放置在合适的子空间中。这样，通过不断地划分空间，最终构建出一棵树，其中每个叶子节点表示空间中的一个区域。使 VSD 问题易于解决。

讲到这里，你需要先了解一下为什么分割场景可以奏效：如果你在场景上画条线（对应三维空间里的一个平面），你就可以指出玩家或者摄像机视角在这条线的哪一侧，在这条线另一侧的物体无法遮挡玩家所在一侧的物体。如果多次重复这一操作，该三维场景最终会被分割为多个区域，这并不是对原始场景的改进，只是现在你知道了更多关于场景的不同部分会如何相互阻挡。

用途：

1. 空间裁剪（Clipping）：BSP树可以用于剔除不可见的物体或区域，提高图形渲染性能。通过构建BSP树，可以确定哪些物体在视锥体内部，从而避免对视锥体外部的物体进行渲染和处理。
2. 可视性检测（Visibility Determination）：BSP树可以用于确定场景中哪些物体对于特定视点是可见的，从而优化图形渲染过程。通过遍历BSP树，可以快速确定与视点相交的节点和区域，提高渲染效率。
3. 碰撞检测（Collision Detection）：BSP树可以用于检测物体之间的碰撞。通过构建BSP树，可以有效地判断两个物体是否相交，从而进行碰撞检测、物体遮挡检测等。
4. 光线跟踪（Ray Tracing）：BSP树在光线跟踪算法中有重要的应用。通过构建BSP树，可以加速光线和物体之间的相交检测，从而实现高效的光线跟踪渲染。

总的来说，BSP树通过对空间进行递归的二叉分割，能够有效地处理复杂的空间关系，提高图形渲染和物体检测的效率。然而，BSP树也有一些限制，例如在处理动态场景时，需要频繁地更新树结构，且构建过程较为复杂。因此，在具体应用中需要根据场景需求和性能要求综合考虑是否使用BSP树或其他的空间分割数据结构。

应用：
BSP 适合结构比较紧凑的互相遮挡多的场景
fps 室内，portal 系统

KD树

一种特殊形式的 BSP 树（轴对齐的 BSP 树），每一层都在不同的轴，适用于最近的静态目标的查找，构造比较耗时，一般不动态刷新。查询点均落在划分轴上，每次划分前都计算这个块中中间位置的点，穿过这个点进行轴划分

在KD树中，每个节点代表一个数据点，并根据其特征值在某个维度上进行划分。具体划分的方式有多种，常见的有以下两种：

1. 坐标轴对齐划分：每个节点按照某个维度上的特征值进行划分，左子树包含小于等于该特征值的点，右子树包含大于该特征值的点。划分的维度会循环选择，例如第一层按照x轴划分，第二层按照y轴划分，以此类推。
2. 中值划分：每个节点选择在某个维度上的中值作为划分值，将小于等于中值的点放入左子树，大于中值的点放入右子树。划分的维度可以通过循环选择，也可以在每个节点中选择方差最大的维度。

应用：
最近邻静态目标查找，例如上百的单位找最近的建筑，用 kd 树代替遍历+距离判断。

几种结构的比较

几种结构的比较
（1） 四叉树最适合二维数据，例如导航系统中的地图渲染。在这种情况下，它比八叉树更快，因为它可以更好的适应几何形状并保持节点结构较小；如果数据是三维的，则用八叉树和 BVH。
（2） BSP 旨在优化大型静态几何体，不适合需要大量动态增加物体的场合中，自带排序属性。
（3） BVH 多用于光线追踪（bvh 做 pvs(潜在可视几何)并不算特别有效率。bvh 做线段求交很快）碰撞检测，潜在碰撞集是关键，所以会使用更加优化邻近搜索的侧脸譬如 kdtree 或者 rtree。
（4） KD 树是平衡的，很难动态更新；OCTree 比较容易更新。

A*寻路算法

A*算法的寻路是基于代价作为计算的，它把一个地图划分为一个个节点，我们可以以一个整数坐标作为一个节点当算法探寻到这个节点的时候，会给这个节点一个代价值，这个值由两部分构成，一部分是从起点到现在的点所消耗的代价，可以如果每个节点所消耗的代价是1，那么没走一个代价+1，第二部分是一个预估值，预估了从当前节点到目标节点的距离，这个距离可以用欧式距离或曼哈顿距离来计算。把这两个值相加得到一个总代价，然后把节点放入优先队列中，把这个代价作为优先值。然后我们每次从优先队列中取出优先值最低的元素，然后遍历其周围的节点，计算其代价，然后放进优先队列中，循环往复直到找到目标节点。
我们在场景中可以利用四叉树来简化地图简单，或者Unity的导航三角网格。

def a_star_search(graph, start, goal):
  frontier = PriorityQueue()
  frontier.put(start, 0)
  came_from = {}   
  cost_so_far = {} # 键为节点，值为代价
  came_from[start] = None
  cost_so_far[start] = 0

  while not frontier.empty():
    current = frontier.get()
    if current = goal:
      break
    for next in graph.neighbors(current):
      next_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
        cost_so_far[next] = new_cost
        priority = new_cost + heuristic(goal, next)
        frontier.put[next] = current
  return came_from, cost_so_far

图形学（Shader）

这部分详情查看《跨引擎TA Shader》这篇文章

MMORPG项目

注册登录系统

保存了账号密码，还有对应的角色ID，角色名字不可是全数字，不能与其他玩家相同。

移动同步

同步指两个或两个以上随时间变化的量在变化过程中保一定的相对关系。游戏中需要同步的是角色信息，位置、状态。各个客户端的数据应当是同步的。这里使用了基于TCP的状态同步，状态同步有以下特点：

1. 消息传输的频率较低
2. 回放还原较难
3. 逻辑在服务器，安全
4. 比较难以进行精确的战斗校验
5. 服务器压力大
6. 断线重连无负担
7. 实现难点在于客户端需要做插值或行为预测等方式优化卡顿体验，调测压力较大

帧同步有以下特点：

1. 消息传输的频率较高
2. 回放还原容易
3. 逻辑在客户端，难以避免外挂
4. 服务器可以进行完整战斗模拟
5. 服务器只负责转发，压力小
6. 游戏时间越长断线重连越难
7. 难点在于需要规避浮点数的问题，并且逻辑和表现要进行分离，对设计有一定要求。

过程：

1. 客户端输入：
   客户端收集玩家的输入操作，例如按键、鼠标点击等。
   客户端根据输入生成相应的指令或消息，并将其发送给服务器。
2. 服务器接收指令：
   服务器接收客户端发送的指令或消息。
   服务器对指令进行验证和解析，确保其合法性和正确性。
3. 服务器更新游戏状态：
   服务器根据接收到的指令更新游戏状态，例如玩家位置、动作、血量等。
   服务器执行游戏逻辑，处理碰撞、计算伤害等。
4. 服务器广播状态更新：
   服务器将更新后的游戏状态广播给所有连接的客户端。
   服务器使用网络协议将状态信息发送给客户端。
5. 客户端接收状态更新：
   客户端接收服务器广播的游戏状态更新。
   客户端根据接收到的状态更新，更新本地的游戏状态。
6. 客户端渲染和表现：
   客户端根据本地的游戏状态进行渲染和表现，显示最新的游戏画面给玩家。

UI系统架构

UI可以分为静态UI和动态UI
静态UI：普通窗口、对话框、信息框
动态UI：公告，TIPs、战斗飘字

UIMain：首先，在主场景我们设置了一个UIMain的节点，上面挂着的脚本是常驻内存的，设置为单例类，这个节点下挂了很多在UI界面常驻的UI，例如人物头像，血条，人物的技能栏，聊天系统，背包，任务，坐骑，属性，等按钮。这个主UI是不会销毁的，只会隐藏。
UIManager：各个游戏系统的UI，用不到的时候不会加载，管理所有UI的脚本，UI需要在其中注册，并且可以设置这些UI在关闭时销毁或隐藏，然后利用注册的Key调用对应Show和Close方法来实现打开和关闭逻辑。

UIWindow：里面编写了常用的点击事件，并且有不同的关闭方法。使得继承它的UI都拥有基本的功能。

UIMessagerBox：用户用来显示提示，分为只有确定按钮的提示，和确定和取消两种按钮的提示，这个UI显示在界面的最上层。我们可以自由配置信息文章，按钮文字，标题文字。

道具和背包系统架构

道具一共有几种分类：可使用、可装备、任务物品、材料、通用（可卖钱）
道具系统需要的功能：添加道具、删除道具、道具使用、获取道具列表（用于背包）
为了便于管理，我们需要一张配置表，配置表上指定了物品的名字，描述，类型，能否使用，购买价格，售出价格，最大堆叠数量等等，这些往往有策划进行配置，程序只需要把这张excel转换为Json，然后读到程序之中即可。

因此，客户端和服务端都需要一个ItemManager、ItemService，ItemService负责双端之间的通信，ItemManager负责添加物品，删除物体等逻辑的处理，不同的地方在于客户端只存在一个ItemManger（单例类），服务器每个角色都配置一个ItemManager。ItemManager收到
ItemService传过来的数据，读取配置表的相关数据，对道具进行处理就可以了，处理完成之后保存数据库就可以了。

背包系统是基于道具系统之上开发的功能，具有查看，管理，道具交互的功能，比如说：分页、整理，道具使用、丢弃。背包系统以每个格子作为一个单独的对象，设定了存放物品的种类的数量等，通常来说，对物品进行使用，丢弃等操作的时候，背包需要刷新一下，我们就可以更加特定的顺序，物品堆叠的数量来整理背包。背包的状态改变后把对应的信息储存到数据库中。

除此之外，拼UI也是比较讲究的，关键是运用好ScrollView组件，可以实现背包中上下拖动的功能，然后在Content里面使用Grid Layout Group组件来管理格子，Content里面包含了所有解锁和未解锁的背包格子，使用代码遍历这些格子，然后在配置表中找到对应图片的路径，加载出来，并把父物体设为这些格子就能实现背包的功能了。

商店系统

商店类型可以分为杂货店，装备店等等，功能主要是展示商品列表，道具购买，一般的商店系统会和NPC系统有一定的联系，比如点击NPC打开商店，所以商店系统需要设定对应的接口给其他系统进行调用。
对于商店系统，我们也需要配置一张表，这张表包含了每个商店物品的信息，购买数量等等。购买之后需要和道具与背包联动。

装备系统

装备其实也是道具的部分，部分信息存储于道具配置表，但是还有一些道具配置表没有的信息，例如增加的力量，智力，敏捷，生命，法力等等，所以我们需要另外一张表存储这些信息。
装备的获取和道具一样，不同点在于装备是可以穿戴的，并且会实时改变玩家的属性，这涉及到战斗系统的部分内容。玩家的属性由几部分决定，第一是职业，不同的职业会有不同的初始化属性，第二是等级，等级成长导致属性增加，第三是装备导致的属性改变，这几种属性基本上不会随着时间的流逝而改变，第四种是buff属性，分为增益buff和负面buff，这项属性会随时变动，随着时间的流逝叠加或消失。
客户端会管理一个自己身上穿着的装备列表格子，每种装备只能穿戴一件，并且有穿戴要求，服务器管理着每个人身上的装备列表，当穿戴发生改变时客户端发送给服务器做逻辑处理，服务器保存数据库之后返回客户端，客户端表现为外观的改变以及数值的改变。

任务系统

任务分类可以分为主线和支线任务，任务目标可以分为对话，杀怪，收集，任务奖励分为经验，金币，道具，任务领取对象一般为NPC，任务的交互一般分为查看任务，接受任务，拒绝任务，完成任务。
每个人身上的的任务都有几种状态：未接取，已接未完成，已完成未提交，已提交状态，而很多任务又有前置任务，前置任务未完成无法接取这个任务。
所以任务系统需要配置这样一个表，规定任务等级，职业，前置任务，任务接取NPC，任务描述，对话，任务目标，奖励等。
数据库也需要保存任务列表及其完成状态，分别是已接取，已完成未提交，已提交。在和NPC交互的时候，只显示符合自己条件的，未完成的任务。完成任务后提供对应的奖励，这和NPC系统，道具系统有一定的交互。

好友系统

在数据库添加好友，对应的ID，等级职业等，并且在好友列表上显示在线装态

组队系统

需求分析：组队一般用于副本，组队入口可以是聊天，以及好友列表，我们可以邀请在线好友进行组队，并且队长可以踢人，转让队长，队员可以离开队伍。组队信息一般不存储在数据库上，跑在服务器的内存中。服务器内存会维护一个队伍的列表，每个队伍都有其队长。队伍生成后不销毁只重置，防止对象的反复创建销毁。

公会系统

和组队类似，但是公会系统是保存在数据库中的，并且数据库会储存申请信息以便会长处理，会长可以提拔罢免副会长，会长和副会长都可以通过入会申请，踢出普通成员，队长离开公会会提拔副会长为会长。

聊天系统

需求分析：聊天分为多种，一种是私聊1对1发送，其他频道聊天有本地、世界、组队、公会。聊天区的交互可以有私聊、加好友，邀请组队。
聊天系统使用了Candlelight插件，用于显示聊天文本，支持超链接，并且可以设计对应种类的文字样式，点击超链接触发对应的事件，例如弹出菜单，可以选择私聊，组队，加好友。
聊天系统的核心是对应频道的通信，如果是私聊，服务器可以只做转发，如果是频道聊天，服务器需要自己储存一份，然后转发给对应频道的人，如果有人上线了，也需要从频道中获取之前的聊天信息。

坐骑系统

坐骑没有做Service和Manager，如果很轻量可以把代码放到一起，坐骑可以看作是物品的一种，只是可以从坐骑面板中看到而已。因此我们无需添加额外的协议和数据库，直接利用道具系统、商店系统以及移动同步就能把坐骑系统完成

刷怪系统

刷怪系统由刷怪规则和刷怪逻辑组成，刷怪规则就是每隔多久在什么地点刷怪，刷怪逻辑对应刷怪的流程，刷怪的种类，等级。我们可以配置一个表定义了每个地图有哪些刷怪点，每个刷怪点有哪些怪物，怪物等级，刷新时间等。然后我们可以通过Unity编辑器脚本来可视化生成对应的刷怪位置信息。刷怪是服务器的事情，客户端只负责表现。

战斗系统

客户端战斗：客户端执行核心逻辑，服务端验证逻辑，分为数据验证（属性验证）和战斗回放验证，两个人以上比较好验证。
服务器战斗：服务器执行核心逻辑，客户端处理表现，这样就不需要验证。
每一个战斗都用一场BattleManager来管理，战斗管理可以分为战斗对象管理，战斗状态管理，战斗结算。

在设计战斗系统之前我们需要设计属性模块：
属性分为基础属性（初始值、等级成长）、附加属性（装备等）、动态属性（Buff等）。属性分为一级属性和二级属性，一级是力量、智力，敏捷，二级是生命，法力，物理攻击，法术攻击，物理防御法术防御，暴击率等。每次角色生成都会把这些属性计算一次，每一次状态改变时都会重新计算属性。

开始战斗时，由一个单位向另一个单位释放技能。这通知到服务器之后，服务器判断技能是否可以释放（冷却，别的技能释放中，没有MP等释放不了），如果可以释放，发信息给客户端做表现，然后服务器开始进行逻辑计算，在什么时候，对什么范围的敌人产生伤害，叠加buff，并且把buff和伤害信息发送给客户端，客户端表现为伤害跳字，buff特效。发包数量是优化过的，这些信息如果在同一帧内是可以打包发出去，如果同一帧发包过多，可以放在队列中储存，每一帧发送一定量的包出去，使负载得到均衡。
技能可以分为瞬发技能，非瞬发技能（有前摇），也可以分为单体技能和范围技能，也可分为子弹技能和非子弹技能，也可分为有持续时间和没有持续时间的技能，技能的释放过程是先经历一个前摇时间，这个前摇时间不可移动，还有一个施法时间，如果移动会取消施法。然后是释放时间，如果技能是一段的话，立刻产生伤害，如果是多段则每隔一段时间产生一次伤害，如果是范围技能，就是每隔一段时间对响应范围内的敌人产生伤害。

最有挑战性的bug，怎么解决的

1. 角色死亡释放技能，切换地图后报错，没找到被销毁的物体，反复测试找到原因

Xlua框架

这部分内容具体参考《XLua热更新框架》这篇文章

框架的构成

UIGameLoading：热更新检测模块，检测版本，检测资源，开启下载，并进入游戏主界面
AppBoot：启动器模块，初始化音频模块，SDK初始化完毕方法，Lua回调时间列表监听与调用
LuaTools：Lua工具类，有网络请求方法，网络请求回调方法，音频播放，等等
LuaBehaviour：Lua纽带类，与main.lua通信，定义luaAction，启动lua虚拟机，执行自定义lua资源目录，绑定lua端方法
ResourceManager：预制体管理、游戏体管理，图片管理，功能模块管理，lua脚本管理，音频资源管理，字体资源管理，材质贴图管理
SystemTool：系统拒绝，引擎碰撞回调，射线回调，输入回调等

ui.lua：业务功能管理模块，功能打开关闭，生成预制体，loading界面控制
main.lua：lua主脚本，加载框架模块，打开登录功能，绑定方法接收端
net.lua：网络管理模块，设置请求IP，设置session，设置账户，设置请求数量，网络请求响应回调方法，网络请求发送方法
list.lua：列表工具，列表创建方法
GameMainData：主数据管理模块，引用主数据model，设置主数据，提供数据操作方法
event.lua：事件管理模块，包含事件操作方法
plugin.lua：插件管理目录，设置插件相关信息
public.lua：功能资源管理模块，管理公共方法，管理公共变量
tools.lua：工具管理模块，有工具类方法

UIGameLoading会完成资源热更新的工作，然后加载一个挂载AppBoot和LuaBehaviour脚本的空物体，LuaBehaviour一启动就创建一个lua虚拟机，把lua脚本转换为字节码到内存中，调用main.lua正式开始执行lua脚本。
我们要将lua脚本的某些函数和LuaBehaviour中的某些函数绑定起来，当做入口：

internal static LuaEnv luaEnv = new LuaEnv();
LuaEnv.CustomLoader method = CustomLoaderMethod;
luaEnv.AddLoader(method);

scriptEnv = luaEnv.NewTable();
LuaTable meta = luaEnv.NewTable();
meta.Set("__index", luaEnv.Global);
scriptEnv.SetMetaTable(meta);
meta.Dispose();

scriptEnv.Set("self", this); 
TextAsset mainText = Resources.Load<TextAsset>("main.lua");
luaScript_ls = mainText.text;
luaEnv.DoString(luaScript_ls, "LuaBehaviour", scriptEnv);  
//绑定方法到lua
Action luaAwake = scriptEnv.Get<Action>( "Awake");
scriptEnv.Get( "Start", out luaStart);
scriptEnv.Get( "update", out luaUpdate);
scriptEnv.Get(  "ondestroy", out luaOnDestroy);
scriptEnv.Get("ray", out ray);
scriptEnv.Get("OnTriggerEnter", out TriggerEnter_);
scriptEnv.Get("rayF", out rayF); 

main.lua
在main.lua中对应着C#绑定的方法：

require 'net'  
require 'plugin'
require("tools")  
require 'list'
require 'event'
require 'GameMainData' 
require 'StaticData/StaticData' 
function Start() 
   require("UI/ui_1")   
   UI.OpenUI("loginDemo")
end 

function sockerSendMsg(v) 
  Event.Call("sockerSendMsg" , v) 
end 

function ray(x,y,z) 
  Event.Call("ray" , x,y,z) 
end 
function rayF(v)
	 Event.Call("rayF",v,x,y,z) 
end 
function OnTriggerEnter(v)
   Event.Call("OnTriggerEnter" , v) 
end 
function update()

    Event.Call("updateG" )
end 

而这个框架中的lua部分实现了一个时间系统，在对应的地方监听这个事件即可在 Event.Call的时候调用对应的函数。

框架的使用

配置文件生成：配置文件由工具生成，从excel生成lua脚本。我们有一个汇总数据的GameMainData的Lua脚本，里面require了所有需要用到的数据模块（model）,例如：require(“Model/DemoPlayerModel”),相当于统一管理数据的地方。

游戏每一个功能我们都可以当成一个模块，可以被封装成一个预制体，例如登录模块，装备模块，人物模块，地图模块：

1. 使用一个模块之前，我们需要按照功能将模块封装为预制体，将其存放在Module目录对应的功能目录下，Tag设置为uiComponent。
2. 每个功能模块有两个预制体脚本，一个是逻辑脚本功能（功能名.lua），视图脚本（功能名View.lua），这两个是基于框架设计的，并且由工具生成，生成后再补充内容，这样在多人协作的时候就能保证代码的一致性。
3. 在ui.lua脚本中引用逻辑脚本
4. 一般的逻辑都可以通过lua调用Unity的接口完成，涉及物理引擎的逻辑，可以通过定义一个事件，在C#和lua之间进行通讯，通讯方式和上面的代码一样。
   lua调用C#的方式：

   Vector3 = CS.UnityEngine.Vector3
   Destroy = CS.UnityEngine.GameObject.Destroy

网络请求流程：
业务模块请求方法->Net资源脚本->Net.lua模块->LuaTools Http方法->服务器端->LuaTools回调方法->AppBoot delayCall->Net.lua Receive方法->Net资源脚本 OnReceive OnResult方法->业务模块回调处理

为什么CS.XXX能访问C#中的代码

lua把C#的代码放到了CS这个全局变量下
LuaEnv初始化的时候，会执行lua代码，代码里面会创建CS ={},CS这个table的元表的__index元方法你可以看下，里面会用到xlua.import_type函数。干活的逻辑就是csharp层的ImportType

也就是说，创建一个类型表，一种方式是lua层，CS.A.B.C 会通过触发元方法走到csharp层创建（也是到getTypeId）。另一种是当push该类型的obj实例的时候，也会到getTypeId

xLua 编译lua, 导一个二进制，然后自己实现了把 二进制，导出给.net用，形成了一个.net的lua解释器。这个就是xLua为 .net 的lua方案的原理。然后xLua上层，就导出了 Unity的接口，xLua in .net for unity

逻辑题

赛马问题

https://www.bilibili.com/video/BV1KJ411g78y、

25匹马，5条赛道，不能计时，多少场知道前三名。
答案：7场。

两个 10G 的文件，200m 内存，排序

（1）把 10G 大小的文件拆分成 N 个小文件，每个文件 1M
（2）把每个文件拉倒内存排序，可以并行操作，在内存中直接使用快排，然后写入文件
（3）对文件做两两合并。

对象池

主要使用对象：AssetBundle、频繁使用的GameObject
管理器：

public class PoolManager:MonoBehaviour{
  Transform m_PoolParent;

  Dictionary<string,PoolBase> m_Pools = new Dictionary<string,PoolBase>();

  void Awake(){
    m_PoolParent = this.transform.parent.Find("Pool");
  }

  private void CreatePool<T>(string poolName, float releaseTime) where T:PoolBase{
    if(!m_Pools.TryGetValue(poolName, out PoolBase pool)){
      GameObject go = new GameObject(poolName);
      go.transform.SetParent(m_PoolParent);
      pool = go.AddComponent<T>();
      pool.Init(releaseTime);
      m_Pools.Add(poolName,pool);
    }
  }

  public void CreateGameObjectPool(string poolName,float releaseName){
    CreatePool<GameObjectPool>(poolName, releaseTime);
  }

  public void CreateAssetPool(string poolName, float realeaseTime){
    CreatePool<AssetPool>(poolName, releaseTime);
  }

  public Object Spawn(string poolName,string assetName){
    if(m_Pools.TryGetValue(poolName, out PoolBase pool)){
      return pool.Spawn(assetName);
    }
  }
// assetName存一个全路径最好
  public void UnSpawn(string poolName, string assetName, Object asset){
    if(m_Pools.TryGetValue(poolName, out PoolBase pool)){
      pool.UnSpawn(assetName, asset);
    }
  }
}

public class GameObjectPool:PoolBase{
  public override Object Spawn(string name){
    Object obj = base.Spawn(name);
    if(obj == null) return null;
    GameObject go = obj as GameObject;
    go.SetActive(true);
    return obj;
  }

  public override void UnSpawn(string name,Object obj){
    GameObject go = obj as GameObject;
    go.SetActive(false);
    go.transforn.SetParent(this.transform,false);
    base.UnSpawn(name,obj);
  }

  public override void Release(){
    base.Release();
    foreach(PoolObject item in m_Objects){
      if(System.DateTime.Now.Ticks - item.LastUseTime.Ticks >= m_ReleaseTime * 10000000){
        Destory(item.Object);
        m_Objects.Remove(item);
        Release();
        return;
      }
    }
  }
}

public class AssetPool:PoolBase{
  public override Object Spawn(string name){
    return base.Spawn(name);
  }

  public override void UnSpawn(string name,Object obj){
    base.UnSpawn(name,obj);
  }

  public override void Release(){
    base.Release();
    foreach(PoolObject item in m_Object{
      if(System.DateTime.Now.Ticks - item.LastUseTIme.Ticks >= m_ReleaseTime * 10000000){
        Manager.Resource.UnloadBundle(name);
        m_Object.Remove(item);
        Release();
        return;
      }
    })
  }
}

public class PoolBase:MonoBehaviour
{
  protected float m_ReleaseTime;
  // 单位：毫微秒，1秒=10^7毫微秒
  protected long m_LastReleaseTime = 0
  protected List<PoolObject> m_Objects;
  public void Start(){
    m_LastReleaseTime = System.DateTIme.Now.Ticks;
  }

  public void Init(float time){
    m_ReleaseTime = time;
    m_Object = new List<PoolObject>();
  }
  // 取出对象
  public virual Object Spawn(String name){
    foreach(PoolObject po in m_Objects){
      if(po.Name = name){
        m_Objects.Remove(po);
        return po.Object;
      }
    }
    return null;
  }

  public virtual void UnSpawn(string name,Object obj){
    PoolObject po = new PoolObject(name, obj);
    m_Objects.Add(po);
  }

  public virtual void Release(){

  }

  void Update(){
    if(System.DateTime.Now.Ticks - m_LastReleaseTime >= m_ReleaseTime * 10000000){
      m_LastTeleaseTime = System.DateTime.Now.Ticks;
      Release();
    }
  }
}

public class PoolObject
{
  public Object Object;
  public string Name;
  public System.DateTime LastUseTime;

  public PolObject(string name,Object obj)
  {
    Name = name;
    Object = obj;
    LastUseTime = System.DateTime.Now;
  }
}

对象池的调用时机

在游戏初始化函数中调用管理器创建对象池：

Manager.Pool.CreateGameObjectPool("UI",10);
Manager.Pool.CreateGameObjectPool("Monster",120);
Manager.Pool.CreateGameObjectPool("Effect",120);
Manager.Pool.CreateGameObjectPool("AssetBundle",300);

在UI的Close函数中调用UnSpawn，OpenUI函数中调用Spawn，写一个判断，如果对象池中没有这一类对象，再按照原来的方法生成，这样，Close函数中会自动把新生成的对象纳入对象池。

public void OpenUI(string uiName,string group, string luaName){
  GameObject ui = null;
  Transform parent = GetUIGroup(group);
  string uiPath = PathUtil.GetUIPath(uiName);
  Object uiObj = Manager.Pool.Spawn("UI",uiPath);
  if(uiObj != null){
    ui = uiObj as GameObject;
    UILogin uiLogic = ui.GetComponent<UILogic>();
    uiLogic.OnOpen();
    ui.transform.SetParent(parent,false);
    return;
  }
  Manager.Resource.LoadUI(uiName,(Object obj) =>
  {
    ui = Instantiate(obj) as GameObject;
    --snip--
  })
  --snip--
)

在决定要不要卸载AssetBundle的时候，可以设一个AssetData,每有一个资源引用Bundle的时候就给AssetData的Count加1(从对象池拿或加载Bundle)，资源被销毁的时候减1，当Count等于0放入对象池，一段时间不变就卸载AssetBundle

UI架构设计

UI层级管理：
分层（从底到上）：场景UI、主界面UI、普通UI（窗口）、信息UI（广播）、提示窗口、加载界面

工具：资源后处理工具、资源去重校验工具、UI编辑器、UI配置表、脚本自动生成工具

配置表架构设计

配置表是用来灵活调整游戏表现数据的储存文件，可以是Excel文件
期待：在机制上避免篡改，能提供配置数据再封装入口，使用简单，不占用过多内存，有错误快速响应。
在游戏的每个阶段需要使用的配置表的数据都不一样，我们不用一次性把所有配置数据加载进来，防止占用过多内存。

客户端如何跟服务器对接

1. 编写客户端Socket程序，连接服务器，做好连接管理
2. 与服务器开发人员确定协议的格式
3. 与服务器确定数据内容的编码方式
4. 做一个服务器代码模块与每个服务器进行通讯

如何找游戏创意和扒资源

1. 我们要学会从不同的平台找好的创意移植
2. 推荐数据平台：七麦数据，可以参考上面各个排行榜上的数据，找到别人不错的创意
3. 确定游戏引擎，通过网络获取游戏的apk文件，或通过iturns获取IOS的ipa文件。这两个文件本质上是zip压缩包，可以直接解压，根据资源结构可以确定引擎。通过lib文件夹中的文件名确定。
4. 安装资源解包工具：AssetStudio（github找）。如果游戏用Unity开发，用工具打开assets->bin。点击Model->Export All Objects导出模型。Export->All Assets导出所有资源。这两个要分开导出。
5. 这些资源包括模型，动画，贴图，甚至shader，音效。我们可以通过这些资源逐步积累自己的资源库。

HR面

1. 自我介绍

2. 是什么让你选择游戏行业

3. 项目中最有成就感的事

4. 为什么投我们公司

5. 职业规划是什么样的

6. 对加班的看法

7. 自己有什么缺点