分类目录归档:数学及物理

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

概述

最近看到了一个非常有趣的东西,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坐标的位置。

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

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

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

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区域依次排列,另外钉刺为动画,且区块属性是动态变化的。

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

 

插值那些事——译Interpolation Tricks

引言

插值这个概念是在几年前看到的,当时不是很理解,以为是一个数学概念就忽略了,实际上这个东西应用很多,特别是在游戏开发中,我们要做实时渲染,如果说只有0和1,中间没有过渡的话,一切都会显得很生硬,下面这篇文章是我看到的最好的解释这个概念及其应用的文章,传送门地址

插值技巧

或者说我如何做到停止烦恼并爱上0~1区间的

  1. 为什么是0…1这个范围

当在做游戏原型时我发现了许多不同的插值技巧,这些非常有价值,比如在各种移动中增加一些平滑,这些移动可以是摄像机,物体,灯光渐隐渐现等等,你会发现增加这些技巧之后会更加的令人享受。生硬的移动会让人觉得不舒服,应该极力避免。

一般说来,当做一些动画时,我们都会知道一个起始位置和终止位置,然后在他们中间可以进行一些过渡,所有的这些都可以转化为0到1的问题。(其实随机数也是类似的道理)

0值还有1值有很多有趣的属性,基于这些属性你可以拼接出任意开始和结束的值,正因为如此,所以我们只要把0到1的过程处理掉即可。

2. 开始进入0到1区间

如果我们希望将一个变量X从A移动到B点,通过N步,那我们应该写如下代码

for (i = 0; i < N; i++)
{
    X = ((B * i) + (A * (N - i))) / N;
}

或者我们重新写一下

for (i = 0; i < N; i++)
{
    t = i / N;
    X = (B * t) + (A * (1 - t));
}

这样看起来清楚多了吧?此时t的范围从0到1。

3. 线性插值(Linear Interpolation)

用N个离散步数从0移动到1被称为线性插值,或者叫“lerp”,见下图

linear

Get Adobe Flash player

依靠线性插值可以解决很多从A到B的基本问题,但是如果从B点重新运动回A点,也是通过同样的线性插值,你就会发现有明显的不和谐。幸运的是,这里不仅仅有一种方案能够解决从A到B的问题(实际上有无数种,但我们将只关注一部分)。

4. 更平滑的步骤(smoothstep)

如果你从这个小教程中带不走其他的,那就带走它

#define SMOOTHSTEP(x) ((x) * (x) * (3 - 2 * (x)))

smoothsetp就好像一种神奇的盐,你可以把它洒在任何你想变得更好的地方,你可以很简单的替换大多数的线性插值,如下

for (i = 0; i < N; i++)
{
    t = i / N;
    t = SMOOTHSTEP(t);
    X = (B * t) + (A * (1 - t));
}

smoothstep看起来是这样的

smoothstep

Get Adobe Flash player

通过对比,你可以很明显的看到他刚开始会加速,当快要接触目标的时候会慢慢减速。

5. 高次幂(higher powers)
如果你只想要有缓慢的加速时间,简单的加个N次幂可以解决问题,如下

for (i = 0; i < N; i++)
{
    t = i / N;
    t = t * t;
    X = (B * t) + (A * (1 - t));
}

如果你更想要的是缓慢减速,上面的式子做下反相就行了

for (i = 0; i < N; i++)
{
    t = i / N;
    t = 1 - (1 - t) * (1 - t);
    X = (B * t) + (A * (1 - t));
}

两个式子看起来是这个样子的

squared

Get Adobe Flash player

如果我们把次幂再调高到立方次,这个曲线看起来是这样的

squared

Get Adobe Flash player

同样的道理,这个还可以再次应用smoothstep,应用smoothstep到已经被平滑过的值可以让曲线更进一步(真不知道怎么翻),这个结果不是很容易应用到所有东西上,正如你所见,他会在原地待一段时间,但是有时候又很有用(也不说什么时候有用)。

squared

Get Adobe Flash player

6. 正弦

另外一个方便的曲线就是正弦,正弦可以像幂函数一样应用,结果也是十分相似的。

for (i = 0; i < N; i++)
{
    t = i / N;
    t = sin(t * Pi / 2);
    X = (B * t) + (A * (1 - t));
}

这个曲线同样可以像幂函数一样反相,结果如下

squared

Get Adobe Flash player

如果我们使用了整条三角函数,我们可以可以将曲线做得很近似于smoothstep

squared

Get Adobe Flash player

for (i = 0; i < N; i++)
{
    t = i / N;
    t = 0.5 - cos(-t * Pi) * 0.5;
    X = (B * t) + (A * (1 - t));
}

不过,使用三角函数会比刚才的方法有更大的开销。

7. 加权平均(weighted average)

一个相当方便的算法,特别是当你没办法知道未来的目标行为时(比如摄像机跟随者角色,目标点点一直在改变)。注,这种算法应用很多,你甚至都不需要记录当前时间t,所以特别方便。

t = ((t * (N - 1)) + w) / N;

其实我更喜欢这么写(这段是我自己拼的)

t += ((w - t) / N;

是的,当t越靠近w,则累加量越少。
t代表当前值,w代表目标点,N是缓动因子,N值越大,t接近w就越慢。

squared

Get Adobe Flash player

t越靠近w,则他运动得就越慢,越远离,他就越快,在理想的世界中,t实际上将永远到不了w,只是他们之间的距离越来越小越来越小,再说,计算机是不理想的。

8. 样条

最后,如果你需要更多的控制,你可以使用样条,Catmull-Rom样条是一个非常方便的方法,他总是会经过控制点,所以他可以更容易的应用到插值计算中,而其他的样条函数可以得到更自然的曲线,但是也有更少的可预知性,这里有份实现Catmull-Rom函数的代码。

float catmullrom(float t, float p0, float p1, float p2, float p3)
{
    return 0.5f * (
        (2 * p1) +
        (-p0 + p2) * t +
        (2 * p0 - 5 * p1 + 4 * p2 - p3) * t * t +
        (-p0 + 3 * p1 - 3 * p2 + p3) * t * t * t
    );
}

for (i = 0; i < N; i++)
{
    t = i / N;
    t = catmullrom(t, Q, 0, 1, T);
    X = (B * t) + (A * (1 - t));
}

在正常使用中,你可以给他很多的控制点,比如,5, 6, 比如4, 7,你能做出很多不一样的效果,下面就是一些例子。

squared 

Get Adobe Flash player

上面的参数值是Q和T的值,即p0, p3。
注意:这个值必须经过0和1,但是并不意味着要在0和1之间。

9. 结论

我希望这个简短的技术概览教程可以帮助你从你的移动行为中去掉那些尖锐的角落。

更多的阅读

使用perlin噪音生成随机地图

引言

还是随机地图的问题,除了细胞自动机的生成方式以外,一般3D游戏中的地形大部分是使用某个噪音原图,这个原图大部分是由perlin噪音产生的(perlin noise),perlin噪音的主要作用可参考Perlin噪音

Perlin噪音的实现方式有点复杂,一时间不是很好看懂,我个人理解的是,噪音不太可能是完全随机的,自然界的很多东西虽然看起来是随机的,但是随机中间又蕴藏着很多规则,这些规则导致出现随机实际上是有些规则的,不可能出现类似电视雪花点的噪音。

所以为了用计算机图形来更好的描述自然界的这一随机现象,perlin创造了perlin噪音这么个自然随机算法。perlin噪音包含了平滑差值及八阶分形的内容,有点复杂,不好在这里展开。

实现思路

通过perlin噪音生成随机的灰度(即只有黑白的)噪音图,然后一定比率的颜色变成可通行区域颜色,一定比例的成为障碍物颜色。如0~100为陆地,101~255为障碍物。然后,神奇的一幕发生了。

效果

Get Adobe Flash player

高清无码

Get Adobe Flash player

像不像地球呢?

源码

package {
	import flash.display.BitmapData;
	import flash.display.Bitmap;
	import flash.geom.Rectangle;
	import flash.geom.Point;
	import flash.events.Event;
	import flash.display.Sprite;
	import flash.events.MouseEvent;

	public class PerlinNoiseRandomMap extends Sprite {
		protected var bmTerrain:Bitmap;
		protected var bmpTerrain:BitmapData;
		protected var freq:Number = 0.5;
		protected var octs:Number = 8;
		protected var seed:Number = 12;
		protected var stitch:Boolean = true;
		protected var fractal:Boolean = true;
		protected var channels:Number = 7;
		protected var gray:Boolean = true;
		protected var red:Array = new Array(256);
		protected var green:Array = new Array(256);
		protected var blue:Array = new Array(256);
		protected var land:Number = 0xff00ff00;
		protected var water:Number = 0xff0000ff;

		public function PerlinNoiseRandomMap() {
			init();
			stage.addEventListener(MouseEvent.CLICK, reset);
		}

		public function init():void {
			for (var i:Number = 0; i < 128; i++) {
				red[i]=green[i]=blue[i]=land;
			}
			for (i = 128; i < 256; i++) {
				red[i]=green[i]=blue[i]=water;
			}
			bmpTerrain = new BitmapData(800,600);
            // perlin噪音
			bmpTerrain.perlinNoise(bmpTerrain.width * freq,bmpTerrain.height * freq, octs, seed, stitch, fractal, channels, gray);
            // 以红色通道举例,0-128的红色值重新映射到red[0]到red[128]的数组值
			bmpTerrain.paletteMap(bmpTerrain,new Rectangle(0,0,bmpTerrain.width,bmpTerrain.height),new Point(0,0),red,green,blue);
			bmTerrain = new Bitmap(bmpTerrain);
			bmTerrain.width = stage.stageWidth;
			bmTerrain.height = stage.stageHeight;
			addChild(bmTerrain);
		}

		public function destroy():void {
			removeChild(bmTerrain);
			bmTerrain = null;
			bmpTerrain = null;
		}

		public function reset(e:MouseEvent):void {
			destroy();
			seed = Math.random();
			init();
		}

	}
}

参考文献

基于细胞自动机的随机地图生成方案

引入

前天拜读了林伟的一篇GDC的ppt,名字叫《游戏地图自动生成》,这个ppt的前半部分说的是原地图的生成,因为这个地图一般是给3d游戏用的,通过这个灰度图取得具体的高度。这个具体还可以参见《Focus.on.3D.Terrain》。本篇文章关注的是那个灰度图的生成。

最终效果

QQ截图20140122102256

黑色代表障碍物,白色代表可通行区域。

做法

  1. 创建随机噪点,可通行区域与障碍点保持一定比率
  2. 根据细胞自动机算法,通过当前节点的周边8个节点得到新的通行状态,比如5个以上的障碍点,则当前点是障碍点,5个以下障碍点,则当前点是可通行点。

randomMap