I'm trying to generate a mesh for my game and I'm being overwhelmed by all the tricky details. I keep simplifying my goals to try to make it easier, but it's still a struggle. Soon I'll have nothing but a Tomb Raider grid, but I desperately want to find a design pattern or a trick of some sort to make the whole thing more manageable.

The game level is represented by a 2D array, like a height map, but I very much want vertical cliffs, so each corner of each cell has its own height, allowing it to be discontinuous with neighboring cells. That's good, but I very much want more than just axis-aligned cliffs; that would never look natural. I used to try to have cliffs at arbitrary angles, but I've since abandoned that ambition, and now I just want diagonal cliffs, so each cell can be divided into two triangles along one of the two diagonals, with each corner of each triangle getting its own height.

That's the vertical element. Horizontally I want to use Marching Squares to define various regions in the level, like desert, forest, lake, and so on. We just have to create fields of values across the corners of all the cells, then linearly interpolate between the corners to determine which field has the greatest value at any point. So, if value of the desert field is greater than value of the forest field, then that point is part of the desert, and so on. The beauty of Marching Squares is that it meshes each cell independently, so if we can just mesh a single cell, we can mesh the whole level. Unfortunately, the cliffs turn some of the squares of marching squares into triangles, as well as creating other complications.

The usual advice for marching squares is to have a lookup table filled with predefined meshes, but thanks to the cliffs the number of possibilities is exploding and the lookup table seems awkward. Now I'm thinking that we should generate a half-edge data structure from the grid to represent all the squares and triangles of the cells, then procedurally construct the game mesh from that.

I feel like I'm missing something and that this is all much harder than it should be. Is there some book I should read, or some algorithm I should be using? Is there some data structure that would solve all my problems?