World Tiling/Grid

[HyperbolicHadron]

I feel that this topic will be divisive enough to require a separate discussion from the rest of the world generation threads. Also, it is primarily a game design issue, and this can affect how the art assets are created so it would be best to get it right the first time.

The main question asked here is: what grid should the world use? Should it use a square grid, hex grid, other type of grid, or no grid at all (freeform)?

So far, it seems like the hexagonal (hex) grid has been the standout idea for the world grid. It is an obvious one, as it is what was chosen for the organelle and early multicellular editors. I think that these were good choices for those editors, but I do not think that enough evaluation has been done for what grid is best to use for the later stages and a premature selection could cause significant issues in the future.

The hex tiling has a few points going for it that are independent of any other considerations specific to the stages: it has already been chosen and implemented for some of the game stages, and it would be consistent to use it for all later stages. This could potentially save development effort and would have a coherent style across the game.

However, I think that these points for hex tilings are not enough to on their own to determine the world tiling without deeply considering how it would be actually used in the later stages.

The early stages from microbial to awakening will primarily be focused on interactions between organisms, and not on structures, so the choice of grid should not be a major, visible thing noticed by the player.

In the later stages when you start to build structures and cities are developed, from the end of awakening stage onwards, a world grid will become very transparent to the player. Any buildings built would be very obviously constrained to the type of grid used, and the buildings would have to be designed to fit correctly in the grid type. So, the choice of grid is quite important in the later stages.

Quick Grid Survey:

The hex grid has become popular lately for strategy games, and there is a trend for some games moving towards using it away from their previous square grid. For example, the Civilization series has used a square grid from games 1-4, and switched to a hex grid for the most recent games 5-6.

Here is the thing though: most of these games are set at a scale larger than that of buildings. They are almost never games that have the actual buildings in a hex grid. For example, Civilization games have each tile represent an entire city, with perhaps a few very specific “buildings” take up entire tiles, but these are usually collections of buildings or monuments (in the case of Civ 5-6 at least)

As for city building games, basically all of them over the years have either used a square grid or a free grid. Here are two articles that were top results when searching for “Best city building games” (The best city-building games on PC 2023 | PCGamesN) (Best City Builder Games Of All Time). It is interesting that not a single one of the games listed on either of these lists are hex based. And even with a free grid, snapping to a square grid or building in square grids is very common. The Sim City 1-4 games all used square grids for example. Sim city 2013 was the first in the series to switch away from a square grid, and it used a free grid. (It also was the one to kill the series, though that wasn’t due to the grid change…) Cities Skylines is a great example of a game that uses a mostly free form placement, and it does it fairly well. Using snap to grid is still present though, and that grid used is a square grid. The square grid in Cities Skylines is at a finer resolution than many of the buildings or structures, so the result is more free form even when using the grid.

There are still many new city buildings games being created today that still align strongly to a grid, and most of them use a square grid. For example Banished (not actually that new, but is still fairly recent overall), and Caesar III’s new updated release both use square grids. One interesting case is Frostpunk, which is different in that it has a central building that all of the buildings are built off of. It uses a radial sector grid, but it is still similar to a square grid in that the sectors are all made up of warped square grids, giving a sort of quadrilateral tiling. The buildings are all pretty much square grid aligned though, just somewhat warped.

As for RTS games, there is more variation than the city building games. Some games have stuck to a square tiling, others have switched to hex or free form tilings.
It still seems like the pattern of building-level placement using square tiles still holds though. Age of Empires for example still uses a square based grid for Age of Empires 4 (released in 2021). And I have seen this series be mentioned before as one of the examples for what some sections of the society stage will be similar to.

Another game that has been talked about before is Rimworld. This game uses a hex grid on the planet as it uses a hexsphere, just like what has been talked about here before. Except, the actual main part of the game uses a square grid. Pretty much all gameplay, building structures, etc is done using the square grid. The hex grid is used very little in comparison, mostly just for interacting with different settlements.

Dwarf Fortress is in a very similar vein to Rimworld, except that it has a square grid for both its local gameplay, and its overall world view. It does however just have a square, 2d world that it uses instead of a realistic spherical planetary projection though, so the comparison isn’t completely apples-to-apples.

More possibilities would include having a hybrid system, where small regions would have no grid, so buildings could be placed anywhere. But, the regions themselves would be in a grid. This is similar to what Rimworld does, except they use a hybrid of square tiling for the local region, and hex tiling for the global map. The difficulty with having a hybrid grid is that it could become difficult to get continuity between the different tiling types. Especially for switching from a square grid to a hex based grid, as you can’t easily turn one into the other.

A couple of other points going for the hex grid that have been discussed elsewhere have been: A hex grid is a good fit for a spherical world tiling, as it is what the hexsphere uses (except for those pesky pentagons that are required). This is a bit of an implementation detail though. And besides, using a square grid would not necessitate the use of a cubesphere, it would not even stop you from using an icosahedron as you can tile an icosahedron with squares as well. (It won’t be as natural of a fit of course, but then again hexagons can’t tile a icosahedron naturally anyway, it still requires insertion of those pentagons.) There are many other alternative ways to project a grid onto a sphere, just look at all of the different map projections there are out there. A basic octahedron sphere is another basic option that hasn’t been considered, but there are far more options such as using a quincuncial type projection (Square Equal-area Map Projection | Matthew Petroff) which has the added benefit of being equal area, which the basic hexsphere method does not provide and results in hex sizes varying across the surface. I think I might make a thread about different map projections at some point as well, as there are many interesting options.

Another point is that it has been said here before that hexagon tiling are better for doing tectonic simulation on. I have not researched this much, but this seems far less important of a factor than the other considerations in the long run, and should still be possible to simulate regardless of what tiling is used even it is does become more difficult.

So, I think that while relevant, these considerations are all less important than the question of what grid would be optimal for buildings to use. Choosing the wrong grid system early could result in some severe redesigns of the game later on if the wrong grid was chosen too early.

Also, I think that the main thing to think on should be not on whether to use a grid based system or a free placement system, but instead on what grid we would choose if we were to use a grid. I think that it would be easier to switch from a hex or square grid to a free grid, than switching from a hex grid to a square grid or vice-versa. We would need to redo basically any assets made for one grid system if we were to switch to another. If we were to switch from a square grid to a free grid on the other hand, then the assets could still likely be used or tweaked in order to be used with a free grid system.

Discussing whether or not we should use a free grid system is also important, but I think that might come down to how the world is created and stored to see if it would be possible to do, or if it is too difficult to do on our real scale world. Perhaps discussions could be had on how worth it the free grid system would be? It seems like the free grid system would be the ideal to strive for, but that might just be infeasible to do at Thrive’s scale. (Even without accounting for Thrive’s development budget in terms of development time to actually implement the more complex system)

All that being said, I am completely willing to agree with a different choice of grid system if a good enough case can be made for it. I would even be willing to choose the triangle tiling if someone came up with a smashing argument for it…

TL,DR

I posit that any non-square (or quadrilateral) grid would be a poor choice for Thrive’s world grid. The hexagonal grid that has been a great choice for the lower stages will not be a good fit for the grid in later society stages. This is because buildings have pretty regularly been designed as quadrilaterals, or shapes that fit well in quadrilaterals. The main type of grid that has a good potential of working in Thrive would thus be a square grid due to the buildings being mostly designed to fit well within quadrilateral areas. If we were to prematurely choose the wrong grid system, this could result in major redesigns later on if we decided to change it.
My main conclusion is that if there is to be a grid that the world uses, then it should be a square grid. If building placement is to be free placement, then it would become more of a implementation detail as to what grids if any are to be used internally to the world’s implementation.

If anyone has some other points that I haven’t thought of, either for or against what I have said, then please tell me. I do not think that what I have researched is in any way exhaustive, only what I was able to think of in the time I spent on it. If the problems that I have identified with hex grids can be solved, then it would be great to be able to use hex grids for the world.

Also, I was unable to find any good city building games with hex grids, but I might have missed something obvious. If you know of any, I would really like to know. There can’t really be basically none out there…

[Nunz]

Good post,

My primary concern with regards to the grid has been what will take less effort and make data as compact as possible. With hexes, you at any point have 6 neighbors who are offset exactly by a unit of 1, giving you the ability to conduct more sophisticated near neighbor queries with less/smaller floating points. This makes a lot of huge scale stuff simpler, especially movement/pathing (less chess moves.) We also, have an entire script for basic Hex maths.

City builder games are indeed always square grids because modern cities and building are usually partitioned in squares. This isn’t universal however. Many ancient, non-european civilizations for example used mostly circular structures, and arranged their stuff in what was basically a circle around some central structure/resource. Even lots of medieval towns and colonies were like this as they needed people to be able to go straight to the castle if there was an invasion. Hex grids provide an interesting approximation of circle packing, though realistically the best system for that, is Voronoi Diagrams.

I think free-form placement is ultimately what everyone wants just like with the editors but, for the under-lying system it would basically come down to whatever is easiest to program I would think. I don’t really know what the answer is for stuff in the future but I love City Skylines and Transport Fever so, I’m not opposed to any option in particular.

[Gamedungeon]

Me and Nunz had a bit of an argument about this on discord a while back if you feel like going back and seeing the points made then.

I generally dislike hexagons as a choice here, as hex spheres have some strange edge cases, and a few other reasons I would need to go back to remember.

I do agree that free-form is probably the best system for gameplay though. If we go that route then I don’t believe we actually need a grid, but a triangle grid would probably be best (Assuming a non-visible backend grid)

[HyperbolicHadron]

I do agree, I would really want to have a hex grid because of all of the better geometric properties it has over the square tiling.

Still though, if we do decide to make the buildings in a hex layout, even if it has been a thing that was used frequently in the past, it might make the game look less realistic overall. If a hex grid is chosen, then that would potentially make it difficult or impossible to make cities look ‘normal’ or at the very least what our modern cities look like. I think it would be better to choose the option of getting stuck with the more modern design and have the later stages have good looking cities than having people complain about the strange hex based grid stopping people from making cities look realistic. And I am assuming that the more ‘normal’ looking cities are what people would want, if we had to make that decision. I, personally, would rather have the quadrilateral based buildings more than I would like to have the nice hexagonal tiling. This is a bit of an annoying tradeoff, and it would be nice to find a solution to this that would give us both…

[Nunz]

Frankly, if we have to expose the underlying grid then I agree. I assume most of our players would be far more receptive to being able to organize things in terms of boxes. Like, when I think of a city layout, I would want to either have as many straight lines as possible or follow the lines of nature (rivers, slopes, etc)

The edge case here is big scale strategy stuff. Having played both the old and new Civ games, not having a hex drove me mad sometimes. Lots more and better possibilities with hexes there, and unfortunately free-form would hurt unless it’s done really well like Total War battles.

There’s also the fact a square grid would be rather new to the player in-game after having constantly interacting with hex based layouts, and free form creatures.

[HyperbolicHadron]

As far as players interacting with a square grid for the first time, this is an interesting case. I think that when the players are first interacting with it, it might seem like a different enough situation to not seem strange. The players would be building their first structures or buildings from the perspective of a single creature, and would be done in very small amounts at first, just a single shelter or building at a time. If the buildings are square/quadrilateral like a player might expect them to be (the society center in the prototype society stage is already quadrilateral…) then the square grid would probably feel natural. Of course, if it actually turns out that way, we will have to see (or do more research first).

To tie this discussion in to the world generator that I proposed, DGGIS (The World Generator: A Dynamically Generated GIS), I am envisioning that a tiling would be more apparent only near the ‘base unit’ of the tiling (the lowest possible LOD level). This base unit for buildings could be a more constrained tiling like Sim City 4, where each tile could be an entire building. Or it could be a smaller unit which the buildings are aligned to, but are not as coarse as entire building sizes. Once the perspective shifts to higher scales, like in the later society stage and industrial stage, then the grid would become much less apparent. The cities would not just turn into large squares representing an entire city; they would just become lower resolution approximations of it. With a good LOD system the approximations should be unnoticeable, and the grand strategy view you would have of your World would not use large hexes or squares, but would appear continuous. (Until you zoom back into the highest LOD level, where the individual buildings are constrained to the grid). This would result in the large scale strategy view appearing to be like a free form placement, while the small scale regions would be constrained to a grid. However, as stated in the World Generator thread, I don’t think that doing it this way is a requirement of the design, only one that I think could give good results.

[HyperbolicHadron]

Also, there is another annoyance of a hexagonal tiling that hasn’t mentioned yet: It isn’t as simple to subdivide a hexagonal tiling into smaller hexes (or go the other way) as you can with a square grid.

Here is how Uber’s H3 does it:

It has some very annoying issues with the hexes not being fully contained within the larger hex, and other hex areas encroaching into it. This is way worse than the square subdivision situation, where you can trivially subdivide a square into any square array of squares that you want. This would make a LOD system that uses subdivision more annoying to deal with on a hex grid. (The triangle grid does not have this problem though, it divides nicely just like the square tiling)

[Nunz]

Hexsphere LODs don’t work like that, they use an Icosphere then truncate it, since a Hexsphere and an Icosphere are essentially the same shape.

But I get your general point for subdividing say zones and such, that would be a pain.

[HyperbolicHadron]

I am not sure exactly what you mean, the Uber H3 system is using a Hexsphere?

[Nunz]

I mean the standard way other people do it, and have done it. It’s a truncation. Uber has teams of top researchers who came up with that on their own, hence it having it’s own name H3.

Note: Uber’s H3 system is really neat mathematically btw, not talking down or anything at all.

[HyperbolicHadron]

How exactly does the hexsphere LOD subdivision look like though, in reference to the previous LOD hexes? All that I have found look like Uber H3, or something like this paper: (IJGI | Free Full-Text | A Precision Evaluation Index System for Remote Sensing Data Sampling Based on Hexagonal Discrete Grids) which is even worse in terms of how the levels are related.

https://www.researchgate.net/figure/4-types-of-hexagonal-grid-systems-on-the-sphere-a-Superposition-of-the-3rd-and-the-4th_fig2_331880714

[Nunz]

In computer graphics world, we usually just truncate the Icosphere. We lop off every pointy bit basically.

This generally translates to putting a point at each triangle face and connecting those points. If you read an old enough issue of Computer Graphics, you’ll probably find some mentioning. Tangent and related is the concept of Delaunay Triangles and their dual, the Voronoi Diagram.

Here is a person doing it in Roblox:

[HyperbolicHadron]

So, would it look like on of either images (c) or (d) in my previous post? I am trying to wrap my mind around how it would look, and I had forgotten that Uber’s H3 wasn’t just the standard hexsphere method.

[Nunz]

Neither, it would be a Geodesic subdivision which is a whole kind of mathematics

[HyperbolicHadron]

I think that, for Thrive, something more like Uber’s H3 configuration would work better, as I think that having as neat as possible of a grid subdivision would work well to allow the Thrive simulator to be able to run on a lower LOD, coarse grid, then have its results able to propagate to a higher LOD grid if a subdivision is necessary. Or the reverse: changes made to a high LOD grid could be propagated up to the higher LOD levels without having to split the data across different hexes if possible. the square grid doesn’t have this problem at all, and is along with the issue of buildings typically being quadrilateral, the two reasons why I am not sure that hex tilings would be best suited for the game. I will have to look more into the geodesic subdivisions, but I am not sure if this would do any better of a job than the Uber H3 subdivision.

[Nunz]

Uber H3 algorithm is almost purely for geolocational data reasons. You have to remember, GPUs only know triangles, so if quick and clean mesh generation is the goal Geodesic Subdivisions would be wisest given it has an easy established path from triangle to hex that is given with the original generation of triangles since the hex grid and triangular grid are dual to each other. Not saying Uber’s system (if even open source) isn’t brilliant and probably way better, I just know it wasn’t designed with game graphics in mind.

Edit: I’m saying here that the established way of making the planets and Geodesic Subdivision mappings with hexes is the easiest and most efficient method since they’re mathematically related but, obviously, if we tailor the mappings as a separate system that is merely projected onto the sphere, it’s not critical to consider how the sphere comes to be as long as we consider warpage of the grid.

[HyperbolicHadron]

As an interesting resource, here is a random sampling of different cities that I looked at on Google Earth, if you want to look at the shape of various city layouts across the world. I would also recommend just looking around on Google Earth, it is quite interesting to see all the different possibilities. There seems to be a strong tendency towards quadrilateral based blocks of some sort, and some cities are even nearly completely square gridded, like Chicago. There are many other cities that are not very nice or regular at all on the opposite end of the spectrum. Comparing this with some more ancient city layouts would likely prove interesting if someone knows a good source on that.

https://drive.google.com/file/d/1worwNEvU7RAwnCWDjeWmROpDGkEhgMsj/view?usp=share_link
(Images I took were a bit too high resolution to fit here without a link)

[Nunz]

Lots of ancient cities are not gathered in a single place but some cities I find interesting:

Cairo

Baghdad

Old Sarum

Norman Norwich

Babylon

Jamestown

Athens

Rome

Jerusalem

Tripoli

Coba

Karakorum (circles are Mongol mobile homes)

[HyperbolicHadron]

A lot of these examples of the larger ancient cities seem similar to what I saw in the modern examples of cities I looked at, except that when walls are involved the cities get a bit more unique. Baghdad is very interesting in that it looks similar to how Frostpunk has its buildings grow radially from a central structure. The buildings themselves are arranged in circular sectors that are very quadrilateral on the local scale, with the houses being essentially quadrilateral.The cities could likely fit nicely in the center of a hex tile, with the society building as perhaps the center of it. That would mean however that you would be forced to go find the center of a hex tile to put your society center in. I don’t think that method would scale very well to later stages with larger cities, but I do still like it. I think that method might have the best change of having a hex tiling on the global scale, as it wouldn’t limit the buildings to being hex based as well.

[Nunz]

I remember reading that a lot of that common design comes from the fact these cities were very major, pre-planned, and made to last. When you look at nomadic people (most ancient people) is when you start to see funny shaped building and cities/settlements. The Mongols for example, prior to making that big city, would just live in those circular mobile homes, in big huddles whenever they decided to stop with their horses. Native Americans used Teepees and usually put the chief in the middle as protection and generally formed a circle around him. Ancient Africans would often build circular mud huts (literally called Round Huts) believing them to be structurally superior, some tribes/rural people still do this.

Layouts of those kind of towns obviously don’t exist, they just kinda happened.