面经-游戏相关的一些知识
本文最后更新于：2025年1月21日 凌晨
程序框架
从Script到Code Blocks、Code Behind到MVC、MVP、MVVM
ECS
MVC
MVVM
MVP
贝塞尔曲线
一种比较简单计算并且比较自然的曲线的方式，利用插值的方式
博客教程：https://www.cnblogs.com/msxh/p/6270468.html
游戏AI
比较常见的有状态机，行为树，效用系统，目标导向
状态机
一个比较简单的改进方案是分层状态机，比如把巡逻的都放在一个大的巡逻里面
行为树
行为树是树型结构的，每个节点都代表了一个行为，每个行为都可以有子行为。
所有行为都有一个先决条件，就是产生的这些行为的条件。
整个算法先从树的根部开始，然后开始检查每一个先决条件。树的每一层只可以执行一个行为，所以当一个行为正在执行，它的兄弟节点都不会被检查，但是它们的子节点还是要检查的。相反如果一个行为的先决条件当前并不满足，则跳过判断它的子节点，继续判断它的兄弟节点。一个树全部检查完毕之后，决定执行优先级最大的，然后再依次执行每个动作。
不同于状态机，行为树是无状态的，不需要记下之前执行的行为，只是判断行为该不该执行。
行为树的节点之间是不相关的，删除或增加节点，对其他节点都无影响。所以，可扩展性也是行为树的一个优势。另外还可以为决策树添加灵活性与随机性，父节点可以随机决定是否检查子节点。
- 序列（Sequence）节点：顺序执行所有子节点返回成功，如果某个子节点失败返回失败。
- 循环（Loop）节点：循环执行子节点到指定次数后返回成功，如果循环次数为-1，则无限循环。
- 条件（Condition）节点：根据条件的比较结果，返回成功或失败。
- 动作（Action）节点：根据动作结果返回成功，失败，或运行。
- 等待（Wait）节点：当指定的时间过去后返回成功。
效用系统
所以有些情况，只是做这些布尔判断是不合适的，会遗漏很多情况，判断也不妥当。比如：我们可能需要同时考虑与敌人的距离、有多少弹药、饥饿程度、HP值，等等。这些判断条件能映射出许多动作，比我们单一的判断做不做这个动作要好很多。utility-based system，基于效用的系统，会根据权重、比率、队列和许多需要考虑的事项来做出最优选择，使AI比普通的行为树更有头脑。根据上面的例子，使用效用系统我们的AI可以做出我们想要的动作，并根据当前情况做出不同强度的动作，使AI真实、更具可能性，也不再是只有一个正确的选择了。决策树就是对AI说，“只是你将要做的一个行为”，效用系统就是对AI说：“这些是你可能要做的行为”
目标导向型
GOAP来源于STRIPS方法，这两种都是让AI创造他们自己的方法去解决问题，我们提供给它一系列可能的动作作为对这个世界的描述，和每个动作使用的先决条件，和行动带来的影响。AI拥有一个初始状态和他需要达到的目标。有一组目标，AI可以通过优先级或当前状态选择一个。计划系统决定一个动作序列来满足当前目标，计划出一个像路径一样的能最简单达到目标状态的动作序列。
GOAP是一个反向链接搜索，从要实现的目标开始，找到什么动作能实现目标，在寻找刚才动作的先决条件，一直往前推，知道达到你的当前（初始）状态。这种反向链接搜索替代了启发式的前向链接搜索。
网络同步
细谈网络同步在游戏历史中的发展变化（上） - 网易游戏雷火事业群的文章 - 知乎
细谈网络同步在游戏历史中的发展变化（中） - 网易游戏雷火事业群的文章 - 知乎
细谈网络同步在游戏历史中的发展变化（下） - 网易游戏雷火事业群的文章 - 知乎
帧同步如何要实现什么东西
确定性的数学和物理运算框架
计算逻辑采用定点数
逻辑层表现层分离，表现层可以浮点数
可靠UDP
UDP加冗余包来保证可靠性
断线重连
比赛回放
反作弊
寻路
A*
描述一下A*算法
- 把起点加入 open list 。
- 重复如下过程：
a. 遍历 open list ，查找 F 值最小的节点，把它作为当前要处理的节点。
b. 把这个节点移到 close list 。
c. 对当前方格的 8 个相邻方格的每一个方格？
◆ 如果它是不可抵达的或者它在 close list 中，忽略它。否则，做如下操作。
◆ 如果它不在 open list 中，把它加入 open list ，并且把当前方格设置为它的父亲，记录该方格的 F ， G 和 H 值。
◆ 如果它已经在 open list 中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更好，用 G 值作参考。更小的 G 值表示这是更好的路径。如果是这样，把它的父亲设置为当前方格，并重新计算它的 G 和 F 值。如果你的 open list 是按 F 值排序的话，改变后你可能需要重新排序。
d. 停止条件
◆ 把终点加入到了 open list 中，此时路径已经找到了，或者
◆ 查找终点失败，并且 open list 是空的，此时没有路径。
- 保存路径。从终点开始，每个方格沿着父节点移动直至起点，这就是你的路径。
F = G + H
这里，
G = 从起点 A 移动到指定方格的移动代价，沿着到达该方格而生成的路径。
H = 从指定的方格移动到终点 B 的估算成本。这个通常被称为试探法，有点让人混淆。为什么这么叫呢，因为这是个猜测。直到我们找到了路径我们才会知道真正的距离，因为途中有各种各样的东西 ( 比如墙壁，水等 ) 。
openlist和closelist的作用？
openlist就是还要搜索的列表，相比于dfs的盲目搜索更加有效率，
closelist就是已经搜过的或者不可搜的节点，加速过程。
红点系统
Unity手游实战：从0开始SLG——独立功能扩展（三）用树实现客户端红点系统 - 放牛的星星的文章 - 知乎
规划红点系统的时候，我们将整个系统分为独立的三个部分：结构层、驱动层和表现层。
结构层用来部署红点的层级结构，使用树结构。
驱动层是指，如何驱动这个树结构产生状态变化，以及状态变化之后如何将变化的行为通知到指定的表现层，在一定的程度上将数据和表现分离开。
表现层就专门承担表现的职责，比如有的红点就是一个单纯的红点，有的需要显示数字，有的可能是图标晃动，有的是显示new标签，有的是播放特效等等。这些都可以归属在表现层统一去管控。
设计模式
【游戏设计模式】之四 《游戏编程模式》全书内容提炼总结 - 毛星云的文章 - 知乎
要结合项目中能用到的东西来记忆
一、常用GOF设计模式
1.命令模式
2.享元模式
3.观察者模式
4.原型模式
5.单例模式
6.状态模式
二、序列型模式
7.双缓冲模式
8.游戏循环
9.更新方法
三、行为型模式
10.字节码
11.子类沙箱
12.类型对象
四、解耦型模式
这个更加像是写代码的方法论。
13.组件模式
14.事件队列
15.服务定位器
五、优化型模式
这个可能更偏向于应用。
16.数据局部性
17.脏标识模式
有一些更新很需要花时间的数据，每次循环的时候，加一个标志，如果没有改变就不tick这里。
18.对象池模式
19.空间分区
避障算法
ORCA