Gosper island of depth 21 (large version).

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.

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:

*p + (0, 2)**p + (1, 1)**p + (1, −1)**p + (0, −2)**p + (−1, −1)**p + (−1, 1)*

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

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.

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.

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