分类目录归档:游戏开发

那些中古游戏的技术(一)

概述

最近看到了一个非常有趣的东西,pico-8,这个小引擎模拟了70-80年代的机器性能,并提供了一个非常不错的编辑平台,包括了代码编辑器,地图编辑器,像素绘制器,甚至有音乐编辑器。开发者可以直接打开这个编辑器进行lua代码编写,因为引擎支持的技术比较久远,所以可以看到贡献者的游戏都是模拟中古时代的游戏,比如pacman,fc赛车等,另外由于卡带本身是文本格式,所以可以直接阅读贡献者代码,从中可以学习到不少东西。

扯回正题,正因为我看到了不少有趣的游戏,所以想整理下那些中古优秀游戏中,那些古老而精巧的技术。

光线投射(Raycasting)

介绍

由于早期的硬件性能限制,光线投是首个用来制作实时3d环境的技术手段,比如如下的 Wolfenstein 3D

image

需要注意的是光线投射不同于光线追踪(raytracing),光线追踪是用来生成真实的三维环境,有反射,阴影。而光线投射是一种廉价的实时半3d解决方案。

基本思路

游戏地图由2d的方格组成,每个方格可以是0(无障碍)或者是其他正值(代表不同的墙的材质)。

然后遍历屏幕的每个x坐标(即屏幕的每个垂直条纹),从相机的当前位置(玩家)发射一个射线,方向为玩家的视野角度和x坐标,然后计算射线击中墙壁的距离,通过这个距离可以计算墙壁渲染高度,这个距离越小,则渲染高度越高。

下图是一个顶视图,绿点代表玩家,红线代表两条射线,蓝色代表墙。

image

人类可以一眼就看出射线与墙的相交点,而计算机不太可能通过一个简单的公式就能得出射线与哪个方格相交了, 因为计算机只能检测有限数量的位置(实际上本文中的这句话不太特别准确),许多光线投射每个步数检测一定的常量距离,但是这有很大的概率错过某个墙,比如下图。

image

计算机错过了一个明显的蓝色墙。因为计算机只对红色点进行检测,就算你缩短检测间距,也不过让这个概率更低而已,我们需要更好的方法来解决这个问题。

image

这个更好的办法就是检查射线会遇到的每个墙的边。这样的话每个步进就不是一个常数,他取决于与下一个边的距离。

image

从上图可见,射线碰到了我们期望的墙,而不是传过去了。我们在这里指出的这个算法,其实是基于DDA(Digital Differential Analysis 数值微分法),DDA是一个快速的算法,一般是用来找出一条线经过了哪些方格,所以我们也可以用来找出射线击中了哪个方格,当一个墙的方格命中的时候,就停止该算法。

我们在提下相机的部分

image

由于这个游戏中的相机只能左右移动,所以可以将3d的相机行为直接做成一个简单的2d顶视图,绿色的点代表玩家当前位置,蓝色的线代表相机平面,平面的矢量朝右,所以右边蓝色的点为pos+dir+plane,黑色的点为pos+dir。

红色的线代表一些射线,这些射线矢量是很容易计算的,比如图上的第三条射线大约在右屏幕三分之一,那么这个矢量则为pos+dir+plane*1/3,得到这个矢量之后,通过他的xy分量就可以拿去DDA算法中使用了。

外部的两个边线为fov,即视角,这个很容易理解,我就不做翻译了。

对于这个游戏的相机来说,还有一个行为需要考虑,那就是旋转,旋转的话也比较容易,直接乘以一个旋转矩阵即可。

[ cos(a) -sin(a) ]
[ sin(a)  cos(a) ]

代码解析和详细介绍

未贴入纹理的光线投射器

下载源码

从最简单的平面着色开始,代码中还包含了fps计数和基本输入(转向和移动) 地图的组成是一个2d数组,每个值代表一个方格,如果值为0,代表这个方格什么都没有,可行走,如果大于0,则代表某一个类型的墙,目前地图的大小比较小,仅24×24大小的方格,但是作为样例来看已经足够了,在真实的商业游戏中,比如Wolfenstein 3D,远比这个大得多,一般也都是从外部文件中读取。 在本样例中,0代表空地, 1代表墙, 2代表一个小房间, 3代表一个柱子, 4代表走廊,具体代码如下。

#define mapWidth 24
#define mapHeight 24

int worldMap[mapWidth][mapHeight]=
{
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,2,2,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,3,0,0,0,3,0,0,0,1},
  {1,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,2,2,0,2,2,0,0,0,0,3,0,3,0,3,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,0,0,0,5,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,4,4,4,4,4,4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
  {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
};

另外我们还需要定义一些变量,posX,posY代表玩家的位置矢量,dirX,dirY代表玩家的朝向矢量,planeX, planeY代表相机平面矢量,相机平面必须保证垂直于玩家朝向。相机平面矢量的大小与玩家朝向矢量的大小由FOV决定,目前设置的FOV为66°,这个是一个常见的FPS游戏的FOV大小,键盘的左右可以用来旋转玩家朝向,但是相机平面的矢量必须保证同样垂直于朝向。

time还有oldTime用来存储当前帧以及上一帧的时间,主要用来计算FPS及用来计算每帧位移。

int main(int /*argc*/, char */*argv*/[])
{
  double posX = 22, posY = 12;  //x and y start position
  double dirX = -1, dirY = 0; //initial direction vector
  double planeX = 0, planeY = 0.66; //the 2d raycaster version of camera plane

  double time = 0; //time of current frame
  double oldTime = 0; //time of previous frame

main函数剩余的部分是定义屏幕的分辨率,由于是遍历了每个竖向的屏幕,所以分辨率越大,则运行越慢。

screen(512, 384, 0, "Raycaster");

屏幕设置完毕后,游戏循环开始,在循环里面将会读取每帧输入及绘制每帧输出。

while(!done())
  {

接下来看是光线投射的部分,光线投射的循环是遍历所有的竖线,而不是屏幕的所有像素,所以遍历的压力会小得多,在处理光线投射逻辑前,我们需要定义一些变量。 rayPos代表射线起始位置,初始设置在玩家的位置

cameraX代表相机平面(即屏幕)的x坐标,屏幕最右边坐标值为1, 中间坐标值为0,左边坐标值为-1,按照上面的计算思路,射线的方向矢量则为玩家朝向矢量加上相机平面矢量的部分。

for(int x = 0; x < w; x++)
    {
      //calculate ray position and direction
      double cameraX = 2 * x / double(w) - 1; //x-coordinate in camera space
      double rayPosX = posX;
      double rayPosY = posY;
      double rayDirX = dirX + planeX * cameraX;
      double rayDirY = dirY + planeY * cameraX;

下一部分代码将会将之前说的DDA算法更加的深入编写。

mapX,mapY代表射线当前的方格位置,射线的位置是一个浮点型,而现在的mapX和mapY仅仅是作为一个方格坐标。

sideDistX和sideDistY初始化为射线起点到第一个x边和第一个y边的距离。

deltaDistX代表着第一个x边到下一个x边的距离,deltaDistY同理。

下图为这两个变量做了一个明确的图示。

image

perpWallDist待会会用来计算射线长度

DDA算法每次循环会跳过一个方格,不管方格是在x方向还是y方向,所以定义了两个变量stepX和stepY,这两个变量不是1就是-1。

最后hit变量用来标记循环结束后是否有命中。side变量用来标示命中的是x边还是y边,0代表x,1代表y

//which box of the map we're in
      int mapX = int(rayPosX);
      int mapY = int(rayPosY);

      //length of ray from current position to next x or y-side
      double sideDistX;
      double sideDistY;

       //length of ray from one x or y-side to next x or y-side
       // x/y = 1/y' => y' = y/x
       // so deltaDistX = sqrt(1^2 + y'^2)
      double deltaDistX = sqrt(1 + (rayDirY * rayDirY) / (rayDirX * rayDirX));
      double deltaDistY = sqrt(1 + (rayDirX * rayDirX) / (rayDirY * rayDirY));
      double perpWallDist;

      //what direction to step in x or y-direction (either +1 or -1)
      int stepX;
      int stepY;

      int hit = 0; //was there a wall hit?
      int side; //was a NS or a EW wall hit?

在DDA算法开始前,需要预先计算stepX,stepY,sideDistX,sideDistY

当射线方向为负的x分量时,stepX为-1, 反之为1,如果x分量为0时,则不使用stepX分量,y分量同理。

如果射线方向为负的x分量,则sideDistX为起始点到左边的第一个边,如果是正的x分量,则为右边的第一个边。

由于三角形的等比关系,则可算出sideDistX的值,sideDistY同理。

//calculate step and initial sideDist
      if (rayDirX < 0)
      {
        stepX = -1;
        sideDistX = (rayPosX - mapX) * deltaDistX;
      }
      else
      {
        stepX = 1;
        sideDistX = (mapX + 1.0 - rayPosX) * deltaDistX;
      }
      if (rayDirY < 0)
      {
        stepY = -1;
        sideDistY = (rayPosY - mapY) * deltaDistY;
      }
      else
      {
        stepY = 1;
        sideDistY = (mapY + 1.0 - rayPosY) * deltaDistY;
      }

接下来我们进入实际的DDA流程,循环中会每次循环进行一个方格的判断,我们通过sideDistX和sideDistY的大小判断下次应该判断的是x方向的下一个方格,还是y方向的下一个方格,并递增mapX和sideDistX,如果mapX,mapY对应的格子大于零,则判断击中,退出循环。

//perform DDA
      while (hit == 0)
      {
        //jump to next map square, OR in x-direction, OR in y-direction
        if (sideDistX < sideDistY)
        {
          sideDistX += deltaDistX;
          mapX += stepX;
          side = 0;
        }
        else
        {
          sideDistY += deltaDistY;
          mapY += stepY;
          side = 1;
        }
        //Check if ray has hit a wall
        if (worldMap[mapX][mapY] > 0) hit = 1;
      }

DDA完成后,我们需要计算射线与墙的距离,这样我们才能计算出需要绘制的墙的高度。需要注意的时,我们不使用斜边距离,而采用垂直相机平面的距离,否则会出现鱼眼效果。

这里是整个文章中最为困难的部分

通过代码分析应该得到的是如下图,其中如何得到除于rayDirX的,可参考下图,基本就是几何的三角形相似推出来的,实际上也可以通过斜边乘以这个角的余弦值得到,只不过计算量更多点。 另外(1 – stepX) / 2主要是为了兼容不同的step而已,不做解释。

image

//Calculate distance projected on camera direction (oblique distance will give fisheye effect!)
      if (side == 0) perpWallDist = (mapX - rayPosX + (1 - stepX) / 2) / rayDirX;
      else           perpWallDist = (mapY - rayPosY + (1 - stepY) / 2) / rayDirY;

计算完成距离之后,就可以计算画线的高度了,绘制高度与距离成反比,然后再乘以h,当然这里也可以乘以2h,这个取决于你要你的墙高点还是低点。

接下来我们需要计算绘制的起点及终点,在本例中,我们定义绘制的起点会导致墙体中心在屏幕中心,并做一些边界约束,代码如下

//Calculate height of line to draw on screen
      int lineHeight = (int)(h / perpWallDist);

      //calculate lowest and highest pixel to fill in current stripe
      int drawStart = -lineHeight / 2 + h / 2;
      if(drawStart < 0)drawStart = 0;
      int drawEnd = lineHeight / 2 + h / 2;
      if(drawEnd >= h)drawEnd = h - 1;

另外,我们通过不同的方块类型,定义不同的绘制颜色,另外当射线碰到y边界时,产生不同的亮度,这样效果会更好一些,至此整个循环结束。

//choose wall color
      ColorRGB color;
      switch(worldMap[mapX][mapY])
      {
        case 1:  color = RGB_Red;  break; //red
        case 2:  color = RGB_Green;  break; //green
        case 3:  color = RGB_Blue;   break; //blue
        case 4:  color = RGB_White;  break; //white
        default: color = RGB_Yellow; break; //yellow
      }

      //give x and y sides different brightness
      if (side == 1) {color = color / 2;}

      //draw the pixels of the stripe as a vertical line
      verLine(x, drawStart, drawEnd, color);
    }

接下来的部分比较简单,本不想多做解释,既然都到这里了,还是继续吧。 后面主要是计算fps值和各种移动速度及转向速度。

//timing for input and FPS counter
    oldTime = time;
    time = getTicks();
    double frameTime = (time - oldTime) / 1000.0; //frameTime is the time this frame has taken, in seconds
    print(1.0 / frameTime); //FPS counter
    redraw();
    cls();

    //speed modifiers
    double moveSpeed = frameTime * 5.0; //the constant value is in squares/second
    double rotSpeed = frameTime * 3.0; //the constant value is in radians/second

最后部分是读取输入,然后计算新的移动位置和朝向矢量

readKeys();
    //move forward if no wall in front of you
    if (keyDown(SDLK_UP))
    {
      if(worldMap[int(posX + dirX * moveSpeed)][int(posY)] == false) posX += dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY + dirY * moveSpeed)] == false) posY += dirY * moveSpeed;
    }
    //move backwards if no wall behind you
    if (keyDown(SDLK_DOWN))
    {
      if(worldMap[int(posX - dirX * moveSpeed)][int(posY)] == false) posX -= dirX * moveSpeed;
      if(worldMap[int(posX)][int(posY - dirY * moveSpeed)] == false) posY -= dirY * moveSpeed;
    }
    //rotate to the right
    if (keyDown(SDLK_RIGHT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(-rotSpeed) - dirY * sin(-rotSpeed);
      dirY = oldDirX * sin(-rotSpeed) + dirY * cos(-rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(-rotSpeed) - planeY * sin(-rotSpeed);
      planeY = oldPlaneX * sin(-rotSpeed) + planeY * cos(-rotSpeed);
    }
    //rotate to the left
    if (keyDown(SDLK_LEFT))
    {
      //both camera direction and camera plane must be rotated
      double oldDirX = dirX;
      dirX = dirX * cos(rotSpeed) - dirY * sin(rotSpeed);
      dirY = oldDirX * sin(rotSpeed) + dirY * cos(rotSpeed);
      double oldPlaneX = planeX;
      planeX = planeX * cos(rotSpeed) - planeY * sin(rotSpeed);
      planeY = oldPlaneX * sin(rotSpeed) + planeY * cos(rotSpeed);
    }
  }
}

然后结果就是如此

image

下面是我用pico-8做的模拟。

贴入纹理的光线投射器

引入纹理的基本原理跟之前类似,主要的区别在于将创建屏幕缓冲,而非直接输出到屏幕中,然后在画线的部分做修改,不使用划线的api,而是绘制纹理的部分位置,所以主要的难点在于计算纹理uv坐标的位置。

因为难度不大,所以暂时跳过不做说明。

关于颜色预乘(premultiply)

引言

在许多纹理打包器中都有一个颜色预乘选项,但是我在第一次使用的时候,并没有特别理解这个句话的意思,理解上只是混合算法不同,并不理解引入这个的目的如何。

从理解上来说,将本来分离的RGBA四个因子重新预乘起来,是一个很奇怪的事情,特别是在早期,我一直觉得不预乘扩展性应该还好点,反正我可以在运行时再乘,也不是很在乎多一个乘法的效率问题。

为什么要引入预乘

这个就是我在本次阅读中学习到的点,我从这个文章中得到的启示,这个是spine论坛中的一篇文章,从目的到混合算法都说得很明确,我这里简单说明下。

传统的后乘alpha算法在shader或者混合配置中应该是这样的。

blend(source, dest) = (source.rgb * source.a) + (dest.rgb * (1 – source.a))

而预乘算法是这样的

blend(source, dest) = source.rgb + (dest.rgb * (1 – source.a))

从感受上来说,只是程序员为了效率引入的东西,而实际上他还解决了以下几个问题。 ·解决纹理比例缩放映射产生的颜色错误问题 ·可以和其他纹理一起正常混合而不打破批次渲染

本文最重要的目的是讲解第一点,为什么会出现颜色的错误问题。当一个图片素材被引擎放置在屏幕上时,往往不是1:1映射的,有可能因为在世界坐标的不同位置,映射到屏幕可能有不同的缩放比例。

比如有linear,nearest等算法可以将缺失的像素补全。这时候这些缺失像素的计算,会因为alpha因子的本身也会被平均而导致RGB因子被缩放两次,进而会产生一个黑色的边缘。

而实际上我们希望的结果应该是alpha因子RGB值只被平均一次,进而有需求就是将RGB值在素材中就被预乘。

关于瓷砖贴图的过渡(tile)

引言

瓷砖在游戏开发中的作用可以说非常巨大,哪怕在现在的2016年,依旧有非常多的游戏地表都是用有限的瓷砖拼起来的,除了id的mega texture以外,这里面的原因恐怕是不言自明的,因此我这段时间主要研究了一下这里面的一些技术问题,当然该问题跟美术相关性也比较大。

最早的瓷砖游戏

早期在红白机的几乎所有游戏都是瓷砖的,但是其中印象最深的或者最low的应该是dq1代,他的画面是这样的。

image

从这个游戏的画面可以明显的看到人为的瓷砖拼接痕迹,应该说瓷砖完全就是按类型划分的,中间完全没有过渡。 同样的位置,在sfc时间,已经变成了这样。

image

我们只看地形的话,特别是水与草地的连接区块,已经明显看到了有过渡,当然这种过渡本质上是美术做了第二个草地瓷砖导致的。 顺便说一句,dq1代是1986年出的,sfc版本在1993年同2代一起推出。

对于美国人来说,同样的图像进化印象最深的应该在Ultima IV到Ultima V的跨越,具体可见这个 地址

瓷砖存在的问题

使用瓷砖的首个问题恐怕跟现实中的一样,就是很明显的人造物体,而在游戏中,由于大量需要拟自然的草地,河流等,现在瓷砖首先需要处理的问题就是防止看起来像人造草地,人造河流。 其次是平滑的过渡,自然界的绝大部分地表与地表之间是有合理过渡的,比如草地与沙地,森林与草地等,而不会出现生硬的分割,比如dq1的fc版本。 最后一个问题是美术制作上的,如何生成一个可无限平铺的瓷砖,这个在技术上有一些手段,当然主要的处理还是在美术上。

瓷砖过渡

最简单的瓷砖过渡自然是人肉的方式,比如设计师在设计关卡的时候,根据周围的瓷砖选择应该选择的瓷砖,而美术在制作的时候就会制作一些过渡瓷砖,比如dq1 sfc版中主角的与水相邻的草地,就有明显的水花,这也与现实生活的观感一致,设计师在设计大地图的时候选中这块瓷砖即可。

但是关卡设计师如果每次想做个草地都要进行类似的判断,明显是一件愚蠢的行为,因为采用哪个瓷砖完全可以程序化,简单的说这个逻辑相当简单,完全可以用程序解决,而关卡设计师只要用填充工具填充一个草地即可,不需要关心用哪个过渡草地贴图。

如何处理瓷砖过渡

简单的计算下瓷砖过渡所需的块数

首先是最基本的一个类型一个瓷砖,那么块数显然是1

image

下图是我们预期达到的效果

image

看上去有点复杂,怎么计算需要多少块草瓷砖与水的过渡呢,以上图中三面环水的瓷砖举例,可以看如下的抽象图

1 0 0

0 # 0

1 1 1

#即那个瓷砖块,由这这个简易的抽象图可以明白,实际上采用那个瓷砖块由周围的8个格子决定,所以排列组合有2^8个,即256种组合,而这仅仅是草与水的组合,如果草与沙、泥土等那不得是天文数字。

所以下一步就是如何优化这个组合数量,可以看到这种组合排列方式有是以地形类型在图形中间为准的,即我们的思维方式是草,另外可以看到刚才抽象图中左上角的1对#号并没有相互影响的关系,也就是说,组合排列方式未必是相乘关系(当然想做的更好还是可以做不一样的,这两个草地相挨比较近,按道理中间应该有浅滩)。

现在来说一些详细的对策,对策一就是将4个边缘及4个对角的图片拆开处理,在程序中在动态合并起来,这样的话就只需要2^4 + 2^4 = 32个图片即可解决此问题,这种办法可以参见此文

对策二就是去除一些在游戏中不会出现或者不需要处理的过渡区块,比如刚才的草地对角(刚才也解释了,在这种情况下,实际上有会更好),对角外墙的衔接,这种处理往往在墙这种材质中比较常出现,适合泰格瑞亚这类游戏,具体可以参考此文中的Blob模式(仅需要47块),应该来说非常适合做此类游戏。

对策三是最常使用的招数,绝大部分游戏都使用此处理方式,那就是将瓷砖类型信息放在对角进行考虑,这样2^8 就直接变成了2^4即16个瓷砖组合。

image

当然这种方式也有几个问题,因为整体瓷砖有偏移,所以地表需要做偏移量,否则与人物等上层图层会有偏移。另外一块瓷砖就不仅仅是一个类型信息了,而是有四个类型信息,也就是占用内存会更多点。

在游戏应用上还有一种瓷砖过渡方式与此方式完全不同,过渡块实际上是一个单独的图片,程序会在游戏运行时动态用过渡块混合原始图片,这样美工的工作量很少很多,而且过渡块可以通用于很多资源,下图说明一切。

原理图

image

效果图 image

当然这种通用出来的过渡模板不可能通用一切类型,一般需要多个类型之间做几种,比如这个是我从帝国时代中截图得到的不同过渡块模板。

image

瓷砖类型间的过渡

刚才讨论的仅仅是两种瓷砖间的过渡,我们成功将256种可能缩减到了几十个,而如果有其他类型相互组合又如何处理呢,比如水与沙地,是否要重新制作几十个过渡块?

这个解决方法也有许多,比如在真实世界中,水一般不太可能跟砖块,铁等相互衔接,所以一般制作上不会按n*m的方式制作所有过渡块,只会在需要的时候制作即可,待会我们介绍Tiled编辑器的时候可以看到他是如何记录多个类型之间的过渡的。

另外一种处理方式比较讨巧,就是定好多个类型之间的层级关系,比如草地一定是在水上方,而岩石一定是在草地上方,而图片原型含有透明度,游戏运行是按层级做透明混合即可(war3即是这样的处理方式)。

2D游戏中的瓷砖过渡

下面我想举一些游戏中的例子,来说明下以上的做法。

编辑器Tiled

目前Tiled应该是2d瓷砖编辑器的王者,基本上包含了一个直接可用的瓷砖编辑器,另外他在0.9的版本新增了地形元素,包含了瓷砖过渡的功能。

image

可以看到沙地与鹅卵石、普通路面间均有过渡,另外操作上也很直观,采用的是方案三,即4斜角判断类型的方式,所以仅需16块瓷砖(实际上只需要15块,没有全是0的可能)即可自身瓷砖做任意平铺。不需要对角衔接的情况还可以去除两块。 具体的操作可以查看Tiled文档尝试一下。

泰格瑞亚

泰格瑞亚的采用比较极端,在Reddit上有泰格瑞亚美术的回答,他们使用的是256个过渡块,这个美术同学满是吐槽,我扒了下电脑上泰格瑞亚的游戏,还真是。

image

这个美术同学说,如果重新设计的话,他比较希望采用47块的那种方式,当然这种方式会导致对角块没有衔接,但是问题不大。

Starbound

Starbound是泰格瑞亚团队成员重新创立的一个科幻版的类泰格瑞亚,我没有仔细玩过,不过我特地研究过了一下他的tile拼接方式,发现他的格子是这样的。

image

瓷砖非常小。另外外部的衔接块只有4px,中间的块则是8px,我第一眼的直觉就是,这个应该还是类似方案三的过渡方式,上面的8×8的应该是对角衔接。于是我用ps重新做了下透明像素填充,为了能在Tiled中直接使用,于是这个泥土块变成了这样。

image

由此来看,泰格瑞亚的瓷砖过渡块是非常不人道的。顺便说下,starbound和饥荒的关卡编辑都是用Tiled制作的,虽然他们都包含了绝大部分程序化的世界生成,但是有非常多的套路关卡直接用Tiled设计了。

RPG Maker VX

这个是做RPG游戏非常有名的编辑器,出名的游戏我就不列举了,而这个编辑器给我最大的印象就是我在08年用js做一个rpg引擎时,一直苦恼于如何程序化衔接每个类型的瓷砖,而这个编辑器打开用,我很惊艳于他直接可用的过渡瓷砖,但是当时因为时间有限,并没有去深入研究他的实现,现在因为本篇文章的整理,基本上明白了他的实现原理就是我的类似方案三的实现,只不过他的地表应该是自带偏移了。他的砖块集如下,为了更明确的明白他的实现,我特地在一个可衔接砖块上标注了1到6。

image

不过我的标注应该是错误的,他实际上应该是13块的实现,即没有对角过渡。

3D游戏中的瓷砖过渡

3d游戏中普遍还是瓷砖地图,只不过绝大部分可能用了纹理混合达到细微调整。

魔兽争霸3

war3实际上在上面已经提到了,他使用15块过渡瓷砖做的地表,另外明确多个地表类型之间的层级关系,不过由于是3d游戏,有光照和阴影对场景的影响,所以导致看上去纹理并没有明显的重复。

下图是我用Tiled设定的war3草地图

image

与上面不同的是,war3有对角衔接图。

Dota2

Dota2的平面地表是可以做多材质,多纹理的混合的,而且混合效果非常好,衔接区块是不需要制作的,完全是用程序混合生成。 具体的可参考 这个 还有这个

Wang Tiles

除了边角处理以外,中间都相交的区块重复度还是很高,所以一般游戏基本上都会做多套随机使用,比如war3的图片,明显是有非常多的中间区块用来随机使用的,有没有更好的办法将这种重复感觉进一步弱化呢,答案是Wang Tiles。

image

本质上就是将随机选取中间块变成了根据更加多元化的边界及样式将人造感弱化。

文章已经有点长了,所以不太希望把这个话题再铺开,google下可以搜索得到很多相关文章,比如 这个, 这个

流亡黯道

流亡黯道的处理方式跟上文的瓷砖过渡没有太大关系,主要是使用了wang tiles的做法,做了一个比较不错的应用,我把他放在这里,官方这个教程很不错,主要是美术同学如何制作可以用来做wang tile的教程

其他方案

上文的瓷砖过渡方案主要都是美术制作的,而目前市面上3d游戏另外一部分制作是通过程序混合的,类似地形高度图的使用,应该是生成了专门的笔刷图或者顶点属性,在地图加载的时候动态混合出来使用的。 这样的话,美术可以直接在地图编辑器里作画,可以节省更多的美术资源,不过效果如何还是要看美术的功力。

比如在Dota2 Workshop中的这里文章中可以看到应该是在顶点中存了同个材质不同纹理在顶点的所占比重达到了混合效果,从dota2实际效果看,混合得挺不错的。

游戏样例分析

饥荒

image

饥荒的地表明显是Blob模式,即47块,每块为136像素 比较特别的是,饥荒的地表跟Blob模式是反向的,即实际操作中对应Blob模式的实物居然是空地,我在简单实现中发现,饥荒应该在设计阶段用的是1,0等简单的标示地表类型,而通过程序动态算出使用的区块的,因为如果是地表编辑的时候使用此方式,那么笔刷很难操作。

帝国时代

image

帝国时代的地表也是Blob模式,虽然有很多重复的上下左右贴图,不过那些应该在游戏中只是减少重复感使用的。 不过帝国时代需要衔接的地表类型比较多,所以通用了一个Blend纹理。

[译]帝国时代中的网络编程

原文地址:

1500 Archers on a 28.8 Network Programming in Age of Empires and Beyond

概述

本文解释了在制作帝国时代1&2多人(网络)游戏中使用的设计架构,实现及经验,另外讨论了Ensemble Studios在他的游戏引擎中使用的当前及未来的网络方案。

帝国时代多人游戏:设计目标

在1996年早期帝国时代网络代码开始编写的那个时候,为了实现设想中的游戏体验,我们不得不面对了很多特定的任务。

  • 大量单位参与的历史史诗级战役
  • 支持8个玩家多人游戏
  • 确保平滑的模拟,无论是基于局域网,modern还是互联网
  • 支持目标平台:16MB Pentium 90 with a 28.8 modem
  • 通讯系统需要与现有的游戏引擎协同工作
  • 在最低的机器配置中仍能保持统一的15fps

Genie引擎运行良好,并且逐渐给予了单人玩家一个引人注目的游戏体验,Genie引擎是一个2d单线程游戏引擎,精灵图片绘制成256色,世界基于网格建立而成,随机生成的地图填满了成千上万的物体,从被砍伐的树木到跳跃的羚羊,对该引擎的主要运行任务粗略分解后(优化后)是这样的:30%的图形渲染,30%的ai及寻路,30%的运行逻辑。

在早期阶段,引擎已经很稳定,多人通讯需要工作于已经存在的代码,而非对已经存在的架构重新进行编码。

让事情更加复杂的是完成每个模拟步的时间有很大的不同:如果用户查看单位,滚动或者位于未探索的地形中,渲染时间会改变,另外Ai层面的大型的路径或者战略规划,都会使得游戏游戏回合波动相当的大(200ms左右)。

简单的一些快速计算就可知道,仅仅是传输一小撮单位的数据并保持实时更新,就会严重的限制与玩家交互的单位及物体的数量,即使仅传输x,y坐标,状态,动作,朝向及伤害,顶多也只能保证游戏中的移动单位到250个。

而我们想要做的是使用弩车,弓箭手,战士摧毁一个希腊城市,而同时它也被海上的战船围困,很明显,我们需要其他的方案。

同时模拟

相比于在游戏中传输所有单位的状态,我们更期望的是在每台机器运行同样的结果,在同一个时间传送每一个完全相同的指令集到每一台机器,pc们将会基本同步他们的游戏世界,允许玩家发布命令,然后用同样的方式,在同样的时间运行同样的命令,然后获得完全一致的游戏结果。

这种棘手的同步方案难以刚开始的时候就运行良好,但是确实相比其他方面有突出的优势。

改善基本模型

在最简单的概念层面,实现一个同时模拟似乎是相当简单,对于一些游戏来说,使用锁帧模拟及固定游戏时间甚至是直接可行的。

虽然这个方法能同时解决移动成千上万物体的问题,这个方案依旧需要面对互联网20到1000毫秒的延迟,及每帧处理的时间中解决这些变化。

发送玩家的指令,获取所有的消息,然后在进入下次回合前处理他们,这些导致的启停或者缓慢的指令周期,将会成为可玩性的梦魇,我们需要一套在后台等待通讯的同时继续处理游戏逻辑的方案。

Mark使用了一个标记命令系统,每条指令都将在两个通讯回合后执行(通讯回合在帝国时代中从实际的渲染帧中被分离出来)。

1

所以在回合1000运行的命令将会预定在1002回合中被运行(见图1),回合1001运行的是回合0999的命令,这样就能允许消息在被接收,确认及准备运行的阶段,游戏仍然在动以及运行游戏模拟。

回合通常设定为200ms,将这个回合中的所有命令发送出去,200ms后,回合结束,另外下一个回合开始,在游戏的任何时间,仅仅会执行一个回合的命令,接收及存储下一回合的命令,以及发送未来两个回合后的命令。

速度控制

由于模拟必须总是拥有相同的输入,游戏实际上只能与最慢的机器运行的一样快,速度控制就是我们可以动态改变回合的长度,为了在通讯延迟及处理速度不一致的情况下,保证动画及玩法更为平滑。

  • 如果一台机器掉帧,而其他的机器将会处理他们的命令,渲染分配时间的所有东西,然后继续等待下一个回合,哪怕是微小的停顿都会立即注意到;
  • 通讯延迟,由于网络延迟及丢包也会让玩家需要等待足够的数据包来完成本次回合。

每台客户端计算一个平均帧率,他被统一的计算为若干帧的平均处理时间,由于随着游戏的进程,视角,单位数量,地图大小及其他因素都会被改变,所以这个数据将会在本次回合结束的消息包中被捎带上。

每台客户端也会定期的测量它与其他客户端一个往返的响应时间,他将会发送与其他客户端的最长的平均响应时间到回合结束的消息包中(总共两个字节被用在速度控制中)。

绘图1

每个回合,被指定的主机将会分析回合结束的消息包,计算出一个目标帧率及网络延迟的调节因素,主机将会发送一个新的帧率及通讯回合长度给所有客户端使用,图3到图5显示了通讯回合在不同条件下的分解情况。

QQ截图20150827193001

通讯回合粗略的预估为一个消息往返的响应时间(RTT),这个响应时间分分解了若干的模拟帧,执行这些模拟帧的时间需要在最慢的机器中也能完成。

通讯回合的时间跨度会被加权,这样才能保证在网络延迟时动态变化,慢慢趋向于一个可以保证游戏持续的最佳稳定速度。游戏只会在最糟糕的峰值出现停顿或者减缓)——命令延迟将会上升,但是保持平滑(每回合进调整少量的毫秒数)以逐渐调整到最好的游戏速度。这个方案给予了适应环境变化的同时提供最平滑的游戏体验。

保证送达

网络层使用了UDP,因而命令顺序,丢包检测及重传在每个客户端自行处理,每个消息使用了一系列字节用来标示即将被运行的回合数及每个消息的序列号,如果一个需要被之前回合数被执行,他会被丢弃,否则将会存储给将来的回合运行,由于UDP的性质,Mark假定消息接收规则为“当消息被怀疑的时候,就丢弃它“,如果一个消息不是按顺序被接收,接收方会立即发送一个重传请求给被丢弃的消息,如果一个确认包比预期的晚送达,发送方会预期到这个消息可能已经丢失,重新发送这个消息包,而不需要接收方请求。

潜在的好处

由于游戏的结果取决于所有玩家运行同样的结果,所以修改及欺骗客户端变为极其困难,任何不同的模拟结果都会被标记为“不同步“,然后游戏停止,当然,欺骗本地客户端用来显示更多的信息还是可能的,但是这些轻微的问题相对来说很容易处理,可以由后续的补丁及修订版本修复,安全上无形中已经获得了巨大的胜利。

潜在的问题

起初看起来,让两块相同的代码运行相同的结果应该是相当容易及直接的,然而事实并非如此,微软的产品经理Tim Znamenacek在很早的时候就告诉Mark:“在每个项目中,总有一个顽固的错误影响了所有的地方——我想“不同步”就是这个顽固的问题。“, 他是对的,找出不同步错误的困难点在于每个微小的差异都会随着时间不停的被放大,一只小鹿在生成地图的时候轻微的不对齐,都会导致搜寻饲料的时候有轻微的不同,然后几分钟过去后,村民的路径也会有轻微的偏差导致他的长矛可能会刺不中,然后回家的时候没有食物,所以当由于不同的食物数量的校验和不同时,有时候你很难追溯到造成该问题的本源。

我们差不多校验了世界,物体,寻路,目标及其他所有系统,但似乎总有一些事情被漏掉,巨大的消息(50MB)追踪及世界物体转存进行筛选让这个问题愈发困难,部分的困难是概念上的——程序员们不习惯于编写某些代码,比如不得不使用同样数量的调用来随机游戏模拟。(是的,随机数种子也需要同步)。

我们获得了哪些经验?

我们在开发帝国时代的多人游戏中,获得了一些重要的经验,这些经验也适用于开发其他游戏的多人系统。

了解你的用户。了解用户的期望对于多人游戏的性能,感知延迟及命令延迟至关重要,每个游戏类型都是不同的,你需要理解哪些东西对于你特定的玩法及控制是正确的。

在开发的早期,Mark与主设计师坐在一起,原型化了通讯延迟(这个是贯穿我们开发阶段不断重试的部分),从单人游戏出发,很容易模拟不同区间的命令延迟来获取玩家反馈,什么时候感觉正确、缓慢、急促或者很糟糕。

对RTS游戏而言,250毫秒的命令延迟并不会被察觉,250至500毫秒延迟是可玩的,而大于500毫秒延迟开始能被玩家察觉到,这里也有件有趣的事情值得注意,玩家会自行脑补出一种“游戏节奏”,这是当他们点击直到获得响应精神期望上的延迟。一个始终如一的慢响应比一个忽快忽慢的命令延迟好得多(比如80到500毫秒的延迟),在这个例子中,保持在500毫秒延迟更可玩,而变化的延迟会感觉很卡且难以使用。

实际上这导致了大部分的编程重点转移在了平滑上——选择一个的更长的回合长度肯定会比尽快运行加上一些偶然的减慢更一致也更平滑。任何速度上的改变都应该逐渐缓慢的改变。

我们也计算过系统上玩家的主要数据——他们平均每1.5到2秒的时间发布一次命令(移动,攻击,砍树),在剧烈的战斗中,会提升到每秒3到4个命令的峰值,由于我们游戏的行为是逐渐复杂起来的,所以最大的通讯需求往往在游戏的中后期。

当你花时间学习你的用户行为时,你将会注意到他们怎么玩游戏,这将会帮助你处理网络问题,在帝国时代中,当玩家兴奋的攻击时,他会不停的点击,这些行为会每秒发布非常多的命令,造成短暂的峰值,如果他们对一个巨大的群组进行寻路是,也会产生巨大的网络峰值需求。一个简单的过滤器可以丢弃在同一个位置的重复性命令,这样能大幅度的减少这个行为的影响。

总之,观察用户行为可以帮助你:

  • 明白玩家的延迟期望
  • 尽早原型化多人游戏的部分
  • 观察会影响多人游戏性能的行为

测量为王

你将会发现一个令人惊讶的事情,如果你更早的将测量数据对外,使得测试者可以看到该数据,可以帮助他们理解网络引擎底层所做的事情。

经验:当Mark过早的将测量数据移除,在最终代码加入后,一些帝国时代的通讯问题无法重新校验消息(长度及频率)层级,无法检测一些问题,比如偶然性的AI竞争条件,困难的计算路径,不良的结构命令包在一些被调优过的系统将造成巨大的性能问题

当越过一些边界条件的时候,你的系统是否会通知测试者及开发者?——当开发过程中某项任务对系统产生压力的时候,程序猿及测试人员将会观察到,并在早期就让你知晓,进而去做某些处理。

花些时间对你的测试人员进行一些培训,帮助他们理解你的通讯系统如何工作的,另外暴露及解释一些主要的测试数据给他们——当网络代码不可避免的遇到一些奇怪的错误时,你可能会受益于他们的一些发现。

总之,你的测量数据应该:

·对于测试人员更加可读及易于理解

·暴露瓶颈,速度降低及问题

·不占用太多性能,并保持运行

培训你的开发者  对于那些习惯于单机游戏开发的开发者,让他们开始思考关于命令发布,接收及处理的分拆,你发布的命令可能并不会发生,或者再几秒后发生,这个很容易忘记。命令必须在发送及接受的时候进行双重检测。

在同步模型中,编程人员也必须认识到,当运行游戏逻辑时,代码必须不依赖于本地因素(比如特定的硬件,设置等)。代码在所有机器上的结果必须匹配,比如游戏逻辑中的随机地形可能导致游戏行为不同(保存及重新生成随机种子负责这个事情,我们需要随机,但是不能改变游戏模拟)。

其他经验教训 这应该是常识——如果你依赖于第三方的网络库(我们这里用的是DirectPlay),编写一个独立的测试环境,检查该库所说的消息包保证抵达,保证包顺序等功能是没有问题的,另外测试该产品在处理消息通讯的时候是否有潜在的瓶颈或者奇怪的行为。

准备好创建模拟程序还有压力测试模拟,我们最终编写了三个不同的小的测试程序,每个测试软件都为了突出不同的问题,比如连接泛滥,同时配对连接,丢失保证抵达的包等。

开发过程中,尽早的用modem测试,并持续这个开发过程(这很痛苦)。因为很难隔离出问题(可能因为ISP,游戏,通讯软件,modem,配对服务或者其他可能的原因导致突然的性能下降),另外当用户习惯于实时的LAN连接速度后,真的不太愿意再使用拨号网络。你需要保证在局域网以及modem连接中投入一样的热情,这很重要。

帝国时代2的改进

在《帝国时代2:帝王世纪》中,我们增加了一些多人游戏的功能,比如游戏录像,文件传输,区域内的持续的状态追踪。我们还优化的原先的多人系统,比如DirectPlay的集成,修改速度控制的bug以及帝国时代1发布之后的一些性能问题。

游戏录像功能是一个本来你偶然发现“我可以用他来进行调试”的功能,后面变成了一个成熟的游戏功能,游戏录像在粉丝网站非常的流行,因为他们允许玩家交换及分析游戏数据,观看有名的对战,还有回看他们玩的游戏。作为一个调试工具,游戏录像非常有价值,因为我们的模拟是确定的,游戏录像与多人游戏的采用同样的方式,游戏录像提供给我们一个不断重试播放特定bug录像的机会,因为录像必须保证每次播放的内容都是一致的。

我们集成了一个区域内的比赛匹配系统,原来一代只能简单的运行多人游戏,在二代中,我们扩展了这个功能,允许增加运行参数控制,并且对数据报告进行存储。虽然没有一个完整的由内而外的系统,但是我们利用了DirectPlay的大厅启动功能,允许这个区域通过游戏前置表格控制某些特定的游戏设置,当游戏开始的时候,锁定这些功能。这允许玩家更好的寻找他们想要玩的游戏。因为他们可以在比赛匹配层看到这些参数,而不是直接进入游戏初始化的等待界面。在后台,我们实现了持久化的数据报告及追踪。我们为区域提供了通用的结构,这些数据在游戏结束之后被提交,这些数据用来记录玩家排名及等级,玩家可以通过区域网站观察到这些数据。

RTS3多人游戏:目标

RTS3是Ensembles的下一代策略游戏的内部代号,RTS3的设计基于成功的帝国时代系列设计理念,另外增加了一系列新的功能及多人游戏需求。

  • 基于帝国一二代的功能集,网络设计需要支持互联网游戏,各式各样大型的地图,数以千计的可控制单位;
  • 3d-RTS3是一个全3d游戏,拥有动画补间及非分面的单位位置及专项;
  • 更多的玩家——可能支持多于8个玩家;
  • TCP/IP支持,56k的TCP/IP互联网连接是我们的主要目标;
  • 家庭网络支持——支持终端用户的家庭网络配置(包含防火墙及NAT设置);

在RTS3早期中,我们做了一个决定,使用与帝国1代2代同样的网络模型——同步模拟——因为RTS3的设计以同样的方式能够发挥这种架构的优势。在一代二代中,我们依赖于DirectPlay来传输数据及会话管理,但是在RTS3中我们决定创造一个核心的网络库,用来作为我们最基础的socket库。

全3d的世界意味着我们不得不对帧频问题及多人游戏的模拟平滑更加的敏感,尽管如此,这也意味着我们的模拟更新时间及帧率更容易出现变化,我们可能需要花费更多的时间用来渲染。在Genie引擎中,单位转向是分面的,动画是帧率固定的——然而突然之间,我们突然被允许进行随意的单位转向以及平滑的动画,这意味着游戏将会对视觉更加的敏感(延迟的效果以及摇摆不定的帧频)。

二代开发完成后,我们想要总结出哪些是最重要的功能——那些预先规划设计还有工具化能对调试时间产生最大帮助的功能。我们也认识到迭代测试对于我们游戏的重要性,所以早早的将多人游戏的部分提到最高优先度。

RTS3通讯架构

6

一个OO的方案,RTS的网络架构是一个强面向对象的方式(见图6),强面向对象的设计抽象化了特定的平台,协议、拓扑结构及系统,有助于我们支持不同的网络配置。特定的协议以及特定版本的网络拓扑结构采用尽可能少的代码。大多数的功能被抽离到了高层的逻辑中。实现一个新的协议,我们仅仅需要扩展那些网络对象,实现特定的网络协议代码(比如Client、Session,这些需要基于不同的协议做不同的处理),系统中的其他对象不需要进行修改(比如Channels,TimeSync等),因为他们仅与Client及Session的高层抽象接口调用。

7

点对点的拓扑结构。Genie引擎支持点对点的拓扑结构(所有的客户端直连其他客户端,星形的网络结构),RTS3我们继续使用这个结构,因为这种结构在使用同步模拟的时候有一些与生俱来的优势。点对点的拓扑结构意味着在一次会话中已连接的客户端是一种星形的配置(见图7)。也就是说,所有客户端都连接了其他所有客户端。这是一代二代采用的设置。

点对点的优势:

  • 减少网络延迟,客户端直连比客户端-服务端-客户端需要更少的往返时间。
  • 没有中心点故障为题-如果客户端掉线(哪怕是主机),游戏还可以继续进行。

点对点的劣势:

  • 更多的活动连接数——意味着更多的潜在失败节点及潜在延迟
  • 没办法支持某些NAT配置

Net.lib 我们设计RTS3通讯架构的目标是适合于策略游戏的系统,但是同时我们也希望他能用来支持我们的内部工具以及我们将来的游戏。为了达到这个目标,我们创建了多层级的架构,它能够支持游戏级别的对象,比如Client或者Session,也能支持底层级的传输对象,比如一个链路或者一个网络地址。

RTS3基于我们的次时代BANG!引擎创建,该引擎是一个模块化的架构,由各种组件组成,比如音乐,渲染和网络,网络子系统在这里适合作为一个组件添加到BANG!引擎中(同时也是一个内部工具)。我们的网络模型分离为4个不同的服务器层级,看起来有点像,但不完全像OSI网络模型(见图8)。

8

Socks,第一层

第一层,sock层,提供基本的socket c api,它抽象化为不同的操作系统提供通用的底层网络接口,这个接口类似于berkley socket,这个层级的代码主要为更高等级的网络库使用,而不打算用直接在应用层代码。

链接,第二层

链接层提供传输层级的服务,这个层级的对象,比如Link,Listener,NetWorkAddress,Packet代表着用来连接和发送消息的有用对象。

  • Packet:我们的基本消息结构——一个可扩展的对象,它通过link对象发送消息的时候,会自动处理序列化及反序列化(通过纯虚方法)
  • Linker:两个网络终端的连接,这也可以是一个回路(loopback)连接,即两端都为同一台机器,Linker上的Send和Receive方法用来处理消息,另外有个void*的数据缓冲对象
  • Listener:Link生成器,这个对象监听一个连入的连接,当连接完成后生成一个Link对象
  • Data Steam:这个是一个任意长度的数据流,用来通过一个给定的Link——比如用来实现文件传输
  • Net Address:与协议无关的网络地址对象
  • Ping:一个简单的Ping类,用来报告给定Link的网络延迟

多人游戏,第三层

多人游戏层是net.lib api中最高层级的对象,RTS3使用这个层级来组合低等级的api, 比如links为更有用的对象,比如Client或者Session。

在BAND!网络库中最有趣的对象可能就是这些在多人游戏层级的了,以下的API代表了与游戏层级交互的绝大部分对象集。然而实现上我们还是维持与游戏无关的方案。

  • Client:它是最基本的网络节点的抽象,它可以配置为一个远程客户端(Link)或者本地客户端(loopback Link),Clients无法被直接创建,但是可以由Session生成。
  • Session:这个对象用来创建,连接,收集及管理各种Client,Session包含了所有其他多人游戏层级的对象,想使用这个对象的话,应用程序简单的调用host或者join,给它一个本地或者远程地址,然后Session就会处理好剩下的。它的责任包含了创建及销毁Clients,通知Session事件及派发到合适的对象。
  • Channel及Ordered Channel:改对象代表了一个虚拟的消息管道,通过某个Channel发送的消息将会自动的分离及接收到远程节点对应的通道对象上。一个Ordered Channel与TimeSync对象协同工作,保证所有客户端在Channel上收到的消息次序是相同的。
  • Shared Data:代表着通过所有客户端共享的一些数据,你可以扩展这个对象来创建特定的实例(包含你自己的数据类型)。使用内建的方法可以通过网络自动同步更新这些数据。
  • Time Sync:管理在Session中的所有客户端同步网络时间的平滑过程。

游戏通讯,第四层

通讯层级是RTS3游戏逻辑的部分,它主要搜集了游戏与网络库接口的部分系统,他实际上存在于游戏代码中,通讯曾提供了许多有用的工具方法,用来创建及管理多人游戏层级的网络层级的网络对象,另外试图归纳游戏的联网游戏部分为一个易于使用的接口。

新的功能和更好的工具

改善同步系统 在帝国时代开发团队中没有人不需要可能的更好的同步工具,在任何项目中,当你回头整理开发过程的时候,某些区域总是花费你最多的时间,但是如果你做了更多预先的工作会省掉你非常多的时间。同步的调试工具可能是我们在开发RTS3中最重要的工具。RTS3同步追踪系统主要是为了快速定位每轮的同步问题,开发它的其他要点是开发者的使用上的易用性,它能够处理任意巨大数量的同步数据,也能够从发布版中不编入同步的那部分代码,最终能够通过某些变量或者配置文件随意修改这项配置,而不是重新编译。

RTS3的同步检查主要是采用两个宏

#define syncRandCode(userinfo) gSync->addCodeSync(cRandSync, userinfo, __FILE__, __LINE__)

#define syncRandData(userinfo, v) gSync->addDataSync(cRandSync, v, userinfo, __FILE__, __LINE__)

(每个同步“标签”都有一系列sync打头的宏,每个标签代表需要同步的系统,在这里例子中代表的随机数生成器cRandSync)这些宏都带着一个userinfo的字符串参数,这是一个名字或者显示需要同步的描述,比如,一次这样的调用

SyncRandCode(“syncing the random seed”, seed);

同步控制台命令和配置变量

这对于开发过程来说,意义重大(任何Quakemod的创造者都会证实这点)。控制台命令一般是简单的函数调用,可以通过启动配置文件,在游戏的控制台中, 或者UI 的钩子中, 调用任意的游戏功能。 配置变量被称为数据类型,通过简单的get, set, define和toggle 函数,来做各种测试和配置参数。

Paul 扩展了一个支持对人游戏的控制台命令和配置变量系统。我们可以很容易将一个普通的配置变量(例如, enableCheating), 通过添加一个标记, 加入到对人游戏的配置变量。如果使用了这个标记, 在多人游戏中就会传输这个配置变量,同步的游戏进程也会跟这个值有关(例如, 是否允许资源免费)。 多人游戏的控制台命令也是类似的概念: 调用一个多人游戏下的控制台命令, 会传输到网络中的玩家, 并同步执行。

通过应用这两个工具,开发者可以很简单的使用多人系统, 而不用写一行代码。他们能快速的添加测试工具和配置, 并加入到网络环境中。

总结

点对点的网络同步模型,在《帝国》系列游戏中获得了成功。关键之处在于明白花时间在创建工具和技术上的重要性(例如同步和网络测量)。证明了在实时战略游戏上应用这种架构的可行性。后续在RTS3 中做的改进, 保证了多人游戏的体验和单机时几乎没有区别,除非在最烂的网络环境下。

DOOM3网络同步体系

概述

由于doom3是开源的,另外网页上有大量研究doom3的文章,所以分析起来难度比较小,值得注意的是Valve公司旗下的source引擎的基础也是类似这套体系,所以也可以从中得到不少东西,包括他在source sdk上的一些介绍文章,目前的文章还在草稿期,比较乱,后期我再进行整理。

简单的一句话介绍doom3的网络体系就是基于客户端预测及快照的网络同步方式c/s网络拓扑结构udp作为底层网络协议

基本代码分析

相关文件
AsyncClient.*
AsyncServer.*
AsyncNetwork.*
每帧逻辑位于Common::RunFrame
如果是多人游戏,则代码走
idAsyncNetwork::RunFrame();
if (idAsyncNetwork::isActive()) {
     session->GuiFrameEvents();
     session->UpdateScreen(false);
}
单机游戏的话 ,代码走
session->Frame(); // 最终也是调用Game::RunFrame
session->UpdateScreen(false)
idAsyncNetwork::RunFrame()代码中,如果是服务端,则走AsyncServer::RunFrame逻辑,如果是客户端则走AsyncClient::RunFrame()逻辑
AsyncServer::RunFrame最终调用的逻辑是执行Game::RunFrame,另外在代码最后发送了当前的系统快照。系统快照的发送时间限制了最大比特率为 16000 bytes / s 即大概16k每秒,如果上次发送时间与本次发送时间超过了1秒或者小于每秒的比特率,则发送快照及本帧的指令信息(注意这里的指令信息会额外多发送之前的一些指令,因为udp不可靠,另外如果进行重发及验证,还不如每次都额外多发一些)。
AsyncClient::RunFrame的逻辑最重要的是客户端预测的逻辑,客户端预测的在本玩家PVS下的所有实体(玩家,怪物,投射物灯),不仅仅是本地玩家,另外预测是有一个最大预测时长的,默认的预测时间为c->s的延迟时间,预测的本地玩家直接使用的就是当前的操作指令,而其他玩家,使用的是之前的指令,这样的话本地玩家是完全没有延迟反应的。
关于客户端预测的细节,客户端预测的初始值是往返的响应时间,假设为100ms,首次执行的时候,ClientPredictTIme为100ms,gameTimeResidual为16.67ms,假设客户端机器性能非常好,没有任何掉帧,则本次RunFrame会一次性执行 (100 + 16.67) / 16.67 次模拟,及玩家位置会在这帧内多次执行到7帧后的位置(即客户端预测服务端收到包并返回给自己时 ,自己应该处于的位置) ,
下一帧,如果还是没有收到服务器返回,则本次只执行一次,而非多次,因为由于上一帧的预测影响,导致gameTimeResidual已经是负数了。所以本次只累加了16.67ms。
由于出现延迟的下一帧就会移动预测到延迟时间后的游戏时间,之后每帧实际上都也是步进一次,所以实际上并不会出现预测自己的情况出现,只有在第一次会出现一次跳跃。
注意,客户端预测不仅仅是基于之前指令进行计算,同时也发送了本机之后的指令给服务端,否则服务端会一直接受不到最新的指令,毕竟两者之间是有延迟存在的。

攻击相关的本机预测

查看Weapon::Event_LaunchProjectiles可知,目前联机的时候,甚至连投射物都没有做预测播放,投射物的产生以服务端的快照为准,由于doom3是fps游戏,所以攻击流程为player::Weapon_Combat -> weapon::BeginAttack(); ->weapon脚本调用Event_LaunchProjectiles状态,注意整个过程中,人物,武器的动画状态都是预测的,即立即显示出开火的相关状态,但是伤害的投射物及最终伤害都未预测
投射物由服务端快照创建,当投射物遇到障碍物时,预测爆破及特效。
最终的伤害及效果都有player::readFromSnapshot处理,比如当前血量比原来血量少,则播放受击动画,反馈等,如果死亡,则播放死亡。

关于指令及快照的发送及接收

玩家指令,还有快照信息都是通过不可靠的消息传递的
指令包是不管是否有无收到的,默认doom会复制之前的5条指令,因为就算你保证发送成功了,服务端时间也未必恰好用你发的指令进行计算。当有延迟的情况出现时,延迟的客户端会体验发送预测延迟时间内的指令,为了后期恰好给服务端使用。
服务端的指令包及snapshot也不是保证一定收到的,反正如果没收到,收到最新的时候都会从lastsnapshot从头开始计算
所以在doom中不会出现等待的情况,只会回拉

关于平滑拉扯

由于客户端预测的存在,另外客户端并不会等待服务端指令,服务端也不会等待客户端指令,所以整个客户端及服务端都是异步的,这样肯定会出现不一致的情况,这种情况的处理需要做一些平滑,否则感受会比较差,doom3是这么做平滑的。
其他玩家的渲染位置与当前真实渲染位置是会做平滑的,即当前逻辑位置虽然是直接拉到了理想的服务器位置,但是渲染位置用了smooth做了慢慢平滑
代码在 idPlayer::GetPhysicsToVisualTransform
及 idPlayer::ClientPredictionThink均有涉及,这里的平滑只涉及到了其他玩家。
注意渲染位置并不会立即改变,只会每帧改变一次(smoothedOriginUpdated),免得出现位置跳跃。
因为玩家本身的指令应该与服务端的指令几乎是完全一致的,不应该出现偏差,仅当服务端没有收到指令包(因为这里是UDP)超过两次时,才会进行一次平滑到真实位置(因为udp并不可靠)。
另外还有一个平滑是关于玩家的视角,即玩家的那个晃动视角
其他玩家的攻击指令没有做预测

真实主客机的测试

主机无延迟
客机有200ms单向延迟,400ms往返延迟
现象为
在客机屏幕,由于有400ms延迟及客户端预测的存在,所以主机的玩家一旦移动就会出现尽量同步到400ms后的位置,所以一旦开始移动就有个快速拉扯,停止的时候也会回拉。
在主机屏幕,由于延迟为0,所以客户端移动虽然有延迟,但是不会出现加速及回拉的情况。
比较出乎我意料的是,在客机屏幕的客户端预测,居然不会影响到本地玩家,我一直以为本地玩家也会有快速拉扯,实际上完全没有。不管在主机还是客机屏幕,本地玩家的行为都完全正常。
与之前的代码分析完全一致。

使用该做法的游戏

http://dev.dota2.com/showthread.php?t=527&page=7&p=4253&viewfull=1#post4253

dota2这篇论坛上的资料透露, Counterstrike, Left 4 Dead, Team Fortress 2等游戏都采用了该技术,而dota2在此技术的基础上,去掉了客户端预测,减少了拉扯现象,不过玩家的控制信息得不到立即反馈,该文章也是为了解答玩家关于控制延迟的疑问。

网络游戏的移动同步(五)帧同步算法

发了部分移动同步类的文章后,有一些朋友加了我的联系方式,也进行了一些探讨,在这中间,有个朋友跟我聊了另外一种同步方式,即这种帧锁定的变种算法,帧同步算法,基本是思路是这样的。

算法流程

1.服务器同步随机种子,初始帧索引等会造成每个客户端运算不一致的初始数据;

2.客户端发送指令,比如(选中,移动,攻击目标等),指令包含当前帧索引;

3.服务器每隔一段时间(假设是100ms)发送帧更新包,该更新包将客户端逻辑心跳步进,并且处理当前帧索引的指令,当前帧索引步进1;

这里有一些术语需要解释,比如逻辑心跳,大抵的意思就是,比如移动,攻击等比较高层的逻辑行为,而譬如动画等行为不属于逻辑行为。

也就是在这种情况下,因为所有指令都是等到服务器发送的帧更新包才进行处理,所以所有客户端处理的时间线是完全一致的,虽然服务端到每个客户端的时间不一致,但是并不会出现帧卡住的现象,因为哪怕某个客户端没收到更新包,他所看到的屏幕也仅仅是玩家,怪物不移动,而非锁帧。

另外这种处理方式也解决了另外一个问题,就是延迟以最高延迟的客户端为主,这种情况下,服务器是不等待所有客户端的控制指令到达的,到达时间就发送帧步进。

另外,初始我对该同步方式的担忧是担心流量太大,但是仔细考虑了一下,由于发送的协议仅仅是指令,结果的处理完全由客户端模拟,所以少了需要状态同步的协议,而这些状态同步的协议往往非常大,因此这种方式可能整体流量还会少许多。

参考文献

  1. 帧同步在竞技类网络游戏中的应用
  2. 网络层+架构层 : 自研游戏帧同步方案
  3. 「译」Unity3D中实现帧同步 – Part 1

热血格斗传说场景结构猜想

先看看热血格斗传说的第一个场景图片

1

 

可以看到该场景有相对比较复杂的元素,比如斜坡,几个可跳跃高台,那热血格斗传说是如何实现国夫能够跳上高台,跑上斜坡的呢?

首先需要进行拆解的是国夫的坐标系有多少个轴,因为国夫可以横着走,竖着走,还可以垂直上跳,所以国夫必然是存在三个轴的,只不过最终投影在屏幕上的是两个轴而已,这与三维的mvp变换类似,只不过对于这种简易的横版动作游戏不需要复杂的mvp矩阵,两个公式即可。

Xs = Xw

Ys = aYw + bZw

 

即在Y屏幕的贡献是包含了Z轴与Y轴逻辑坐标的。在对游戏进行斜走的尝试后,发现游戏斜走是趋向于45度的,即X轴显示上的移动速度是与Y轴显示上的移动速度一致的,a应为1。

所以如果要做到国夫能站在高台上,那国夫当前在该位置的Z坐标一定是比不在高台上大的,而不是Y坐标变大了,否则会与竖向位移产生冲突。

那么该场景的数据结构就比较好拆分了,首先我先尝试对场景进行网格化,网格化能够简化游戏计算,我猜想对于一个90年代的游戏应该都会采用该技术,在对所有我认为特殊区块的位置进行对齐之后,我得到了一个大致的网格大小为8×8,然后在大致对区块进行划分,如下图

2

得到这样的区块后我进行了一下确认,比如C块最底下的位置与显示不完全对齐,于是我去游戏中进行验证,看国夫是否也是无法走到该位置,得到如下图(国夫跳跃能力在5个格子左右到达最高点)

3

可见,该游戏的边界应该是以网格为基本单位做对齐的,那么我们做进一步的假设,假设b为1,即逻辑z轴对屏幕y轴的贡献与逻辑y轴是一致的,那国夫在区块C的z值应该为3(单位为网格),B为6,D为6,右边两个高台就没有一一编号了。

游戏中如何判断国夫需要跳上高台,而不是走过去呢?当国夫到达地板边界向C区块的格子进去的时候,判断下一个点属于C区块格子,则获取C区块格子类型及属性,得到C区块格子的Z值大于当前Z值,则不可往左移动。至于如何判断落在高台上,只要计算z位置的时候判断当前z位置大于等于当前区块z位置即可不再下落。

那么问题到了A斜坡了,A斜坡的数据结构如何表示,通过游戏得知,国夫在A斜坡的移动是连续的,比如格子为单位,也就是说,很明显A区块内的格子并不是每个格子设置一个Z值,否则得到的效果就会咔吱咔吱的跳。

那么如何表示这个结构呢,因为是斜坡,我们很容易想到的就是斜率,即在中学数学里的直线方程中的斜率 z = kx,通过观察图形,另外加上我们假设的(假设b为1,即逻辑z轴对屏幕y轴的贡献与逻辑y轴是一致的)。则可以得到k为1/2。

那我们在每帧逻辑中是如何计算的呢,我大概猜想了下,如果国夫位于A区块内,则vz = k*vx,也就是说,一旦vx有值,则vz有值,则z会随着时间流逝逐渐上升,同样推导反相也是成立的。

则对于区块A,只需记录值k为1/2即可。

4 5 6 7

仔细观察了下游戏中几个有斜坡的场景,则会发现,斜坡斜率为1/2,1,2这几个值,主要是因为方便计算罢了。

继续整理剩余的几个场景区块类型

8 9 10

 

场景一共有8个,新的场景区块类型为

·定时炸弹(普通击飞,沿着之前移动方向)

·传送(以一定攻击状态传送到指定区域)

·电网(电属性击飞,可传递)

·钉刺(某个朝向的击飞)

·履带(增加定向速度略小于移动速度)

·冰面(增大滑行距离,普通移动除外,对于斜坡会有自动下降的速度)

最为复杂的为最后一个场景,首先改传送区块的传送区域是多个,而且是顺序传送,即传送到A区域,下次传送到B区域依次排列,另外钉刺为动画,且区块属性是动态变化的。

场景数据结构猜想就暂时到这里,下一个部分研究热血格斗传说的动画状态,该游戏虽然画面简单,但是动画状态极为复杂,接近于街头争霸等复杂的格斗游戏动画状态机。

 

OpenGL freetype 创建描边效果及cocos2d-x描边问题

主要参考文章
http://www.cppblog.com/shly/archive/2013/07/14/201796.aspx
http://www.cppblog.com/wc250en007/archive/2011/07/13/150809.html
目的
想了解描边效果的主要原因是因为cocos2d-x自带的效果中(enableGlow,enableOutline,enableShadow),没有一个是满足效果的,enableGlow的效果极其难看,enableOutline的效果感觉Outline的位置总有错误,另外原始3.0版本的描边甚至都存在bug,导致字库的位置是错误的。
基本原理
cocos2d-x的标签类型有三种,位图字体,系统字体,TrueType字体
位图字体与一般的精灵图片类似,从大的精灵表中获取坐标,直接渲染,这个是最快也是最直接的方式
常用的后缀为fnt文件及对应纹理图片
系统字体系统字体为平台相关,比较少用,直接从操作系统已有的字体库中获取字体的位图信息。由于字体文件未必在特定平台都存在,因此此字体几乎没有使用
TrueType字体为矢量字体,这个也是使用频率最高的方式,但是这个效果比较低,因为在使用中,需要根据字体文件,大小,是否描边等参数生成对应的纹理信息,虽然cocos2d-x在使用后会进行缓存,但通过整体的流程可以看出比位图字体慢许多,不过好处是,在设置字体大小不同的业务需求时,字体不会因为变大而产生模糊的情况。因为原始的文件为矢量字体。
绘制描边的基本方式
网络上查询绘制描边的方式有主要几种
  1. 使用freetype的描边api,会沿着字形极其精确的绘制出满意的描边效果
  2. 八方向绘制多次原始字体
  3. 使用发光模糊效果模拟,也是使用多次绘制的方式,在底下绘制一个模糊的原始字字体,并给其填充颜色
方法2 3都会比较消耗绘制效率,2方法在描边宽度比较大的情况下,穿帮会比较严重,u3d的ngui插件使用的就是其描边方案,3方法在flash上经常使用,不过模糊算法会更加的消耗性能,因为需要大量计算周边像素值,并且有多次渲染。
问题
这里的描边主要是针对TrueType字体,TrueType字体在cocos2d-x的内部处理中使用了freetype库,但是在设置outline的处理上与ferrotype的example2存在着比较大的不同。
他的基本思路是与参考文献1类似,但是在处理原始字形的alpha值时,直接采用了绘制原始字形的bitmap值,另外与描边后的边线进行了居中对齐,最终导致了最终字形与描边位置错误比较严重,也就是比较丑。
另外描边后的偏移位置cocos2d-x也是计算错误的,需要增加两个bbox的x,y偏差值,具体可看参考文献2

网络游戏的移动同步(四)帧锁定算法

引言

我一直想了解早期游戏的网络同步,特别是早期的很多对战平台,做了很多单机游戏的对战,而这些同步又可以达到很不可思议的效果。从网络上我得知这种方案叫帧锁定,即保证每帧都是一致的。否则就锁定。比如玩dota时出现的万恶的等待框,本篇文章就希望简单的从客户端代码层面模拟这个过程(实际上到最后,我觉得纯粹用客户端模拟还是不足),另外作为整个网络同步系列的最后一个章节。

基本原理

对于单机游戏或者可联网的局域网游戏来说,大部分是没有服务器的,所有的游戏逻辑都放在客户端中处理,这导致的,只要每个用户所给的输入一致,时间一致,就能达到同样的模拟效果,所以帧锁定的基本原理便是如此。

算法流程

1.客户端定时(比如每五帧)上传控制信息。

2.服务器收到所有控制信息后广播给所有客户。

3.客户端用服务器发来的更新消息中的控制信息进行游戏。

4.如果客户端进行到下一个关键帧(5帧后)时没有收到服务器的更新消息则等待。

5.如果客户端进行到下一个关键帧时已经接收到了服务器的更新消息,则将上面的数据用于游戏,并采集当前鼠标键盘输入发送给服务器,同时继续进行下去。

6.服务端采集到所有数据后再次发送下一个关键帧更新消息。

C/S逻辑

客户端逻辑:

1. 判断当前帧F是否关键帧K1:如果不是跳转(7)。

2. 如果是关键帧,则察看有没有K1的UPDATE数据,如果没有的话重复2等待。

3. 采集当前K1的输入作为CTRL数据与K1编号一起发送给服务器

4. 从UPDATE K1中得到下一个关键帧的号码K2以及到下一个关键帧之间的输入数据I。

5. 从这个关键帧到下 一个关键帧K2之间的虚拟输入都用I。

6. 令K1 = K2。

7. 执行该帧逻辑

8. 跳转(1)

服务端逻辑:

1. 收集所有客户端本关键帧K1的CTRL数据(Ctrl-K)等待知道收集完成所有的CTRL-K。

2. 根据所有CTRL-K,计算下一个关键帧K2的Update,计算再下一个关键帧的编号K3。

3. 将Update发送给所有客户端

4. 令K1=K2

5. 跳转(1)

客户端模拟代码

// 如果当前是关键帧
if (Global.frame == keyFrame) {
    // 查看是否有服务器的更新包,当前关键帧编号,下一关键帧编号,所有玩家的控制信息
    // 获取更新包
    var rp:PlayerInputPack;
    while (client.packets.length > 0) {
        rp = client.packets.shift();
        if (rp.frame == keyFrame) {
            break;
        }
    }
    // 如果等不到当前帧的控制数据,则返回
    if (rp && rp.frame == keyFrame) {
        var nextFrame:int = keyFrame + 5;
        // 采集当前的输入作为包发送
        var p:PlayerInputPack = new PlayerInputPack();
        p.frame = nextFrame;
        p.input = InputManager.instance.keyStatus;
        client.send(p);

        // 以rp.input做输入数据
        // 模拟移动本地及网络客户端
        // 每个客户端的逻辑一致
        var players:Array = [localPlayer, netPlayer];
        for each (var player:Player in players) {
            player.velocity.x = 0;
            player.velocity.y = 0;

            if (rp.input[Keyboard.LEFT]) {
                player.velocity.x = -player.speed;
            }
            if (rp.input[Keyboard.RIGHT]) {
                player.velocity.x = player.speed;
            }
            if (rp.input[Keyboard.UP]) {
                player.velocity.y = -player.speed;
            }
            if (rp.input[Keyboard.DOWN]) {
                player.velocity.y = player.speed;
            }
        }

        // 下一个关键帧
        keyFrame = nextFrame;
        waitTime = 0;
    } else {
        waitTime += Global.elapse;

        // 等待太久了,类似魔兽争霸的那个超时面板
        if (waitTime > 1000) {
            trace('等待不到控制包信息', keyFrame);
        }
    }
} else {
    // 当前帧步进
    Global.frame++;
}

// 更新场景
localScene.update();
netScene.update();

演示

Get Adobe Flash player

总结

可以从flash演示中看到,两个场景在低延迟的情况下同步效果非常理想,甚至远远超过之前的客户端预测例子,不过这种做法的缺点就是当延迟过大时会极大的影响控制手感,另外延迟受最慢的客户端影响。

当服务器迟迟没有收到每五帧的所有控制输入时,就会发送通知给所有客户端,出现dota或者war3联网时的那个网络延迟框。在war3中,因为没有专门服务器,所以这个责任是由主机承担的。

对于游戏中的随机元素,则可以在游戏初始化时,由主机同步随机种子到所有客户端中。

参考文献