Procedural Hex Terrain
Madis Janno
Repo: https://github.com/madisjanno/Hexi
Live: https://madisjanno.github.io/Hexi/
Video: Attach:Hexi_long_video.mp4
The purpose of this project is to generate terrain that would be suitable for a hex-based game, although there is a possibility it will also work with other shapes and possibly a spherical world, which would need to contain 12 pentagons to fit together.
The shape of the world will be encoded by a height value for each hex midpoint and flags for which connections to neigbouring hexes are cliffs. The created program should generate terrain geometry based on that data, with associated normals and texture UV's which could be used to seamlessly texture the terrain.
Initial milestones will be based around generating the geometry, with "flat" terrain and cliffs. The next step is the construction of normals which would be appropriately sharp or shared between faces. After that comes applying textures to the resulting hexes, with appropriate mixing between different hex types and so on. If there is still time left over at that point, the plan is to attempt to port the code over to a proper game engine.
The prototype is presently written in JS and will most likely stay as that unless there is a pressing need for advanced features.
Basic principle
When generating terrain we start with a set of control points, in this case the centres of hexes, but can also use other shapes.
These are the connections between the different hexes. They form triangles in case of hexes, and the system can handle any shapes whose connections all form triangles, so squares for example are not supported.
I calculate the midpoint of each "triplet" of points.
By connecting all the midpoints we get the actual hex.
Because the triplet are shared, all generated hexes also have matching vertices.
Milestone 1 (06.03)
- Cliffs
Hex borders can now be classified as cliffs, which means that the hex edges are are split apart vertically, with the gap filled in afterwards.
Milestone 2 (20.03)
- Smooth normals
- Single geometry
- Optimization
Previously each hex was made into a separate model and composed of triangles rather than faces which had shared vertices. A large rewrite made it possible to create create a single terrain geometry consisting of all the hexes, with no vertex duplication. This also allowed for smooth normals rather than the previous flat shading. Sadly the result is not very good looking and I will have to investigate ways to make them look better. However further modifications should be easier to do going forward.
The above image shows how to reason about the hexes. Each each edge and triplet gets additional vertices to define the different heights of hexes at those points.
Milestone 3 (03.04)
- Texturing
- Improving normals
During this milestone I settled on using triplanar texturing, meaning that each vertex essentially has 3 UV's for 3 different textures, with weights assigned according to the normals. This required making the normals look smoother.
I considered and tested out many different ways of subdividing the hexes to improve the normals, The main problems with those shown above for example, is that they reacted badly when altering certain parameters, such as making cliffs less sharp.
The final chosen variant is shown above. While it still has some problems, it reacts well to height alterations, allowing for tweaking of terrain.
The internal hexes can also be pushed very close to the hex centres to create a different look.
Improving cliffs was slightly harder, as the internal hex vertices were not shared between different hexes. Cliffs however have connecting points between different hexes. The chosen method was to add "midpoint" vertices, which would act as connecting points. However using this method revealed several problems with improperly handled cliffs, most notably with 3-way cliffs. Meaning that at the moment those are simply not supported.
Testing out different variants took a lot of time meaning actual implementation of texturing was pushed to milestone 4, but should be fairly trivial.
Milestone 4 (17.04)
- Finalize texturing
- Handle 3-way cliffs
- Begin refactor to allow for live editing
Texturing was accomplished by assigning different textures to the XY, XZ and YZ planes, and using the normal xyz values as weights to determine which texture to use. Results looked nicer when squaring the weights before normalizing their sum to 1.
Tutorial that I used as the basis for my implementation of triplanar texturing.
I am also slightly boosting the contrast depending on the blend weights, although the results might be slightly incorrect as I am using mipmaps to determine an expected mean color value. The mipmaps in three.js are not gamma corrected as far as I know, so the mipmap calculations will be incorrect. However it does hide the seams between textures in my opinion.
3-way cliffs are now also correctly handled, which required altering large portions of the cliff creation code. However I am very happy with the results.
Milestone 5 (08.05)
- Refactor code to allow for rendering as different chunks and to regenerate chunks
- Add ability to alter terrain as user
The code now allows for expanding the amount of hexes and rendering hexes in different chunks. It is now also possible to alter the height of hexes with the mouse wheel.
Generation works in two stages.
The first stage involves calculating the connecting edges and triplets of hexes and storing all the generated vertices in relatively easy to access data structures.
The second stage takes a list of hexes, grabs their vertices and generates a list of faces (defined by vertices). This list of faces is then processed to produce a list of unique vertices (compared by object rather than value) and a list of indices to that list. These compose the geometry. This system allows for arbitrarily shaped chunks.
Because I am generating normals from the resulting geometry, then to ensure chunks have contiguous normals when placed next to each other, I also have to process an extra layer of neighbouring hexes, which are hidden during rendering.
The terrain can therefore now be altered in code by altering the hex height or cliffs, running the pregeneration step on that hex and its neighbouring hexes, and then regenerating whatever chunks contain the hex. Speed wise, recreating a chunk of around 500 hexes each frame got slightly less than 60 fps on my desktop.
Milestone 6 (22.05)
- Infinite (or very large) terrain
- New camera movement (RTS style?)
The first thing I added was a new system for camera movement. A user can zoom with the scroll wheel, drag their location by holding down the left mouse button and rotate by holding down the right mouse button. Movement is based around a central location which lies in the exact middle of the screen, and which gravitates toward the height of the geometry at that location. Rotation and camera height and location are based on that location. The camera also raytraces downward to avoid ending up inside geometry and adjusts its vertical rotation to avoid that scenario.
Dragging is nearly exact (only changing in case the central location height changes) in that you can grab any point on geometry and it will follow the mouse. This is accomplished by raytracing from the mouse location onto the geometry to get a "grab point". Based on that point I also create a horizontal plane. When moving the mouse I raytrace to the created plane, and adjust the location of the camera so the two intersections match again.
Terrain is now generated according to the location in the centre of the screen, with more generated as you zoom out or pan around. It is divided up into chunks, with each chunk getting its own generated mesh. With my computer, chrome tends to crash at around a million generated and rendered hexes.
Chunk generation is done in several stages. First individual hexes are generated with their own heights. Then each hex is given a list of its neighbours and it is determined which connections are cliffs and which are not. The second step requires that all surrounding chunks have been pregenerated, and for later steps, a border of 2 hexes from surrounding chunks is also finalized. After that, generation proceeds in the manner described in the previous milestone. The two hex border is required for the layer of invisible geometry (first hex border), which in turn requires that all its surrounding hexes be preprocessed (second hex border).
The meshes can be removed from the scene, but at the moment there is no mechanism for removing the underlying hexes and so you will eventually run out of memory when panning around.