1
DF Suggestions / Map Rewrite; Rationalising a square grid with a spherical surface
« on: April 07, 2023, 03:27:46 am »
Thoughts on how best to map Dwarf Fortress’ square-based maps onto a sphere
With the map rewrite and myth and magic releases on the horizon, I thought I’d share my research on how best to map a square grid-based coordinate system onto a spherical surface.
The problem is that on a spherical surface, all straight lines converge and parallel lines are not straight. This has been a problem for cartographers for centuries, as it frustrates attempts to create maps on square pieces of paper and to implement rational grid-based coordinate systems.
I have made some progress into creating a sensible way of dicing up a spherical surface into a square-based grid for the purposes of games and simulations but ran into a wall as I’m not a mathematician.
The trick is to first divide the world into 8 octants, the anterior and posterior northeast, southeast, southwest and northwest octants. Each octant represents a spherical triangle wherein each interior angle is a right angle and each edge is a great circle; two of the corners rest upon the equator and one of the corners rests upon a pole.
Octants like these are used in conformal octahedral projections used in cartography, like this;
However, because each octant is a triangle, it can be distorted and folded in a particular way to make a square. Two triangles can be added together to form a square and four squares can be added together in this way to form a grid, like this;
On Earth this would produce a distorted map that looks something like this;
Although this seems perfectly convenient at first, it does not preserve either areas or shapes correctly if directly converted into a square-based grid. Consider the most simple sub-division- what does this look like?
If we divide each octant into four equally sized triangular quadrants, what would this look like on a sphere?
It turns out, if we divide each octant into equally sized triangular quadrants, the dividing line separating each quadrant is neither a small circle centred upon one of the corners nor a great circle describing a straight line on a sphere, but a small circle centred upon a point farther outward from the centre of the octant than each of the three corners of the octant. I was, with difficulty, able to determine where this point lay although I’ve since lost the maths to describe it.
The area of a sphere is equal to S=4πr^2 and therefore the area of octant is one eighth of that; therefore a quarter of each octant is equal to one thirty-second of the area of the sphere, or πr2/8.
In this diagram the triangular quadrant is the known area. Note that this is on a spherical surface, so the straight lines are great circles and the lengths are angular, measured in radians or degrees.
Dividing one octant into four is not particularly confusing; however if one wishes to further subdivide each octant into smaller triangles, it became out of my depth to mathematically describe each one in such a way that each triangle had an equal area. Then I remembered that Tarn is a mathematician and could probably work such things out easier than me!
I’m not even sure if each octant can be indefinitely subdivided in such a way as to preserve each component triangle as having equal area, although it looks to me as though it can be. This is a consideration because if each octant is divided many times using straight lines, the innermost triangle has an area about three times greater than those at the corners! This is not so much of a problem in a simulation if these areas are known in advance and accounted for (if one were so inclined), however, it would be better to know that each triangle is of an equal area.
In fact, provided that it is known that each octant can be divided indefinitely into equal areas, and provided that one does not particularly care that each triangle represents a skewed and distorted shape, the actual specifics of how it is distorted does not matter. This happens to be the case for Dwarf Fortress.
In Dwarf Fortress, the simulation occurs within a square-based grid and everything within each square is perfectly abstracted, so internal map distortion is completely irrelevant. The only thing that matters is that area is preserved so that the simulation makes some kind of sense, and that the information can be rationally processed. That’s why this particular way of mapping a sphere onto a grind (or a grid onto a sphere, depending on which way you think of it) makes sense.
In this diagram I’ve divide each octant into sixteen equally sized triangles. This is what it looks like for each triangle when represented on a sphere;
Each triangle can be paired with the one next to it in order to form a rhombus; for the purposes of the simulation, this can be treated as square. (Think about the practical difference between Civilization and Civilization II; the former used squares, the latter rhombuses to give the impression of perspective, but there was no practical difference).
In this diagram, the triangles coloured in grey pair with triangles in the next octant, such that any two adjacent octants can be paired together to form a square grid that tessellates with other square grids.
The big advantage of dividing a spherical world into octants and skewing them this way is that the whole world can be represented as a single square grid and traversed in a rational way. Moving up-down, left-right or diagonally across the grid approximates travel across great circles, particularly between where the corners of each triangle meet. Just like in the real world, an individual travelling in a straight line across the spherical surface will find the compass bearing towards north will change, even though their direction does not. As long as one does not leave the square grid, the compass bearing to north can be calculated, but otherwise you don’t need to think about directionality or rotation of the grid you’re on when travelling from one octant to another- you can just leave it all on the x,y grid and it works itself out. This isn’t really possible on other projections, such as cubic or icosahedral (which have their own advantages otherwise).
When crossing the edges of the square, direction flips and translates in an easily comprehensible way.
Let x,y=0,0 represent the top left corner. When leaving the grid to the left, (x<0) let x=1 and y=(max_y)-y. When leaving to the up (y<0) let y=1 and x=(max_x-x). This is reversed on the opposite sides. Remember that the four corners of the square are colocational; they represent a point antipodal to the centre of the grid on the surface of the sphere.
This means that what lies beyond each edge of the grid can be directly plotted onto the screen provided one rotates the map when keeping the direction of the character the same. (I am thinking in adventure mode for this).
That’s my summary of my thoughts on the best way to rationalise a spherical surface onto a square grid for the purposes of Dwarf Fortress following the map rewrite. It’s as rational as I think is possible. The problem is that I struggle to mathematically describe the shape of the triangles that constitute the distorted quadrilaterals that constitute the squares on the grid. At the extreme corners of each octant, each of the subdivided triangles constituting the distorted quadrilaterals is composed of two straight lines (great circles) and one highly curved small circle. To preserve equal areas between the “triangles” the chain of adjacent triangles fanning out from those points also need to be curved with two (at the edges) or all three sides being composed of small circles. Figuring out how to describe these triangles or where the centre of the quadrilateral formed from two of them is for the purpose of determining the true bearing to north is a mathematically and computationally difficult task that is beyond my abilities so I was hoping that a better mathematician than myself could undertake this task and post the results here.
I couldn’t even make sense of the notation to describe the area of a small circle. This is because the surface area of sphere makes use of the radius of a sphere, but the surface area of an area on a sphere bounded by a small circle also makes use of the curved radius of the circle, which is an angular distance, and it wasn’t clear (looking through the google results for this topic) whether the area represented was in terms of ‘scalar area’ or ‘angular area’ (for want of better terms to describe them; I’m not a mathematician).
I hope that this was all comprehensible. Feedback is welcome!
With the map rewrite and myth and magic releases on the horizon, I thought I’d share my research on how best to map a square grid-based coordinate system onto a spherical surface.
The problem is that on a spherical surface, all straight lines converge and parallel lines are not straight. This has been a problem for cartographers for centuries, as it frustrates attempts to create maps on square pieces of paper and to implement rational grid-based coordinate systems.
I have made some progress into creating a sensible way of dicing up a spherical surface into a square-based grid for the purposes of games and simulations but ran into a wall as I’m not a mathematician.
The trick is to first divide the world into 8 octants, the anterior and posterior northeast, southeast, southwest and northwest octants. Each octant represents a spherical triangle wherein each interior angle is a right angle and each edge is a great circle; two of the corners rest upon the equator and one of the corners rests upon a pole.
Octants like these are used in conformal octahedral projections used in cartography, like this;
However, because each octant is a triangle, it can be distorted and folded in a particular way to make a square. Two triangles can be added together to form a square and four squares can be added together in this way to form a grid, like this;
On Earth this would produce a distorted map that looks something like this;
Although this seems perfectly convenient at first, it does not preserve either areas or shapes correctly if directly converted into a square-based grid. Consider the most simple sub-division- what does this look like?
If we divide each octant into four equally sized triangular quadrants, what would this look like on a sphere?
It turns out, if we divide each octant into equally sized triangular quadrants, the dividing line separating each quadrant is neither a small circle centred upon one of the corners nor a great circle describing a straight line on a sphere, but a small circle centred upon a point farther outward from the centre of the octant than each of the three corners of the octant. I was, with difficulty, able to determine where this point lay although I’ve since lost the maths to describe it.
The area of a sphere is equal to S=4πr^2 and therefore the area of octant is one eighth of that; therefore a quarter of each octant is equal to one thirty-second of the area of the sphere, or πr2/8.
In this diagram the triangular quadrant is the known area. Note that this is on a spherical surface, so the straight lines are great circles and the lengths are angular, measured in radians or degrees.
Dividing one octant into four is not particularly confusing; however if one wishes to further subdivide each octant into smaller triangles, it became out of my depth to mathematically describe each one in such a way that each triangle had an equal area. Then I remembered that Tarn is a mathematician and could probably work such things out easier than me!
I’m not even sure if each octant can be indefinitely subdivided in such a way as to preserve each component triangle as having equal area, although it looks to me as though it can be. This is a consideration because if each octant is divided many times using straight lines, the innermost triangle has an area about three times greater than those at the corners! This is not so much of a problem in a simulation if these areas are known in advance and accounted for (if one were so inclined), however, it would be better to know that each triangle is of an equal area.
In fact, provided that it is known that each octant can be divided indefinitely into equal areas, and provided that one does not particularly care that each triangle represents a skewed and distorted shape, the actual specifics of how it is distorted does not matter. This happens to be the case for Dwarf Fortress.
In Dwarf Fortress, the simulation occurs within a square-based grid and everything within each square is perfectly abstracted, so internal map distortion is completely irrelevant. The only thing that matters is that area is preserved so that the simulation makes some kind of sense, and that the information can be rationally processed. That’s why this particular way of mapping a sphere onto a grind (or a grid onto a sphere, depending on which way you think of it) makes sense.
In this diagram I’ve divide each octant into sixteen equally sized triangles. This is what it looks like for each triangle when represented on a sphere;
Each triangle can be paired with the one next to it in order to form a rhombus; for the purposes of the simulation, this can be treated as square. (Think about the practical difference between Civilization and Civilization II; the former used squares, the latter rhombuses to give the impression of perspective, but there was no practical difference).
In this diagram, the triangles coloured in grey pair with triangles in the next octant, such that any two adjacent octants can be paired together to form a square grid that tessellates with other square grids.
The big advantage of dividing a spherical world into octants and skewing them this way is that the whole world can be represented as a single square grid and traversed in a rational way. Moving up-down, left-right or diagonally across the grid approximates travel across great circles, particularly between where the corners of each triangle meet. Just like in the real world, an individual travelling in a straight line across the spherical surface will find the compass bearing towards north will change, even though their direction does not. As long as one does not leave the square grid, the compass bearing to north can be calculated, but otherwise you don’t need to think about directionality or rotation of the grid you’re on when travelling from one octant to another- you can just leave it all on the x,y grid and it works itself out. This isn’t really possible on other projections, such as cubic or icosahedral (which have their own advantages otherwise).
When crossing the edges of the square, direction flips and translates in an easily comprehensible way.
Let x,y=0,0 represent the top left corner. When leaving the grid to the left, (x<0) let x=1 and y=(max_y)-y. When leaving to the up (y<0) let y=1 and x=(max_x-x). This is reversed on the opposite sides. Remember that the four corners of the square are colocational; they represent a point antipodal to the centre of the grid on the surface of the sphere.
This means that what lies beyond each edge of the grid can be directly plotted onto the screen provided one rotates the map when keeping the direction of the character the same. (I am thinking in adventure mode for this).
That’s my summary of my thoughts on the best way to rationalise a spherical surface onto a square grid for the purposes of Dwarf Fortress following the map rewrite. It’s as rational as I think is possible. The problem is that I struggle to mathematically describe the shape of the triangles that constitute the distorted quadrilaterals that constitute the squares on the grid. At the extreme corners of each octant, each of the subdivided triangles constituting the distorted quadrilaterals is composed of two straight lines (great circles) and one highly curved small circle. To preserve equal areas between the “triangles” the chain of adjacent triangles fanning out from those points also need to be curved with two (at the edges) or all three sides being composed of small circles. Figuring out how to describe these triangles or where the centre of the quadrilateral formed from two of them is for the purpose of determining the true bearing to north is a mathematically and computationally difficult task that is beyond my abilities so I was hoping that a better mathematician than myself could undertake this task and post the results here.
I couldn’t even make sense of the notation to describe the area of a small circle. This is because the surface area of sphere makes use of the radius of a sphere, but the surface area of an area on a sphere bounded by a small circle also makes use of the curved radius of the circle, which is an angular distance, and it wasn’t clear (looking through the google results for this topic) whether the area represented was in terms of ‘scalar area’ or ‘angular area’ (for want of better terms to describe them; I’m not a mathematician).
I hope that this was all comprehensible. Feedback is welcome!
