tag:blogger.com,1999:blog-72506491355277104632017-08-08T20:49:04.464-04:00HypatianDwarf + Gravity Well = ?Katherine Prevostnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-7250649135527710463.post-79324430628449989292010-09-20T21:50:00.002-04:002010-09-21T04:02:16.489-04:00Global Grids, Part 2: Indexing the grid<p>As I alluded to in my previous post, identifying the grid system I wanted to use was just part of the solution. In order to work effectively at this scale, I needed to have a way to concisely identify each cell, a method to quickly calculate the neighbors of a given cell, and a method to quickly calculate the position of a given cell.</p><p>The first step in any of the possible solutions is to remember that each hexagonal grid cell (and the twelve pentagonal cells) is generated by using points in a triangular mesh. Each point (or vertex) identifies an individual grid cell. The lines between these vertices (forming the faces of the triangles) connect them to the vertices which identify the adjacent grid cells. The following image illustrates this:</p><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5519082788502884738" title='Depth 2, triangles and strip'><img src="http://lh5.ggpht.com/_eoPgF1wybxs/TJe4jgav0YI/AAAAAAAAAHM/-eK07CGqn98/s128/depth-2-triangles.png" width="144" height="144"/></a><p>You may note that the triangular grid seems to “pop out” slightly above the cells. This is because my current rendering scheme draws the cells by computing each cell-vertex’s position as the average of the positions of the three surrounding triangle-vertices. Because of this, the sphere defined by the cells is slightly smaller than the sphere defined by the triangles. (The solution to this is simple: compute the average then normalize the length of the vector. But the extra computation is not worth doing at this point, and may never be.)</p><p>It’s also worth noting at this point that it’s particularly valuable to work with the triangular view of the world because most algorithms will only be interested in the cells and the connections between them, which the triangles represent wonderfully. Pretty much only the display code needs to know how to show the cells as actual hexagons.</p><a name='more'></a><p>If we take the triangular grid and flatten it, it becomes slightly easier to think about. The following image shows the flattened form of the depth-0 triangular grid (a regular icosahedron) and the flattened form of the depth-1 triangular grid (with each triangular face of the original icosahedron divided into four sub-faces). Note that when the grid is flattened, certain vertices are shown twice. In this image, I’ve chosen one position for each vertex as canonical, and drawn dotted lines connecting it to the other places the same vertex is shown.</p><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5519106462298239762" title='Flattened grid showing subdivisions and poles'><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJfOFgLZcxI/AAAAAAAAAHY/gsiD5ZKL_zU/s128/triangular-grids.png" width="144" height="144"/></a><p>Recall from the previous post that a grid of depth <i>d</i> has 10·4<sup><i>d</i></sup> + 2 cells (or triangular vertices). If you examine the image, the source of this formula becomes clear. For each of the original vertices <i>except the north and south poles</i> in the depth-0 grid, there are four vertices in the depth-1 grid. I’ve used colors to show this relationship.</p><p>This suggests a very obvious way to compute a unique integer for each cell. Number the icosahedron vertices 0–11, with 10 and 11 being the north and south poles, respectively. As you increase in depth, multiply the previous number by 4 and add 0–3 for the four child vertices (for the co-located child, the north-east child, the east child, and the south-east child, respectively.) Voila, problem solved. There exists a simple mapping between cells and integers.</p><p>Of course, it’s never quite that easy. I also needed an easy fast method of calculating the neighbors of each cell, and my work towards a solution to that problem led me to choose a different system.</p><p>Let me first describe the system that I’m actually using, then I will explain why it is superior for computing the list of adjacent cells. First, recall the “gray strip” in the first image I posted (showing the triangular grid on a sphere). That strip is equivalent to all of the children from putting two of the original icosahedral vertices together. For example, all of the yellow and all of the cyan nodes in the second image. If you squint carefully and maybe tilt your head a bit, you may also notice that the shape of that collection of nodes on the flattened layout is something like a rectangle.</p><p>Those five rectangular “strips” are the basis of the improved solution. The following image is a view of a single one of those five rectangular strips on a depth-2 grid laid out as a rectangle, with all of the edges shown along with adjacent cells in other strips.</p><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5519122615430113922" title='"Rectangularized" grid showing adjacent cells'><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJfcxvSJaoI/AAAAAAAAAHg/dPzlRhMFkpw/s128/rect-grid-with-adj.png" width="144" height="144"/></a><p>Each cell is labeled with its strip (A–E), with a horizontal position <i>i</i> within the strip, and with a vertical position <i>j</i> within the strip (in addition to “NP” for the north pole and “SP” for the south pole.) The bottom right yellow cell “A30” has <i>s</i> = A, <i>i</i> = 3, and <i>j</i> = 0. The values of <i>i</i> for depth <i>d</i> range from 0 to 2<sup><i>d</i></sup> − 1, and the values of <i>j</i> range from 0 to 2<sup><i>d</i>+1</sup> − 1.</p><p>To calculate the integer for a given cell, we take <i>s</i> encoded in three bits, followed by <i>i</i> encoded in <i>d</i> bits, followed by <i>j</i> encoded in <i>d</i> + 1 bits. I’ve chosen to always represent the north and south poles as 0 and 1, respectively, so I then add 2 to the value from this formula.</p><p>On the face of it, this mapping is more complicated than the original recursive definition I described above. However, it turns out to be much much easier to work with when calculating adjacencies (and, luckily, positions).</p><p>To see why, notice first that all of the “internal” edges in the adjacency graph are very easy to compute—those for A25, for example, which can be had simply by adding or subtracting 1 from <i>i</i> and <i>j</i>. The remaining “special-case” edges are all along the border of the graph, and those fall into a handful of regular patterns. For example, in the “north-east” direction (labeled 2 in the image) from A07–A37, each cell is adjacent to a sister-cell on side “B”. In fact, there’s a simple formula we can use to compute the adjacency in direction 2 along that border: <i>s’</i> = <i>s</i> + 1, <i>i’</i> = 0, <i>j’</i> = 7 - <i>i</i>. There are similar simple rules for all of the other borders.</p><p>With this representation of the cells as integers, it is very easy to determine if a cell is inside the rectangle or on a border, it is very easy to determine which border it is on, and it is very easy to calculate the numeric representation of the cells on the other side of that border. With the recursive base-4 representation, sadly, it’s not nearly so easy. (For example, in the base-4 representation, the cells on the border where <i>j</i> = 7 would be those cells in which <i>every other</i> bit of the integer representation was 1.)</p><p>So, given a cell position <i>s</i>, <i>i</i>, <i>j</i>, with the length of the short side <i>n</i> = 2<sup>d</sup> and the length of the long side <i>m</i> = 2<sup><i>d</i>+1</sup>, you can calculate the adjacent cells with the following system of rules:</p><pre> i < n-1 s, i+n, j [3]<br /> j < m-1 s, i+1, j+1 [2]<br /> j < m-1 s, i, j+1 [1]<br /> i > 0 s, i-1, j [0]<br /> j > 0 s, i-1, j-1 [5]<br /> j > 0 s, i, j-1 [4]<br /><br /> i = 0<br /> j < n s-1, n-1, n+j [0]<br /> j > 0 s-1, n-1, n-1+j [5]<br /> else j >= n s-1, m-j-1, m-1 [0]<br /> j > n s-1, m-j, m-1 [5]<br /><br /> i = n-1<br /> j < n s+1, n-j-1, 0 [2]<br /> j = 0 SP [3]<br /> else j > 0 s+1, n-j, 0 [3]<br /> j >= n s+1, 0, j-n [3]<br /> j < m-1 s+1, 0, 1+j-n [2]<br /><br /> j = 0 s-1, n-1, n-1-i [4]<br /> i > 0 s-1, n-1, n-i [5]<br /> else if j = m-1 s+1, 0, m-1-i [2]<br /> i = 0 NP [1]<br /> else i > 0 s+1, 0, m-i [1]</pre><p>The number in square brackets after each rule indicates in which direction that adjacent cell lies. Note that I explicitly chose the way I laid out my “rectangle” such that cells A00 and A04, which have only five adjacent cells, are missing a cell in direction 5. That way, each cell is adjacent to cells in directions 0–4, and a handful are missing a cell in the last direction 5.</p><p>Next time: Computing the physical locations of the cells.</p>J. Prevostnoreply@blogger.com2tag:blogger.com,1999:blog-7250649135527710463.post-11463535312637369232010-09-18T21:17:00.002-04:002010-09-21T04:12:49.084-04:00Global Grids, Part 1: The setup<p>I’ve just finished implementing my spherical grid system, based on the work and links I saw at <a href="http://www.dungeonleague.com/">Dungeon League</a>. There were a couple of unique issues I had to work through, however, and I used a slightly different grid system from the one he’s using.</p><p>First, some sample images:</p><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518363973546023890" title="Depth 0 spherical grid"><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJUqy-CGG9I/AAAAAAAAAEE/5eWL-xSQWVY/s128/x-grid-0.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364097487368066" title="Depth 0 spherical grid"><img src="http://lh6.ggpht.com/_eoPgF1wybxs/TJUq6LwA74I/AAAAAAAAAEI/ynqS78Vl_FM/s128/x-grid-1.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364135005681922" title="Depth 0 spherical grid"><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJUq8XhE-QI/AAAAAAAAAEM/CCbwM_eK1sg/s128/x-grid-2.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364171594359010" title="Depth 0 spherical grid"><img src="http://lh6.ggpht.com/_eoPgF1wybxs/TJUq-f0f4OI/AAAAAAAAAEQ/bw6AczZFV3Q/s128/x-grid-3.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364207891834658" title="Depth 0 spherical grid"><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJUrAnCfZyI/AAAAAAAAAEU/40EFlPpQSJA/s128/x-grid-4.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364249317427746" title="Depth 0 spherical grid"><img src="http://lh5.ggpht.com/_eoPgF1wybxs/TJUrDBXHyiI/AAAAAAAAAEY/nc_0fXsVSCY/s128/x-grid-5.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364297930200930" title="Depth 0 spherical grid"><img src="http://lh4.ggpht.com/_eoPgF1wybxs/TJUrF2dT12I/AAAAAAAAAEc/6kXIKsdNw1s/s128/x-grid-6.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364387038722530" title="Depth 0 spherical grid"><img src="http://lh5.ggpht.com/_eoPgF1wybxs/TJUrLCab-eI/AAAAAAAAAEg/nA-JxePWXnc/s128/x-grid-7.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364446119967826" title="Depth 0 spherical grid"><img src="http://lh3.ggpht.com/_eoPgF1wybxs/TJUrOeggPFI/AAAAAAAAAEk/5I9RwxTv1U0/s128/x-grid-8.png" width="144" height="144"/></a><a href="http://picasaweb.google.com/j.prevost/SphereGrids#5518364491036247666" title="Depth 0 spherical grid"><img src="http://lh6.ggpht.com/_eoPgF1wybxs/TJUrRF1YRnI/AAAAAAAAAEo/ZPkz5xeI-cE/s128/x-grid-9.png" width="144" height="144"/></a><p>These hex grids are based on a Class I aperture 4 triangle hierarchy, starting with an icosahedron. (See the <a href="http://webpages.sou.edu/~sahrk/dgg/" title="Discrete Global Grids">Discrete Global Grids</a> site at Southern Oregon University for more details about grid types. Particularly the paper <a href="http://webpages.sou.edu/~sahrk/dgg/pubs/gdggs03.pdf"><i>Geodesic Discrete Global Grid Systems</i></a> by Sahr, White, and Kitterling.</p><p>The important number here is the aperture size. This determines how much bigger the grid is (or smaller the cells are) with each subdivision. The Dungeon League grid is slightly different, using alternating Class I and Class II subdivisions to produce an aperture 3 hierarchy. That means that he has more different “resolutions” available to him—an aperture 3 system could produce a grid of 5.9×10<sup>5</sup>, 1.8×10<sup>6</sup>, 5.3×10<sup>6</sup>, 1.6×10<sup>7</sup> cells (going up one depth each time). An aperture 4 system could only produce grids in that general range at 6.6×10<sup>5</sup>, 2.6×10<sup>6</sup>, and 1.0×10<sup>7</sup> cells. (Take a look at the DGG website’s <a href="http://webpages.sou.edu/~sahrk/dgg/isea/tables/tables.html" title="Characteristics of ISEA DGGs">tables of grid characteristics</a> for more details.)</p><p>The images above are at depths 0 through 9 from left to right. Each grid has 10·4<sup><i>d</i></sup> + 2 cells, where <i>d</i> is the depth. So the depth 0 grid is has an area of 12 cells. The depth 2 grid has an area of 162 cells. And the last image, at depth 9, has an area of 2,621,442 cells. At this depth, the sphere appears totally white because the image is only 984×984 pixels.</p><p>The next question that comes to mind is this: What depth would it take to model a body of approximately the size of the Earth down to a one meter resolution? Assuming the hexagons are regular (they’re not, but we’re just estimating here) with centers spaced 1m apart, each hexagon should have an area of approximately 3.46m<sup>2</sup>. The Earth’s surface area is approximately 5.10×10<sup>14</sup>m<sup>2</sup>—at 3.46m<sup>2</sup> per hex, that’s 1.47×10<sup>14</sup> cells.</p><p>Pretty huge compared to the depth 9 grid. It turns out that in order to get a resolution at this level, you’d need a depth 22 grid. Such a grid has 1.76×10<sup>14</sup> cells, which isn’t too far off. 176 trillion cells. Yikes! It’s clear at this point that it would be completely impossible to keep any information at all about the entire grid in memory. But, there are two <i>very</i> important pieces of knowledge we need all the time: which cells are adjacent to any given cell, and where on the surface of the globe is any given cell located. We also need an efficient way to identify each cell, in order to keep track of information that <i>cannot</i> be automatically generated when the player is visiting a locationg. (For example, any changes the player has made to the area.)</p><p>Up next: A system for identifying cells and calculating their neighbors.</p>J. Prevostnoreply@blogger.com6tag:blogger.com,1999:blog-7250649135527710463.post-62592419430619471712010-09-18T16:45:00.002-04:002010-09-18T22:44:47.102-04:00The Dwarrowdelf Project<p>For a while now, I’ve been working on a new development project. It all started with me thinking “You know, I bet it’s possible to do a better fluid dynamics simulation than what Dwarf Fortress currently uses” while waiting for the bus. I thought through a good bit of the problem, and came up with some ideas... But of course, I couldn’t attempt to implement them in DF since Toady keeps the source code close to his chest. (And I totally understand why, given that it’s his livelihood!)</p><p>Like any red-blooded programmer, my next thought was “Well, if I can’t do it in DF, I could write something myself and try it out there.” That lead to a lot of additional thoughts about the mechanics of NPC AIs, and so on, and so forth. I won’t go into those bits for now, because I’m still a good distance from implementing any AIs at all.</p><p>After a long and harrowing journey through the web reading about procedural content generation, I came to the following plan:</p><p>I will write some kind of roguelike that is played on the surface of a sphere. The sphere’s high-level terrain will be generated using “naturalistic” means—that is to say, techniques that use global knowledge of the map to create terrain that looks a bit more natural than a simple fractal height-map. At the low-level, terrain detail in the “gaps” between the high-level features will be filled in using fractal noise techniques.</p><p>To put it a different way: I want to produce continents (or “pseudo-continents” on a smaller sphere) in a way that makes them look like actual continents. Then, I want the player to play on a map at person scale, and in order to do that I need a system that doesn’t actually generate all of the terrain ahead of time. Why? Because the whole map at person scale would be <i>huge</i>. It would be too slow to generate it all at once, and also too massive for players to want to keep around.</p><p>Before I get started describing what I’ve done (and eventually, what I’m doing), I wanted to credit the major projects that I’ve been using for inspiration:</p><ul><li><a href="http://www.bay12games.com/dwarves/">Dwarf Fortress</a>, the mother of all “world-building” roguelikes. Or “fortlikes”, if you would.</li><li><a href="http://minecraft.net/">Minecraft</a>, which got me thinking about dynamic generation and "building" games from the point of view of a single character (instead of planning with an entourage of characters.)</li><li><a href="http://www.dungeonleague.com/">Dungeon League</a>, a great development blog that gave me the idea to work with a spherical world, and enough details to figure out how to do it right.</li><li><a href="http://doryen.eptalys.net/">The Chronicles of Doryen</a>, which spawned the fantastic <a href="http://doryen.eptalys.net/libtcod/">libtcod</a> library for building roguelikes. I’m not going to be using it myself, but its capabilities have given me a lot of ideas for how to do more advanced rendering without totally leaving the roguelike mold.</li></ul>J. Prevostnoreply@blogger.com0