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. It just gives
some basics, look at the source for details.
Modules in HyperRogue
Each module has a corresponding *.cpp
This file implements the underlying continuous hyperbolic geometry. Lots of vectors,
matrices, and math there.
Technically, the game displays the world in the
Poincaré disk model
, but the
Minkowski hyperboloid model
is used for internal calculations.
Basically, if you wrote a game on a sphere, you would probably encode each point
with three coordinates (x,y,z
) such that x2
(basically, points in the three-dimensional space which fall on the sphere), and
to move, instead of simply adding values to the x
the sphere using the sin
functions. The Minkowski hyperboloid is
similar, but now, we use points on the hyperboloid (x2
and rotate them using the hyperbolic sine and hyperbolic cosine functions
(but still use the normal sin and cos for spinning around the Z axis).
Note that to get the approximate
distance between points on the hyperboloid, you should use the Minkowski metric
) instead of the
Euclidean one sqrt(x2
This file implements the underlying heptagonal tesselation.
Two structures are
which represents a heptagon, and heptspin
which is used to walk through the network (it remembers the current heptagon
and the current facing direction; you can "spin" it to change the facing direction
by i clockwise, or "step" it to move forward and face the i-th neighbor of
that heptagon, where 0-th is the original one.
Technically, each heptagon receives an unique path which leads to it. Paths leading to each
heptagon form a tree, as follows:
(click to zoom)
You can play with this picture, and see how it behaves further from the origin, by
pressing Ctrl+W several times in the cheat mode.
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 implement the heptspin, that is, if you
start at the heptagon with code a1, a2, ..., ak, 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.
Note that this does not use 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 2240 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.)
This file implements the hyperbolic soccerball tesselation which is
actually used by HyperRogue.
The tesselation is built on top of the heptagonal tesselation built by heptagon.
Structures cell and cellwalker are implemented, which works just like
the heptagon and heptspin structures from heptagon, but
they work on cells instead. Nothing really exciting here.
This implements/calculates some mathematical constants (edge lengths and such)
and objects (matrices) which show how the tesselations relate to the Minkowski
hyperboloid. Nothing really interesting here.
All the game mechanics is implemented here.
This uses the cell and cellwalker structures heavily. Neither
heptagons nor the underlying Minkowski hyperboloid are used directly.
classes.cpp contains all the structures, enumerations, and tables, while
game.cpp contains the actual implementation of the mechanics.
This module implements all the graphics and GUI.
The game world, as described by game and classes, is displayed
using the hyperboloid model from hyperpoint. Note that the "rotations" used
in the hyperboloid model, even though they are not real rotations, still can be
handled by OpenGL! :) This allows us to use the usual methods for accelerating graphics.
This module implements periodic patterns.
This file implements some rules for generating periodic patterns (like the Zebra
or Palace pattern -- play with the Map Editor to get the idea). 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.
This module implements the shoot'em up mode.
Each object (monster) in the shoot'em up mode knows what cell it is on
For all the cells c in the sight range, gmatrix[c] is calculated,
containing its placement relative to the current center of the screen -- thus, each
monster's coordinates relative to the center of the screen can be calculated as
gmatrix[base] * at * C0. 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 (and thus they do not act, and their at will simply be still
valid when they get back into the sight range).
Other complex stuff
For most monsters and items, it is sufficient to generate them when they get into
the player's sight range (7), but the world is generally 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. 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.
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
Big circles (Camelot) are generated by creating another alternate network of
heptagons, and heptagons in the given part of the game world
additionally get a link (alt) to the in this network -- and 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 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.
Press Ctrl+W four times
in the cheat mode (near to horocycle/big circle) to display this alternate network.
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 Z (Z3 for the rainbow landscape,
Z221 for Galapagos). 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).
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. As te 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 game.cpp
and classes.cpp to implement the game mechanics, and graph.cpp and/or
polygons.cpp to represent your creations graphically (you need to understand
a bit about matrices for more complicated graphics). In fact, when creating
new versions of HyperRogue, I usually don't even look at the most technically
complicated files heptagon.cpp, geometry.cpp or cell.cpp.