面经-游戏相关的一些知识
本文最后更新于:2024年9月1日 晚上
程序框架
从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是一个反向链接搜索,从要实现的目标开始,找到什么动作能实现目标,在寻找刚才动作的先决条件,一直往前推,知道达到你的当前(初始)状态。这种反向链接搜索替代了启发式的前向链接搜索。
网络同步
细谈网络同步在游戏历史中的发展变化(上) - 网易游戏雷火事业群的文章 - 知乎
细谈网络同步在游戏历史中的发展变化(中) - 网易游戏雷火事业群的文章 - 知乎
细谈网络同步在游戏历史中的发展变化(下) - 网易游戏雷火事业群的文章 - 知乎
寻路
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这里。