26
\$\begingroup\$

It's easy to deal with the way locations interact on a clean Cartesian grid. It's just vanilla math. And you can kind of ignore the geometry of the sphere's surface for a bunch of it if you want to just truncate the poles or something. But I keep coming up with ideas for games where the polar space matters. Geo-coded ARGs and global roguelikes and stuff.

I want square(ish?) locations -- reasonably representable by square tiles of the same size across the globe, anyway.

This has to be a solved problem, right?

What are the solutions?

ETA:

At the equator -- and assuming that your square locations are reasonably small, it's close enough to true that you can get away with having one square in the rows north and south of the most equatorial row. And you could probably get away with that by just hand-waving the difference up to like 45-degrees or so. But eventually, you need to have fewer squares in a pole-ward circumferential row. If I reduce the length of the row by one and offset the squares by 1/2 then they're just like hexes and it's relatively easy to do the coding to keep track of the connections. But as you get pole-ward, it gets more and more extreme.

Projecting the surface of the world onto the surface of a cube is tempting. But I figured there must be more elegant solutions already in use.

If I did the cube thing (not dissecting it further through geodesy) Are there any pros and cons related to placing the pole at the center of a face or at the vertex of three sides?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Could you elaborate on what you mean by "square(ish)"? How squarish is "square(ish)"? \$\endgroup\$
    – Steve H
    Aug 31, 2010 at 2:17

9 Answers 9

5
\$\begingroup\$

I think you are looking for a geodesic grid. Lots of people approximate the earth with a cube:

Most cartographic problems would disappear on a polyhedral Earth

Carlos A. Furuti has lots of maps of earth that fold up into a cube

You may also be interested in the The Peirce quincuncial projection which maps the whole Earth to one or two squares.

The icosahedron (Dymaxion map ; "What is the best way to pixelize a sphere?" ) gives slightly less distortion, but is more complicated.

\$\endgroup\$
11
\$\begingroup\$

I've always wanted to see a game where the spherical map used a regular polyhedron of some some sort instead of playing the world on a torus. This technique is called Dymaxion map. alt text         
(source: grunch.net)

I would recommend an Icosahedron. Plop the current triangle so it's aligned on one edge of a square. When the player moves off the triangle, pull up the next triangle and map it identically again. The player's coordinates would then be remapped to the new section. So each section of your map has its own coordinate system. Also you'll need to draw the background for the 3 adjacent and 9 semi adjacent sections. I don't think the user would be able to determine how it's implemented if it's well done.

Here is an example of how this might work.

Of course after reading this you'll probably use the classic torus map and I'll be waiting to see a true polyhedral universe.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ I won't use a torus. I could use a cylinder like the Civ games do. But, given the lack of brilliant solutions, I'm seriously leaning toward a cube. A cube is a polyhedron! :) \$\endgroup\$
    – clweeks
    Aug 31, 2010 at 12:35
6
\$\begingroup\$

If you create a sphere using a geodesic base, the polar area is treated no different than any other region in terms of vertex spacing which facilitates uniform uv mapping.

Most modeling apps allow you to create a sphere primitive using a geodesic design.

\$\endgroup\$
5
  • \$\begingroup\$ The problem is you'll get diamonds instead of squares in this case, and that's not what the OP wanted. \$\endgroup\$ Aug 30, 2010 at 14:00
  • \$\begingroup\$ Unless I'm missing something, that doesn't give me regions that are any easier to coordinate and map and link...does it? \$\endgroup\$
    – clweeks
    Aug 30, 2010 at 15:34
  • \$\begingroup\$ Geodesic seems like the way to go to me, can't think of any other options for regular subdivision. If you really need square regions, surely you can generate a square region, centred on the triangle centre, even though it overlaps with other tiles. For large enough spheres (and small enough triangles), the offset between the square regions and the adjacent triangle faces will be neglible. That should preserve the advantage of being able to describe local (i.e. same square) interactions in the same coordinate system, no? \$\endgroup\$
    – MrCranky
    Aug 30, 2010 at 16:17
  • \$\begingroup\$ I think that there are some geodesic shapes that can give aproximate squares if REALLY needed. \$\endgroup\$
    – speeder
    Aug 30, 2010 at 22:09
  • \$\begingroup\$ You get diamonds instead of squares, but that should be fairly easy to make a transform for to correct it. No poles guaranteed. \$\endgroup\$
    – ChrisE
    Mar 8, 2011 at 18:13
5
\$\begingroup\$

There is no way to "map" a sphere with squares (or rectangles) and have them all join up at "common" vertices.

However, would it be feasible to generate the "local view" on demand? The problem space isn't really stated in the question, but if I were working on something where I wanted a city view but wanted to be able to spin the world, I might temporarily just map a grid onto a "flat enough" section of the world. The origin of the grid would be wherever your local center was, and the normal at that point matches the normal of the surface of the planet.

Then, when one walks off of the grid, a new one is generated on demand.

This may or may not work for the OP, but for some it might be useful.

\$\endgroup\$
4
\$\begingroup\$

Take a cube, with the distance between the vertices and the center of the cube equal to the desired radius. You have a sphere made out of 6 quads.

Now in each step, take every quad, divide it into 4, and move the new 5 vertices (one in the center, and 4 on the edges -- warning, they are SHARED) away from the center so that they like on the desired radius.

No, this method is not perfect, but at least it's a more or less equal distribution over the sphere.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ The distortion is actually pretty severe with this - the quads in the middle of the face will be near square, and the ones near the corners will be badly distorted. \$\endgroup\$
    – JasonD
    Aug 30, 2010 at 14:35
  • \$\begingroup\$ @JasonD : It will still be better than all diamonds. Suggest a solution which is less distorted if you want to downvote. \$\endgroup\$ Aug 30, 2010 at 14:39
  • \$\begingroup\$ Well, you can approximate a sphere pretty nicely with geodesic division, but I'm not sure I see how that helps me. \$\endgroup\$
    – clweeks
    Aug 30, 2010 at 15:32
2
\$\begingroup\$

I'm operating several PTZ network cameras from Sony, model SNC-RX570N, for the purposes of tracking moving objects in the sky and triangulating to obtain true 3D tracks. One of the aspects of initial setup is to define unattended "tours", for which waypoints must be chosen. There are a restricted number of such programmable waypoints, and I want to cover the entire hemisphere (the "celestial sphere") from horizon to zenith, leaving no gaps.

So I asked myself the question "What are the minimum number of waypoints that I need for full coverage (no gaps)?". I've discovered that I actually can't fully figure this out.

The camera has endless pan (360 deg) and 0-90 deg tilt, so theoretically it's possible to achieve complete coverage. The camera display, intended for computer use, is 4:3 aspect ratio rectangular. Rough horizontal FOV at 1x zoom is 58 deg.

There are two ways of representing the problem, depending on which projection one chooses: - rectilinear like Mercator, whereby the horizon is "the equator", and the zenith is "the pole", dilated across over 360 deg of pan. - polar, whereby the horizon is the circle's circumference and the zenith is the circle's centre.

I find polar the easiest way to approach the problem. I can carve up the circle into horizontal FOV sized pie slices, and this tells me I need 7 waypoints around the circle with that 58 deg H-FOV. So far so good. The inner radius is simply the tilt or V-FOV, which is 3/4 of 58 deg. So far so good - I've covered the outermost parts of the circle.

But it gets trickier as we approach the zenith. I'll assume that one of my waypoints is exactly at zenith. How do I map my view rectangle onto the region around the centre of the circle? Is that shape a rectangle, an ellipse, a pincushion, or what? How do I fill in the middle bit between the nice neat outer coverage and this odd shape at zenith? Flummoxed.

I note that the solid angle of a hemisphere is 2*PI steradians, and that of my FOV at 1x zoom is 0.762 st, meaning I need a minimum of 9 tessellations. I suspect the answer is higher than 9.

\$\endgroup\$
1
  • \$\begingroup\$ How about this.. The circle has PI^2 rad^2 of area, and the FOV rectangles are area 0.75 rad^2. So naively we need 13.16 points which must be rounded up for full coverage to 14 points. The question now is - how are these to be placed? \$\endgroup\$
    – Andrew
    Jan 24, 2012 at 12:26
1
\$\begingroup\$

With the dymaxion max you've got hexagons laid out in triangles on a flat surface but because the map isn't really flat they are pentagons. If you want to allow the player to keep their orientation when they walk over certain portions you'll need to separate the location maps from how they are actually stored. For things like buildings you could store a little map of rectangle vectors and then just do a harsh job of drawing them at whatever orientation you needed.

You wouldn't need to always make the interior look like there had been a recent Earthquake because I think the average player shouldn't even bat their eyes about entering a door to the north east but entering into a screen with the front door oriented due south and the whole building on a regular grid.

Though if you are going to just store buildings and important sites like that then you've done all the work for a soccerball pattern anyway. The end result is that you're storing the world as some non-square pattern and then forcing it into such a grid wherever the player is at.

There's another alternative though- if you don't give them all that precise an indication of the sphere, like if you just gave them a low precision compass to tell them which of the four orthogonal directions was closest to North, then you could get away with just doing 90 degree rotations for whatever location the player went to. Given the assumed graphics level it isn't as if you have to worry about a tall building obscuring some doorway. So long as they knew if they were near the poles or not they shouldn't get too upset about the compass changing on them, unless the NPCs around there told them to go North East or they try to actually go to specific latitude and longitude coordinates.

\$\endgroup\$
1
\$\begingroup\$

You're asking a question that people who make maps have been asking for a long time :)

Most definitely go read up on Map Projectsions to get some insights and ideas that might help. The challenge of representing the surface of a sphere on/with a flat 2D plane has been something people have been thinking about for a long long time.

Short answer is, no you can't do it. That's why when you look at maps of the world, some parts are distorted and some parts aren't. Usually it's the poles because most maps are about non-polar areas.

As other answers have said, the answer is to either use a different shape (hexes or triangles for example), or dynamically generate your map on the fly for the user's current viewpoint.

Square tiles are pretty easy to manage no question, but I don't think creating a tiling hex map is that hard.

Here is an older article from GameDev.net you might find useful. It's about doing isometric and hexagonal tiles on a grid.

http://www.gamedev.net/reference/articles/article747.asp

Googling "tiling hex map" will give you a lot of hits, some useful some not.

\$\endgroup\$
0
\$\begingroup\$

If you want to make a worldwide grid, I suggest you divide the planet in countries or continents, and make a square grid properly centered on each. Let the ocean cover the seams.

\$\endgroup\$
4
  • \$\begingroup\$ Actually, my question is "since I obviously can't do what you thought I was really asking, what might I do instead?" \$\endgroup\$
    – clweeks
    Aug 30, 2010 at 15:32
  • \$\begingroup\$ Very well, edited then. \$\endgroup\$
    – zaratustra
    Aug 30, 2010 at 15:34
  • \$\begingroup\$ Yeah, I guess I got side-tracked by the other part. I was thinking about implementing Fuller's Dymaxion Map but working with triangular tiles seemed like as much of a clusterF* as the polar-tiling problem that I'm starting with. So, with your suggestion, if someone is sailing from North America to northern Asia, and the coordinates matter (maybe they can establish floating bases or something) how do I stitch the seams together? Just come up with a table of NA:A5 -> A:Z475 type connections? \$\endgroup\$
    – clweeks
    Aug 30, 2010 at 15:38
  • \$\begingroup\$ I guess. Though if they manage to do that, I'd just give them a bonus reward and put them off the grid until they go somewhere sensible. \$\endgroup\$
    – zaratustra
    Aug 30, 2010 at 16:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .