The grid

May 2025

While last month's updates added dynamic detail, this month was mostly about dynamic visibility and scaling up the world further. To make large game worlds possible, scenes have to be subdivided into parts that can be turned on or (completely) off. This goes a bit further than making koi invisible when they're out of view: ponds that are out of view completely shouldn't even be considered for rendering, and in larger scenes, most of what exists isn't in view at all.

To determine what parts of the world are visible, objects usually exist in a grid or some other data structure. When the player moves around, the game calculates which cells are visible, and they are processed and rendered. I need the following things from this system:

• The grid should determine which koi ponds are (partially) visible, and which ones are completely out of view.
• The grid should give a list of vegetation to render, and absolutely make sure invisible vegetation isn't rendered, since this is one of the slowest things to draw.
• The grid needs to prevent plants and objects from being placed too close to each other, and help to spatially distribute things in the world.

The first two things are both about culling invisible things, the third point is a bit more tricky. I want to assign objects in the world to grid cells, and ideally I want to use the spatial properties of these cells to keep objects from clipping in to each other. Most games use square grid cells, since they are computationally the easiest thing to work with. A disadvantage of grid cells is their degree of isotropy, which is the degree of directional independence; square cells can be called anisotropic, meaning they have very clear directional biases. The cells are laid out in horizontal and vertical lines. They have eight neighbors, but the distance to diagonal neighbors is different from the distance to horizontally and vertically aligned ones. This causes all sorts of trouble:

• Objects placed on square grid cells lie clearly on two axes. This is comparable to cornfields or planted forests, all plants are perfectly aligned, it looks unnatural.
• Because the distance to diagonal neighbors is greater, using square grid cells doesn't work great for guaranteeing equal spacing between objects on grid cells.
• When you create a mesh for square grid cells, the squares are made from two triangles, and the diagonal points one way or the other. The resulting mesh has directional biases. These show up during rendering and mesh deformation (like water displacement and ground elevation).

There are games that use square meshes, but hexagonal meshes are also used (for example by the more recent Civilization games). Hexagonal meshes tackle most of these problems: all neighbors are at the same distance from the cell center, directional bias is greatly reduced, and you can create a mesh consisting of six equal triangles per cell, each triangle has the same size. Since hexagonal tiles have six triangles, and since calculating with triangles is slightly faster than calculating with hexagons, I went for a triangular grid. The world is subdivided into equilateral triangles. If you squint at the image, you can imagine a hexagonal grid that fits precisely on top of it; the good properties of hexagonal grids are inherited, but the cells are triangular.

The white lines represent the field of view of the camera. All yellow cells are currently visible, and the others are not. Large objects like ponds have a "grid mask", which is effectively a list of cells it overlaps with. If any of its cells are currently visible, the object is visible as well. When the camera moves, cells turn on and off, while cells that remain visible do nothing. The system was built in such a way that the world size does not matter; not all cells in the world are continuously checked for visibility, only the ones that lie within the field of view. This makes the system lightweight, which means I can make bigger game worlds without performance worries.

Since all triangular cell centers have the same distance towards each adjacent cell center, I can use the cells for spacing out objects. Every grid cell center for example can house one large plant or placeable object, if these objects are guaranteed to fit within the cell. Because of the better isotropic properties of this triangular grid, the placement of objects will still look more natural than placement on a square grid. To place objects that are smaller than a grid cell triangle, I can keep subdividing the triangle into four smaller ones and use these subdivided cells for spacing out properties, subdividing even further for smaller objects.

Another thing I use the grid for is rendering water at dynamic levels of detail. The image on the right shows the grid cells as white outlines, and the water triangles as blue wireframe meshes. Water detail is higher near the camera. Cells have three neighbors, which may or may not have the same level of tessellation. If they have a lower level, the mesh is stitched together by smoothly reducing the level of detail such that no gaps between tile meshes exists (as this would look weird). Water mesh cells are only rendered inside ponds, and when they are visible.

The same tile meshes will be used for rendering terrain elevation, although, I can probably use less detailed meshes for that since terrain elevation is smoother than waves on water. It may also be possible to use lower detail meshes where little or no elevation exists. I've created a compute shader that lets the GPU turn a list of grid coordinates into a list of draw calls which takes the level of detail of each cell into account, so to draw water, I simply send every visible water cell coordinate to the GPU, and I get all the draw calls with level of detail applied back from it.

One awkward thing I noticed with these grid meshes is that very distant cells, which are simply one triangle, cause the GPU to idle. The GPU calculates 32 or 64 vertices at a time, so if I send a mesh that has one triangle for a mesh, 61 of 64 threads are idle when rendering it. This is wasteful, I need those cores for better things, but there's a fix. If I batch cells that use the same model together and render them through instancing, the GPU is often able to put those tiles together and render them without most cores being idle. I'll work on this when I get to terrain rendering later on.