@ Zeno Rogue Games @ Vapors of Insanity @ Necklace of the Eye @ Hydra Slayer @ [ HyperRogue ] @ Untahris @
@ About @ Downloads @ FAQ @ Gallery of Lands @ Images & Videos @ History & Naming & Credits @ [ Programming ] @ RogueViz @
 


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. It just gives some basics, look at the source for details.

Modules in HyperRogue

Each module has a corresponding *.cpp file.

hyperpoint

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+y2+z2=1 (basically, points in the three-dimensional space which fall on the sphere), and to move, instead of simply adding values to the x and y coordinates, you rotate the sphere using the sin and cos functions. The Minkowski hyperboloid is similar, but now, we use points on the hyperboloid (x2+y2-z2=-1), 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 sqrt(x2+y2-z2) instead of the Euclidean one sqrt(x2+y2+z2).

heptagon

This file implements the underlying heptagonal tesselation.

Two structures are exported: heptagon 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.)

cell

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.

geometry

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.

game, classes

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.

graph, polygons

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.

patterns

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.

shmup

This module implements the shoot'em up mode. Each object (monster) in the shoot'em up mode knows what cell it is on (baseat). 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 cells.

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).

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. 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.