HyperRogue - Programming
source link: http://roguetemple.com/z/hyper/dev.php
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 Poincaré 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)(x,y,z), we have (x,y,z,1)(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 (xx) and one time dimension (tt). Contrary to the two-dimensional Euclidean space, these dimensions are not equivalent. A point with coordinates (x,t)(x,t) (in distance xx from us at time tt) according to one observer will have other coordinates (x′,t′)(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≠x′x≠x′, but according to the Special Relativity theory, also t≠t′t≠t′.
The transformation from (x,t)(x,t) to (x′,t′)(x′,t′) is called a Lorentz transformation, and is the Minkowski analog of Euclidean rotation. The inner product of (x,t)(x,t) and (x′,t′)(x′,t′) is given by tt′−xx′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 t2−x2=1t2−x2=1; this is a hyperbola, and can be given by x=sinhαx=sinhα, t=coshαt=coshα, just like the Euclidean circle is given by sinsin and coscos.
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):x2+y2+z2=1}{(x,y,z):x2+y2+z2=1}:
- Given a point (x,y,z)(x,y,z) on the unit sphere, how can you rotate it by angle αα around the axis Y?
(Just like in the usual homogeneous coordinates, we consider (0,0,1)(0,0,1) to be the origin. This rotation operation is the spherical analog of translation by αα along the xx axis.) -
Given two points (x1,y1,z1)(x1,y1,z1) and (x2,y2,z2)(x2,y2,z2) (always on the sphere), how can you find the midpoint?
(Hint: this will be a linear combination of these points.) -
Given two points (x1,y1,z1)(x1,y1,z1) and (x2,y2,z2)(x2,y2,z2), how can you compute the spherical distance between them?
(Hint: There are two ways. One involves computing the distance in R3R3 and then finding the angle based on that. The other is based on the inner product of the two points.) -
Given two points (x1,y1,z1)(x1,y1,z1) and (x2,y2,z2)(x2,y2,z2), how can you compute the tangent vector at (x1,y1,z1)(x1,y1,z1) pointing at (x2,y2,z2)(x2,y2,z2)?
(Hint: a linear combination.) - What is the circumference of a spherical circle of radius rr?
- Given a point p=(x,y,z)p=(x,y,z) on a sphere and a tangent vector tt at (x,y,z), where do we get if we follow this tangent vector for α steps, and what will be the tangent vector there?
(Hint: this should be easy for p=(0,0,1)p=(0,0,1) and t=(1,0,0)t=(1,0,0). Write this as a linear combination of pp and tt, and the general formula will be the same.) -
Given a point (x1,y1,z1)(x1,y1,z1), how can you find the isometry which takes (x1,y1,z1)(x1,y1,z1) to (0,0,1)(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 (x1,y1,z1)(x1,y1,z1), what is its distance from the great circle y=0y=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)(x,y,z) is projected to (x′,y′,1)(x′,y′,1) in such a way that (x,y,z)(x,y,z), (x′,y′,1)(x′,y′,1) and (0,0,−1)(0,0,−1) are colinear. What are x′x′ and y′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):x2+y2+z2=1}{(x,y,z):x2+y2+z2=1}, the Minkowski hyperboloid is {(x,y,t):t2−x2−y2=1,t>0}{(x,y,t):t2−x2−y2=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 (α above is actually a distance); some signs will
change but are easy to guess. So translation of (x,y,t)(x,y,t) by αα will be (coshα⋅x+sinhα⋅t,y,coshα⋅t+sinhα⋅x)(coshα⋅x+sinhα⋅t,y,coshα⋅t+sinhα⋅x);
isometries will keep the Minkowski inner product; the midpoint of h1h1 and h2h2 will be h1+h2h1+h2 normalized; the Poincaré 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 c2c2 is the ii-th neighbor of cell c1c1,
cell c1c1 also remembers which neighbor of c2c2 it is, and in case of non-orientable manifolds, whether this edge is "mirrored"
(i.e., the native orientations of c1c1 and c2c2 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 ii 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 22402240 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 107000107000 cells! Instead, the map is generated lazily: when the game asks for
a neighbor of cell cc, 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:
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 a1,a2,…,aka1,a2,…,ak, are facing dd 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 ∞∞-valent tessellations, such as {5,4} (pictured above),
the binary tiling, or {3,∞}{3,∞} (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
(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 Poincaré 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,ic,i), which returns the
isometry which maps the internal coordinates of the i-th neighbor of cell cc, to
the internal coordinates of cell cc. 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 c0c0 (the cell under the camera) and a matrix VV which maps the internal coordinates
to the screen coordinates. This allows us to draw the cell c0c0, 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 c0c0 to the new
cell under the camera, and adjusting VV 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)(c,d) is called when a more precise generation is required for cc (as given by dd); setdist recursively calls itself for the neighbors of cc, with dd+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) Galápagos. We generate a function
f from the set of all tiles to integers ZZ (Z3Z3 for the rainbow landscape,
Z221Z221 for Galápagos, 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(t0), where
t0 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 H3H3 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 Poincaré disk model display,
just as HyperRogue does. (In 2D of course, in 3D/VR perspective is more relevant,
though Poincaré 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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK