Client-Side Terrain Tile Representation Algorithm

Multithreaded JavaScript has been published with O'Reilly!

Client-Side Terrain Tile Representation Algorithm
Client-Side Terrain Tile Representation Algorithm

Cobalt Calibur, an MMORPG I've been working on for several years, is going to eventually be rendered in 3D. The game will keep its tiled approach to world generation, due to the dynamic-ness of the world (tons of polygons and complex procedurally generated meshes would be insane). Each tile will represent something like a square meter of the world. There will be different types of tiles, such as a water area, sandy, grassy, forest, and at least dozens more. Each tile will have properties attached to it, such as how much wood or stone or metal is left to be harvested. Tiles will have 3D objects on them, e.g. forests will have trees, rocky areas will have boulders, etc.

However, can you imagine how boring a game world with the same repeating tree object would get? Your player could stand between two tiles, and look down hundreds of meters of perfectly planted forest, ruining any perception of realism.

To fix this, we want things to be a bit more complex. Instead of having just one tile for a forest, we'll have possibly dozens of them. Each tile will be unique, with different 3D tree models attached to different locations. Those models will have their own collision, will block rays, etc. Really, the only useful information regarding a tile as far as the global game world is concerned is what resources the tile can provide. Things such as how the forest looks and collision is more of a concern of the individual game clients.

Now, how do we keep track of all these different tiles? Should the game server know which exact tile exists at every single location in this massive grid? I suppose it could, but that would be a lot of information that the server really doesn't need to know about. However, we can have the client decide this. But, we don't want to have them chosen at random. After all, you don't want one character walking through a tree that the other character sees. Plus it's best if every player sees the exact same thing (Games by VALVe do not follow this regarding corpses, something that always drove me nuts).

My solution to this is to use some sort of hashing algorithm using the map coordinates as inputs. Ideally, this algorithm would be really fast, and wouldn't need to be too unique, although it should be pretty good at preventing noticeable patterns from emerging.

Algorithms like this often use modulus (%), you know, the remainder of integer division. This is when prime numbers are used as well, often times the bigger the better (John Carmack used something like this with Quake texture repeating to prevent noticeable terrain texture repeats). However, if I want to use something like the ((X+Y) % 17), I'm going to need 17 different tiles, and perhaps I only want to come up with 12 different tiles for one tile type (rock), and 4 tiles for another tile type (sand).

Also, something like ((X+Y) % 17 is going to form some noticeable patterns (see graphic below). We want something more chaotic, totally unpredictable by a human, but with the same output from any given input. One could do something crazy, such as use the first character of MD5(X + ‘|' + Y). MD5 is a fast hashing algorithm, where the slightest change to the input causes a completely different output, which is perfect for what we want. Unfortunately it isn't fast enough, and the output is mostly truncated for our usage, meaning we waste a lot of that complexity.

Coordinate Hashing Algorithms Visualized
Coordinate Hashing Algorithms Visualized

I suppose the best algorithm would be able to generate a big seemingly random number, yet reproducable, for each X/Y coordinate, and then modulus that number by the number of tiles for that tile type, and then use the resulting number to represent the exact tile to use.

This post is mostly brainstorming, I'm not sure if there is a name for this or even if someone already came up with the perfect algorithm for doing this (I'm no math major). Feel free to leave comments below if you have any information to share on the hashing algorithm to use. I feel the concept itself is pretty sound though.

Oh, and if you want to see the (half assed) code I wrote to generate these images, you can run this Node.js script (for the CSS, .color-0 { background-color: #000;} .color-1 { background-color: #111;} etc.)

var crypto = require('crypto');

// MD5
var hash = null;
var line = '';
var string = '';
console.log("<div id='md5'>");
for (var x = 0; x < 20; x++) {
    line = "<div class='row'>";
    for (var y = 0; y < 20; y++) {
        string = x + '|' + y;
        line += "<div class='color-" + crypto.createHash('md5').update(string).digest("hex").substr(0,1) + "'></div>";
    }
    line += "</div>";
    console.log(line);
}
console.log("</div>");

// MOD
var string = '';
var out = 0;
console.log("<div id='md5'>");
for (var x = 0; x < 20; x++) {
    line = "<div class='row'>";
    for (var y = 0; y < 20; y++) {
        string = x + '|' + y;
        out = (x + y) % 16;
        line += "<div class='color-" + out.toString(16) + "'></div>";
    }
    line += "</div>";
    console.log(line);
}
console.log("</div>");

// Random
var out = 0;
console.log("<div id='md5'>");
for (var x = 0; x < 20; x++) {
    line = "<div class='row'>";
    for (var y = 0; y < 20; y++) {
        out = Math.floor(Math.random()*16) % 16;
        line += "<div class='color-" + out.toString(16) + "'></div>";
    }
    line += "</div>";
    console.log(line);
}
console.log("</div>");
Tags: #gamedev
Thomas Hunter II Avatar

Thomas has contributed to dozens of enterprise Node.js services and has worked for a company dedicated to securing Node.js. He has spoken at several conferences on Node.js and JavaScript and is an O'Reilly published author.