Image from Wikipedia
Some games have tile maps that wrap around. Civilization for example lets you go off the left side of the map and you warp to the right side. You can’t go off the top or bottom of the map. In 3D space, this would be a cylinder. Some games also let you go off the top side and warp to the bottom, and vice versa. In 3D space, this would be a torus. But most tile map games don’t use a sphere. Why? It’s because you can’t tile a sphere with uniform regular square or hexagon tiles (Euler said so!). If you try to tile with hexagons (by subdividing an isocahedron), you end up with twelve pentagons left over. Ick. And you run into other issues too.
On this page I’m going to explore the possibility of hiding the pentagons by just not letting you walk near them. This would only work in games where you’re walking/driving and not games where you can zoom out or freely control the camera. (Note: the /x/ in the url is where I put my quick, unpolished projects like this one.)
The first problem is, what coordinate system should I use to represent the player’s position and direction? A common way of tessalating a sphere is to subdivide an isocahedron. That isocahedron, when unfolded, can look like this:
Idea 1: two-level coordinate system
Treat each region separately. Keep track of which region you are in, and then keep a local x,y coordinate inside of that triangle. When crossing a boundary into another region, calculate the new x,y.
Distances and vectors that cross a region boundary becomes hard. There are no distance or angle distortions for local calculations. Since region crossing is complicated, it’d be best to avoid combat or even land masses crossing regions.
Idea 2: convex coordinate limit
Use a single x,y coordinate for the entire world, but limit it to this shape. If you try to exceed the y bound, you stop at the edge. If you try to exceed the x bound, you wrap around. The triangles are distorted though, especially near the poles.
While global calculations may be a little better, distances and angles are distorted locally. I don’t think this will work well.
Idea 3: teleport regions
Use a single x,y coordinate for the entire world, but limit it to the blue area shape. If you try to exceed the y bound, you stop at the edge. If x goes off the left/right side of a triangle region into a red area, you are teleported into a nearby valid green area region. This doesn’t work near the triple points (where the pentagons are) but if you can’t get close to the pentagons anyway it shouldn’t be a problem. We need to translate both positions and directions to the new triangle.
This is sort of a hybrid of idea 1 (separate regions, two-level coordinate) and 2 (all one region, single coordinate). In the ten tropic regions, it’s all connected; region crossing is easy and acts like a torus. In the ten temperate/polar regions, they’re separate; region crossing requires changing coordinates and directions. Like idea 1, there are no distance or angle distortions for local calculations. The advantage over idea 1 is that you can have larger continents that cross any boundary that includes one tropic region. The advantage over idea 2 is that there are no local distortions.
This is what I’ve been working towards: you can drive around (WASD or arrows) and you see a hexagonal grid everywhere, but the underlying topology is a sphere. You need to stay away from the pentagons; the danger zones are dark gray hexagons. This works on Chrome and IE but not on Firefox or Safari. Sorry.
The idea is to adjust triangular regions near the poles to be adjacent to the ones the player is in. Then when the player moves away we’ll adjust them back, out of sight. The area near the player always looks flat as long as you don’t get near the pentagons.
I made the tiles fairly large for this demo but in a real game you could have a much large map with millions of small hexes, and you’d never get too close to the pentagons. You can’t allow the player to zoom out to keep this working, unless you’re willing to switch to a 3D sphere view when zooming out.
Implementation: determine the region the player is in, then draw that region plus the three adjacent regions. For this demo however I implemented a slightly easier approach: determine the four-region “column” the player is in, and render those four plus the six neighboring regions. I haven’t yet worked out mathematically how far from the pentagons we need to stay but for the demo I just tweaked it until it’s good enough.
There are some bugs in my quick & dirty demo, and some features I wanted to add:
- The areas near pentagons are forbidden zones but the demo lets you drive there.
- It doesn’t work across browsers (for reasons I haven’t figured out).
- The “sphere” should be drawn as a sphere, not an isocahedron.
- The sphere should include the numeric labels and the player’s position.
However I’m not pursuing this idea, so I’m not going to spend a lot more time on it right now.
Working on this miniproject, I decided working with spheres was more effort than I wanted to put into a game, unless the sphere was an essential part of the game. What other ways are there to tile a sphere, and also make it easy to work with?
- I first got interested in this when answering this stackoverflow question; the visualization from https://github.com/vraid/earthgen-old is beautiful! But it too has pentagons. Also see this stackoverflow question.
- The board game Invasion Earth used an unfolded isocahedron projection.
- Dymaxion map (or “Fuller Projection”) is Buckminster Fuller’s nonuniform unfolding of an isocahedron that fits all of Earth’s continents onto the map without splitting any of them at the discontinuities of the unfolding. To do this, he splits some of the isocahedron triangles into smaller shapes.
- This demo lets you move around on a Dymaxion map; it will show you how the triangles are oriented relative to your position.
- This discussion thread includes a post by “coregames” on page 3 showing a hexagonal tiling of the unfolded isocahedron.
- Tissot’s indicatrix is a visualization of distance, angle, and area distortions caused by a map projection. The “World maps comparing Tissot’s indicatrices on some common projections” section of that page shows how common map projections fare. An unfolded isocahedron seems to do fairly well.
- HEALPix tiles the sphere with equal-area but not equal-shape quadrilaterals. I wonder if we can locally display each of those quadrilaterals as a square tile (and prevent the player from approaching problem areas, just as on this page).
- Hexasphere claims to have a hexagonal tiling of the sphere without pentagons. They don’t.
- “What is the best way to pixelize a sphere?” has some math for isocahedron spheres.
- This page compares several approaches for certain types of calculations, but it doesn’t seem especially relevant for games.
- There’s also a way to tile a sphere using the rhombic dodecahedron instead of an isocahedron. It looks like it might work for square tiles, but like the hexagon+pentagons approach, there will be a few places on the map where normal geometry doesn’t hold, so those will have to be treated specially.
- The Pierce quincuncial projection might be a starting point for square tiles; see this visualization from @mbostock. It’s a conformal projection, which preserves angles and local scale.