Bay 12 Games Forum

Thanks Toady! And thanks for the new quote to add to my signature.

Thanks for the reply! I think I understood most of it...

Are you going to start on the map rewrite as soon as you've finished adventurer mode, or do you plan on working on other stuff first?

Have you already worked out most of what you're going up do for the map rewrite, and only need to implement it, or are you going to figure it out as you go?

Won't the rewrite break a bunch of stuff with existing proc gen of sites?

As usual, murder proves an effective solution. By that, I mean murder the caravan.

With all the changes to UI, has it made it technically easier to translate Dwarf Fortress to other languages? Are we likely to see localisation of Dwarf Fortress, perhaps by KitFox or another third party? Is it technically feasible to abstract the interface to the point where fans could do the translations themselves? If not yet, is it possible or likely, perhaps something Putnam could take the lead on?

For Myth & Magic, do you intend for 'vanilla' dwarves to be averse to wizardy type magic, and have preference for "magic" through feats of craftdwarfship, moods, use of magical materials and/or religious devotion?

Do you intend for some features of 'dwarfiness' to be purely cultural and others to be inherent to biology?

One of the features of the Myth and Magic update will be cosmologies, including the shape and nature of the world(s) which the game will be played on. That means everything from islands floating in a sea of chaos to toroidal worlds. It just so happens that one of the hardest ones to bring to a game based on square grids are spherical worlds which, unfortunately, are the default in terms of what we know about the universe.

One of the functions of the map rewrite, as I understand it, is to permit the rotation of the map, and this enables the ability to incorporate spherical worlds and presumeably along with that real (non-global) day/night cycles, seasons, and so on.

It's not really confusing that, even when travelling in a straight line, the bearing of north should change. That's what happens on our real, spherical world. The confusion arises from the fact that most people don't travel in straight lines, or navigate by celestial position fixing, or use a compass to travel. For example, travelling due east using a compass, unless one is on the equator, you won't be travelling in a straight line; you'll be following a small circle, which is a curved line on a spherical surface. Travelling on foot on Earth you wouldn't notice the difference for hundreds of miles, but as an adventurer in Dwarf Fortress you'd notice because the world is so much smaller and you can walk from one end to the other fairly quickly.

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!