MikeRandrup

Have you ever played the video game called From Dust? It contains intriguing land, water, and lava simulation. Since first playing it, I have been fascinated with the results of Ubisoft’s very interesting simulation system. I developed an inspired guess as to how the basic algorithm and technique might work. During some holiday downtime, I put code to the concept and came up with the following:

The algorithm steps through a pair of 2 Dimensional arrays containing the height of land and water at each coordinate in the grid. During each step, it determines if and where the water would run downhill, then adjusts the old and new values accordingly. The resolution of the grid was limited by the performance of Flash, which I could no doubt have improved dramatically by using more advanced stage drawing techniques. After running and adjusting the simulations in Flash, I switched the movie to export a JPG image of each frame. That sequence was then run through After Effects (frame blend) to smooth the adjustments. The final sequences were then applied as separate Y-axis displacement maps on “land” and “water” objects in Lightwave 3D.

In the first of the two animations (mountain springs running downhill into a valley), a trio of simple “water emitters” put out a finite amount of water at the tops of the hills, and the algorithm runs it downhill to pool at the bottom. The land was generated with high values at the edges, and low values at the center, with a touch of randomization of the terrain (a “valley”).

In the second (sea mountain rising), a flat land mass with water sitting on top (an “ocean”) is affected by a strong “land emitter” which pushes a mountain out of the sea floor. The water is reacting by being displaced downhill from the land. The circular wave of water was the natural product of the algorithm I created, which seems to indicate being on the right track for how the video game works internally.

Why generate the frames in Flash AS3? Frankly, that choice was due to my own limitations as a programmer. Also, my algorithm fails to ever resolve the water to a natural state of a flat surface.

I now have an even greater sense of awe for what the Ubisoft team achieved with their amazing video game. For example, the game contains dynamic water foam textures which give realistic cues to how the water runs downhill and around obstacles.

The Flash AS3 source code is below. I realize my coding techniques are horrible, and not even object oriented. Had this been for anything other than a proof-of-concept fun project, many loose ends would be wrapped up. There was nothing else in the Flash movie, as it creates all needed movieclips dynamically. If you want to try it, just create a new Flash (ActionScript v3) document and paste the below into the frame 1 actions. It reflects the coding for the “mountain rising out of the sea” effect.

 ActionScript 3 | 
 copy code |
?
 
001
002
import flash.display.MovieClip;
003
import flash.events.MouseEvent;
004
import flash.events.KeyboardEvent;
005
import flash.geom.Matrix;
006
//import com.adobe.images.JPGEncoder; // external library used for saving frames
007
 
008
stop();
009
var frameNum:int = 99;
010
 
011
var resX:int = 40;
012
var resY:int = resX;
013
 
014
var paintStrength:Number = 1;
015
 
016
var tileSpacing:int = 0;
017
var tileWidth:int = stage.stageWidth/(resX+(resX*tileSpacing));
018
var tileHeight:int = stage.stageHeight/(resY+(resY*tileSpacing));
019
 
020
var alreadyEmitted:Number = 0;
021
var maxEmitted:Number = 0;
022
 
023
var edgeValue:Number =  0;
024
var maxBoundary:int = resX-1;
025
var drawValue:Number = paintStrength;
026
var editMode:String = "water";
027
var hideLand:Boolean = false;
028
var hideWater:Boolean = false;
029
 
030
var waterInit:Number = 0.1;
031
var landInit:Number = 0.05;
032
 
033
var updateTimer:Timer = new Timer(250);
034
updateTimer.addEventListener(TimerEvent.TIMER, advanceFrame);
035
updateTimer.start();
036
 
037
// used to capture frames in non-realtime
038
//stage.addEventListener(KeyboardEvent.KEY_DOWN, advanceFrame);
039
 
040
function advanceFrame(e:TimerEvent):void{
041
	updateMap(null)//commands
042
}
043
 
044
var parent_mc:MovieClip = new MovieClip();
045
stage.addChild(parent_mc);
046
 
047
var landMap:Array = new Array();
048
var landHeight:Number = 0;
049
landMap.push(new Array());
050
for (var yInit:int=0; yInit<resy ; yInit++) {
051
	var newRow:Array = new Array();
052
	//newRow.splice(0,newRow.length);
053
	newRow[0] = new Array();
054
	for (var xInit:int=0; xInit<resX; xInit++) {
055
		landHeight = landInit;//+(Math.random()*.1);
056
		newRow[0].push(landHeight);
057
	}
058
	landMap[0].push(newRow);
059
}
060
 
061
var waterMap:Array = new Array();
062
waterMap.push(new Array());
063
for (yInit=0; yInit<resY; yInit++) {
064
	var waterRow:Array = new Array();
065
	//newRow.splice(0,newRow.length);
066
	waterRow[0] = new Array();
067
	for (xInit=0; xInit<resX; xInit++) {
068
		waterRow[0].push(waterInit);
069
	}
070
	waterMap[0].push(waterRow);
071
}
072
 
073
function calculate_new(x:int, y:int):void {
074
	var newVal:Number = 0;
075
	var newDelta:Number = 0;
076
	var proposedX:int = 0;
077
	var proposedY:int = 0;
078
 
079
	var minLevel:Number = 100;
080
	var minX:int = 0;
081
	var minY:int = 0;
082
 
083
	var curLand:Number;
084
	var curWater:Number;
085
	var checkLand:Number;
086
	var checkWater:Number;
087
 
088
	curLand = landMap[0][y][0][x];
089
	curWater = waterMap[0][y][0][x];
090
	for ( var neighborX:int=-1; neighborX<=1; neighborX++) {
091
		for ( var neighborY:int=-1; neighborY<=1; neighborY++) {
092
 
093
			proposedX = x+neighborX;
094
			proposedY = y+neighborY;
095
			if (
096
				(proposedX&lt;0) || (proposedY&lt;0) ||
097
				(proposedX>maxBoundary) || (proposedY>maxBoundary) 
098
			) {
099
				//trace('skipping edge');
100
			}
101
			else {
102
				checkLand = landMap[0][proposedY][0][proposedX];
103
				checkWater = waterMap[0][proposedY][0][proposedX];
104
				if (neighborX==0 && neighborY==0) {
105
					//trace('skipping self');
106
				}
107
				else {
108
					if ((checkLand+checkWater)<minlevel ) {
109
						minLevel = checkLand+checkWater;
110
						minX = proposedX;
111
						minY = proposedY;
112
						//trace('new tallness found: ' + minLevel);
113
					}
114
				}
115
			}
116
		}
117
	}
118
	compare_cells(x, y, minX, minY);
119
}
120
 
121
function compare_cells(curX:int, curY:int, checkX:int, checkY:int):void {
122
	var delta:Number;
123
	var curLand:Number = landMap[0][curY][0][curX];
124
	var curWater:Number = waterMap[0][curY][0][curX];
125
	var checkLand:Number = landMap[0][checkY][0][checkX];
126
	var checkWater:Number = waterMap[0][checkY][0][checkX];
127
	var idealLevel:Number = 0;
128
 
129
	// if there is water here
130
	if (curWater > 0) {
131
		//if this water should fall
132
		if ((curLand+curLand) > (checkLand+checkWater) ) { 
133
 
134
			// get the goal average height between the two including water
135
			idealLevel = (curLand + curWater + checkLand + checkWater)/2;
136
			if (idealLevel > curLand) { idealLevel = curLand};
137
 
138
			delta = curLand + curWater - idealLevel;
139
			delta *= 0.3;
140
			waterMap[0][curY][0][curX] -= delta;
141
			waterMap[0][checkY][0][checkX] += delta;
142
		}
143
	}
144
}
145
 
146
function updateMap(eventObject:MouseEvent):void {
147
	frameNum++;
148
 
149
	// clean up stage from last update
150
    if(parent_mc.numChildren!=0){
151
        var cond:int = parent_mc.numChildren;
152
        while( cond -- ) {
153
            parent_mc.removeChildAt( cond );
154
        }
155
    }
156
 
157
	var shading:Number = 0;
158
	for (var k in waterMap[0]) {
159
		for (var i in waterMap[0][k][0]) {
160
			var square:Shape = new Shape();
161
			var squareMC:MovieClip = new MovieClip();
162
			calculate_new(i,k);
163
 
164
			if (waterMap[0][k][0][i]>0.001 ) { // water is on this spot
165
				shading = get_water_color(k,i);
166
			}
167
			else { // land is showing on this spot
168
				shading = get_land_color(k,i);
169
			}
170
 
171
			square.graphics.beginFill(shading);
172
			square.graphics.drawRect(0, 0, tileWidth, tileHeight);
173
			square.graphics.endFill();
174
 
175
			squareMC.addChild(square);
176
			squareMC.x = (i * (tileWidth + tileSpacing + tileSpacing)) + tileSpacing;
177
			squareMC.y = (k * (tileHeight + tileSpacing + tileSpacing)) + tileSpacing;
178
 
179
			parent_mc.addChild(squareMC);
180
		}
181
	}
182
 
183
	//save_screenshot();  // used to capture frames in non-realtime
184
 
185
	// water emmitters
186
	emit_water();
187
	progress_land();
188
	trace(frameNum);
189
}
190
 
191
function get_land_color(y:int, x:int):Number {
192
	var color:Number = (int)(landMap[0][y][0][x] * 0xFF);
193
	if (color < 0) { color = 0 }
194
	if (color > 255) { color = 255 }
195
	color = (color < < 16) | (color << 8) | color; // maps to grey of RGB
196
	return(color);
197
}
198
 
199
function get_water_color(y:int, x:int):Number {
200
	var color:Number = 0;
201
	if (waterMap[0][y][0][x] >0)
202
		color = (waterMap[0][y][0][x] + landMap[0][y][0][x]) * 0xFF;
203
 
204
	if (color < 0) { color = 0 }
205
	if (color > 255) { color = 255 }
206
 
207
	// the below line draws the water in greyscale, otherwise shades of blue
208
	// as in an RGB value, the blue is in the least significant digits
209
	//color = (color < < 16) | (color << 8) | color; // maps to grey of RGB
210
	return(color);
211
}
212
 
213
/* 
214
function save_screenshot():void {
215
	var jpgSource:BitmapData = new BitmapData (stage.stageWidth, stage.stageHeight);
216
	jpgSource.draw(stage);
217
 
218
	var jpgEncoder:JPGEncoder = new JPGEncoder(100);
219
	var jpgStream:ByteArray = jpgEncoder.encode(jpgSource);
220
	var file:FileReference = new FileReference();
221
 
222
	file.save(jpgStream, 'riseLand-'+frameNum+'.jpg');
223
}
224
*/
225
 
226
function emit_water():void {
227
	if (alreadyEmitted < maxEmitted) {
228
		if (waterMap[0][int(resY*.30)][0][int(resX*0.95)]<.3) {
229
			waterMap[0][int(resY*.30)][0][int(resX*0.95)] += .2;
230
			alreadyEmitted += .2;
231
		}
232
		if (waterMap[0][int(resY*.10)][0][int(resX*0.45)]<.3) {
233
			waterMap[0][int(resY*.10)][0][int(resX*0.45)] += .1;
234
			alreadyEmitted += .1;
235
		}
236
 
237
		if (waterMap[0][int(resY*.85)][0][int(resX*0.15)]<.3) {
238
			waterMap[0][int(resY*.85)][0][int(resX*0.15)]+= .05;
239
			alreadyEmitted += .05;
240
		}
241
	}
242
}
243
 
244
var landAdded:Number = 0;
245
var landMax:Number = 200;
246
var cur_landshift:Number = 0;
247
var max_landshift:Number = 100;
248
 
249
function progress_land():void {
250
	var proposedX:int;
251
	var proposedY:int;
252
 
253
	// these are the land emitters in the center.
254
	if (landAdded < landMax) {
255
		landMap[0][int(resY*.5)][0][int(resX*0.5)]+= 2;
256
		landAdded += 2;
257
	}
258
 
259
	cur_landshift++;
260
	if (cur_landshift > max_landshift) { return; }
261
 
262
 
263
	for (var k in landMap[0]) {
264
		for (var i in landMap[0][k][0]) {
265
			for ( var neighborX:int=-1; neighborX< =1; neighborX++) {
266
				for ( var neighborY:int=-1; neighborY<=1; neighborY++) {
267
					proposedX = i+neighborX;
268
					proposedY = k+neighborY;
269
					if (
270
						(proposedX&lt;0) || (proposedY&lt;0) ||
271
						(proposedX>resX-1) || (proposedY>resY-1) 
272
					) {
273
						//trace('skipping land edge');
274
					}
275
					else {
276
						shift_land(i, k, proposedX, proposedY);
277
					}
278
				}
279
			}
280
		}
281
	}
282
}
283
 
284
function shift_land(curX:int, curY:int, checkX:int, checkY:int):void {
285
	var delta:Number = landMap[0][curY][0][curX] - landMap[0][checkY][0][checkX];
286
	delta *= .5;
287
	landMap[0][curY][0][curX] -= delta;
288
	landMap[0][checkY][0][checkX] += delta;
289
}
290
 
291
</minlevel></resy>