Creating a hexagonal wraparound map

Question

I'm trying to create a wraparound map for a hexagonal map, so when you exit a tile on one side of the big hexagon-shaped map, you enter a tile on the other side.

Example image from Red Blob Games article on Hexagonal Grids.

In the image, the pale tan hexagonal chunk in the center is our map. The greenish/reddish chunks around it are shifted copies of the same map. If we stand on the blue tile under the cursor and walk off the main map into the green copy to the right, that's the same as wrapping around our map to the corresponding point on the other side: here, walking from the blue tile in the lower-right-hand red copy into the bottom-right corner of the center map.

I used an approach with a lookup table first. But as soon as those maps get too big, the lookup tables get even bigger. I'm searching for a solution which works without a lookup table.

Answer 1

Here's a simple method which does not become more complex as the map grows in radius:

1. Keep a list of the center coordinates of your main map (0, 0, 0), and its 6 shifted copies.

2. After a move that might take you off the edge of the map, calculate the distance to your destination tile from each of these center points.

3. Stop when you find a center point whose distance away is less than or equal to your map radius.

4. Subtract this center point from your destination point. Now your destination is correctly expressed as an offset from the center of your original map (0, 0, 0).

Implemented directly, this is at most 7 distance checks, no matter how big your map gets.

But, if your distance from the original center is less than your map radius, you can skip the other checks entirely, since you haven't crossed an edge.

Answer 2

Here's a demo of a wraparound hexagonal map. Use the QWEASD keys to move around:

const size = 20;
const dx   = size * 3 / 2;
const dy   = size * Math.sqrt(3);

const radius   = 3;
const diameter = 2 * radius;

const canvas  = document.createElement("canvas");
const width   = canvas.width  = diameter * dx;
const height  = canvas.height = diameter * dy;
const context = canvas.getContext("2d");

const y_axis  = 3 * radius - 2;
const length  = radius ** 3 - (radius - 1) ** 3;
const coords  = Array.from({ length }, coordOf);

const colors  = ["#E6A86E", "#FFCD9E", "#CF8846"];

var player = 0;

document.body.appendChild(canvas);

document.body.addEventListener("keypress", keypress);

draw(player);

function coordOf(_, i) {
    const [x, y, z] = toCoords(i);
    return [ width / 2 + (x - y) * dx
           , height / 2 + (z - (x + y) / 2) * dy];
}

function toCoords(i) {
    const coords = getCoords(i, 0, 0);
    return Math.max.apply(Math, coords) < radius ?
        coords : getCoords(i - length, 0, 0);
}

function getCoords(x, y, z) {
    return x < 0 ? getCoords(x + y_axis + 1, y, z + 1) :
        x < radius ? [x, y, z] : getCoords(x - y_axis, y + 1, z);
}

function keypress(event) {
    const y = y_axis, z = y + 1;

    switch (event.key) {
    case "q": player += y; break;
    case "w": player += z; break;
    case "e": player += 1; break;
    case "a": player -= 1; break;
    case "s": player -= z; break;
    case "d": player -= y; break;
    }

    if (player < 0) player += length;
    else player %= length;
    draw(player);
}

function draw(player) {
    const [x, y] = coords[player];
    context.clearRect(0, 0, width, height);
    field(width / 2, dy);
    hexagon(x, y, size / 2, "#000000");
}

function field(cx, cy) {
    for (let i = 1 - radius; i < radius; i++) {
        const j = Math.abs(i);
        const x = cx + i * dx;
        const y = cy + j * dy / 2;
        const k = diameter - j - 1;

        for (let i = 0; i < k; i++) {
            hexagon(x, y + i * dy, size, colors[(2 * i + j) % 3]);
        }
    }
}

function hexagon(x, y, size, color) {
    context.beginPath();
    context.moveTo(x + size, y);

    for (let i = 1; i < 6; i++) {
        const angle = i * Math.PI / 3;
        context.lineTo( x + Math.cos(angle) * size
                      , y + Math.sin(angle) * size );
    }

    context.closePath();
    context.fillStyle = color;
    context.fill();
}

Oftentimes in programming, choosing a suitable data structure can drastically simplify the algorithm for solving a particular problem. Your problem can be elegantly solved by vectorizing the hexagonal map as follows:

        16
    15      09
14      08      02
    07      01
06      00      13
    18      12
17      11      05
    10      04
        03

Vectorization means converting the two-dimensional hexagonal map into a one-dimensional array. The numbers in the above diagram represent the indices (of the corresponding hexagonal map cells) in the one-dimensional array. For example, the center cell of the hexagonal map is stored at index 0 in the one-dimensional array.

This representation of a hexagonal map has an important advantage. For any given cell, its six neighbors (including wraparound neighbors) are always a fixed distance away (modulo the total number of cells in the hexagonal map):

    +8
+7      +1

-1      -7
    -8

For example, the six neighbors of 0 (going counter-clockwise) are:

• 1 ≡ 0 + 1 (mod 19)
• 8 ≡ 0 + 8 (mod 19)
• 7 ≡ 0 + 7 (mod 19)
• 18 ≡ 0 - 1 (mod 19)
• 11 ≡ 0 - 8 (mod 19)
• 12 ≡ 0 - 7 (mod 19)

Note that vectorization works for hexagonal maps of any size. The above example is a hexagonal map of side length 3. It has 19 cells and its neighbors on the y-axis are 7 indices apart. These values can be obtained using the following equations:

• cells(n) = 3n² - 3n + 1
• y-axis(n) = 3n - 2

The neighbors on the x-axis are always 1 index apart and therefore the neighbors on the z-axis are always (y-axis(n) + 1) indices apart. Here are the axes for reference:

    -z
+y      +x

-x      -y
    +z

Hope that helps.

Answer 3

You can actually do a rectangular projection without wasted space in the array. This enables yo has the added benefit, that the character visually goes upwards instead of in an angle.

You can get the center of a hex with the following formula (width and height is the hexagon width and height, x and y are the current position):

centerX = x * width + (y % 2 + 1) * width / 2
centerY = y * height + height / 2

If you have a map with the width n and height m, then every hexagon on the left side will have the x coordinate 0, on the right side the x coordinate n, in the top row they'll have a y coordinate 0 and and on the bottom a y coordinate m.

This also means the four corners are (0; 0), (0; m), (n, 0), (n, m).

So, to achieve a wrapping effect, you need to check if the x coordinate of the player is bigger than n, and if it is, then set it to 0, if it's smaller than 0, then set it ton, if the y coordinate is smaller than 0, then set it to m and if it's bigger than m, than set it to 0.

In code:

if (x < 0) x = n;
if (x >= n) x = 0;
if (y < 0) y = m;
if (y >= m) y = 0;