飞机引擎封装完毕后，自然考虑到外部环境了，这部分是进入玩家视野最多的部分，自然也要精心设计，否则对不起玩家的眼睛。

在2D游戏中，场景只是一张平面的图片，但是现在是在做3D游戏场景，玩家可以在游戏中允许的范围内任意改变视角，并且能够观察到其他角度的场景，要做到这种效果，必须想一种方法将2D图片贴在玩家的四周以及顶部和底部，让玩家即时在旋转180度后依然可以看到身后的场景。

根据DirectX8.1中一个示例的启发，我采用了立方体构造场景，根据顶点定义的顺序可以让立方体的内部贴图，而所有的物体都置于这个立方体内部，截个图就可以很形象描述了

 

也就是说，我们的所有活动都是在这个立方体内部进行了，就像古代的人们认为我们生活的空间是方的一样。为了显示效果，上边的图片只显示了两个内面，如果所有6个内面都想看到的话，那么就什么都看不到了呵呵~在游戏中，将这个立方体变换到一个比较大的尺寸，并且最重要的是让立方体跟随玩家的飞机移动，因为我们绝对不可以穿出这个立方体，无论飞到哪里，天还是那么远，甚至不能有跟天边逼近的感觉，否则总会到达天边的，真是应了“远看天边，近在眼前”，想不到3D游戏开发中不止要用到自然科学，还有社会科学的思想呵呵，其乐无穷。

这样看来，场景跟飞机一起移动，岂不是感觉不到飞机的移动了吗？还没有做完呢，还需要有陆地的衬托，当然也可以是海洋或者是什么其他的地面物体，因为陆地是不会随着飞机移动的，正所谓“路要踏踏实实的走，想着一步登天是永远到不了天边的”~~

地面实际上是一个平面，横向插入立方体，并且上面渲染不同的纹理，以及各种地形。在立方体空间模型下，这种地面会产生四个直角，在玩家旋转视角的时候，会感觉不真实。我想过一些弥补的办法，比如将地面的起伏落差加大，通过山峰遮盖住地面的直角，但是在该游戏中不适合，因为我们驾驶的飞机，在海面上飞行的时候，总会看到海天一线的，不可能前边总是高山。所以这种方法在使用了一天以后，以失败告终了！

接着想到用球体内面做场景，找了相关的资料，发现很多场景渲染都是这样做的，这里有一个“鱼眼”的概念，简单的说，就是通过平面贴图的构造方式，让贴了它的球体给人一种平面的感觉，也许跟鱼眼一样，可能这里又用了仿生学，再一次感叹3D游戏！

看以下这张鱼眼效果的2D贴图，你就会明白了！

 

我将它贴到游戏的场景中，看看效果

呵呵感觉飞机似乎成了玩具~~

球体内侧贴图的效果不太容易展示，所以我在球体外侧贴图，展示一下效果

看了这么久文字，也来动动你的脑子，把你的内存中将外贴图变换到内贴图想想究竟是什么效果呵呵。

这种贴图仍然存在一些不足，比如图片的质量不高，因为球体在游戏中会变得很大，所以环境贴图中最好只有天空，而不要加入其它的物体，因为天空内容比较单一，蓝天和白云，在拉伸比例很大的时候仍然可以保持很高的可观性，而其它物体就会发生失真，因为那毕竟是位图。其它的物理我们通过地面上的模型来实现，比如山峰、海洋、地面武器等。

今天所幸找到一个论坛上边有很多全景鱼眼贴图，正好全部下载，贴上几个，大家看看效果，当然以后不会在游戏中使用这些直接作为环境贴图。

日前，代号为:attackJapan的3D模拟游戏开发正式拉开帷幕，该款游戏的名字暂定为《空袭日本》，游戏中玩家将驾驶自己的飞机，飞跃浩瀚太平洋，驶入渺小的日本岛，在上空进行眼花缭乱的各种空投，投掷的弹药需要不断的升级，并且贯穿游戏始终。在主动进攻的同时，日本岛上会有一些地对空的武器，对玩家的飞机造成一定的威胁，在游戏中，玩家要巧妙的躲过岛上武器的袭击，并且击中它们，获得相应的分值，然后升级自己的武器……

呵呵~~看了以上的报道，你也许以为是哪家游戏公司的大作，其实不然，该游戏的创作是我昨天晚上跟北京的同学聊天时灵感突发，便有了在前几天做好的飞机引擎基础上完成这部游戏的想法。目前游戏制作工作室名字暂无，不过现任成员两名，我的同学策划游戏中武器升级系统，我则完成所有的其它的策划和实际开发。

那么这款游戏的历史意义究竟是什么呢？我想每个中国人都清楚，呵呵~每次说到这个问题上，中国人总是非常的有同感。当然这款游戏只是模拟游戏，并没有挑起战争的暗示，我们可以把它作为二战模拟游戏。前几年还有一些抗日题材的游戏，我玩过一个回合制的，一个射击类的，这款《空袭日本》就算是世界反法西斯模拟游戏的延续，以此来纪念在反法西斯战争中牺牲的无辜生命。并且在最近国内反日情绪高涨以及日本各种无承认历史的行为下，让奋斗过后更多无奈的国民能够在游戏中一解心头之恨。

关于该款游戏的大概剧情在前边已经提到了，但是具体的内容我们还在制定，同时也希望大家来留下来自己好的建议，比如一下几个方面：

游戏画面：包括3D场景、2D贴图、灯光等
游戏剧情：包括武器升级体系、游戏发展过程、关卡设置、胜利条件、奖励措施等
游戏操作：包括个人的按键习惯、按键分布、鼠标与键盘的配合、飞机导航系统等
游戏道具：包括各种武器的名称、参数等
游戏音乐：包括背景音乐、关卡音乐、各种音效
……

另外，我们也希望有兴趣并且有能力者加入到我们的开发，包括：

3DMax模型设计师
2D贴图设计师
游戏策划人员
游戏音乐原创人员

最后，贴一张游戏目前效果图

毕设已经交付测试了，优秀的系统要能经受住绝大多数用户的考验，但是永远不会十全十美。

最近我把全部的精力转移到了D3D平台。本来准备设计一个2D平台下的RPG游戏，因为有天晚上在图书馆看到一些东西，所以迸发出一些思想，改天会在Blog上写出一个大概的计划，想请大家都来集思广益，做一个游戏策划。

转入正题……

由于要帮忙给同学设计的一个3D飞机游戏中加入地图以及地图编辑器，我看了一些D3D文档和相关的论文，最后采用了Y坐标随机地形生成方法，其实道理很简单，比如一张10*10的地图，包括100个矩形，每个矩形是由2个三角形构成，所以这张地图一共有200个三角形，600个顶点（包括重合的顶点）。

这里顺便说一下索引缓冲，因为地形处理即消耗内存又占用cpu时间，如果是一张非常大的地图的话，那么对游戏的速度有很大的影响，600个顶点实际上真正只需要121个，因为去处了三角形重合的顶点，剩余的只有11*11=121个，这样就节省了479个顶点结构的空间，跟121对比，这绝对不是一个小数字。

在这121个顶点中，除了四边的定点以外，其它顶点的Y坐标随机生成，我们规定并且选择一个最大高度，尽量让生成的地形看起来比较平滑，但实际上只是逼近。看看以下的两张截图：

所有顶点Y坐标都是0.0

除四边外，所有的顶点去了随机的Y坐标

所用到的贴图

远处的两个小点是两个飞行器，可以当作敌机，呵呵~~我方的飞行器即将推出……

这种地形比较简单，更加复杂的是类似《三角洲部队》游戏里的那种带有山脉的地形，当然那种不是随机的，是地图编辑器做好的，但是原理跟这个是一样的，都是用三角形贴图无限逼近高低起伏的地势，而且在设计碰撞检测算法，这样才可以有人物造型在上边行走，还有各处的重力加速度以及前进加速度，总之3D游戏的设计是一门综合科学，希望有兴趣的朋友能够进入这个殿堂之门~

附：参考论文

Generating Random Fractal Terrain

Paul Martz
martz@frii.com

 

Introduction

Ten years ago, I stumbled across the 1986 SIGGRAPH Proceedings and was awestruck by one paper in particular, entitled The Definition and Rendering of Terrain Maps by Gavin S. P. Miller ¹ . It described a handful of algorithms for generating fractal terrain, and the authors also introduce a new method which they considered to be an improvement.

Initially I was impressed that these algorithms (even the algorithms considered “flawed” by the authors) could create such incredible landscape images! Then, upon reading the paper, I was floored by the simplicity of these algorithms.

I’ve been a fractal terrain addict ever since.

The math behind the algorithm can get quite complex. However, completely understanding the math is not a prerequisite for grasping the algorithm. And that’s good. Because if I had to explain all the math to you before explaining the algorithm, we’d never get to the algorithm. Besides, there is literally tons of material out there on the mathematical concepts involved in fractals. See the references at the end of this article for a good start.

For the same reasons that I won’t go into the math details, I can’t include a broad overview of fractals and everything they can be used for. Instead, I’m going describe the concepts behind fractal terrain generation, and give a focused and detailed description of my personal favorite algorithm: the “diamond-square” algorithm. I’ll demonstrate how to use this algorithm to statically tessellate an array of height data that can be used for geometric terrain data, terrain texture maps, and cloud texture maps.

What can you do with a fractal terrain? I assume you already know that; that’s why you’re reading this. Random terrain maps are great for flight simulators or making texture maps to use as a background (showing a distant mountain range, for example). The same algorithm that makes terrain can also be used to generate texture maps for partly cloudy skies.

Before I go further, a disclaimer: I am not a game programmer. If you are reading this because you want algorithms for rendering terrain quickly, you’ve come to the wrong place. I’ll only describe the process of generating the terrain model. How you render it is up to you.

Self-Similarity

The key concept behind any fractal is self-similarity. An object is said to be self-similar when magnified subsets of the object look like (or identical to) the whole and to each other.²

Consider the human circulatory system. This is a fine example of self-similarity in nature. The same branching pattern is exhibited from the largest arteries and veins all the way down to the smallest capillaries. If you didn’t know you were using a microscope, you wouldn’t be able to tell the difference between capillaries and arteries.

Now consider a simple sphere. Is it self-similar? No. At significantly large magnification, it stops looking like a sphere altogether and starts looking like a flat plane. If you don’t believe me, just take a look outside. Unless you happen to be in orbit while reading this, you’ll see no indication that the Earth is a sphere. A sphere is not self-similar. It is best described using traditional Euclidean geometry, rather than a fractal algorithm.

Terrain falls into the “self-similar” category. The jagged edge of a broken rock in the palm of your hand has the same irregularities as a ridgeline on a distant horizon. This allows us to use fractals to generate terrain which still looks like terrain, regardless of the scale in which it is displayed.

A side note on self-similarity: In its strictest sense, it means self-identical, that is, exact miniature copies of itself are visible at increasingly small or large scales. I actually don’t know of any self-identical fractals that exist in nature. But the Mandelbrot set is self-identical. I won’t even go into describing the Mandelbrot set. Go dig up any of the references for more info.

Midpoint Displacement in One Dimension

The diamond-square algorithm, which I will describe later, uses a kind of midpoint-displacement algorithm in two dimensions. To help you get a grip on it, we’ll look at it first in one dimension.

One-dimensional midpoint displacement is a great algorithm for drawing a ridgeline, as mountains might appear on a distant horizon. Here’s how it works:

Start with a single horizontal line segment. Repeat for a sufficiently large number of times {  Repeat over each line segment in the scene {   Find the midpoint of the line segment.   Displace the midpoint in Y by a random amount.   Reduce the range for random numbers.  } }

How much do you reduce the random number range? That depends on how rough you want your fractal. The more you reduce it each pass through the loop, the smoother the resulting ridgeline will be. If you don’t reduce the range very much, the resulting ridgeline will be very jagged. It turns out you can tie roughness to a constant; I’ll explain how to do this later on.

Let’s look at an example. Here, we start with a line from -1.0 to 1.0 in X, with the Y value at each endpoint being zero. Initially we’ll set the random number range to be from -1.0 to 1.0 (arbitrary). So we generate a random number in that range, and displace the midpoint by that amount. After doing this, we have:

Now the second time through the outer loop, we have two segments, each half the length of the original segment. Our random number range is reduced by half, so it is now -0.5 to 0.5. We generate a random number in this range for each of the two midpoints. Here’s the result:

We shrink the range again; it is now -0.25 to 0.25. After displacing the four midpoints with random numbers in this range, we have:

Two things you should note about this.

First, it’s recursive. Actually, it can be implemented quite naturally as an iterative routine. For this case, either recursive or iterative would do. It turns out that for the surface generation code, there are some advantages to using an iterative implementation over a recursive one. So for consistency, the accompanying sample code implements both the line and surface code as iterative.

Second, it’s a very simple algorithm, yet it creates a very complex result. That is the beauty of fractal algorithms. A few simple instructions can create a very rich and detailed image.

Here I go off on a tangent: The realization that a small, simple set of instructions can create a complex image has lead to research in a new field known as fractal image compression. The idea is to store the simple, recursive instructions for creating the image rather than storing the image itself. This works great for images which are truly fractal in nature, since the instructions take up much less space than the image itself. Chaos and Fractals, New Frontiers of Science ³ has a chapter and an appendix devoted to this topic and is a great read for any fractal nut in general.

Back to reality.

Without much effort, you can read the output of this function into a paint program and come up with something like this:

This could be used as scenery outside a window, for example. The nice thing about it is that it wraps, so you can keep around one relatively small image and completely wrap a scene with it. That is, if you don’t mind seeing the same mountain in every direction.

OK, before we go into 2D fractal surfaces, you need to know about the roughness constant. This is the value which will determine how much the random number range is reduced each time through the loop and, therefore, will determine the roughness of the resulting fractal. The sample code uses a floating-point number in the range 0.0 to 1.0 and calls it H. 2^(-H) is therefore a number in the range 1.0 (for small H) to 0.5 (for large H). The random number range can be multiplied by this amount each time through the loop. With H set to 1.0, the random number range will be halved each time through the loop, resulting in a very smooth fractal. With H set to 0.0, the range will not be reduced at all, resulting in something quite jagged.

Here are three ridgelines, each rendered with varying H values:

Height Maps

The midpoint displacement algorithm described above can be implemented using a one-dimensional array of height values which indicate the vertical location of each line segment vertex. This array is a one-dimensional height map. It maps its indices (X values) to height values (Y values).

To simulate random terrain, we want to extrapolate this algorithm into 3D space, and to do so we need a two-dimensional array of height values which will map indices (X and Z values) into height values (Y values). Note that although our end goal here is to generate three-dimensional coordinates, the array only needs to store the height (Y) values; the horizontal (X and Z) values can be generated on the fly as we parse through the array.

By assigning a color to each height value, you could display a height map as an image. Here, high points in the terrain (large values) are represented by white, and low points (small values) are represented by black:

 Rendering a height map this way is useful for generating cloud texture maps, which I’ll discuss later. Such a representation could also be used to seed a height map.

Now I’ll describe how to tessellate our two-dimensional height map array.

The Diamond-Square Algorithm

As I mentioned at the start of this article, I was first introduced to the concept of generating random terrain in Gavin S. P. Miller’s paper ¹ . Ironically, Miller describes the diamond-square algorithm as flawed in this paper, and he then goes on to describe a different algorithm based on weighted averaging and control points.

Miller’s complaints with the diamond-square algorithm stem from his attempt to force the algorithm into creating a mountain, that is, with a peak, by artificially increasing the height of the grid center-point. He lets all other points in the array generate randomly. If Miller had simply generated the center-point randomly, then even he would’ve had to admit that the algorithm works pretty decently as a terrain generator. The Diamond-Square algorithm can be used to force a mountain with a peak, by “seeding” the array with values. More than just the center point of the array must be seeded to achieve acceptable results. He complains of some inherent creasing problems as well. But you judge for yourself. The algorithm is originally described by Fournier, Fussell, and Carpenter ⁴.

Here’s the idea: You start with a large empty 2D array of points. How big? To make it easy, it should be square, and the dimension should be a power of two, plus one (e.g. 33×33, 65×65, 129×129, etc.). Set the four corner points to the same height value. If you look at what you’ve got, it’s a square.

As a simple example, let’s use a 5×5 array. (We’ll be referring to this image later on in the article, so don’t forget about it.) In figure a the four corner “seed” values are highlighted in black:

This is the starting-point for the iterative subdivision routine, which is in two steps:

The diamond step: Taking a square of four points, generate a random value at the square midpoint, where the two diagonals meet. The midpoint value is calculated by averaging the four corner values, plus a random amount. This gives you diamonds when you have multiple squares arranged in a grid.

The square step: Taking each diamond of four points, generate a random value at the center of the diamond. Calculate the midpoint value by averaging the corner values, plus a random amount generated in the same range as used for the diamond step. This gives you squares again.

So if you were to seed a square and make a single pass through the subdivision routine, you would end up with four squares. Running it twice would yield 16 squares. A third pass would result in 64 squares. It gets big fast. The number of squares generated is equal to 2^(I+2), where I is the number of iterations through the recursive subdivision routine.

Referring to the previous five figures, Here’s what happens as we make two passes over the array with our diamond-square algorithm.

For the diamond step of the first pass, we generate a value at the center of the array based on the height of the four corner values. We average the four corner values (really not necessary if they were all seeded to the same value), and add a random value from the range -1.0 to 1.0. In figure b, the new value is shown in black, and the existing corner values are shown in gray.

For the square step, we use the same range for generating the random values. There are four diamonds at this stage; they all meet in the center of the array, so we calculate four diamond centers. The corners of the diamonds are averaged to find the base for the new values. Figure c shows the new values in black and existing values in gray.

That’s the first pass. If you were to connect these 9 points with lines, you might get a wireframe surface which looks like this:

Now we perform the second pass. Again start with the diamond step. The second pass is different from the first pass in two ways. First, we now have four squares instead of one, so we need to calculate four square centers. Second, and this is key,the range for generating random numbers has been reduced. For the sake of example, let’s say we are using an H value of 1.0. This will reduce our random number range from (-1.0, 1.0) to (-0.5, 0.5). In figure d, the four square center values we calculate at this step are shown in black.

Finally, we perform the square step for this second pass. With 12 diamond centers, we now need to calculate 12 new values. Figure e shows them in black.

Now, all 25 elements of the array have been generated. We might now have a wireframe surface which looks like this:

Had a larger array been allocated, we could have continued to make more passes, adding more detail in each pass. For example, after five passes, our surface might look something like this:

I previously mentioned that the array dimensions need to be a power of two plus one. This is because the number of floats needed in the 2D array is equal to (2^I+1)². Eight iterations would require a 257×257 array of floats, more than 256 Kbytes of memory for standard 32-bit IEEE floating-point numbers.

OK, so it’s big. Using chars instead of floats would help. The sample code uses floats; if memory is really a concern and you must use chars, it should be easy to modify the sample code to use a range of -128 to 128. But don’t forget to clamp those values as you generate them. Even if you limit your first pass to generating values between -128 and 128, subsequent passes could result in values outside this range, resulting in an overflow condition. This is especially likely for small values of H.

The sample code demonstrates another way to deal with the size problem. A large array is allocated and tessellated with the diamond-square algorithm. It is then rendered from a top-down orthographic view. This image is read back and used as a texture map on a second array tessellated to a lesser extent. Although the sample code doesn’t do this, once the image is read back from the framebuffer, the first array can be freed.

Here’s an example of one such texture map:

The map is artificially colored with white at the peaks, green in the valleys, and gray in between. Feel free to experiment with your own color scheme using the example source code provided.

Earlier I had mentioned that there are advantages to implementing this routine iterative rather than recursive. Here’s why: A recursive implementation might take the form:

 Do diamond step.  Do square step.  Reduce random number range.  Call myself four times.

That’s a nice simple implementation, and I have no doubt that it would work. But it requires that some points be generated with insufficient data. Why? After the first pass, you’ll be called upon to perform the square step without having all four corners of a diamond.

Instead, I’ve implemented this iteratively, and the basic pseudocode looks like this:

 While the length of the side of the squares   is greater than zero {  Pass through the array and perform the diamond   step for each square present.  Pass through the array and perform the square   step for each diamond present.  Reduce the random number range.  }

This eliminates the problem of missing diamond corners found in the recursive implementation. But you’ll run into this problem again anytime you generate a point on the edge of the array. It turns out this is only a concern in the square step. You can easily overcome this and simultaneously make the surface wrappable by taking into account that one of the four diamond corner points lies on the other side of the array. (Another key to making the surface wrappable is to remember to seed the four corners with the same value.)

Here’s an example of taking a diamond corner from the other side of the array. In the following figure, we generate a point in the square step, and it just happens to fall right on the edge. The four locations in the array which comprise the diamond corners are highlighted in gray. They need to be averaged to find the base for the new value, shown here in black.

Note that two values are highlighted in black. They are actually the same value. Every time you calculate a value on the edge during the square step, make sure to also store it on the opposite side of the array. These points need to be exactly the same in order for seamless wrapping to occur.

This means that in figure e earlier, we really didn’t need to calculate 12 separate values, since four of them are repeats of other values on the opposite side of the array. So actually, only 8 values needed to be calculated.

I’ll leave this as an exercise to the interested reader: Take the source code and make it work without having repeated elements on the edges. It’s really not necessary for the algorithm to work; it just happens to be the way I wrote it.

If you haven’t played with the sample program yet, now might be a good time to open it up and have a look. It starts up with a surface generated with two iterations. It is rendered in wireframe, simply by connecting the values of the array with line segments. The array values are treated as Y values, while the X and Z coordinates of each vertex are generated on the fly as the array is parsed. This could easily be rendered as triangles by breaking each square up into two triangles. Triangles are generally good primitives to use since they are always convex and always planar.

Go into the View Options dialog box and tweak the Random seed value. This should cause a different surface to be generated. Tweak the Iterations value a little higher to add more detail to the surface. The code limits this value to 10, which is a little much for my 32 Meg RAM Pentium Pro system and just looks black anyway. (Five years from now, people will run this code on new processors and higher resolution screens and wonder why on Earth I limited that to 10…)

The first H value controls the roughness of the surface. By default it is set to 0.7. Try setting it higher and lower and note the results.

Yes, this algorithm does occasionally produce localized spikes and some creasing. But I tend to like the surreal nature of the spikes, and the creasing is not obvious depending on what angle you are viewing it from, or how fast you’re flying over it.

Cloudy Skies

Now we know how to generate the surface. We can either generate and render tons of triangles, or we can generate a high-res texture map and apply it to a low-res surface. Either way, it looks pretty cool. Now how do we generate some sky overhead? It’s easier than you think.

The array, after being completely tessellated by the diamond-square algorithm, is ideally suited for representing a texture map of a cloudy sky. Instead of thinking of the array as a collection of Y values in a height map, think of it as cloud opacity data. The smallest array values represent the bluest, clearest parts of the sky, and the largest array values represent the whitest, cloudiest part of the sky.

It’s trivial to parse through the array and generate a texture map like so:

This is very similar to the height map image earlier in this article, but I have clamped the low and high values to create patches of clear and clouded sky.

You can produce an image like this with the sample code. Set the Select rendering type pulldown menu to 2D mesh / clouds. (By default it will look pixelated. Try setting the Cloud iterations value to eight or higher to fix this.) Try different settings for the H value, immediately preceding the Cloud iterations value, to get different cloud effects.

If you go back up to the top of this article, the very first image puts together much of what I’ve discussed here. The sky is made with a texture map as shown above, tiled multiple times over an eight-sided pyramid. The surface geometry is rendered with a high-res texture map. This texture map was generated by rendering a highly-tessellated lit surface from a top-down orthographic view. The image was then read back and used as the texture map.

The accompanying example program was used to generate nearly all of the images that appear in this article.

Other Methods

You’ll probably want to have a little more control over the surface generation than what the sample code has provided. You might, for example, want to initially seed the first few passes of the array with your own values, so that mountains, valleys, etc., can be placed according to your own design. Then, fill out the rest of the detail using the diamond-square algorithm.

Don’t just kick the central array point upwards like Gavin Miller did, to create a mountain. To get reasonable results, you’ll need to seed at least two or three passes of the array.

This is easily accomplished by altering the code to skip over assigning values to elements of the array that already have values. Initialize your array to, say, -10.0, seed the first few iterations with your own values, and enhance the fractal generation code to only assign values where the current value is -10.0. The first few iterations will not generate any values, since your seed values are already there. Subsequent passes will generate new values based on your seed values.

How to get the seed values? Well, if the shape you want follows a known mathematical form, such as a sine curve, then simply use that function to generate the values. Otherwise, you’ll need to find some other creative way to do it. One method I have seen used is to paint your own height map with gray values. Map the gray values to height values and store them in your array. Then use the diamond-square algorithm to add more detail.

Besides the diamond-square algorithm, there are plenty of other methods for tessellating surfaces.

With successive random addition, a random region of the 2D array is incremented by a small amount. Repeat this process over and over, adding a small amount into each randomly chosen region of the array. This generates good results but is not computationally linear. If compute time is not a concern, I encourage you to try this algorithm out.

Another similar method involves making a “fracture” across the array and incrementing one side of it, as if an earthquake had occurred. Again, repeat several times. This is also not a linear algorithm and takes several passes to get acceptable results.

Refer to the references for many other different approaches.

　　最近网上到处都是反对日本“入常”的签名活动，先不说活动本身，单看签名本身就觉得没有什么说服力，这些签名的数量能说明什么问题？中国按照13亿人口来算，现在就算官方签名有5亿，那剩下的8亿到底是什么态度？不知道！何况现在签名可能连1亿都没有，更有一些网站是乘着这个机会，做一回免费的自我宣传，到处群发信息，你还不能说它是垃圾信息……

　　有位网友说，为什么不再作一个[赞成日本“入常”]的签名，我们也好进行数据对比。但是我们的网站都相信不会有多少人去那里签名的，甚至一个人都不会，如果有人签名，那个人一定是日本人，而且害怕万一日本黑客利用漏洞把赞成投票变多，我想日本黑客既然有那个本事，那同样也能把不赞成签名变少。那说来说去，签名没有安全性，没有可靠性，没有对比性，签名还有什么意思啊，可能只是证明一下我们有多么强烈的反日决心，但是再强烈，跟韩国两位游行者断指反抗日本关于独岛的行为相比，还差一截，我们做的也不过就是点点鼠标，只不过人多势众。

　　最近，北京、上海等城市又爆发了反日游行，砸日本车和日本店，但是为什么不直接去砸日本人呢？我一向也非常讨厌日本的很多行为，但是我不赞成在中国领土上砸中国人买来的日本东西，有本事去日本砸日本店，我不会反对！但是这可能吗？日本也是很强硬的，会出来制止的，所以不能在日本砸了，就在中国砸？为什么呢？说到底还是中国好欺负，连自己的同胞都欺负自己，还有什么权力不让别人欺负自己。

　　说到日本“入常”，任何一个反对的中国人都是出于曾经饱受日本侵略摧残后的仇视，当初的清政府以及国民党政府软弱无能，导致了近代中国历史上的幕幕惨剧。而回顾清朝之前，我们的领土总是在不断的扩大，因为我们强大，总是在欺负周围的邻国。但是逐渐的，我们固步自封，在科学领域发展缓慢，如果那个时候直到现在，我们一直都在抵制外国产品的话，我想现在我们至少要比国际水平落后100年。看看现在，我们再用日本产品，日本也在用我们的产品，中日贸易是国际第一的，如果中日直接中断了贸易，并不是很多人想象中的日本企业会关闭，而我们中国胜利了。结果对我们中国更加不利，导致我们在有些领域技术落后，发展缓慢，跟日本差距拉大。当然我们还可以引进其他国家的技术，但是日本的有些技术是国际领先的，我们不得不承认，那么我们为什么不直接拿来用到自己国家建设中呢。

　　在使用日本技术的同时，希望游行的这些大学生，能够把时间都用到研发自己的技术，等有一天我们自己的产品超过日本了，抵制日货就不只是一句空话了！

附：香港《文汇报》9日发表资深评论员刘斯路撰写的文章《中日关系的理性思维》

原文提要

　　中国和亚洲人民在处理对日问题上需要更多的理性思维。目前，要反的不是日本企业，不是日本人民，也不是日本文化、日本的产品、日本的技术、日本的资金，要反的是日本右翼势力及其政策。如果将反对日本右翼简化为“反日”，正好为日本右翼所用，进一步煽动日本国民的反华情绪，使他们的右翼政策有植根之处。

　　就中国的利益而言，中国百姓在处理对日问题上需要更多的理性思维。

　　日本“入常”，中国和许多亚洲国家认为，这是一个够不够格的问题。但是，日本的出版社又一次公然篡改二战中日本的侵略历史，则是绝对不能原谅的事情。中国人不能原谅，韩国人不能原谅，受过日本侵略的地区的人民不能原谅。值得思考的问题是，小泉政府为什么一再在历史问题上发出挑衅，他就真的不知道中国和亚洲人民的反对吗？看来，事件有深层次的内在因素。

　　有人解释，这是日本的右翼势力抬头。也有人说，这是日本追随美国围堵中国政策的结果。在中东问题稍为安定下来后，美国加大了对中国的遏制，日本充当马前卒。所以动作频仍。其实，这些看法都是表面的。影响日本对华政策的基点，是日本的国家利益。20年前，中国的经济规模才是日本的零头，现在已有日本的1／3，而且中国的发展速度远高于日本，与日本平起平坐指日可待。亚洲双雄争霸的态势已经成形。同时，围绕着能源和其他资源争夺的东海经济海域、钓鱼岛及其他礁石的纷争，日益尖锐。这只能解释为中日的国家利益之争。日本的日益右倾化，则不过是表象。

　　但是，中日之间的共同利益，又是再明显不过。中日之间的经贸，世界第一。中国如果抵制日货，日本也会抵制中国货，结果是两败俱伤。所以，北京有要求理性处理对日关系的声音，日本也有要求小泉政府改善对华关系的声音。最终，中日两国终将能够冷静地权衡战略利弊，促使两国关系走向相对协调与稳定。　事实上，日本的政治势力也不是铁板一块。日本媒体也认为国内有四股政治势力：其一是“亲美国际派”，在外交上主张紧跟美国，主张“日美安保条约至上”，现在这一派占主流，小泉内阁就在沿袭这种主张；其二是“亚洲国际派”，主张开展独立自主的日本外交，既重视对美关系，也重视对亚洲特别是对中国的关系，主张在美中日之间建立一种相对平衡的三角关系，其代表人物是自民党政治家加藤弘一等人；其三是“理性民族派”，在国内政治上倾向于民族主义，强调日本的国家理念与国家战略，但在国际关系上能理性对待，认为日本必须与亚洲国家搞好关系，特别是与正在崛起的中国搞好关系，共同构筑东亚共同体，其代表人物是前首相中曾根康弘；其四是“极端民族派”，其民族主义色彩比理性民族派更加浓厚、更带感情色彩，在对外关系上既有一定的反美情绪，更有强烈的反华情绪和言行，主张构筑以日本为中心、排除中国的东亚经济圈，以对抗中国的崛起，其代表人物是东京都知事石原慎太郎。

　　真理只要多走一小步，就会变成谬误。目前，中国和亚洲人民要反的是什么，不是日本企业，不是日本人民，也不是日本文化、日本的产品、日本的技术、日本的资金，要反的是日本右翼势力及其政策。如果将反对日本右翼，简化为“反日”，正好为日本右翼所用，进一步煽动日本国民的反华情绪，使他们的右翼政策有植根之处。（完）（来源：参编）