WHCSRL 技术网

客户端游戏开发——2021年面经02

        作者经过面试国内大大小小的游戏公司面试,经过有十几次的面试,最终也拿到了自己心仪的offer。期间不断总结积累下来的面试经验,希望能够对大家有所帮助~

26,什么是垃圾,什么需要GC

        一个就是值类型,另一个就是引用类型。前者是分配在栈上,并不需要GC回收;后者是分配在堆上,因此它的内存释放和回收需要通过GC来完成。GC的全称为“Garbage Collector”,顾名思义就是垃圾回收器,那么只有被称为垃圾的对象才能被GC回收。也就是说,一个引用类型对象所占用的内存需要被GC回收,需要先成为垃圾。那么.Net如何判定一个引用类型对象是垃圾呢,.Net的判断很简单,只要判定此对象或者其包含的子对象没有任何引用是有效的(引用计数为0),那么系统就认为它是垃圾。

        对于内存中的垃圾分为两种,一种是需要调用对象的析构函数,另一种是不需要调用的。

        前者回收步骤,第一步是调用对象的析构函数,第二步是回收内存,但是要注意这两步不是在GC一次轮循完成,即需要两次轮循;

        后者回收步骤,则只是回收内存而已。

简单了解:

Lua的gc:(详情看:云风的 BLOG: Lua GC 的工作原理

在 Lua 5.0 以前,Lua 使用的是一个非常简单的标记扫描算法。它从根集开始遍历对象,把能遍历到的对象标记为活对象;然后再遍历通过分配器分配出来的对象全集链表,把没有标记为活对象的其它对象都删除。

但是,Lua 5.0 支持 userdata ,它可以有 __gc 方法,当 userdata 被回收时,会调用这个方法。所以,一遍标记是不够的,不能简单的把死掉的 userdata 简单剔除,那样就无法正确的调用 __gc 了。所以标记流程需要分两个阶段做,第一阶段把包括 userdata 在内的死对象剔除出去,然后在死对象中找回有 __gc 方法的,对它们再做一次标记复活相关的对象,这样才能保证 userdata 的 __gc 可以正确运行。执行完 __gc 的 userdata 最终会在下一轮 gc 中释放(如果没有在 __gc 中复活)。 userdata 有一个单向标记,标记 __gc 方法是否有运行过,这可以保证 userdata 的 __gc 只会执行一次,即使在 __gc 中复活(重新被根集引用),也不会再次分离出来反复运行 finalizer 。也就是说,运行过 finalizer 的 userdata 就永久变成了一个没有 finalizer 的 userdata 了。

GC 的性能表现对整个系统的性能表现影响重大。Go 语言早期就是因为 GC 问题而饱受诟病。如果我们把 GC 关闭,那么 CPU 就完全没有额外开销,但是会有极大的内存开销;如果我们每次分配新对象都运行一遍 GC ,那么就不会有任何额外的内存开销,但是 CPU 开销会完全不可接受(现在 Lua 保留着一个宏开关,可以不停的运行完整的 GC ,用来测试 GC 实现的正确性)。Lua 5.0 采用的是一个折中的方案:每当内存分配总量超过上次 GC 后的两倍,就跑一遍新的 GC 流程。但 Lua 5.0 这种会把整个虚拟机都停下来的 (Stop the World )的简单粗暴的 GC 实现,在实践中的问题非常明显,这导致 Lua 5.0 成为一个分水岭。5.0 之前的 Lua 多用于内嵌脚本,只充当系统中的底层模块间的粘合剂,而之后解决了大部分的 GC 停顿问题后,人们才逐渐让 Lua 承担更多工作。

从 Lua 5.1 开始,Lua 实现了一个步进式垃圾收集器。这个新的垃圾收集器会在虚拟机的正常指令逻辑间交错分布运行,尽量把每步的执行时间减到合理的范围。

一旦 GC 不能一次完成,它就无法把整个虚拟机看成一块静态数据加以分析。那么怎么办呢?我们就要借助 Mutator 模式 。只要我们把所有对象的修改都监控起来,从垃圾收集器的角度来看,程序就只是一段段在修改它需要去回收的数据的东西,它不用管程序到底执行了什么,只要知道什么时候修改了什么。

Lua 5.1 采用了一种三色标记的算法。每个对象都有三个状态:无法被访问到的对象是白色,可访问到,但没有递归扫描完全的对象是灰色,完全扫描过的对象是黑色。

我们将对象分为青年的和年老的两代,新创建出来的对象一律归为青年代,一旦年轻的对象经历了两轮收集周期而依旧健在,他们就成长为老年对象。在每个次级收集周期,收集器只对青年代的对象进行遍历清除工作。这样就避免了每次都遍历大量并不活跃却长期存活的老年对象,又可以及时清理掉大量生命短暂的青年对象。

次级收集周期越密集,单个周期内的青年对象数量就越少,需要做的工作也越少,停顿时间也就缩小了。可见增加收集周期并不会太多的增加整体工作量,却可以更及时的回收内存;而相对于之前的算法,增加收集周期则意味了更多的工作(因为每个周期都需要遍历所有的对象)。

这里为什么强调是两个次级收集周期而不是单个?这就要提到 Lua 5.2 所犯的错误。Lua 5.2 的分代 GC 算法中,就只针对单个次级收集周期处理。任何对象活过当前的收集周期,就会变老。这样处理固然简单,但有极大的问题。如果一个对象刚刚被创建出来,次级收集过程就开启了,它很容易就活过这个周期(例如函数尚未返回,刚在堆栈上创建出来的对象就不能回收),这个对象就迅速变老了。这种本该随即回收的对象未被回收的越多,并不老的老对象增多会进一步增加中间状态的对象数量,次级收集过程能收集的临时对象更少。

29,解释一下什么是 promise ?

【参考答案】

promise是js中的一个对象,用于生成可能在将来产生结果的值。 值可以是已解析的值,也可以是说明为什么未解析该值的原因。

promise 可以有三种状态:

pending:初始状态,既不是成功也不是失败

fulfilled:意味着操作完全成功

rejected:意味着操作失败

一个等待状态的promise对象能够成功后返回一个值,也能失败后带回一个错误

当这两种情况发生的时候,处理函数会排队执行通过then方法会被调用。

常用于处理异步问题。

31,es5 => es6带来的新特性

43. https 和 http 的区别

【已知】

SSL:(Secure Socket Layer,安全套接字层),位于可靠的面向连接的网络层协议和应用层协议之间的一种协议层。SSL通过互相认证、使用数字签名确保完整性、使用加密确保私密性,以实现客户端和服务器之间的安全通讯。该协议由两层组成:SSL记录协议和SSL握手协议。

TLS:(Transport Layer Security,传输层安全协议),用于两个应用程序之间提供保密性和数据完整性。该协议由两层组成:TLS记录协议和TLS握手协议。

【答】

        超文本传输协议HTTP协议被用于在Web浏览器和网站服务器之间传递信息,HTTP协议以明文方式发送内容,不提供任何方式的数据加密,如果攻击者截取了Web浏览器和网站服务器之间的传输报文,就可以直接读懂其中的信息,因此,HTTP协议不适合传输一些敏感信息,比如:信用卡号、密码等支付信息。

        为了解决HTTP协议的这一缺陷,需要使用另一种协议:安全套接字层超文本传输协议HTTPS,为了数据传输的安全,HTTPS在HTTP的基础上加入了SSL/TLS协议,SSL/TLS依靠证书来验证服务器的身份,并为浏览器和服务器之间的通信加密。

        HTTPS协议是由SSL/TLS+HTTP协议构建的可进行加密传输、身份认证的网络协议,要比http协议安全

        HTTPS协议的主要作用可以分为两种:一种是建立一个信息安全通道,来保证数据传输的安全;另一种就是确认网站的真实性。

44.TCP的三次握手过程;Tcp建立连接为什么是3次握手?关闭连接为什么是四次?

三次握手的过程

step1:第一次握手

建立连接时,客户端发送SYN包到服务器,其中包含客户端的初始序号seq=x,并进入SYN_SENT状态,等待服务器确认。(其中,SYN=1,ACK=0,表示这是一个TCP连接请求数据报文;序号seq=x,表明传输数据时的第一个数据字节的序号是x)。

step2:第二次握手

服务器收到请求后,必须确认客户的数据包。同时自己也发送一个SYN包,即SYN+ACK包,此时服务器进入SYN_RECV状态。(其中确认报文段中,标识位SYN=1,ACK=1,表示这是一个TCP连接响应数据报文,并含服务端的初始序号seq(服务器)=y,以及服务器对客户端初始序号的确认号ack(服务器)=seq(客户端)+1=x+1)。

step3:第三次握手

客户端收到服务器的SYN+ACK包,向服务器发送一个序列号(seq=x+1),确认号为ack(客户端)=y+1,此包发送完毕,客户端和服务器进入ESTAB_LISHED(TCP连接成功)状态,完成三次握手。

未连接队列

在三次握手协议中,服务器维护一个未连接队列,该队列为每个客户端的SYN包(syn=j)开设一个条目,该条目表明服务器已收到SYN包,并向客户发出确认,正在等待客户的确认包时,删除该条目,服务器进入ESTAB_LISHED状态。

常见面试题:

1.为什么需要三次握手,两次不可以吗?或者四次、五次可以吗?

我们来分析一种特殊情况,假设客户端请求建立连接,发给服务器SYN包等待服务器确认,服务器收到确认后,如果是两次握手,假设服务器给客户端在第二次握手时发送数据,数据从服务器发出,服务器认为连接已经建立,但在发送数据的过程中数据丢失,客户端认为连接没有建立,会进行重传。假设每次发送的数据一直在丢失,客户端一直SYN,服务器就会产生多个无效连接,占用资源,这个时候服务器可能会挂掉。这个现象就是我们听过的“SYN的洪水攻击”。

总结:第三次握手是为了防止:如果客户端迟迟没有收到服务器返回确认报文,这时会放弃连接,重新启动一条连接请求,但问题是:服务器不知道客户端没有收到,所以他会收到两个连接,浪费连接开销。如果每次都是这样,就会浪费多个连接开销。

四次挥手过程(关闭客户端到服务器的连接)

step1:第一次挥手

首先,客户端发送一个FIN,用来关闭客户端到服务器的数据传送,然后等待服务器的确认。其中终止标志位FIN=1,序列号seq=u。

step2:第二次挥手

服务器收到这个FIN,它发送一个ACK,确认ack为收到的序号加一。

step3:第三次挥手

关闭服务器到客户端的连接,发送一个FIN给客户端。

step4:第四次挥手

客户端收到FIN后,并发回一个ACK报文确认,并将确认序号seq设置为收到序号加一。首先进行关闭的一方将执行主动关闭,而另一方执行被动关闭。

客户端发送FIN后,进入终止等待状态,服务器收到客户端连接释放报文段后,就立即给客户端发送确认,服务器就进入CLOSE_WAIT状态,此时TCP服务器进程就通知高层应用进程,因而从客户端到服务器的连接就释放了。此时是“半关闭状态”,即客户端不可以发送给服务器,服务器可以发送给客户端。

此时,如果服务器没有数据报发送给客户端,其应用程序就通知TCP释放连接,然后发送给客户端连接释放数据报,并等待确认。客户端发送确认后,进入TIME_WAIT状态,但是此时TCP连接还没有释放,然后经过等待计时器设置的2MSL后,才进入到CLOSE状态。

2.为什么需要2MSL时间?

首先,MSL即Maximum Segment Lifetime,就是最大报文生存时间,是任何报文在网络上的存在的最长时间,超过这个时间报文将被丢弃。《TCP/IP详解》中是这样描述的:MSL是任何报文段被丢弃前在网络内的最长时间。RFC 793中规定MSL为2分钟,实际应用中常用的是30秒、1分钟、2分钟等。

TCP的TIME_WAIT需要等待2MSL,当TCP的一端发起主动关闭,三次挥手完成后发送第四次挥手的ACK包后就进入这个状态,等待2MSL时间主要目的是:防止最后一个ACK包对方没有收到,那么对方在超时后将重发第三次握手的FIN包,主动关闭端接到重发的FIN包后可以再发一个ACK应答包。在TIME_WAIT状态时两端的端口不能使用,要等到2MSL时间结束才可以继续使用。当连接处于2MSL等待阶段时任何迟到的报文段都将被丢弃。

3.为什么是四次挥手,而不是三次或是五次、六次?

双方关闭连接要经过双方都同意。所以,首先是客服端给服务器发送FIN,要求关闭连接,服务器收到后会发送一个ACK进行确认。服务器然后再发送一个FIN,客户端发送ACK确认,并进入TIME_WAIT状态。等待2MSL后自动关闭。

总结:

(1)为了保证客户端发送的最后一个ACK报文段能够到达服务器。即最后一个确认报文可能丢失,服务器会超时重传,然后服务器发送FIN请求关闭连接,客户端发送ACK确认。一个来回是两个报文生命周期。

如果没有等待时间,发送完确认报文段就立即释放连接的话,服务器就无法重传,因此也就收不到确认,就无法按步骤进入CLOSE状态,即必须收到确认才能close。

(2)防止已经失效的连接请求报文出现在连接中。经过2MSL,在这个连续持续的时间内,产生的所有报文段就可以都从网络消失。

45.Get和Post区别

  1. Get是不安全的,因为在传输过程,数据被放在请求的URL中;Post的所有操作对用户来说都是不可见的。
  2. Get传送的数据量较小,这主要是因为受URL长度限制;Post传送的数据量较大,一般被默认为不受限制。
  3. Get限制Form表单的数据集的值必须为ASCII字符;而Post支持整个ISO10646字符集。
  4. Get执行效率却比Post方法好。Get是form提交的默认方法。
  5. GET产生一个TCP数据包;POST产生两个TCP数据包。(非必然,客户端可灵活决定)

46.Http请求的完全过程

  1. 浏览器根据域名解析IP地址(DNS),并查DNS缓存
  2. 浏览器与WEB服务器建立一个TCP连接
  3. 浏览器给WEB服务器发送一个HTTP请求(GET/POST):一个HTTP请求报文由请求行(request line)、请求头部(headers)、空行(blank line)和请求数据(request body)4个部分组成。
  4. 服务端响应HTTP响应报文,报文由状态行(status line)、相应头部(headers)、空行(blank line)和响应数据(response body)4个部分组成。
  5. 浏览器解析渲染

47.计算机网络的五层模型

  1. 应用层:为操作系统或网络应用程序提供访问网络服务的接口 ,通过应用进程间的交互完成特定网络应用。应用层定义的是应用进程间通信和交互的规则。(HTTP,FTP,SMTP,RPC)
  2. 传输层:负责向两个主机中进程之间的通信提供通用数据服务。(TCP,UDP)
  3. 网络层:负责对数据包进行路由选择和存储转发。(IP,ICMP(ping命令))
  4. 数据链路层:两个相邻节点之间传送数据时,数据链路层将网络层交下来的IP数据报组装成帧,在两个相邻的链路上传送帧(frame)。每一帧包括数据和必要的控制信息。
  5. 物理层:物理层所传数据单位是比特(bit)。物理层要考虑用多大的电压代表1 或 0 ,以及接受方如何识别发送方所发送的比特。

48.tcp和udp区别

  1. TCP面向连接,UDP是无连接的,即发送数据之前不需要建立连接。
  2. TCP提供可靠的服务。也就是说,通过TCP连接传送的数据,无差错,不丢失,不重复,且按序到达;UDP尽最大努力交付,即不保证可靠交付。
  3. TCP面向字节流,实际上是TCP把数据看成一连串无结构的字节流,UDP是面向报文的,UDP没有拥塞控制,因此网络出现拥塞不会使源主机的发送速率降低(对实时应用很有用,如IP电话,实时视频会议等)
  4. 每一条TCP连接只能是点到点的,UDP支持一对一,一对多,多对一和多对多的交互通信。
  5. TCP首部开销20字节,UDP的首部开销小,只有8个字节。
  6. TCP的逻辑通信信道是全双工的可靠信道,UDP则是不可靠信道。

49.tcp和udp的优点

  • TCP的优点: 可靠,稳定 TCP的可靠体现在TCP在传递数据之前,会有三次握手来建立连接,而且在数据传递时,有确认、窗口、重传、拥塞控制机制,在数据传完后,还会断开连接用来节约系统资源。 TCP的缺点: 慢,效率低,占用系统资源高,易被攻击 TCP在传递数据之前,要先建连接,这会消耗时间,而且在数据传递时,确认机制、重传机制、拥塞控制机制等都会消耗大量的时间,而且要在每台设备上维护所有的传输连接,事实上,每个连接都会占用系统的CPU、内存等硬件资源。 而且,因为TCP有确认机制、三次握手机制,这些也导致TCP容易被人利用,实现DOS、DDOS、CC等攻击。
  • UDP的优点: 快,比TCP稍安全 UDP没有TCP的握手、确认、窗口、重传、拥塞控制等机制,UDP是一个无状态的传输协议,所以它在传递数据时非常快。没有TCP的这些机制,UDP较TCP被攻击者利用的漏洞就要少一些。但UDP也是无法避免攻击的,比如:UDP Flood攻击…… UDP的缺点: 不可靠,不稳定 因为UDP没有TCP那些可靠的机制,在数据传递时,如果网络质量不好,就会很容易丢包。 基于上面的优缺点,那么: 什么时候应该使用TCP: 当对网络通讯质量有要求的时候,比如:整个数据要准确无误的传递给对方,这往往用于一些要求可靠的应用,比如HTTP、HTTPS、FTP等传输文件的协议,POP、SMTP等邮件传输的协议。 在日常生活中,常见使用TCP协议的应用如下: 浏览器,用的HTTP FlashFXP,用的FTP Outlook,用的POP、SMTP Putty,用的Telnet、SSH QQ文件传输。什么时候应该使用UDP: 当对网络通讯质量要求不高的时候,要求网络通讯速度能尽量的快,这时就可以使用UDP。 比如,日常生活中,常见使用UDP协
  • 议的应用如下: QQ语音 QQ视频 TFTP。

50.设计模式

单例模式:单例对象的类必须保证只有一个实例存在,整个系统只能使用一个对象实例。

简单工厂模式:简单工厂模式又叫静态工厂方法模式,就是建立一个工厂类,对实现了同一接口的一些类进行实例的创建。

抽象工厂模式:抽象工厂模式是在简单工厂的基础上将未来可能需要修改的代码抽象出来,通过继承的方式让子类去做决定。

观察者模式:观察者模式是定义对象间的一种一对多依赖关系,使得每当一个对象状态发生改变时,其相关依赖对象皆得到通知并被自动更新。观察者模式又叫做发布-订阅(Publish/Subscribe)模式、模型-视图(Model/View)模式、源-监听器(Source/Listener)模式或从属者(Dependents)模式

装饰器模式:装饰器模式是指动态地给一个对象增加一些额外的功能,同时又不改变其结构。

模板方法模式:模板方法模式是指定义一个模板结构,将具体内容延迟到子类去实现。

代理模式:代理模式是给某一个对象提供一个代理,并由代理对象控制对原对象的引用。

策略模式:策略模式是指定义一系列算法,将每个算法都封装起来,并且使他们之间可以相互替换。

适配器模式:适配器模式是将一个类的接口变成客户端所期望的另一种接口,从而使原本因接口不匹配而无法一起工作的两个类能够在一起工作。

51.A*寻路算法:

开表,记录了当前需要处理的地图上的点。

1什么点会加入开表?

1.1    当一个点是起始点时,可以加入;

1.2    当一个点是起始点的邻接点,且不再闭表里时,可以进入开表;

2什么点会离开开表?

2.1开表中的点会按照f(n)进行升序排序,得到最小值的一个点被最先处理;当一个点已经处理后,会离开开表,加入闭表。

闭表,记录了当前已经处理的地图上的点。

1什么点会加入闭表?

1.1当一个点已经处理后,会加入闭表;

2什么点会离开闭表?

不会有点离开闭表。

估值函数

估值函数,估算了当前点处于最优路径上的代价。

估值函数f(n) = g(n) + h(n),其中g(n)表示由起点到当前点的代价;h(n)表示由当前点到终点的代价。A*算法的最核心部分也就是这个估值函数的设计。

在我的实现中,我用简单的几何距离作为估值函数的实现。

算法描述

1将起点加入开表

2开表里如果为空,算法退出;否则,取出f(n)最小的点作为最优路径上的点;

3针对当前处理的点,计算邻接点,如果邻接点不在闭表,且不在开表,加入开表

4重复2,3步骤直到退出

52.帧同步与状态同步的区别

实时游戏发展迅猛,同步技术也逐渐成为解决方案的核心之一。 本文简单讨论了帧同步和状态同步。

帧同步

什么是帧同步:帧同步常被RTS(即时战略)游戏常采用。在游戏中同步的是玩家的操作指令,操作指令包含当前的帧索引。一般的流程是客户端上传操作到服务器, 服务器收到后并不计算游戏行为, 而是转发到所有客户端。这里最重要的概念就是 相同的输入 + 相同的时机 = 相同的输出。

实现帧同步的流程一般是:

同步随机数种子。(一般游戏中都设计随机数的使用, 通过同步随机数种子,可以保持随机数一致性)

客户端上传操作指令。(指令包括游戏操作和当前帧索引)

服务器广播所有客户端的操作。(如果没有操作, 也要广播空指令来驱动游戏帧前进)。

因为帧同步的特性, 我们可以很方便的做出战斗回放:服务器记录所有操作, 客户端请求到操作文件再执行一次即可。

帧同步的特性导致客户端的逻辑实现和表现实现必须完全分离。Unity中的一些方法接口(如 Invoke, Update、动画系统等)是不可靠的,所有要自己实现一套物理引擎、数学库,做到逻辑和表现分离。 这样即使Unity的渲染是不同步的,但是逻辑跑出来是同步的。

我曾经参与过一个飞机类弹幕游戏的项目,它的同步方案就是帧同步, 可以完美的播放回放, 并实现服务器上加速验算。

状态同步

什么是状态同步:同步的是游戏中的各种状态。一般的流程是客户端上传操作到服务器,服务器收到后计算游戏行为的结果,然后以广播的方式下发游戏中各种状态,客户端收到状态后再根据状态显示内容。状态同步最广泛的应用应该是在回合制游戏中。

状态同步其实是一种不严谨的同步。它的思想中,不同玩家屏幕上的表现的一致性并不是重要指标, 只要每次操作的结果相同即可。所以状态同步对网络延迟的要求并不高。像玩RPG游戏,200-300ms的延迟也可以接受。 但是在RTS游戏中,50ms的延迟也会很受伤。

举个移动的例子,在状态同步中, 客户端甲上操作要求从A点移动到B点,但在客户端乙上, 甲对象从A移动到C,然后从C点移动到了B。这是因为, 客户端乙收到A的移动状态时, 已经经过了一个延迟。这个过程中,需要客户端乙本地做一些平滑的处理,最终达到移动到B点的结果。

所以国产RPG游戏中,动画的特效一般做的比较绚丽(大), 攻击的时候给人感觉是击中了。放技能之前一般也有一个动画前摇,同时将攻击请求提交给服务器。等服务器结果返回时,动画也播放完毕了,之后就是统一的伤害效果和结算。

状态同步和帧同步的比较和选择:

对比如下

选择:对于单位比较多的即时策略游戏,帧同步是很好的选择。反过来,如果玩家比较多,状态同步更合适,安全性更高。


重要的事情:

最后,肯定会问一下以前的 项目难题以及解决方案,这个就要靠大家自己总结啦~

最后,肯定会问一下以前的 项目难题以及解决方案,这个就要靠大家自己总结啦~

最后,肯定会问一下以前的 项目难题以及解决方案,这个就要靠大家自己总结啦~

推荐阅读