Flowsnake: space-filling curve for honeycombs

Gosper curve of length 7^21
Gosper island of depth 21 (large version).

Introduction

The Flowsnake library implements a pair of conversion routines, which can be used to translate between X/Y coordinates on a 2D hex map and indices on the Gosper space-filling curve. Both functions run in O(log n) time, where n denotes the number of cells within the curve. The author is not aware of any previously existing implementations satisfying this bound.

Because the X/Y axes have to fit in 32 bits and the index on the curve in 64 bits, n is set to 7^21 = 558545864083284007. Because the curve indices have been adjusted to translate position (0, 0) to curve index 0, the index can have any value between −209454699031231502 and 349091165052052504.

In addition to the Gosper curve, the library also implements two additional space-filling curves for hexagonal grids. One of these is an Alternating Gosper curve, which provides a rotation-free tiling by applying two Gosper tilings in inverse order. The other is the Marita curve, which uses the same tiling, but uses a different curve, where position (0, 0) is placed exactly on the middle of the curve. These curves provide better conversion performance, since they use a bigger tiling, thus less levels of depth.

A typical application of such a set of mapping routines could for example be a game, where a player is spawned at point (0, 0). As the player moves through the terrain, parts of the map have to be loaded from disk. Because the Gosper curve provides good locality, this can be done more I/O efficiently compared to naive approaches, such as row-major order.

Terrain model

Each cell on the honeycomb has six neighbours, unlike a regular 2D grid which has four direct and four indirect neighbours. Because Flowsnake only works with integer coordinates, the Y direction is stretched by a factor √3. Therefore, grid cell p has the following neighbours:

Therefore even rows may only use even columns and odd rows may only use odd columns.

The API

Flowsnake provides the following API:

#include <flowsnake.h>

int
gosper_itoxy(fsidx_t i, fsdim_t *x, fsdim_t *y);

int
gosper_xytoi(fsdim_t x, fsdim_t y, fsidx_t *i);

The gosper_itoxy() function maps curve index i to the point having coordinates (x, y).

The gosper_xytoi() function maps the point having coordinates (x, y) to curve index i.

Both functions return 0 on success. They may return −1 if the curve index or the point are not part of the Gosper curve having depth 21, or if the provided coordinates do not satisfy the terrain model.

Obtaining Flowsnake

The latest version of Flowsnake is 0.1. It can be obtained from the distfiles directory.

The latest source code can be checked out from Git as follows:

git clone git://git.80386.nl/flowsnake

The source code can also be viewed online.

The author

Flowsnake is written by Ed Schouten. He can be reached by email at <ed@80386.nl>.

Last modified: Wed Aug 3 11:10:06 2011 +0200