月度归档:2014年01月

插值那些事——译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();
		}

	}
}

参考文献

自然连通图

引言

接上一文章,当每个随机区块完成后,需要对每个区块进行连接,如果更好的进行连接,随机乱连肯定是不行的,会出现如下情况

图片1

直觉上告诉我们,我们希望得到的是类似下面的图

QQ截图20140122111343

这种连接方式看上去很“自然”,那如何得到这种比较自然的连线方式呢?我们从结果出发可以得到几点规则:

  1. 连线不能交叉
  2. 连线不要经过其他点
  3. 最好不好一个点有多条连线

通过上面的约束,我们可以得到一个算法

  1. 初始时所有点都处在自己的独立集合中
  2. 从第一个集合出发,找到一个离开最近的集合
  3. 与最近的集合做连线,并将那个集合取消,将连线后的点增加到当前集合
  4. 重复第2步,直到所有点都在一个集合

代码

package
{
	import flash.display.Sprite;
	import flash.events.MouseEvent;
	import flash.geom.Point;

	[SWF(frameRate="60", width="800", height="600")]
	public class LineMap extends Sprite
	{
		private var points:Array;
		private var lines:Vector.;
		private var units:Vector.;
		private var step:int = 0;
		private var currentPoint:Point;

		public function LineMap()
		{
			stage.addEventListener(MouseEvent.CLICK, onClick);
		}

		public function initUnit():void {
			units = new Vector.();
			// 初始时每个球一个单元
			for each (var p:Point in points) {
				var u:Unit = new Unit();
				u.points.push(p);
				units.push(u);
			}
		}

		protected function onClick(event:MouseEvent):void
		{
			init();
			initUnit();
			line();
			draw();
		}

		private function line():void
		{
			lines = new Vector.();
			// 遍历所有单元,选择出最近连线,且不相交
			while (units.length > 1) {
				var u:Unit = units[0];

				// 遍历其余单元,找出距离最短的那个单元
				var minDist:Number = Number.MAX_VALUE;
				var minIndex:int = -1, minP1:Point, minP2:Point;
				for (var j:int = 1; j < units.length; ++j) {
					var o:Unit = units[j];
					assert(o.points.length <= 1);
					var dist:Array = u.dist(o);
					if (dist[0] < minDist) {
						minDist = dist[0];
						minIndex = j;
						minP1 = dist[1];
						minP2 = dist[2];
					}
				}

				var l:Line = new Line();
				l.p1 = minP1;
				l.p2 = minP2;
				lines.push(l);

				// 将最短距离的那个单元加入当前单元
				u.points.push(units[minIndex].points[0]);
				units.splice(minIndex, 1);

//				currentPoint = minP1;

//				step++;
//				break;
			}
		}

		public function init():void {
			var count:int = 30;
			var padding:int = 10;
			points = [];
			for (var i:int = 0; i < count; ++i) {
				var p:Point = new Point(rand(padding, stage.stageWidth - padding), rand(padding, stage.stageHeight - padding));
				points.push(p);
			}
		}

		public function rand(x:Number, y:Number):Number {
			return x + Math.random() * (y - x);
		}

		public function draw():void {
			graphics.clear()
			for each (var p:Point in points) {
				graphics.beginFill(0x0);
				if (currentPoint == p) {
					graphics.beginFill(0xFF0000);
				}
				graphics.drawCircle(p.x, p.y, 10);
				graphics.endFill();
			}
			for each (var l:Line in lines) {
				graphics.lineStyle(1, 0x0);
				graphics.moveTo(l.p1.x, l.p1.y);
				graphics.lineTo(l.p2.x, l.p2.y);
			}
		}

		public function assert(b:Boolean):void {
			if (! b) {
				throw new Error("断言错误");
			}
		}
	}
}
import flash.geom.Point;

class Unit {
	public var points:Array = [];

	public function dist(u:Unit):Array {
		var minDist:Number = Number.MAX_VALUE;
		var minP1:Point, minP2:Point;
		for each (var p1:Point in points) {
			for each (var p2:Point in u.points) {
				var dist:Number = p1.subtract(p2).length;
				if (dist < minDist) {
					minDist = dist;
					minP1 = p1;
					minP2 = p2;
				}
			}
		}
		return [minDist, minP1, minP2];
	}
}

class Line {
	public var p1:Point;
	public var p2:Point;
}

效果

Get Adobe Flash player

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

引入

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

最终效果

QQ截图20140122102256

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

做法

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

randomMap

“饥荒”游戏动画格式分析

动画流水线(从美术到程序)

  1. 美术通过flash cs设计人物
  2. 人物由多个部位组成(骨骼),每个部位可能有不同的表现形式,比如头部在人物朝上,朝下的时候肯定是不同的显示状态,这个显示状态肯定是无法通过变换矩阵完成的。
  3. 通过jsfl将美术设计的动画转为两种不同的文件,build.xml与anim.xml及散列的部位图片。

build.xml的主要作用是描述人物的整体组成结构,比如

1

 

anim.xml的主要作用是动画构成,比如

2

4. 通过python脚本打包xml为bin(二进制格式),打包build的过程中额外生成纹理集(大位图,mipmap)及定点信息。

这种动画的做法整合了帧帧位图动画以及骨骼动画的优点,首先由于每帧信息大部分更改的是转换矩阵,所有整体动画不会特别大,另外可以通过同一个部位信息做出很多动画,另外由于每个部位状态的存在,也让动画有一定的扩展性,当然对于美术来说,肯定是什么限制都没有最合适了。

 

下面是我写的一个简单的“饥荒”动画读取器

3