http://roguetemple.com/z/hyper/dev.php @ Zeno Rogue Games @ Vapors of Insanity @ Necklace of the Eye @ Hydra Slayer @ [ HyperRogue ] @ Untahris @ @ About @ Downloads @ Gallery of Lands @ FAQ @ Models @ Geometries @ Curves @ [ Programming ] @ RogueViz @ Images & Videos @ History & Naming & Credits @ press @ hyperrogue-imagepluslogo.png How to create a game using hyperbolic geometry? If you would like to know how HyperRogue is implemented -- whether you are a game developer who wants to create their own, or a mathematician who wants to know how this was done -- this subpage is for you. How to represent the continuous hyperbolic geometry It is common to use the Poincare disk model to explain hyperbolic geometry; this is also the projection used by default in HyperRogue. However, for computational purposes, Minkowski hyperboloid model is usually better and more natural. The Minkowski hyperboloid model makes hyperbolic geometry obvious! Well, of course this is a bit of exaggeration, but not by much: based on the Minkowski hyperboloid model, I have been able to find out all the formulas necessary to create a hyperbolic game with general geometric intuitions, and almost no knowledge of hyperbolic or spherical geometry in particular. This section is a simple description of this approach. You will need the following knowledge: * The Cartesian coordinate system, and basic trigonometry. * The basics of linear algebra: vectors, linear combinations, linear transformations (matrices), and the inner product. * Homogeneous coordinates. This means we add an extra coordinate which equals 1 (for the points in our space): instead of $(x,y,z) $, we have $(x,y,z,1)$. This approach is used in 3D graphics libraries, as it allows both translations and rotations to be represented as (4x4) matrices. * Minkowski geometry. This is the only thing that is not taught in school or early years of maths/CS programs. The Minkowski geometry is most commonly used to model the spacetime in the Special Relativity theory. For simplicity consider one space dimension ($x$) and one time dimension ($t$). Contrary to the two-dimensional Euclidean space, these dimensions are not equivalent. A point with coordinates $ (x,t)$ (in distance $x$ from us at time $t$) according to one observer will have other coordinates $(x',t')$ according to another observer who was at the same point at time 0, but then was moving with a constant speed; it is clear that $x \neq x'$, but according to the Special Relativity theory, also $t \neq t'$. The transformation from $(x,t)$ to $(x',t')$ is called a Lorentz transformation, and is the Minkowski analog of Euclidean rotation. The inner product of $(x,t)$ and $(x',t')$ is given by $tt'-xx'$; Lorentz transformations do not change this, just like Euclidean rotations do not change the usual inner product. The analog of the "unit circle" is the set of points $t^2-x^2=1$; this is a hyperbola, and can be given by $x=\sinh \alpha$, $t=\ cosh \alpha$, just like the Euclidean circle is given by $\sin$ and $\cos$. The first three bullets are essential to deal with the spherical geometry, and Minkowski geometry will be necessary to find the hyperbolic analogs. To see how to deal with the spherical geometry, try to answer the following questions about points on the unit sphere $\{(x,y,z): x^2+y^2+z^2=1\}$: * Given a point $(x,y,z)$ on the unit sphere, how can you rotate it by angle $\alpha$ around the axis Y? (Just like in the usual homogeneous coordinates, we consider $ (0,0,1)$ to be the origin. This rotation operation is the spherical analog of translation by $\alpha$ along the $x$ axis.) * Given two points $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$ (always on the sphere), how can you find the midpoint? (Hint: this will be a linear combination of these points.) * Given two points $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$, how can you compute the spherical distance between them? (Hint: There are two ways. One involves computing the distance in $\mathbb{R}^3$ and then finding the angle based on that. The other is based on the inner product of the two points.) * Given two points $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$, how can you compute the tangent vector at $(x_1,y_1,z_1)$ pointing at $ (x_2,y_2,z_2)$? (Hint: a linear combination.) * What is the circumference of a spherical circle of radius $r$? * Given a point $p=(x,y,z)$ on a sphere and a tangent vector $t$ at (x,y,z), where do we get if we follow this tangent vector for a steps, and what will be the tangent vector there? (Hint: this should be easy for $p=(0,0,1)$ and $t=(1,0,0)$. Write this as a linear combination of $p$ and $t$, and the general formula will be the same.) * Given a point $(x_1,y_1,z_1)$, how can you find the isometry which takes $(x_1,y_1,z_1)$ to $(0,0,1)$ and does not do any extra rotation? (This is a bit harder. You could decompose it into simpler isometries, or (better) think in terms of linear combinations.) * How does the Pythagorean Theorem work in spherical geometry? What about the cosine rule? (Hint: this should be an easy corollary of translations and computing distances (first and second bullet).) * Given a point $(x_1,y_1,z_1)$, what is its distance from the great circle $y=0$? * The stereographic projection is a convenient two-dimensional projection of the sphere. This projection keeps angles, and maps circles to circles. The point $(x,y,z)$ is projected to $ (x',y',1)$ in such a way that $(x,y,z)$, $(x',y',1)$ and $ (0,0,-1)$ are colinear. What are $x'$ and $y'$? This should be enough to make a simple game in spherical geometry (move the camera, draw objects in the stereographic projection, etc.) Now, the Minkowski hyperboloid is basically a unit sphere in Minkowski geometry (or, you could also view it as a sphere of imaginary radius). Just like the usual sphere is $\{(x,y,z):x^2+y^2+z ^2=1\}$, the Minkowski hyperboloid is $\{(x,y,t):t^2-x^2-y^2=1, t>0\} $. Every formula or fact we have found above about the sphere, has a direct analog in hyperbolic geometry (based on the Minkowski hyperboloid model). The general rule is that sin and cos change to sinh and cosh if the argument represents distance (a above is actually a distance); some signs will change but are easy to guess. So translation of $(x,y,t)$ by $\alpha$ will be $(\cosh\alpha \cdot x + \sinh \alpha \cdot t, y, \cosh\alpha \cdot t + \sinh \alpha \cdot x)$; isometries will keep the Minkowski inner product; the midpoint of $h_1$ and $h_2$ will be $h_1+h_2$ normalized; the Poincare disk model is the stereographic projection of the hyperboloid; and so on. (Note: This is for the hyperbolic plane, but everything is exactly the same in higher dimensions. See also this writeup for a quick reference of the basic formulas, and some pictures.) How to represent tessellations Unfortunately, the Minkowski hyperboloid model alone is not sufficient if you want to make a game with a large world. Because the hyperbolic space grows exponentially, any representation based on a bunch of floating point values will lose precision completely and amazingly quickly. Whether you are making a grid-based game or a world with diameter of more than 40 absolute units or so, tessellations are essential. To represent the map, every cell is represented by an object; this object has a list of pointers to its all adjacent cells, in counterclockwise order. If $c_2$ is the $i$-th neighbor of cell $c_1$, cell $c_1$ also remembers which neighbor of $c_2$ it is, and in case of non-orientable manifolds, whether this edge is "mirrored" (i.e., the native orientations of $c_1$ and $c_2$ are opposite). This general system works perfectly for all 2D manifolds. For 3D manifolds, the system is similar, except that "counterclockwise" order loses its meaning. So the neighbors are now in more arbitrary order, and algorithms relying on the counterclockwise order have to be implemented in a different way. One useful abstraction used in HyperRogue is that of a walker -- i.e., an object that is currently in the specific cell, and facing in some specific direction, and whether it is currently "mirrored" relatively to the cell's native orientation. A walker can be moved forward, rotated (by $i$ edges), and mirrored. Based on the tessellation described above, a walker is easy to implement. Note that this discrete representation is orthogonal to the Minkowski hyperboloid representation. (Maybe it would be possible to encode heptagons with their Minkowski coordinates, but the rounding errors would destroy this solution once you got far enough from the starting point -- when encoding them as three long doubles, there would be less than $2^{240}$ coordinates possible, and there are more cells than that in radius 400, so some nearby cells at that distance (actually, probably much sooner) would basically crash into each other due to rounding.) In HyperRogue, the game mechanics, including procedural generation are done (almost) completely using the tessellation, without taking the continuous form into account. Hyperbolic heptagonal grid It is of course impossible to store the whole HyperRogue map in memory -- it contains over \(10^{7000}\) cells! Instead, the map is generated lazily: when the game asks for a neighbor of cell $c$, it checks whether it already knows that neighbor -- if no, that cell is created and linked. We start to explain the implementation of the heptagonal grid first. Every heptagon receives an unique path which leads to it. Paths leading to each heptagon form a tree, as follows: [underlying] [underlying] The underlying tree in {7,3} and {5,4}. (Click to zoom; play interactively here {7,3} or here {5,4}) (You can play with this picture to see how it behaves further from the origin. This tree can be seen from the game by: special modes -> experiment with geometry -> patterns -> line patterns -> underlying tree. Since it could be used for cheating, enabling it also enables the cheat mode. If the cheat mode is enabled, you can also use the Ctrl+W hotkey.) Each heptagon is then uniquely identified by a sequence of numbers which says where to turn at each intersection, starting from the origin point. There are relatively simple rules which say how to do this: if you start at the heptagon with code $a_1, a_2, \ldots, a_k$, are facing $d$ to the right from the path to the origin, and go forwards, we can easily calculate the code of the target heptagon, and the index of the direction we are coming from. In most cases you simply create children in the tree, in other cases you go back a few steps, query the parent, and go from there. This tree-based approach works well with other regular 3-valent, 4-valent or $\infty$-valent tessellations, such as {5,4} (pictured above), the binary tiling, or $\{3,\infty\}$ (just a binary tree). Other valences and less regular tessellations may be more tricky, see this paper for a general approach to generating and using tree structures for arbitrary periodic tessellations. See also this for the three-dimensional case. Bitruncation [underlying] (click to zoom; play interactively here) The default HyperRogue map is obtained by applying bitruncation to the tessellation above. While a similar tree structure can be found for the bitruncated tessellation, we just bitruncate the {7,3} structure. How to display the world The Poincare disk model (and other general perspective projections) is obtained from the hyperboloid model by projecting from the point (0,0,-1). This lets us display the HyperRogue world in a straightforward way even in the most basic OpenGL. To display other projections, or 3D worlds, we need to write a vertex shader (to map the Minkowski coordinates to screen coordinates). Every cell has its internal Minkowski coordinate system. We also uses the function adj($c,i$), which returns the isometry which maps the internal coordinates of the i-th neighbor of cell $c$, to the internal coordinates of cell $c$. This adj can be computed quite easily by multiplying the matrices of the necessary rotations and shifts. The current camera position is represented by the cell $c_0$ (the cell under the camera) and a matrix $V$ which maps the internal coordinates to the screen coordinates. This allows us to draw the cell $c_0$, and by applying adj recursively, also all the nearby cells. We take care to draw every cell just once (except in quotient spaces). When the camera moves, the view is "optimized" by changing $c_0$ to the new cell under the camera, and adjusting $V$ accordingly; this can be also done easily using adj. Continuous game mechanics For continuous game mechanics (i.e., the shmup mode and the racing mode in HyperRogue, movement animations, etc.), every object remembers the discrete cell it is on, and a transformation matrix (at) to map from that cell's internal coordinates to object's model coordinates. This two-layer relative approach allows us to do precise calculations on the region of hyperbolic plane around the player, and at the same time do not lose precision for the monsters which are very far from the location of the player (such monsters do not act, and their at will simply be still valid when they get back into the sight range). Other complex stuff The above topics cover the basics of making a hyperbolic game. Implementing HyperRogue also required devising lots of innovative algorithms for its procedural generation, and representation of other grids and geometries. Here we explain these algorithms briefly. Land generation The above explains how to lazily generate the map, but how to fill it with content? This is done as follows: every cell remembers a value (called mpdist) which tracks the progress of generation of that cell. The name mpdist stands for "minimum player distance": cells where the player has been have mpdist of 0, adjacent cells have mpdist 1, and so on. In default HyperRogue settings, cells with mpdist <= 7 (the visible ones) are fully generated; the world is also partially generated in a slightly bigger radius (10, or 9 for the Android version to reduce the memory), as this is necessary in some cases. The land generation function setdist$(c,d)$ is called when a more precise generation is required for $c$ (as given by $d$); setdist recursively calls itself for the neighbors of $c$, with $d$+1. For example, the land generation algorithm for Icy Land works as follows: for each cell c, with some (low) probability, place Ice Walls on c and some of the cells in distance at most 2 around it. The random check is done for each cell once they are at distance 9 from the player -- this way, Ice Walls in the player's sight range (7) will all be already generated, and since everything is done symmetrically, it is impossible to tell from which direction the player came by looking at the map. Patterns include the Zebra and Palace pattern, which are used by the map generation in some lands. Generally, each heptagon gets a code which uniquely determines its place in the pattern, and how it is rotated. As more heptagons are generated, codes for the previous ones are checked, and codes for the new ones are determined uniquely, according to a table. Different patterns have slightly different algorithms. Great Walls are created when the game finds out that a Great Wall fits in the already generated area, and are automatically extended into the yet ungenerated part of the world when you get close to them. Equidistants are generated basically by calculating the distance to the Great Wall, based on the already calculated distances of the nearby cells. Big circles (Camelot) are generated by creating another alternate map, whose cells correspond to the cells of the original map, but centered in a different location. Original heptagons get a link (alt) to the counterpart in this alternate map. Again, as the world is generated, and we are not too far away from the circle, alt links are calculated for the nearby heptagons, based on the links for the old ones. This alternate network allows HyperRogue to calculate the distance to the alternate center, and generate terrain based on that. The same is used for horocycles, except that a slightly different underlying tree is used -- it is not rooted in a specific point, it has an infinite trunk instead. The underlying tree of the alternate map can be also viewed in-game, in the same way as the main underlying tree. For calculating the electric currents in the Land of Storms, the Tarjan-Hopcroft algorithm for finding biconnected components has been adapted :) Fractal landscapes are used to generate chasms in the Dragon Chasms and Reptiles, rock lines in Trollheim, and (after some modification) Galapagos. We generate a function f from the set of all tiles to integers $\mathbb{Z}$ ($\mathbb{Z}^3$ for the rainbow landscape, $\ mathbb{Z}_2^21$ for Galapagos, etc.). A delta (+1 or -1) is randomly chosen for every Great Wall-style straight line. For a heptagonal tile t, f(t) is computed as the sum of deltas for all lines between t and the starting point, or in other words, if we already know (f(t') for the parent of t in our tree, we add deltas for the two straight lines between t and t'. The fractal landscape generated by this algorithm is uniform: it is impossible to tell where we are if we know the relative value of f for the cells around us (by relative we mean f(t)-f(t[0]), where t[0] is the cell we are on). Other geometries and tessellations All geometries, from 2D to non-isotropic 3D geometries, use the same set of abstract geometric routines, which work correctly in all geometries. All the geometries supported by HyperRogue can be represented using points in 3D or 4D space, with isometries being linear transformations. See this paper for more details. Tree structures described above work for most 3-valent and 4-valent tessellations (including the regular ones, and variants of the binary tiling), as well as the Penrose kite-and-dart tiling (which is basically a $\mathbb{H}^3$ tessellation constructed using a similar tree structure, restricted to a horosphere); for Euclidean or Nil tessellations, we can just use the coordinates, and Sol geometry uses two tree structures. However, for tessellations loaded from files, Archimedean tessellations, or 3D honeycombs, constructing tree structures is more tricky. It can be done (probably), but it requires significant research. In some cases HyperRogue uses a significantly less elegant, but simpler approach. The cells are identified by their Minkowski coordinates; when asking for a neighbor, we compute the expected coordinate of its center, and look whether there is already a cell on that center -- if no, we create it, if yes, we link the already existing cell. While this approach works perfectly for spherical geometry, it does not work in large-scale hyperbolic geometry because of precision issues. This is avoided by constructing another mapping tessellation, for which a tree structure is known (e.g., {7,3} in 2D and binary tiling in 3D), and cells are identified by thier positions relative to this mapping tessellation (in a similar way as described in the "continuous game mechanics" section above). (Tree structures are implemented for some 3D honeycombs, but they turn out to be quite complex.) Implementation See the source code and the (incomplete) code documentation for implemetation details. Unfortunately it might be somehow hard to read at times, because of lacking documentation and the amount of special cases (because of all the geometries and tessellations supported); earlier versions have less special cases, although they sometimes use less general and less elegant solutions. The most relevant files are: * In hyperpoint.cpp the basic continuous geometry is defined, using structs hyperpoint (a point in the continuous space) and transmatrix (a matrix, used for isometries and other things). * In location.cpp, the struct cell is used for cells, and cellwalker for cell walkers (as the name suggests). The analogous structs heptagon and heptspin are used for the underlying heptagonal grid (this was a good design when bitruncated {7,3} was the only map supported, but I do not think it is a very good design anymore now when all kinds of maps are supported; in other tessellations heptagons are not heptagonal, but the name stuck). * heptagon.cpp implements the heptagonal grid * cell.cpp implements various things related to cells * geometry.cpp computes the basic geometric properties of the current tilings (such as the edge length) * geometry2.cpp uses these to implement the adj function * hypgraph.cpp has various other useful functions regarding optimizing, camera movement, etc. Summary If you want to create a game taking in the continuous hyperbolic space, I recommend using the Minkowski hyperboloid model internally, and the Poincare disk model display, just as HyperRogue does. (In 2D of course, in 3D/VR perspective is more relevant, though Poincare disk is still cool.) As the shmup section shows, the tesselation might be useful too, to help with the precision of local computations. Use hyperpoint.cpp, or write your own. If you want to create a game on the same grid (tesselation) as used by HyperRogue, you only need to understand how to access the tesselation structure using the cell and cellwalker objects, and then change the game files to implement the game mechanics; you do not need to look at the geometry implementations. See here for more guidance. @ Donate @ Project Blog @ Twitter @ Discord @ Discuss @ Tweet Thanks to Slashie for hosting this at RogueTemple! @ Zeno Rogue Games @ Vapors of Insanity @ Necklace of the Eye @ Hydra Slayer @ [ HyperRogue ] @ Untahris @ @ About @ Downloads @ Gallery of Lands @ FAQ @ Models @ Geometries @ Curves @ [ Programming ] @ RogueViz @ Images & Videos @ History & Naming & Credits @ press @