# Heightmap with Cliffs

Here's a screenshot of my heightmap editor:

I have been trying to find a way to represent my game world that is based on a grid, but that also permits interesting terrain, buildings, and underground structures.

I *hope* I'm on the right track. Let's discuss!

## Game Worlds

Games are played in many different worlds. The black and white squares of the chessboard are a battlefield. The spaces on the Monopoly board are boulevards and thoroughfares lined with housing developments and construction sites.

To construct a world for a video game, we have to describe the geometry of our universe in a way that can be taught to the computer.

### 3D Engines

Game engines have tried a bunch of different world representations:

- DOOM-style 2D BSP tree.
- 3D BSP tree.
- Bounding volume hierarchies.
- Voxels.

The classic setup in a modern 3D engine is to represent everything as an arbitrary triangle mesh (possibly wrapped in a collision shape), and hand everything over to a general collision detection system with a global spatial partitioning tree.

This is incredibly flexible.

For some games, this maps well to the gameplay. Shooters, adventure games, 'walking simulators' - we've been given a thousand different environments to explore. Game engines make this easier all the time.

But other games start with a different view of the world. Wall placement in the Sims, blocks in Minecraft, the tactical grid in X-COM, or the mostly-2D landscapes of RTSes and MOBAs might end up as meshes and physics volumes, but they start life as something more abstract.

### Heightmaps

Heightmaps are awesome. They let us represent complex terrain in an efficient and compact way.

Go outside in Word of Warcraft and you'll see that most of Azeroth is a heightmap, with buildings placed atop or inside it. On Earth, mapping systems use heightmaps to store the topology of real-world terrain.

But heightmaps have one big problem. They can't represent a vertical surface. A cliff can be very steep, but it will never be a wall. A landscape without any fences and without any buildings ends up feeling pretty boring.

### Grids

Endless games have been played on grids, all the way back to Go and chess. Table-top RPGs use feet and inches in the theatre of the mind, but on a battle map everyone knows that each square is five feet.

For the computer, a grid is simply and efficiently represented as a 2D array.

So a grid is a very attractive place to have adventures - as players, we enjoy moving pieces on the chessboard, and as programmers, we have a clear way to represent the rules of the space.

But grids also have a problem. If one square is the smallest unit we can represent, then all our obstacles must be at least one square wide. We end up with a blocky, Minecraft-like world - awesome, but let's see if we can do something different.

## The Cliffmap

Here's my plan. Take a heightmap, and draw a set of edges on top. These edges slice the map into disconnected sections.

The terrain on one side of an edge can be a different height from the terrain on the opposite side. Each edge is a discontinuity in the heightmap.

Each edge can also be a wall, impassable even if there is no cliff.

This augmented heightmap gives us an interesting 3D surface on which to move our play pieces. Grids and height samples complement each other - between each four samples there is a grid square.

### Edges

A drawing made of connected straight-line edges is a polygon mesh, whether in 2D or 3D. Edges connect vertices. Edges divide the plane into a set of polygonal faces.

The classic way of representing such a mesh is using a half-edge data structure - the same structure used in most 3D modelling packages.

An edge between vertex A and vertex B is actually represented as a pair of directed half-edges. One half-edge travels from A to B, and the opposite half-edge travels from B to A.

The half-edge data structure lets us know which edges, vertices and faces are connected to each other.

- Each half-edge is linked to the opposite half-edge.
- Each half-edge is linked to its end vertex.
- Each vertex is linked to one of the half-edges that leaves it.
- Each half-edge is part of a doubly-linked loop of edges anticlockwise around a face, or clockwise around a hole.
- Each face is linked to the loop anticlockwise around its perimeter, and to each loop clockwise around each hole.

Maintaining all these linked lists is extremely fiddly. But it ends up being useful.

With this topological information the can answer questions about the mesh. Which edges describe the perimeter of a face? Which edges are connected to each vertex? In which order?

### Heights

One of the great things about a heightmap is its regularity. We store the height as just one number for each sample.

Unfortunately, adding cliffs destroys this beautiful simplicity.

Look at a sample point intersected by an edge:

This sample now needs to store *two* heights - one for each side of the edge.

The case at a sample point which is a vertex in the edge graph is even more irregular:

The vertex is split into a series of corners, each of which is disconnected from the others and which has its own height. If we allow horizontal, vertical, and 45° diagonals, there can be up to eight corners at each vertex.

My implementation stores these additional required heights in two places.

On the heightmap:

- Each heightmap sample has a 'left' and 'right' height.
- Samples inside faces use the left height.
- Samples along edges use both heights.
- Samples at vertices don't use either - corner heights are stored in the mesh.

On the mesh:

- Each half-edge stores a 'corner' height.
- Samples at vertices use the corner heights of each incoming edge.
- A half-edge's corner height is used for the corner between it and the next half-edge clockwise around the end vertex.

The topology of the triangular mesh generated from the cliffmap must take these discontinuities into account, selecting the correct height at each triangle vertex depending on the angle of approach. Normal calculation is also not quite so simple anymore.

## Conclusion

Getting it to this point has been quite hard! Updating a half-edge structure
is very fiddly, and I am always tempted to use accelerating structures to
optimize spatial queries. I did a *lot* of work on those before throwing it
away and brute forcing my way through each edge and vertex one-by-one.

Maybe in the future I'll have time for more elegant algorithms.

I still need to add generation of cliff and wall geometry, which is going to be another tricky problem, especially where edges meet around each vertex.

Let me know what you think! `>:D`

If you enjoyed this post, check out the whole blog, or follow me @isaaktual on Twitter!