导图社区 游戏客户端(v1.0.0)
游戏客户端
算法与数据结构
链表
单向链表
双指针法
删除倒数第K个节点
快指针先走,慢指针与快指针间隔K的距离再开始同时移动,当快指针移动到尾部后,慢指针就是倒数第K个节点
判断链表是否是环形链表
快指针每次走两步,慢指针每次走一步,如果相遇则是环形链表,如果有尽头,就不是环形链表
判断两个链表是否相交
先判断两个链表的长度,设长度排列大小为 a 、b(a>b),让最长的先移动,移动的步子为a-b。移动结束后,两个链表上的指针同时移动,对比每一个节点。若都是相等则链表相交
双向链表
二叉树
平衡二叉树
概念:一棵空树或它的左右两个子树的高度差的绝对值不超过1
红黑树
一些递归解法
二叉树的最大深度
两个二叉树是否相等
前序、中序、后序遍历
图
排序
冒泡排序
两两比较
快速排序
选择值后比较,分为大于和小于两部分,然后分别对这两部分进行选值再排序,直到排序完成
选择排序
从无序的集合中,选择最大或最小的值出来,然后再从剩下的无序集合中选择下一个最大或最小值,直到排序完无序的集合。
归并排序
思路是分治法,子序列有序后,再将有序的队列归并
四大常用算法
动态规划
回溯算法
八皇后问题
贪心算法
分治算法
归并排序有运用
网络
应用层
HTTP
传输层主要依靠TCP,需要建立TCP连接才能通信,而HTTP是无状态协议,后来引入了Cookie
HTTPS
是对HTTP的加密版本
WebSocket
是对HTTP的一次升级,保证一个长连接
FTP
文件传输协议
表示层
会话层
传输层
TCP
可靠有序、重传机制是全部重传
三次握手
为什么是三次
四次挥手
为什么是四次
UDP
面向报文,无连接,不可靠的传输层协议,主要追求一个快
KCP
实现一层可靠的机制,选择重传、保证传输速度
网络层
IP
数据链路层
物理层
计算机数学
向量
点乘
叉乘
矩阵
四元数
几何计算
2D方面
判断点是否在多边形内
面积法
射线法
多边形与多边形碰撞
凸多边形与凸多边形
分离轴定理,多边形做每条边的法向量,把两个多边形在法向量上投影,如存在不重叠部分,那就是未碰撞
凹多边形需要分割为凸多边形
四叉树
AABB
3D方面
点与线的距离
射线与三角形是否相交
主流游戏开发工具
H5方向
Cocos Creator
JSBing
把JS方法绑定到C++中去
热更新
localStorage
定制JS引擎
渲染流
LayaBox
手游、端游
Unity3D
Unreal4
物理引擎
2D物理引擎
Box2D
3D物理引擎
图形渲染
OpenGL
OpenGL ES
WebGL
DirectX
渲染管线
游戏优化
CPU
GPU
内存
游戏开发语言
JavaScript
C#
C++
Lua
XLua
其他
AI
状态机
有限状态机
为AI设定多个状态行为,通常以某些事件去触发状态的转变
行为树
结构与状态机不一样,行为树可以做更多的组合:选择执行、顺序执行、同步执行
博弈树
多了一些“思考”,对周围环境进行评估再决策。
极小极大值算法
剪枝算法
神经网络
遗传算法
模糊逻辑
同步
状态同步
主要逻辑在服务器,客户端只做输入与显示
比较好防范外挂,因为服务器的状态才是准确的,可以直接判断到哪些请求是恶意的。
比较好做断线重连,因为服务器可以选择存储游戏的状态
帧同步
主要逻辑在客户端,服务器只转发操作指令
不好防外挂,缺少一个仲裁的服务器
不好做断线重连
防外挂的手段
客户端状态哈希值,通过这个值来比较,不过这个方法适合三人及三人以上玩家
复盘检验,将指令进行模拟检验,看结果是否一样
重连的方式
Crash后重连
丢失了游戏上下文,一般需要从游戏开始的第一帧开始,服务器需要把第一帧到当前帧的所有操作数据发送
非Crash重连
服务器需要下发客户端当前帧到服务器当前帧内的所有操作指令