贪吃蛇io的实现要点

Posted on 2017-06-17

总体架构

逻辑与渲染分离。如有需要,逻辑层可被客户端和服务器公用。

移动与更新

slither.io与8bit贪吃蛇不同,它的移动是像素级的,而不是一个格子一个格子移动的。

但是如果考虑绘制时,采用的是如下方法来决定身体的节数,就会发生身体的拐点处鳞片跳变(浮点数及精度原因),以及转弯不平滑的问题。

身体长度 / 鳞片间距 = 鳞片数量

最终参考了贪吃蛇大作战的方法,蛇的最小移动速度就是鳞片的间距,具体实现如下:

逻辑层

蛇与位置相关的逻辑数据只有拐点列表,它记录了蛇的头尾和每一个拐点,使蛇身由一条条线段连接而成。

移动时,头拐点按照蛇头朝向移动一段距离,同时尾拐点缩短同样距离,如果最后一段长度不足移动距离则继续向上查找。如此更新拐点列表。

渲染层

蛇身由若干圆片组成,蛇的长度发生变化是会增删圆片,宽度变化时会改变渲染尺寸。
移动时,逻辑帧的每帧蛇移动的距离是圆片间的间距,所以将最后一个圆片移至蛇头即可。

渲染帧是高于逻辑帧的,渲染帧更新时,每个圆片以前一个圆片为目标做插值移动,这样效果会比较平滑。

碰撞检测

头部与身体碰撞

抽象碰撞模型

  1. 头部->点,身体->OBB(叉乘*4)
  2. 头部->线段,身体->线段(叉乘*2)
  3. 头部->圆,身体->线段
  4. 头部->圆,身体->OBB

算法优化

  1. 四叉树

    • 结点存储的是蛇身体各段的OBB
    • 四叉树需要不停的维护,如果量级不大,可能反而浪费时间和空间
  2. 包围盒

运算操作优化

  • 避免sqrt,直接使用平方值比较
  • 避免三角函数和除法,使用向量运算

实际开发选择了 4.头部->圆,身体->OBB 及 2.包围盒。效率没有任何问题,也就没有再进一步优化。

蛇与食物碰撞

抽象碰撞模型

  • 头部->圆,食物->圆(其中一个换成点可能也没问题)

算法优化

  1. 四叉树
  2. 平均分片

实际采用了 2.平均分片,效率就已经足够高了。

同步

  • 采用帧同步,需要同步的只有蛇的创建和玩家的操作。所有的碰撞检测,及蛇的分数,长度变化等计算全都放到客户端。

  • 游戏开始时会服务端决定随机种子,同步给各客户端。足以保证所有的随机结果是一致的(食物的随机产生,蛇的随机位置和朝向)。

  • 碰撞的结果也是各自计算,结果完全相同。(吃食物,蛇的死亡)

  • 蛇的死亡是需要通知服务器。

  • 服务器可以通过多数玩家的上报结果来简单甄别有无作弊现象。

  • 支持中途加入,加入时间越晚,需要从头计算的数据越多,即便服务器已经过滤掉已死亡的玩家数据。这部分计算只能放到loading中,否则极其影响体验。