Wraparound tile maps with sphere topology | Hacker News Reader

Wraparound tile maps with sphere topology

redblobgames.com

87 pointsespeed28 comments

Astronomy used this for very long time. Most advanced is Healpix: http://healpix.sourceforge.net/

I really like how fast it is. For example irregular area size of Greenland at 1 meter accuracy only takes a few hundred MB. One can do joins and unions, on such areas on modest laptop.

Disclaimer: I send a few patches to this project.

HEALpix is cool. It has the same connectivity issue as with all the solutions — some locations are a little different. With hexagons a few polygons are different (polygons); with HEALpix a few vertices are different (three quads instead of four). In games we can get away with not mapping everywhere whereas in astronomy we can't :-)

For curiosity: It's possible to segment a sphere into equal area rectangles, plus circular caps. This is based on the arguably surprising relation between sphere area and the corresponding area on a cylinder of the same height as described in this article [1].

Paul Leopardi describes a neat 33 equal area region tiling, Recursive Zonal Equal Area Sphere, in his talk [2].

[1] http://blog.zacharyabel.com/2012/01/slicing-spheres/ Especially this animation: http://i1.wp.com/blog.zacharyabel.com/wp-content/uploads/201...

[2] http://maths-people.anu.edu.au/~leopardi/ORNL-2014-Leopardi-... Matlab Code: http://eqsp.sourceforge.net/

Your link #1 is about the volume of a ball, not the surface area of a sphere.

There are hundreds of different ways of segmenting a sphere. Your link #2 a relatively obscure one which is potentially worth evaluating for some uses (e.g. you start with a fine latitude/longitude grid but want to group your data into coarser histogram bins, and you them to have equal area), but is pretty far removed from the mostly hexagonal tilings in the OP.

For a summary of some other methods, I recommend Popko’s book Divided Spheres, http://www.dividedspheres.com

You can almost draw a congiguous hexagon map on a subdivided icosahedron, if you subdivide each triangle edge in 3 parts on each recursive step. Adjacent triangles will form hexagons.

This will leave 20 pentagons where the vertices of the original icosahedron's vertices were located. The rest of the sphere can be covered with a regular hexagon map for a strategy game.

I've been thinking about "hiding this" in a game design element so the 20 pentagons would be "capitals" or otherwise special tiles in the game. They're nicely equidistant from each other, so it could make a nice and fair map to play on.

An icosahedron has 12 vertices, so you get 12 pentagons.

You're correct. 12 vertices, 20 triangles.

The game RimWorld does exactly this.

(Author here) I had been trying to hide the 12 pentagons on the game map but RimWorld stretches the hexagons so that it doesn't have to hide anything. You can see one here: http://steamcommunity.com/sharedfiles/filedetails/?id=823772... Once you build a colony anywhere though, the colony map is square so it doesn't matter if you're on a hexagon tile or a pentagon tile.

Interesting. I thought RimWorld hid a few pentagons. Maybe the creator changed that plan?

I think I'd prefer a map where all tiles were slightly irregular, to avoid having 12 special tiles. Something like this: http://i.imgur.com/jQwYqZB.png You can make it by putting a bunch of point electrical charges on a sphere, letting them repulse each other, then taking a Voronoi diagram of the result.

(Author here) I had been trying to avoid the irregularities for that particular project because the storage of extremely large game maps saves a lot of space if you can use a regular grid instead of an irregular graph. (Certain algorithms like grid distance also run much faster.) If you embrace irregularity you can get some pretty neat maps, like this one from Andy Gainey: http://experilous.com/1/blog/post/procedural-planet-generati...

The author of this material is definitely on my free beer if I ever meet them list. I've learned a lot about geometric mapping, hexagonal pathfinding and lots of other fascinating nerdy stuff from his articles over the years.

They are good enough I keep my own archive copies just in case the site ever goes away.

I'm surprised there's no mention of a rather successful and efficient way of doing this in the real world: Google's S2 geometry library [1]. Basically the earth can be covered in almost aquare tiles down to about 1cm^2 with 64 bit integers.

[1] http://blog.christianperone.com/2015/08/googles-s2-geometry-...

(Author here) S2 is great (and Eric is brilliant). It uses a cube projection underneath. S2 solves some problems I didn't have (equal area, curve filling) but the main problem I was looking at was the nonuniform connectivity, and as far as I can tell, it's the same with S2 as if you use a cube directly.

The special sauce in S2 is the space filling curve aspect of it which is totally not what you want here, the concept behind it is I want to say called a 'geo grid' which off the top of my head a guy I know made a library for [1].

[1] https://www.npmjs.com/package/geogrids

Funny enough, I was just planning to email the author of this w/r/t some of my new maps:

e.g. http://i.imgur.com/U16RRnv.png

Those shapes look like they could be tiled with hexagons, which would create a hexagonal tiling of the sphere. Since the article mentions that this is impossible (and links to a proof), can anyone tell me what I'm missing in this image?

There are spots where a vertex would have two hexagons at it rather than three.

For instance, look at the border between the upper left and lower left islands. In this picture, those two islands are only touching along a third of the border that they share on the sphere. If you look at the leftmost point of where they are touching in this picture, that's a vertex that would have only two hexagons.

Notice how the lines are stretched, Not every hexagon in the tiling represents the same area if mapped back to a sphere. The non-polar edges of the tiles pictures are larger. If you actually printed it out, and tried to wrap it around a globe, the middles would have to expand or the edges would have to shrink for the tiles to join.

Edit: Basically he hasn't actually tiled a sphere with regular hexagons (which is what the proof said was impossible. He has titled a flat projection of a sphere with regular hexagons, which would have to be morphed to irregular hexagons if tiling a sphere when the projection was reversed.

Not taking away from the tiling, which is quite interesting in itself.

It’s possible to make a map projection from the sphere to a flat surface either preserve areas, or preserve angles (and local shapes), but not both. This projection preserves angles, but it could be modified to preserve area instead, or some compromise between the two.

There are 6 points on the map where pairs of adjacent “hexagons” are folded in at the corner so that they border each-other along two sides. If you like you can think of these as pairs of pentagons rather than hexagons.

I love seeing Red Blob Games' articles on HN. They're all excellent, recommending everybody to explore the site a bit.

My favourite article: http://www.redblobgames.com/grids/hexagons/

If you want the topology of a sphere (rather than the geometry) all you need to do is identify pairs of adjacent edges of your rectangular map instead of opposite edges.

For the record, I show all of my programming students the redblobgames website (towards the end of the semester and they are working on a final, "fun" project). It's an awesome resource!

Shameless plug: I've written a hexagonal grid library [hexameter] based on Amit's (redblobgames) excellent guide for hexagon grids.[hexameter][https://github.com/Hexworks/hexameter]

amitp, the way you capture the arrow keys for the demo makes it so I can't use the arrow keys to scroll the text of the page.

Otherwise, I find you entire site super inspiring :)

why not start players on the pentagons?

Reply on news.ycombinator.com