News for hackers. Stuff that matters.
Re:Wraparound tile maps with sphere topology by jankotek on Monday January 30, 2017 @02:54AM (#13519354)
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.

Re:Wraparound tile maps with sphere topology by amitp on Monday January 30, 2017 @10:47AM (#13522085)
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 :-)
Re:Wraparound tile maps with sphere topology by mxfh on Monday January 30, 2017 @08:28AM (#13520927)
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/

Re:Wraparound tile maps with sphere topology by jacobolus on Tuesday January 31, 2017 @03:35AM (#13528781)
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

Re:Wraparound tile maps with sphere topology by exDM69 on Monday January 30, 2017 @06:29AM (#13520223)
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.

Re:Wraparound tile maps with sphere topology by robinhouston on Monday January 30, 2017 @08:49AM (#13521084)
An icosahedron has 12 vertices, so you get 12 pentagons.
Re:Wraparound tile maps with sphere topology by exDM69 on Monday January 30, 2017 @04:30PM (#13525221)
You're correct. 12 vertices, 20 triangles.
Re:Wraparound tile maps with sphere topology by Waterluvian on Monday January 30, 2017 @08:11AM (#13520809)
The game RimWorld does exactly this.
Re:Wraparound tile maps with sphere topology by amitp on Monday January 30, 2017 @10:49AM (#13522103)
(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.
Re:Wraparound tile maps with sphere topology by Waterluvian on Tuesday January 31, 2017 @07:14AM (#13529868)
Interesting. I thought RimWorld hid a few pentagons. Maybe the creator changed that plan?
Re:Wraparound tile maps with sphere topology by cousin_it on Monday January 30, 2017 @09:40AM (#13521501)
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.
Re:Wraparound tile maps with sphere topology by amitp on Monday January 30, 2017 @10:53AM (#13522150)
(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...
Re:Wraparound tile maps with sphere topology by techdragon on Monday January 30, 2017 @02:35AM (#13519295)
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.

Re:Wraparound tile maps with sphere topology by cletus on Monday January 30, 2017 @06:48AM (#13520353)
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-...

Re:Wraparound tile maps with sphere topology by amitp on Monday January 30, 2017 @10:43AM (#13522043)
(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.
Re:Wraparound tile maps with sphere topology by cwmma on Monday January 30, 2017 @08:10AM (#13520801)
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

Re:Wraparound tile maps with sphere topology by jacobolus on Monday January 30, 2017 @05:05AM (#13519826)
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

Re:Wraparound tile maps with sphere topology by yorwba on Monday January 30, 2017 @08:20AM (#13520868)
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?
Re:Wraparound tile maps with sphere topology by arundelo on Monday January 30, 2017 @11:25AM (#13522483)
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.

Re:Wraparound tile maps with sphere topology by chad-autry on Monday January 30, 2017 @10:46AM (#13522071)
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.

Re:Wraparound tile maps with sphere topology by jacobolus on Monday January 30, 2017 @04:39PM (#13525291)
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.
Re:Wraparound tile maps with sphere topology by jacobolus on Monday January 30, 2017 @04:40PM (#13525301)
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.
Re:Wraparound tile maps with sphere topology by scrollaway on Monday January 30, 2017 @07:15AM (#13520527)
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/

Re:Wraparound tile maps with sphere topology by stephencanon on Monday January 30, 2017 @11:17AM (#13522382)
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.
Re:Wraparound tile maps with sphere topology by coreyp_1 on Monday January 30, 2017 @11:11AM (#13522327)
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!
Re:Wraparound tile maps with sphere topology by edem on Monday January 30, 2017 @11:38AM (#13522610)
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]
Re:Wraparound tile maps with sphere topology by maggit on Monday January 30, 2017 @10:55AM (#13522163)
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 :)

Re:Wraparound tile maps with sphere topology by jlebrech on Monday January 30, 2017 @08:29AM (#13520934)
why not start players on the pentagons?