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 @