详细介绍在游戏制作中的分形算法

　　所谓分形，在数学上是指具有如下性质的一类图形：
　　1.具有无限的细节。具有无限的细节的意思是指这个图形无论如何放大，都无法存在一个平坦的表面。这个定义有些抽象。举个例子就知道了。比如说吧，一块石头。无论怎么放大，表面都是粗糙不平的。
　　2.自相似。自相似是指一个图形无论怎样放大，看起来都于原图形相似。举个例子来说，人体的微小血管和大血管看起来没什么两样。
　　
　　具有如上性质的图形就被称做分形。通常分形都是极度对称的，对称到了完美的地步。非常的美观（具体请参见《计算机图形学 第二版》后面的彩色附图，电子工业出版社出版）。但生成这种图形却不需要非常复杂的程序。因为它们具有无限的细节表面，就可以使用递归算法来实现。下面我就来简单介绍一些分形的算法。
　　
　　首先我们来考察二维的情况。
　　
　　二维分形的创建一般是通过一维变换得到的。通常用的算法是一维线段中点随机平移算法。考虑以下算法：
　　
　　首先创建一条线段，设端点为A，B。则首先找到它的中点C，并在线段上随机移动一点距离。这样就得到了两条线段AB，AC。重复以上步骤，一直到足够多的次数，那么就可以得到比较满意的二维分形了。其伪代码如下：
　　
　　do {
　　遍历线段数组，并找到线段中点；
　　沿线段随机移动一点距离；
　　}while(足够多的次数）;
　　
　　接着我们考察三维的情况。
　　想法跟二维情况相似，三维的分形一般通过二维平面变换得到。我们考虑以下算法：
　　
　　算法一：随机生成地形算法。首先我们考虑一个空的2维数组。在各个结点处随机生成一个值，然后渲染。这样生成地形速度快，但是有个缺点，就是地形太离散。这种算法的应用较局限，但是生成海面我想是不错的。伪代码如下：
　　
　　do{
　　遍历数组，生成随机值；
　　}
　　
　　算法二：将上面的算法扩展。我们还是考虑一个空的2维数组。但是只在某些点随机生成值，然后以这些点为原点向周围递减。这种算法就已经较上面的不错了，而且比上面算法生成的图形要平滑了许多。其伪代码如下：
　　
　　do
　　{
　　遍历数组，在随机点生成随机数值；
　　}
　　then
　　{
　　以这些点为原点向周围递减；
　　}
　　
　　以上算法是我在研究分形的过程中研究出的简单的分形算法，同时我还研究出了几个算法，但是忽然想不起来了，只好以后再说明。需要说明得是，以上两个算法适用的范围比较局限，所以接下来我介绍一种比较有名的算法：Diamond+Square算法，算法描述如下：
　　
　　首先我们考虑一个空的2维数组，这个数组必须是方的，也就是2的N次+1乘以2的N次方。然后取四角组成的正方形，并随机生成一个数值，然后使这个正方形中心的数值等于四角数值的和的平方根加上刚才生成的随机数，这样我们就得到了4个正方形了，然后重复以上步骤，即取四角并生成随机数，然后将正方形中心付值，这样经过A次以后，我们就有2的2N个正方形了，非常的满足 ：）
　　
　　接着我们考虑着色的问题，就以上算法而言，除了生成地形非常好之外，还能生成云纹理。很简单。由于数组值已经确定了，我们就可以将数值最大处着不透明的白色，最小处着兰色。依次平滑过度，而半透明效果将由RGBA的ALPHA分量决定。
　　
　　接下来我想讨论一下有关分形的平滑过度问题。
　　
　　通常的做法有两种：自平方和乘以一个叫做平滑系数的数字。我们先看自平方。所谓自平方，就是将某点或该点周围的数值经过平方或开方后付值给该点。这样做是由于2次曲线所具有的一些性质决定的。而开方函数也具有这样的优良性质。而使用平滑系数（一般叫做H数），则能使数值教较平滑过度。一般来讲，0　　
　　这就是现在我所要说的一些东西。假若以后想起了什么的话，我再做补充。