Global Grids, Part 1: The setup

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×105, 1.8×106, 5.3×106, 1.6×107 cells (going up one depth each time). An aperture 4 system could only produce grids in that general range at 6.6×105, 2.6×106, and 1.0×107 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·4d + 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.46m2. The Earth’s surface area is approximately 5.10×1014m2—at 3.46m2 per hex, that’s 1.47×1014 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×1014 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.

6 comments:

Miranda said...

Where are you going with this, Hyp? Please tell me it's all leading to Master of Magic II. :)

J. Prevost said...

Hmm. I hadn’t actually made that connection. I somehow missed MoM completely back in the day, so I’ve never seen it. But my understanding is that it was a 4X game more focused on “cities and empires” scale gameplay, with tactical combat being done on smaller distinct maps at the individual unit level.

Right now, I have some ideas about where I want to go with gameplay, but they’re still very nebulous. I know that I want the player to be represented in the world by a single character at an appropriate scale, and that I want the world to be seamless at that scale. “Zoomed out” scales of play are a possibility I’ve been mulling, but it’s difficult to say at this stage of the project what will be workable and what will be needed.

I’ll see about posting soon about the game concepts I’ve been mulling over—but for now, the development is very much focused on building a world to have a base to try things on.

Miranda said...

Yar, I was just hoping you had a goal in mind that involved making a fun game for me to play. :)

J. Prevost said...

Hopefully. But there's a long way to go, yet. :)

Miranda said...

I've been thinking about your numbering problem for the faces. Seems like a recursive traversal is the way to go. Do you have the planar graph of the 12 pentagons lying around somewhere?

J. Prevost said...

The numbering problem is solved in my post from this evening. The location problem is also solved, and thanks for your help last week on that one! I’m just getting the bits I have done documented right now (it will finish up with the next post) before moving on to new development. I expect that I’ll post much more slowly then, since it’s taken me a few weeks to get this far. On the other hand, working out how to do all of this “just-in-time” locating stuff on a sphere business has been a real bear, so this is a big chunk of hard work behind me.

Post a Comment