世界上最小的3D-FPS游戏KKrieger，猜猜有多大？《递归之美：数学，电脑科学与分形》

cheerblues

5 p! _* W; [2 G9 f' L+ w游戏世界真是卧虎藏龙，今天大家有机会遇到啦。目前在欧美网络上流传一个震撼玩家的游戏「kkrieger」，以超炫的游戏画面效果让人瞠目结舌，而且最猛的是这个游戏的容量只有96K，但画面表现却可以打死其它市面上同类型的游戏，真的是好厉害好霹雳啊!!

! k( u: e' |3 w2 I. ~" P/ `这个容量只有96K的第一人称射击游戏「kkrieger」，是由德国一家名为「.the .produkkt」的小组完成的，但玩过的玩家都被这吓死人的游戏视觉表现震撼，不管是超炫的光影表现、实时阴影投射、环境贴图、凹凸贴图...等3D效果一应俱全，加上游戏中的人物、怪物3D模块也建构得很仔细，游戏关卡也设计得颇有气氛，这么高水平的游戏就算是直接拿市面上已经发售的同类型游戏来比都胜过太多了，但游戏容量竟然只有96K，讲白点，游戏Screenshot容量都不只96K了，只能说这款游戏「kkrieger」真的是太强了!!
0 G7 ^! T: x6 r: G: o) D
当然，其画面肯定无法和QUAKE3、DOOM3之类相比，但光影效果可以说甚至超越了DOOM3!，考虑到其96KB的身材，也足以令人震惊。

那么.theprodukkt小组是如何将这款游戏微缩到96KB中呢？该小组表示，他们并没有采用什么特别的压缩算法，只是对游戏中将用到的材质、网孔等资源进行了最为合理的安排，保证足够紧凑。对于该游戏所采用的深入技术细节，该小组并不愿公布。(其实就是“过程生成”)
, r4 K% ^: D1 K# @5 M7 ~
不知道大家是否有印象，以前网上经常传出许多大小只有64KB的3D演示动画，那是一些编程高手为了展示自己的实力完全采用汇编语言完成的作品。而相比来看，这款96KB的FPS游戏则更加精彩，因为他是一款有声有色，并且真正可以“玩”的游戏，但这款游戏并不是人们所想象的100%采用汇编语言完成，反而其主体由C++完成，之间贯穿少量汇编语言。
  A9 x6 A1 r& L# O( A
别看该游戏体积很小，但对机器配置要求却很高，一般人的电脑恐怕都不能运行。看来是拿来测试计算机硬件效能的好东西喔，要求配备如下：（达不到不能运行）：

" ?3 U' o1 {7 f操作系统：Windows Me / 2000 / XP
DirectX 9.0b
1 }5 M0 v, _/ g4 F  QCPU：Pentium3 1.5GHz 以上
3 R4 I2 {& k, S内存：512MB 以上
0 w, o9 q% V/ h' O7 J3D显示卡：Geforce4Ti 或 ATI Radeon8500 以上
（支持pixel shaders 1.3功能，内建128MB绘图内存）
释放后占用了近300MB内存
/ T2 c+ A6 H" g; P
' u1 L/ U0 _  d( D1 K运行该游戏后先要经历一段长时间的解压缩过程，而这些数据都将释放到内存中，所以512MB以上的内存配置是必须的。该游戏所占据的内存容量，已经接近300MB。

# C7 V. {4 C$ M* k4 X8 s( B; R/ m- etheprodukkt小组表示，.kkrieger这款游戏总共将有三个章节，而现在发布的仅仅是第一章的测试版，未来发布的版本体积可能会上100KB，但将修正更多BUG，运行也会更加稳定。

cheerblues

递归之美：数学，电脑科学与分形
6 |2 U9 a$ r! L3 W0 }! P7 r——转自http://mmdays.wordpress.com/2007/05/24/recursive/
* B0 E3 s: B, ], N, F

1 p6 \5 q4 e5 B" s/ s) Q想像一下，我刚才说了一句话，那句话是：“想像一下，我刚才说了一句话，那句话是：“想像一下，我刚才说了一句话，那句话是：……….””，如此下去，就好像站在两面平行摆设的镜子中间，镜子中的影像不断的重复。再举个例子，写完一封信想要匿名保密，就署名“知名不具”。回信的人写：“知知名不具具”。之后再回信的时候就变成：知知知名不具具具，加上括号可能比较清楚：(知(知(知名不具)具)具)。
6 c/ m1 ]/ `. B; y3 W4 P
# v1 w* G/ K  E* ~- f) l( D

0 t$ n8 \* Z* x5 v! N. b  P0 V递归就是类似这样子，不断的重复同样的东西，只不过每次重复的是比较小的东西了。大家应该对数学归纳法不陌生，在使用数学归纳法时，我们首先确定n=1的时候某件事情是成立，然后在证明n到n+1的过程是正确的，就可以从n=1的例子，一路推论出第n项是什么东西。就像是推骨牌一样，把第一张牌推倒了之后，剩下的骨牌自然就被前面的骨牌给推倒。

/ Q4 A: q( B3 A2 I# h
递归的概念则是相反的方向：我们想要解决一个大小为n的问题，我首先做的事情是把问题化简成大小为n-1的问题，但是解决的方法还是一样，只不过大小是n-1。如此继续化简，最后变成大小为n=1的基本问题，接着只要n=1的基本问题解决了，原来大小为n的问题也跟着解决了。
* E: P% N! ]9 D  G' T
0 \. V- v  L0 g. J( Y- F( l' D/ R) L这又好像层层分工。假设每个人都会加法，然后今天我想求出1+2+…+n等于多少？其中一个办法就是递归，我先假设1+2+…+(n-1)已经有人算好，那么我只要再加上n，就可以得到答案了。然而1+2+…+(n-1)要怎么得到呢？我就请另外一位朋友帮我算。另外一位朋友接到这个问题以后，也用同样的方法，他把1+2+…+(n-2)的结果交给另外一位朋友算，然后把这个结果加上(n-1)，就变成我想要的1+2+… +(n-1)了。朋友的朋友也继续用类似的方法，直到最后一位朋友只需要回答1，接着倒数第二位朋友就把1加上2，传给倒数第三位朋友，倒数第三位朋友加上3，一直到我收到1+2+…+(n- 1)的结果，再加上n，就大功告成了。
. ^4 y% C7 d! _  o
% j; B& t' f2 L) {  i" f' e* P

不过可能会觉得，如此简单的问题，为何还需要递归呢？其实递归也是比较适合一些问题来解，也就是那些“解决方式一样，但是可以化成大小比较小”的问题，除此之外还可以轻松解决基本问题(n=1的时候)。举例来说，有个古老的问题叫做河内塔(Hanoi Tower)，问题的定义引述如下(引用网站)


9 {: U1 R9 p" }1 U, @* x
- N, S) ~. b# {. N6 H: Z  D& N1883年，一位法国的数学家Edouard Lucas教授在欧洲的一份杂志上介绍了一个相当吸引人的难题──迷人的智力游戏。这个游戏名为河内塔(Tower of Hanoi)，它源自古印度神庙中的一段故事(也有一说是Lucas教授为增加此游戏之神秘色彩而捏造的)。传说在古老的印度，有一座神庙，据说它是宇宙的中心。在庙宇中放置了一块上面插有三根长木钉的木板，在其中的一根木钉上，从上至下被放置了64片直径由小至大的圆环形金属片。古印度教的天神指示祂的僧侣们将64片的金属片移至三根木钉中的其中一根上。规定在每次的移动中，只能搬移一片金属片，并且在过程中必须保持金属片由上至下是直径由小至大的次序，也就是说不论在那一根木钉上，圆环形的金属片都是直径较小的被放在上层。直到有一天，僧侣们能将64片的金属片依规则从指定的木钉上全部移动至另一根木钉上，那么，世界末日即随之来到，世间的一切终将被毁灭，万物都将至极乐世界。
6 ]2 U6 w* F8 i6 D0 m- Y+ r/ |
. q5 Q: n$ D( Z/ x倘若这个故事的叙述为真，那么，我们只需加速移动金属片，是不是就能愈早到达极乐世界呢？果真要移动这64片金属片，那么，至少要花几次的搬动才能完成呢？有没有规律可循呢？

- x$ f6 `; _3 b! C( s
这个问题，就很符合刚才的特性：我们可以把大问题化成小问题，而且解决的方法相同，只不过问题的大小变小了。另外基本问题(n=1)，就是移动一根金属片所需要的次数，这个我们也可以轻易解决，所以这个问题就可以用递归来解。
, W$ P3 K9 n1 V* |' X  Y
0 T$ p- `' [' n- L! L1 o' H首先，我们假设有A、B、C三根柱子，这64片金属片一开始在柱子A上面，我们想要搬到柱子C。因为问题中规定某个金属片上面是空的时候才能移动，我们就假设有个人可以帮我们把63片比较小的金属片先从柱子A搬到柱子B上面，然后我们把最大的那一片从柱子A搬到柱子C，再请那位朋友把刚才的63片从柱子B搬到柱子C，整个问题就解决了。然后我们只要知道刚才那位朋友搬了几次，然后加上我们自己般动的1次，就是整个问题要求的搬动次数了。
  w6 l8 ~0 U1 j, }1 U8 L9 [' P
* u: _& Z. v$ A4 f- d$ r. }递归不仅仅在数学上有其重要性，在电脑科学之中扮演的角色更是至关重要。程式设计者对于递归绝对不会陌生，上面所举的河内塔问题，实际上也是电脑科学的经典例子之一，是初学程序设计的人一定会学到的东西。递归的思维，常常可以让程式设计者打造出简洁的程式，让繁冗的问题透过简单的程式码来解决(例如parser的设计)。演算法上所讲的dynamic programming，就是递归思维在演算法的具体呈现。
' _9 F7 H' Z* M5 `
0 ^6 s( W1 ^# Z2 F$ f$ c' b+ K6 Q0 H
: j& I* w7 |9 ]8 U) U/ A
递归同时也是分形(fractal)这门大学问的基石，分形是一种相当美妙的几何图案，就如同上面那一张蒙娜丽莎的图一样，图中有图，形中有形，且小的部分都是大的部分的缩影，我们就称之为分形。分形本身的数学定义，实际上就包含了递归定义在里面，我们甚至于可以说，分形是递归在几何学的一种具体呈现。但是分形不仅仅是一种数学概念而已，在自然界中，有许许多多的地方都出现自然的分形，让人赞叹递归原来就出现在我们的生活周围。图中的这棵花椰菜，就蕴含了递归的碎形图案与于其中。分形同时也在各个研究领域有着广泛的应用，光是在电脑科学领域，就有人把分形应用在影像和影片压缩之上(这不难想像，由于分形这种以小见大的特性，我们可以用小的来表现大的，因此可以有压缩的概念出现)，在电脑图学上(computer graphics)，也有人把碎形应用在设计电脑游戏之中的一些景物，打造出有效率和简洁的系统。现在电脑游戏之中的景物，很多都是玩家边玩、游戏系统边产生出即时的景物，这叫做procedural generation（过程生成），这种即时产生景物的技术，可以避免游戏软件预先储存一堆要展现的景物，帮整个软件瘦身。“过程生成”就使用了大量的分形产生与合成技术于其中，而这些都根植于递归这一个深刻却简单的思维。

" F& ?3 R7 _4 m. K% n( j: Ifractal:

2 i% K0 ^/ E$ |9 K由B．B．Mandelbrot于1975年提出来的分形(fracta1)理论，是20世纪70年代同混沌理论一起发展起来的，是非线性科学的重要组成部分．不同于传统的欧氏几何以零维、一维、二维、三维、四维对应的点、线、面、体和时空来描述物体的形状，分形理论用“分维”(fractal dimension)来描述大自然．事实上任何物体的微观平面都是凹凸不平的，因而欧氏几何所描述的对象，严格来讲，在现实生活中是不存在的。

" x0 v3 W! V) x* E' Z" ^7 c7 J分形是用来描述大自然的一门几何学，它所描述的图形可以是分数维．分形的特征是整体和局部有严格的或统计意义下的自相似性．描述分形的定量参数为分维，而维数的定义种类很多，如相似维数、Hausdorff维数、盒维数(box dimansion)、拓扑维数(topological dimension)等，需要随研究对象的改变来选择．研究表明，分形在自然界中随处可见，例如，曲折而不规则的闪电路径，弯曲复杂的海岸线形状、密如蛛网的人体血管系统、变换不定的宇宙星云分布以及材料的组织生长、准晶态的晶体结构、材料的损伤等等．从地理学、生物学到物理学、化学甚至社会科学都普遍存在分形现象．分形理论在高分子科学中的应用研究也有很多文献报道，例如分形理论与各种现代分析手段相结合，已用于研究高分子的链结构、结晶过程、凝胶化过程、高分子的相形态结构等等方面．

"Fractal"原是一个几何概念, 意为多维、超维或分维, 它打破了原来3 维空间的概念, 不仅可以超过3 维, 而且还可以有小数维(小数点以后 1 位、2 位或更多位数)空间。“Fractal”引用在纤维纱和织物(称为纤维集合体)中, 就是立体多层次、有不同尺度的纤维粗细、长短配合,以及存在着凹凸状点接触的纱、线织物结构。
1 A7 o4 M0 [4 O* S6 c, S! f
: i  J0 w1 `# \/ a5 r, I美国和日本都开始注意纤维的分形（Fractal）结构的研究,它们触及了纤维表面凹凸构造的自相似性与大自然的色、光的对应关系。分形理论和混沌论都是20世纪物理学的第三次革命,它研究自然界非线性过程内在随机性所具有的特殊规律性, 从字面上看是指一类极其零碎而复杂但有其自相似性的体系, 是在自然界中普遍存在的。它是用自相似、无标度方法全面描述宏观、中观、微观大自然的科学概念, 混沌是物理概念, 其几何形态则是分形的概念。

6 C# x* I" x: l- f) L3 O天然纤维内在的分形维自然扭曲是其特有的一种分形结构, 它与合成纤维有本质的不同, 合成纤维的机械或化学卷曲, 包括三维卷曲都与天然纤维的从微纤的扭曲开始、自相似放大、最后导致的纤维扭曲截然不同。合成纤维中的超细旦、竹节丝、异截面丝、异收缩丝等都是1 维、2维甚至3维的整数维变化, 而天然纤维则是符合分形理论的分形维变化。
关于更多分形的图片可以查看这里：http://browse.deviantart.com/cus ... r/fractals/?order=5

至于把分形应用在游戏之中，现在已经做到有多可怕的地步了呢？请大家看看以下的几张张图片，不妨猜猜拥有这种精致画面的游戏软件，其整个游戏的大小是多少呢？
4 `# y, E8 H- m. H$ C

& z- c1 L- x6 q/ _  O" V: q


, V) e. e5 l( l. O4 G2 s

正确答案是97KB！没错，我没有打错字，你的眼睛也没有看错，这款游戏的大小只有97KB！传统的一片3.5吋磁片可以装下十几个这款游戏！这一款第一人称的射击游戏叫做.kkrieger，是由德国的demogroup .theprodukkt 所开发，截至目前为止还在beta测试版的阶段，这款游戏之所以可以压缩到这么小的境界，就是因为游戏之中的场景和音乐几乎全部都是由动态产生，游戏之中预先存放的资料只有一些简单的几何形状和MIDI音乐档，所以自然档案大小非常小。如果这款游戏没有用“过程生成”（Procedural Generation）的技巧进来的话，估计档案大小会爆增成200~300MB，这样的技术，真是令人叹为观止。而背后最大的功臣，就是这篇文章谈到的递归和碎形。各位也不妨下载来玩玩看吧 (下载点)。 不过需要注意到一件事情，这款游戏的载入时间非常长，因为他要靠着一点点的程式码即时来运算制造出场景，所以要耗去很多计算时间，这可说是一种time和space的tradeoff。
6 i+ a- c% I9 D! u* [6 G& l
9 y# O7 }- P0 n% [
% C7 E8 ?4 v, p8 S+ r# y* ?6 Y" T看完这篇文章，各位有没有对看似枯燥的数学有了一点点不同的看法呢？没想到递归可以这样应用在游戏开发之中吧。下次学习数学感觉到枯燥时，不妨从应用的角度切入试试看吧！

damahu79

哎几个很多年没提过数学概念= =

colorlemon

这东西几年前就看过了，记得最近还有人发过的～lz撞车了～

何处为家

要是没有解压的过程才令人震惊。

lemonpsycho

这已经是我第n次在网上看到这个帖了，又跑到这里来了。
游戏做的小也好，动辄好几个g的游戏下载太麻烦了

爱健永远

我们期待有一天游戏都可以做到只有几十K大小

liunbbq

96KB的3D游戏？

liunbbq

发现钱不够了...

老钱

, B) K% l9 B- L. E那个那个。。。。递归问题的思路，俺在几年前，解那个“海盗分宝”的问题时隐隐约约想到过了。就是把所有的问题从最简单的元素开始做。
' t$ i; _/ C2 s) ^0 r, k$ D* p2 x
5 e2 ?! }! v2 ~, K7 N附注：海盗分宝问题：10个海盗，依照力量强弱，依次分为1-10号。海盗的行动模式如下：1，海盗总是倾向于获得金币的；2，在获得金币的数量相同的时候，总是倾向于把人扔下海去的；3，海盗总是理性的，总是严格按照前两条规则行动。
2 q$ `2 f" n; b4 \最开始时，这十个海盗共同拥有100枚金币。然后由1号海盗（力量最强的海盗）提出分配方案。如果分配方案获得不小于一半人数的支持，那么就按照这个方案分配；如果支持的人数小于一半人，则提出分配方案的海盗被扔到海里去，2号海盗来继续主持分配。以此类推。被扔下海的海盗不能获得任何金币。金币不能分割。强力的海盗不能使用威胁，引诱，责骂等等手段影响其他海盗的理性判断。
0 O- V7 H/ S- I! X2 y. H; T* P
求解的问题是：1号海盗如何主持分配方案，让主持分配的海盗获得最多的金币？
0 s2 t2 x; ~* b/ {1 U( l

; Y  e/ |/ J/ U
当年计算了很久。。。后来想到先不管10个海盗，只从2个海盗的情况下一个个加上去来计算。。。果然简单多了。。。

PS：题目出自传说中的微软面试题。除了论述啊这一类的没有确定结论的题目外，俺基本上把那些题目都做出来了。。。有些题目比较巧妙

hackerzl

刚刚在这个FPS游戏作者的官网找到一个相当牛逼的demo，播放了进10分钟的3D动画，那个光影效果太NB了，最神奇的是这些东西全部包含在一个不足200kb的exe文件里。没法截图，有兴趣的，可以下来看看。估计配置有点高，我1366*768分辨率还没开抗锯齿感觉有点顿卡。