## 2009/05/04

### Cell-based games and graphs. (i)

I promised myself that I'd not write about this until it was in a useful state, but there are several issues connected to it that I actually want to talk about so...

A couple of weeks ago, I started playing with the roguelike game engine that I've been meaning to write for some time. (Partly as something to do with Xcode, and partly because I realised that I could leverage existing Python libraries to handle some of the boring stuff.)

The key to this game engine being different to other Roguelike engines is in how it treats the discrete array of cells that is the gameworld. Most roguelikes use a square grid where either nsew motion, or 8-way motion is possible, purely because this is the obvious approach to the limitation imposed by a terminal style display. (Indeed, presumably this is essentially why Rogue did so, as much as the reference to RPG graph-paper maps.) However, squares are not the only regular shapes that can tile a plane, and hence hexagon-based roguelikes are possible (only two examples exist that I am aware of, one of which is a simple translation of Rogue itself), along with triangle-based games (of which I am aware of none).
More than this, however, one realises that the roguelike map is just a particularly simple lattice, and that we can thus consider other extensions of the representation than those implied by regular tilings.
For example, inspired by the fact that the hex and tri tilings are dual to each other (replace the mutual corners in each with a tile, and you get the other), we might note that "nsew" square lattices are selfdual (but contain two interleaved square lattices if we rotate our directions of movement by 45 degrees), but the 8-way lattice (which is really an "octagonal lattice", implying a hyperbolic space) is dual to a curious lattice best represented by an array of right-triangles grouped four-to-a-square, and which has even less "connectivity" than the tri lattice dual to hexagons (we will call this lattice "dual octagonal").

The dual octagonal lattice appears to be as "unconnected"* as we can easily produce for a dual tiling within the constraints of a flat representational medium; we can't represent a tiling with more than 8 neighbours in a square-tiled array, and hence we can't produce a more connected tiling than the octagonal one to be made dual to.
However, considering the representation as a lattice, which is just a special case of an undirected graph, there is one other thing we can do; we can make the graph directed. This leads us to a "loop" lattice, where each node has two "outgoing" and two "inward" edges, arranged so that adjacent nodes alternate two of their edge directions relative to the origin node. The only consistent way of arranging this produces "cycles" of four nodes, in which a path exist starting at any element of such a cycle, passing through each of the other nodes before arriving at the origin again. It can be noted that considering such "cycles" as "units", each unit is connected to four adjacent units by both "in" and "out" connections, and so the units form a lattice equivalent to the starting square lattice.
The internal loop then looks a lot like a compactified "third dimension" embedded in the 2d lattice structure. There are amusing comparisons to string theory possible here.

More problematic is the consideration of what the appropriate dual to this "loop lattice" is. Considering the "dual nodes", we swap a notion of oriented edges with a notion of "oriented nodes" themselves - the boundaries of the dual nodes are either the "loops" we previously noticed, or the "non-loops" formed by the connections between those loops.
If we examine the loop structure more carefully, we see that the chirality of the loops alternates in a checkerboard fashion - alternating clockwise and anticlockwise across the lattice.
This gives rise to the idea that the chirality of the nodes perhaps encodes a different kind of separation - is this a different encoding of some kind of three-dimensional structure, with clockwise = +1, counterclockwise = -1, and the other nodes in between?

*Or, equivalently, "positively curved" - the "circumference" of a "circle", defined in terms of the distance from a central point within the lattice constraints, is smaller for a dual octagonal lattice (being roughly 2.5*r) than it is for the tri lattice (at 3r). What I mean by connectivity is implied to be proportional to this, as the number of paths out from a given point is proportional to the length of the edge (or the area of the surface in 3d).