那些中古游戏的技术（一）

概述

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

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

光线投射（Raycasting）

介绍

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

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

基本思路

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

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

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

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

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

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

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

我们在提下相机的部分

由于这个游戏中的相机只能左右移动，所以可以将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同理。

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

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而已，不做解释。

//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);
    }
  }
}

然后结果就是如此

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

贴入纹理的光线投射器

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

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