分形地形算法
24 Oct 2012
好久没写东西，这个算法是去年就看到别人有用THREE.JS写过，自己也玩一下。
关于分形地形请参考这篇文章：http://gameprogrammer.com/fractal.html
(function() {
function generateTerrain(width, height, smoothness) {
var smoothness = typeof smoothness === 'undefined' ? 1 : smoothness;
var size = smallestPowerOfTwoAfter(Math.max(width, height));
var squareTerrain = generateSquareTerrain(size, smoothness);
var terrain = [];
for (var i = 0; i <= height; ++i) {
terrain.push(squareTerrain[i].slice(0, width + 1));
}
return terrain;
}
function smallestPowerOfTwoAfter(n) {
var ret = 1;
while (ret < n) {
ret <<= 1;
}
return ret;
}
function generateSquareTerrain(size, smoothness) {
if (size & (size - 1)) {
throw new Error('Expected terrain size to be a power of 2, received ' +
size + ' instead.');
}
var mat = generateMatrix(size + 1);
iterate(mat, smoothness);
return mat;
}
function generateMatrix(size) {
var matrix = [];
for (var i = 0; i < size; i++) {
var row = [];
for (var j = 0; j < size; ++j) {
row.push(0);
}
matrix.push(row);
};
return matrix;
}
function iterate(matrix, smoothness) {
var counter = 0;
var numIteration = Math.log(matrix.length - 1) / Math.LN2;
while (counter++ < numIteration) {
diamond(matrix, counter, smoothness);
square(matrix, counter, smoothness);
}
}
function diamond(matrix, depth, smoothness) {
var len = matrix.length;
var terrainSize = len - 1;
var numSegs = 1 << (depth - 1);
var span = terrainSize / numSegs;
var half = span / 2;
for (var x = 0; x < terrainSize; x += span) {
for (var y = 0; y < terrainSize; y += span) {
// (x, y)
// \
// a---b---c
// | | |
// d---e---f
// | | |
// g---h---i
//
// \___ ___/
// V
// span
//
var va = [x, y];
var vc = [x + span, y];
var ve = [x + half, y + half];
var vg = [x, y + span];
var vi = [x + span, y + span];
var heights = [va, vc, vg, vi].map(function(v) {
return matrix[v[1]][v[0]];
});
var avg = average(heights);
var offset = getH(smoothness, depth);
matrix[ve[1]][ve[0]] = avg + offset;
}
}
}
function square(matrix, depth, smoothness) {
var len = matrix.length
var terrainSize = len - 1;
var numSegs = 1 << (depth - 1);
var span = terrainSize / numSegs;
var half = span / 2;
for (var x = 0; x < terrainSize; x += span) {
for (var y = 0; y < terrainSize; y += span) {
// h = avg(g, c, i, m) + random;
// f = avg(a, g, k, i) + random;
// j = f;
//
// (x, y)
// \
// a---b---c---d---e
// | \ | / | \ | / |
// f---g---h---i---j
// | / | \ | / | \ |
// k---l---m---n---o
// | \ | / | \ | / |
// p---q---r---s---t
// | / | \ | / | \ |
// u---v---w---x---y
//
// \___ ___/
// V
// span
//
var va = [x, y];
var vb = [x + half, y];
var vc = [x + span, y];
var vf = [x, y + half];
var vg = [x + half, y + half];
var vh = [x + span, y + half];
var vk = [x, y + span];
var vl = [x + half, y + span];
var vm = [x + span, y + span];
var vhr = [x + half * 3, y + half];
if (vhr[0] > terrainSize) vhr[0] = half;
var vfl = [x - half, y + half]
if (vfl[0] < 0) vfl[0] = terrainSize - half;
var vlu = [x + half, y + half * 3];
if (vlu[1] > terrainSize) vlu[1] = half;
var vba = [x + half, y - half]
if (vba[1] < 0) vba[1] = terrainSize - half;
squareHelper(matrix, depth, smoothness, va, vg, vk, vfl, vf);
squareHelper(matrix, depth, smoothness, va, vba, vc, vg, vb);
squareHelper(matrix, depth, smoothness, vc, vhr, vm, vg, vh);
squareHelper(matrix, depth, smoothness, vk, vg, vm, vlu, vl);
}
}
for (var y = 0; y < terrainSize; y += span) {
matrix[y][terrainSize] = matrix[y][0];
}
for (var x = 0; x < terrainSize; x += span) {
matrix[terrainSize][x] = matrix[0][x];
}
}
function squareHelper(matrix, depth, smoothness, a, b, c, d, t) {
var heights = [a, b, c, d].map(function(v) {
return matrix[v[1]][v[0]];
});
var avg = average(heights);
var offset = getH(smoothness, depth);
matrix[t[1]][t[0]] = avg + offset;
}
function getH(smoothness, depth) {
var sign = Math.random() > 0.5 ? 1 : -1;
var reduce = 1;
for (var i = 0; i < depth; ++i) {
reduce *= Math.pow(2, -smoothness);
}
return sign * Math.random() * reduce;
}
function average(numbers) {
var sum = 0;
numbers.forEach(function(v) {
sum += v;
});
return sum / numbers.length;
}
var root;
if (typeof exports !== 'undefined' && exports !== null) {
root = exports;
} else {
root = window;
}
root.generateTerrain = generateTerrain;
}).call(this);
var RandomPool = (function() {
var origRandom = Math.random;
var pool = [];
var counter = 0;
function next() {
var rand;
if (counter >= pool.length) {
rand = origRandom();
pool.push(rand);
} else {
rand = pool[counter];
}
counter++;
return rand;
};
function seek(index) {
counter = Math.min(index, pool.length);
}
function reset() {
counter = 0;
pool = [];
}
function hook() {
Math.random = next;
}
function unhook() {
Math.random = origRandom;
}
return {
next : next,
seek : seek,
reset : reset,
hook : hook,
unhook : unhook
};
})();
var TerrainModel = (function(){
var model;
function update(opts){
var size = opts.size || 32;
var smoothness = opts.smoothness || 1.0;
var zScale = opts.zScale || 200;
model = generateTerrain(size, size, smoothness);
updateZ(zScale);
}
function updateZ(z){
var width = model[0].length;
var height = model.length;
var terrain = [];
var i, j;
var row;
for(i = 0; i < height; ++i){
row = [];
for(j = 0; j < width; ++j){
row.push(model[i][j] * z);
}
terrain.push(row);
}
$.publish('terrain-update',[terrain]);
}
return {
update : update,
updateZ : updateZ
};
})();
var TerrainView = (function(){
var renderer;
var scene;
var camera;
var mesh;
function init(container){
var $container = $(container);
var width = $container.width();
var height = $container.height();
var ratio = width / height;
var near = 1;
var far = 6000;
var fov = 45;
scene = new THREE.Scene();
camera = new THREE.PerspectiveCamera(fov, ratio, near, far);
camera.position.y = 400;
if(!Detector.webgl){
renderer = new THREE.CanvasRenderer();
}else{
renderer = new THREE.WebGLRenderer({
clearColor: 0xf1f1f1,
clearAlpha: 1,
antialias: true
});
}
renderer.setSize(width, height);
renderer.shadowCameraNear = 3;
renderer.shadowCameraFar = camera.far;
renderer.shadowCameraFov = 50;
renderer.shadowMapBias = 0.0039;
renderer.shadowMapDarkness = 0.5;
renderer.shadowMapEnabled = true;
renderer.shadowMapSoft = true;
setupLights();
$container.append(renderer.domElement);
}
function setupLights(){
var ambientLight = new THREE.AmbientLight(0xffffff, 0.9);
scene.add(ambientLight);
var mainLight = new THREE.SpotLight(0xffffff, 1.0);
mainLight.position.set(500, 500, 500);
mainLight.castShadow = true;
scene.add(mainLight);
var auxLight = new THREE.SpotLight(0xffffff, 1.0);
auxLight.position.set(-300, 500, -400);
auxLight.castShadow = true;
scene.add(auxLight);
}
function getTerrainMesh(model){
var modelWidth = model[0].length - 1;
var modelHeight = model.length - 1;
var segLength = getOptimalSegLength(modelWidth, modelHeight);
var height = (model.length - 1) * segLength;
var width = (model[0].length - 1) * segLength;
var mesh = new THREE.Mesh(
new THREE.PlaneGeometry(width, height, model.length - 1, model.length - 1),
new THREE.MeshLambertMaterial({
color: 0xbb3355,
wireframe: true,
})
);
mesh.rotation.x = -Math.PI / 2;
mesh.castShadow = true;
mesh.receiveShadow = true;
var vertices = mesh.geometry.vertices;
for(var i = 0; i< model.length; ++i){
for(var j = 0; j < model.length; ++j){
vertices[i * model.length + j].position.z = model[i][j];
}
}
return mesh;
}
function getOptimalSegLength(width, height){
return ~~(640 / Math.max(width, height));
}
function drawCoordinate(center, length){
var orthogonal = [
[new THREE.Vector3(length, 0, 0), 0xff0000],
[new THREE.Vector3(0, length, 0), 0x00ff00],
[new THREE.Vector3(0, 0, length), 0x0000ff]
];
for(var i = 0; i< orthogonal.length; ++i){
var v = orthogonal[i][0];
color = orthogonal[i][1];
var geometry = new THREE.Geometry();
geometry.vertices.push(new THREE.Vertex(center));
geometry.vertices.push(new THREE.Vertex(center.clone().addSelf(v)));
var line = new THREE.Line(
geometry,
new THREE.LineBasicMaterial({
color: color,
opacity: 1,
linewidth: 3
})
);
scene.add(line);
}
}
function getTexture(model, width, height){
var modelWidth = model[0].length - 1;
var modelHeight = model.length;
var ratio = width / modelWidth;
var canvas = document.createElement('canvas');
canvas.width = width;
canvas.height = height;
var context = canvas.getContext('2d');
var imageData = context.getImageData(0, 0, width, height);
var pixels = imageData.data;
var i = 0;
var xx = 0;
var yy = 0;
var rgba;
for(var y = 0; y < height; ++y){
for(var x = 0; x < width; ++x){
yy = ~~(y / ratio);
xx = ~~(x / ratio);
rgba = elevation2RGBA(modelp[yy][xx]);
pixels[i++] = rgba[0];
pixels[i++] = rgba[1];
pixels[i++] = rgba[2];
pixels[i++] = rgba[3];
}
}
context.putImageData(imageData, 0, 0);
texture = new THREE.Texture(
canvas,
new THREE.UVMapping(),
THREE.ClampToEdgeWrapping,
THREE.ClampToEdgeWrapping
);
texture.needsUpdate = true;
return texture;
}
function elevation2RGBA(elevation) {
if (elevation > 0.5) {
return [255, 255, 255, 255];
} else if (elevation > 0){
return [104, 53, 20, 255];
} else {
return [58, 131, 21, 255];
}
}
function update(evt, model){
scene.remove(mesh);
mesh = getTerrainMesh(model);
scene.add(mesh);
}
function animate (interval) {
var timer = new Date().getTime() * 0.0001;
camera.position.x = Math.cos(timer) * 800;
camera.position.z = Math.sin(timer) * 800;
camera.lookAt(scene.position);
requestAnimationFrame(animate, interval);
renderer.render(scene, camera);
}
return {
init : init,
update : update,
animate : animate,
drawCoordinate : drawCoordinate
};
})();
var TerrainController = (function(){
var view = TerrainView;
var model = TerrainModel;
function init () {
RandomPool.hook();
initUI();
animate();
bindEvents();
update();
}
function initUI(){
view.init('#container');
}
function animate () {
view.animate(30);
}
function bindEvents(){
$.subscribe('terrain-update', view.update);
}
function reset(){
RandomPool.reset();
update();
}
function update () {
RandomPool.seek(0);
var opts = {
size : 64,
smoothness : 1.0,
zScale : 220
};
model.update(opts);
}
function updateZ(){
var zScale = 220;
model.updateZ(zScale);
}
return { init : init };
})();