As I alluded to in my previous post, identifying the grid system I wanted to use was just part of the solution. In order to work effectively at this scale, I needed to have a way to concisely identify each cell, a method to quickly calculate the neighbors of a given cell, and a method to quickly calculate the position of a given cell.

The first step in any of the possible solutions is to remember that each hexagonal grid cell (and the twelve pentagonal cells) is generated by using points in a triangular mesh. Each point (or vertex) identifies an individual grid cell. The lines between these vertices (forming the faces of the triangles) connect them to the vertices which identify the adjacent grid cells. The following image illustrates this:

You may note that the triangular grid seems to “pop out” slightly above the cells. This is because my current rendering scheme draws the cells by computing each cell-vertex’s position as the average of the positions of the three surrounding triangle-vertices. Because of this, the sphere defined by the cells is slightly smaller than the sphere defined by the triangles. (The solution to this is simple: compute the average then normalize the length of the vector. But the extra computation is not worth doing at this point, and may never be.)

It’s also worth noting at this point that it’s particularly valuable to work with the triangular view of the world because most algorithms will only be interested in the cells and the connections between them, which the triangles represent wonderfully. Pretty much only the display code needs to know how to show the cells as actual hexagons.

Read more »

I’ve just finished implementing my spherical grid system, based on the work and links I saw at Dungeon League. There were a couple of unique issues I had to work through, however, and I used a slightly different grid system from the one he’s using.

First, some sample images:

These hex grids are based on a Class I aperture 4 triangle hierarchy, starting with an icosahedron. (See the Discrete Global Grids site at Southern Oregon University for more details about grid types. Particularly the paper Geodesic Discrete Global Grid Systems by Sahr, White, and Kitterling.

The important number here is the aperture size. This determines how much bigger the grid is (or smaller the cells are) with each subdivision. The Dungeon League grid is slightly different, using alternating Class I and Class II subdivisions to produce an aperture 3 hierarchy. That means that he has more different “resolutions” available to him—an aperture 3 system could produce a grid of 5.9×10⁵, 1.8×10⁶, 5.3×10⁶, 1.6×10⁷ cells (going up one depth each time). An aperture 4 system could only produce grids in that general range at 6.6×10⁵, 2.6×10⁶, and 1.0×10⁷ cells. (Take a look at the DGG website’s tables of grid characteristics for more details.)

The images above are at depths 0 through 9 from left to right. Each grid has 10·4^d + 2 cells, where d is the depth. So the depth 0 grid is has an area of 12 cells. The depth 2 grid has an area of 162 cells. And the last image, at depth 9, has an area of 2,621,442 cells. At this depth, the sphere appears totally white because the image is only 984×984 pixels.

The next question that comes to mind is this: What depth would it take to model a body of approximately the size of the Earth down to a one meter resolution? Assuming the hexagons are regular (they’re not, but we’re just estimating here) with centers spaced 1m apart, each hexagon should have an area of approximately 3.46m². The Earth’s surface area is approximately 5.10×10¹⁴m²—at 3.46m² per hex, that’s 1.47×10¹⁴ cells.

Pretty huge compared to the depth 9 grid. It turns out that in order to get a resolution at this level, you’d need a depth 22 grid. Such a grid has 1.76×10¹⁴ cells, which isn’t too far off. 176 trillion cells. Yikes! It’s clear at this point that it would be completely impossible to keep any information at all about the entire grid in memory. But, there are two very important pieces of knowledge we need all the time: which cells are adjacent to any given cell, and where on the surface of the globe is any given cell located. We also need an efficient way to identify each cell, in order to keep track of information that cannot be automatically generated when the player is visiting a locationg. (For example, any changes the player has made to the area.)

Up next: A system for identifying cells and calculating their neighbors.

For a while now, I’ve been working on a new development project. It all started with me thinking “You know, I bet it’s possible to do a better fluid dynamics simulation than what Dwarf Fortress currently uses” while waiting for the bus. I thought through a good bit of the problem, and came up with some ideas... But of course, I couldn’t attempt to implement them in DF since Toady keeps the source code close to his chest. (And I totally understand why, given that it’s his livelihood!)

Like any red-blooded programmer, my next thought was “Well, if I can’t do it in DF, I could write something myself and try it out there.” That lead to a lot of additional thoughts about the mechanics of NPC AIs, and so on, and so forth. I won’t go into those bits for now, because I’m still a good distance from implementing any AIs at all.

After a long and harrowing journey through the web reading about procedural content generation, I came to the following plan:

I will write some kind of roguelike that is played on the surface of a sphere. The sphere’s high-level terrain will be generated using “naturalistic” means—that is to say, techniques that use global knowledge of the map to create terrain that looks a bit more natural than a simple fractal height-map. At the low-level, terrain detail in the “gaps” between the high-level features will be filled in using fractal noise techniques.

To put it a different way: I want to produce continents (or “pseudo-continents” on a smaller sphere) in a way that makes them look like actual continents. Then, I want the player to play on a map at person scale, and in order to do that I need a system that doesn’t actually generate all of the terrain ahead of time. Why? Because the whole map at person scale would be huge. It would be too slow to generate it all at once, and also too massive for players to want to keep around.

Before I get started describing what I’ve done (and eventually, what I’m doing), I wanted to credit the major projects that I’ve been using for inspiration:

• Dwarf Fortress, the mother of all “world-building” roguelikes. Or “fortlikes”, if you would.
• Minecraft, which got me thinking about dynamic generation and "building" games from the point of view of a single character (instead of planning with an entourage of characters.)
• Dungeon League, a great development blog that gave me the idea to work with a spherical world, and enough details to figure out how to do it right.
• The Chronicles of Doryen, which spawned the fantastic libtcod library for building roguelikes. I’m not going to be using it myself, but its capabilities have given me a lot of ideas for how to do more advanced rendering without totally leaving the roguelike mold.