A heightmap is a texture where the texels are mapped to an object or the world, and the color of each texel represents the height of the object/world. Generally, a heightmap is a grayscale image, as only one of the texels color channels are needed to read the height of the object. The value of each channel is limited to the range [0.0,1.0]. Here’s a screenshot of a typical heightmap, the one we use: (Scaled down, original size is 1024×1024)

Collision Detection
As our game is a top down game, a heightmap is ideal for collision between the feet of our heroes and the terrain. Other techniques are used for collision between players / projectiles and blocking terrain. We know that the terrain used in our game has a maximum height of ”1 modelspace length units” and that the terrain width and height are limited to the range [-10,10]. We also know that our terrain is positioned around origin (0.0,0.0,0.0 worldspace). We can use this to our advantage by ”placing” the heightmap so that it too has its centre in origin. Now we can map between world space X/Z coordinates and the texel coordinates in the heightmap.

float xTexel = MathUtils.clamp(position.x, -10, 10)*(heightMapWidth/2-1)/10+heightMapWidth/10;
float zTexel = MathUtils.clamp(position.z, -10, 10)*(heightMapHeight/2-1)/10+heightMapHeight/10;
position.y = g.m.heightmap.elevation(MathUtils.floor(xTexel), MathUtils.floor(zTexel));

We clamp the value, to make sure that if we are outside the terrain we use the same height as if we were to be just on the edge. We could of course just set borders so that it would be impossible for the player to move outside of the terrain – but we prefere our application to not crash even if the player does something bad. (In fact, in our specific use case – the player is allowed to move outside of the map, but will be punished by taking damage over time while staying there.)

We then multiply the clamped value with the total size of the heightmap divided by 2 and 10 and add the heightmaps size divided by 10 minus 1. This means that if our heightmap is 1024×1024, the following calculations will be made:

position.x = 10, position.z = -10
float xTexel = 10*51.1+512 = 1023
float xTexel = -10*51.1+512 = 1

As you can see, our result will be in the range [1,1023] while the possible lookups are in the range [0,1023]. This is because we could not think of a simple formula that would calculate this in a better way – and the bias is not noticable.

Decals
Collision with ground terrain is not the only usecase we have for our height map. We also use it to efficiently project decals to the ground, so that they follow the terrain. We do this by creating a square mesh – in our case consisting of 8×8 squares. This mesh ranges from -1,0,-1 to 1,0,1 – meaning that it is a 2d mesh following the X/Z axis with at height 0. When it is time to project something, we simply move the mesh to the target, and iterate over each vertice using the heightmap to set the y value. Doing this, we get a lot of z fighting when we try to render the decals. In order to solve that, we simply disable depth testing and depth writing. This means that we can fake projection of decals to the ground in a simple and batchable way. So far, we use these decals to create simple shadows and targetting arrows. But in the near future we will start using animated textures to draw other interesting effects on the ground – such as cracks, ice and heat.

Left – a targeting arrow. Right – shadows of characters and objects.

Here’s a video demonstrating our heightmap – both used for collision and for projection:

And here’s a simple implementation of a heightmap in libgdx:
http://www.dagger.se/code/HeightMap.java
http://pastebin.com/P629SX9E

If you have any questions or requests for additional information or source, let us know!