Hexagonal Grids

https://www.redblobgames.com/grids/hexagons/
Admin
A comprehensive guide covering hexagonal grid geometry, coordinate systems, algorithms, and...
Tokens:36,581
Snippets:313
Trust Score:9.7
Update:6 months ago
Show doc for...
Tokens:
Raw
### Generate Hexes Within Range (Inefficient)

Source: https://www.redblobgames.com/grids/hexagons-v2

This method iterates through all possible x, y, and z values within the range N and checks if they satisfy the cube coordinate constraint (x + y + z = 0). Use this as a conceptual starting point, but prefer the optimized version.

```pseudocode
var results = []
for each -N ≤ x ≤ +N:
    for each -N ≤ y ≤ +N:
        for each -N ≤ z ≤ +N:
            if x + y + z = 0:
                results.append(cube_add(center, Cube(x, y, z)))
```

--------------------------------

### Main Entry Point

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

The main method that initiates the execution of all defined tests for the hexagonal grid library.

```csharp
static public void Main()
    {
        Tests.TestAll();
    }
```

--------------------------------

### Define Orientation structure

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Stores the forward and inverse matrices along with the starting angle for hex orientations.

```cpp
struct Orientation {
    const double f0, f1, f2, f3;
    const double b0, b1, b2, b3;
    const double start_angle; // in multiples of 60°
    Orientation(double f0_, double f1_, double f2_, double f3_,
                double b0_, double b1_, double b2_, double b3_,
                double start_angle_)
    : f0(f0_), f1(f1_), f2(f2_), f3(f3_),
      b0(b0_), b1(b1_), b2(b2_), b3(b3_),
      start_angle(start_angle_) {}
};
```

--------------------------------

### Main Execution and Test Output

Source: https://www.redblobgames.com/grids/hexagons/codegen/OutputLua.hx

Initializes the Lua output generator and triggers the generation of grid code and test suites.

```Haxe
public static function main() {
        var output = new OutputLua();
        
        Sys.println('-- Generated code -- CC0 -- No Rights Reserved -- http://www.redblobgames.com/grids/hexagons/
function bitand(a, b)
    -- For lua >= 5.3 use this:
    -- return a & b
    -- For lua 5.2 and luau use this:
    return bit32.band(a, b)
end
');
        
        Output.outputAll(output.output, true);

        Sys.println('

-- Tests

function complain (name)
    print("FAIL ", name)
end
');
            
        Output.outputTests(output.output);

        Sys.println('
test_all()
');
        
    }
}
```

--------------------------------

### Hexagon Neighbor and Direction Functions

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Defines a static list of hex directions and provides functions to get a specific direction vector or a neighboring hex. The `hex_neighbor` function adds a direction vector to a given hex.

```cpp
const vector<Hex> hex_directions = {
    Hex(1, 0, -1), Hex(1, -1, 0), Hex(0, -1, 1), 
    Hex(-1, 0, 1), Hex(-1, 1, 0), Hex(0, 1, -1)
};

Hex hex_direction(int direction /* 0 to 5 */) {
    assert (0 <= direction && direction < 6);
    return hex_directions[direction];
}

Hex hex_neighbor(Hex hex, int direction) {
    return hex_add(hex, hex_direction(direction));
}
```

--------------------------------

### Test Hex Addition and Subtraction

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the Hex.Add and Hex.Subtract methods by comparing the results with expected Hex values.

```csharp
static public void TestHexArithmetic()
    {
        Tests.EqualHex("hex_add", new Hex(4, -10, 6), new Hex(1, -3, 2).Add(new Hex(3, -7, 4)));
        Tests.EqualHex("hex_subtract", new Hex(-2, 4, -2), new Hex(1, -3, 2).Subtract(new Hex(3, -7, 4)));
    }
```

--------------------------------

### Pixel to Hex Coordinates (Saevax)

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Converts pixel coordinates (x, y) to axial hex coordinates (q, r) using an algorithm by Saevax, based on the playtechs hex guide. It inlines and simplifies the code, and switches between flat-top and pointy-top orientations.

```javascript
(x, y) => {
    // Algorithm written for flat top, so switch from pointy to flat
    [x, y] = [y, x]
    
    // Algorithm from /u/Saevax on Reddit, based on playtechs
    const edge = 1
    const diameter = sqrt(3)
    const radius = diameter / 2

    let t1 = x / edge
    let t2 = y / diameter

    let r = floor( (floor(y / radius) + floor(t2 - t1) + 2 ) / 3)
    let q = floor( (floor(t1 - t2) + floor(t1 + t2) + 2 ) / 3)

    return {q: r, r: q} // Convert from flat back to pointy
}
```

--------------------------------

### Test Offset Coordinate Roundtrip Conversions

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the conversion between cube coordinates and offset coordinates (odd-q, odd-r, even-q, even-r) by converting back and forth and checking for equality.

```csharp
static public void TestOffsetRoundtrip()
    {
        for (int q = -2; q < 3; q++)
        {
            for (int r = -2; r < 3; r++)
            {
                Hex cube = new Hex(q, r, -q - r);
                Tests.EqualHex("conversion_roundtrip odd-q", cube, OffsetCoord.QoffsetToCube(OffsetCoord.ODD, OffsetCoord.QoffsetFromCube(OffsetCoord.ODD, cube)));
                Tests.EqualHex("conversion_roundtrip odd-r", cube, OffsetCoord.RoffsetToCube(OffsetCoord.ODD, OffsetCoord.RoffsetFromCube(OffsetCoord.ODD, cube)));
                Tests.EqualHex("conversion_roundtrip even-q", cube, OffsetCoord.QoffsetToCube(OffsetCoord.EVEN, OffsetCoord.QoffsetFromCube(OffsetCoord.EVEN, cube)));
                Tests.EqualHex("conversion_roundtrip even-r", cube, OffsetCoord.RoffsetToCube(OffsetCoord.EVEN, OffsetCoord.RoffsetFromCube(OffsetCoord.EVEN, cube)));
            }
        }
        for (int col = -2; col < 3; col++)
        {
            for (int row = -2; row < 3; row++)
            {
                OffsetCoord offset = new OffsetCoord(col, row);
                Tests.EqualOffsetcoord("conversion_roundtrip odd-q", offset, OffsetCoord.QoffsetFromCube(OffsetCoord.ODD, OffsetCoord.QoffsetToCube(OffsetCoord.ODD, offset)));
                Tests.EqualOffsetcoord("conversion_roundtrip odd-r", offset, OffsetCoord.RoffsetFromCube(OffsetCoord.ODD, OffsetCoord.RoffsetToCube(OffsetCoord.ODD, offset)));
            }
        }
    }
```

--------------------------------

### Layout Conversion Tests

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/Tests.java

Tests conversion between hex coordinates and pixel coordinates for both flat and pointy layouts.

```java
    static public void testLayout()
    {
        Hex h = new Hex(3, 4, -7);
        Layout flat = new Layout(Layout.flat, new Point(10.0, 15.0), new Point(35.0, 71.0));
        Tests.equalHex("layout", h, flat.pixelToHexRounded(flat.hexToPixel(h)));
        Layout pointy = new Layout(Layout.pointy, new Point(10.0, 15.0), new Point(35.0, 71.0));
        Tests.equalHex("layout", h, pointy.pixelToHexRounded(pointy.hexToPixel(h)));
    }
```

--------------------------------

### Hex Reachable (Flood Fill BFS)

Source: https://www.redblobgames.com/grids/hexagons-v2

Implements a distance-limited flood fill (Breadth-First Search) to find all reachable hexes from a starting point within a given movement limit, while respecting obstacles. `fringes[k]` stores hexes reachable in exactly `k` steps.

```pseudocode
function hex_reachable(start, movement):
    var visited = set() # set of hexes
    add start to visited
    var fringes = [] # array of arrays of hexes
    fringes.append([start])

    for each 1 < k ≤ movement:
        fringes.append([])
        for each hex in fringes[k-1]:
            for each 0 ≤ dir < 6:
                var neighbor = hex_neighbor(hex, dir)
                if neighbor not in visited and not blocked:
                    add neighbor to visited
                    fringes[k].append(neighbor)

    return visited
```

--------------------------------

### Implement Chris Cox optimized algorithm

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

An optimized version of the Chambers algorithm by Chris Cox, reducing the number of floor calls.

```javascript
(x, y) => {
    // Convert to their coordinate system
    x *= 1/sqrt(3)
    y *= -1/sqrt(3)
    // Algorithm from Charles Chambers
    // with modifications and comments by Chris Cox 2023
    // <https://gitlab.com/chriscox/hex-coordinates>
    let t = sqrt(3) * y + 1         // scaled y, plus phase
    let temp1 = floor( t + x )      // (y+x) diagonal, this calc needs floor
    let temp2 = ( t - x )           // (y-x) diagonal, no floor needed
    let temp3 = ( 2 * x + 1 )       // scaled horizontal, no floor needed, needs +1 to get correct phase
    let qf = (temp1 + temp3) / 3.0  // pseudo x with fraction
    let rf = (temp1 + temp2) / 3.0  // pseudo y with fraction
    let q = floor(qf)               // pseudo x, quantized and thus requires floor
    let r = floor(rf)               // pseudo y, quantized and thus requires floor
    return {q, r: -r}
}
```

--------------------------------

### Implement Kenneth Shaw algorithm

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

A simplified version of the Chambers algorithm provided by Kenneth Shaw.

```javascript
(x, y) => {
    // Make the coordinates match my grid
    x = x / sqrt(3)
    y = y + 1
    // Algorithm from Kenneth Shaw posted in a comment 2013
    // <https://www.redblobgames.com/grids/hexagons/#comment-1063818420>
    // but I'm using x,y whereas he is using x,z
    let t1 = y
    let t2 = floor(x + y)
    let r = floor((floor(t1 - x) + t2) / 3)
    let q = floor((floor(2 * x + 1) + t2) / 3) - r
    return {q, r}
}
```

--------------------------------

### C++ Vector Initialization Pattern

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Standard approach for initializing nested vectors based on loop bounds.

```cpp
vector<vector<T>> map(a2-a1);
for (int a = a1; a < a2; a++) {
    map.emplace_back(b2-b1);
}
```

```cpp
int height = bottom - top + 1;
vector<vector<T>> map(height);
for (int r = 0; r < height; r++) {
    int width = right - left + 1;
    map.emplace_back(width);
}
```

--------------------------------

### Test Hex Layout Conversion

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the conversion between Hex coordinates and pixel coordinates using both flat and pointy top layouts. It converts a Hex to pixel, then back to Hex, and checks for equality.

```csharp
static public void TestLayout()
    {
        Hex h = new Hex(3, 4, -7);
        Layout flat = new Layout(Layout.flat, new Point(10.0, 15.0), new Point(35.0, 71.0));
        Tests.EqualHex("layout", h, flat.PixelToHexRounded(flat.HexToPixel(h)));
        Layout pointy = new Layout(Layout.pointy, new Point(10.0, 15.0), new Point(35.0, 71.0));
        Tests.EqualHex("layout", h, pointy.PixelToHexRounded(pointy.HexToPixel(h)));
    }
```

--------------------------------

### Test Offset to Cube Coordinate Conversion

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Verifies correct mapping from offset coordinates back to cube coordinates.

```C#
    static public void TestOffsetToCube()
    {
        Tests.EqualHex("offset_to_cube odd-r", new Hex(-3, 2, 1), OffsetCoord.RoffsetToCube(OffsetCoord.ODD, new OffsetCoord(-2, 2)));
        Tests.EqualHex("offset_to_cube odd-r", new Hex(2, -1, -1), OffsetCoord.RoffsetToCube(OffsetCoord.ODD, new OffsetCoord(1, -1)));
        Tests.EqualHex("offset_to_cube even-r", new Hex(-3, 2, 1), OffsetCoord.RoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-2, 2)));
        Tests.EqualHex("offset_to_cube even-r", new Hex(2, -1, -1), OffsetCoord.RoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(2, -1)));
        Tests.EqualHex("offset_to_cube odd-q", new Hex(-2, 3, -1), OffsetCoord.QoffsetToCube(OffsetCoord.ODD, new OffsetCoord(-2, 2)));
        Tests.EqualHex("offset_to_cube odd-q", new Hex(-1, -1, 2), OffsetCoord.QoffsetToCube(OffsetCoord.ODD, new OffsetCoord(-1, -2)));
        Tests.EqualHex("offset_to_cube even-q", new Hex(-2, 3, -1), OffsetCoord.QoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-2, 2)));
        Tests.EqualHex("offset_to_cube even-q", new Hex(-1, -1, 2), OffsetCoord.QoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-1, -1)));
    }
```

--------------------------------

### Test Offset from Cube Coordinate Conversion

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Verifies correct mapping from cube coordinates to various offset coordinate layouts.

```C#
    static public void TestOffsetFromCube()
    {
        Tests.EqualOffsetcoord("offset_from_cube odd-r", new OffsetCoord(-2, 2), OffsetCoord.RoffsetFromCube(OffsetCoord.ODD, new Hex(-3, 2, 1)));
        Tests.EqualOffsetcoord("offset_from_cube odd-r", new OffsetCoord(1, -1), OffsetCoord.RoffsetFromCube(OffsetCoord.ODD, new Hex(2, -1, -1)));
        Tests.EqualOffsetcoord("offset_from_cube even-r", new OffsetCoord(-2, 2), OffsetCoord.RoffsetFromCube(OffsetCoord.EVEN, new Hex(-3, 2, 1)));
        Tests.EqualOffsetcoord("offset_from_cube even-r", new OffsetCoord(2, -1), OffsetCoord.RoffsetFromCube(OffsetCoord.EVEN, new Hex(2, -1, -1)));
        Tests.EqualOffsetcoord("offset_from_cube odd-q", new OffsetCoord(-2, 2), OffsetCoord.QoffsetFromCube(OffsetCoord.ODD, new Hex(-2, 3, -1)));
        Tests.EqualOffsetcoord("offset_from_cube odd-q", new OffsetCoord(-1, -2), OffsetCoord.QoffsetFromCube(OffsetCoord.ODD, new Hex(-1, -1, 2)));
        Tests.EqualOffsetcoord("offset_from_cube even-q", new OffsetCoord(-2, 2), OffsetCoord.QoffsetFromCube(OffsetCoord.EVEN, new Hex(-2, 3, -1)));
        Tests.EqualOffsetcoord("offset_from_cube even-q", new OffsetCoord(-1, -1), OffsetCoord.QoffsetFromCube(OffsetCoord.EVEN, new Hex(-1, -1, 2)));
    }
```

--------------------------------

### Generate Lua Class Constructor

Source: https://www.redblobgames.com/grids/hexagons/codegen/OutputLua.hx

Constructs a Lua function string for object initialization with optional precondition assertions.

```Haxe
var fields = collectFields(decls);
        if (fields.length > 0) {
            var preconditions = collectPreconditions(decls);
            var preconditionTest = (preconditions != null)? '${indent(1)}assert(not (${Expr(preconditions.test)}), ${Expr(preconditions.message)})
' : '';
            var fieldNames:Array<String> = [for (f in fields) f.name];
            var parameters:String = [for (f in fieldNames) '${f}'].join(", ");
            var init:String = [for (f in fieldNames) '${f} = ${f}'].join(", ");
            output = '

function ${classname}(${parameters})
${preconditionTest}${indent(1)}return {${init}}
end

' + output;
        }
        return output;
    }
```

--------------------------------

### Test Suite Execution

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/Tests.java

Methods for running the full test suite and handling test failures.

```java
    static public void testAll()
    {
        Tests.testHexArithmetic();
        Tests.testHexDirection();
        Tests.testHexNeighbor();
        Tests.testHexDiagonal();
        Tests.testHexDistance();
        Tests.testHexRotateRight();
        Tests.testHexRotateLeft();
        Tests.testHexRound();
        Tests.testHexLinedraw();
        Tests.testLayout();
        Tests.testOffsetRoundtrip();
        Tests.testOffsetFromCube();
        Tests.testOffsetToCube();
        Tests.testOffsetToDoubled();
        Tests.testOffsetFromDoubled();
        Tests.testDoubledRoundtrip();
        Tests.testDoubledFromCube();
        Tests.testDoubledToCube();
    }
```

```java
    static public void main(String[] args)
    {
        Tests.testAll();
    }
```

```java
    static public void complain(String name)
    {
        System.out.println("FAIL " + name);
    }
```

--------------------------------

### Compare Integer Values

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Compares two integer values for equality. If they are not equal, it calls Tests.Complain with a given name.

```csharp
static public void EqualInt(String name, int a, int b)
    {
        if (!(a == b))
        {
            Tests.Complain(name);
        }
    }
```

--------------------------------

### Test Offset to Cube Conversion

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/Tests.java

Verifies that specific offset coordinates map to the correct cube coordinates.

```java
static public void testOffsetFromCube()
{
Tests.equalOffsetcoord("offset_from_cube odd-r", new OffsetCoord(-2, 2), OffsetCoord.roffsetFromCube(OffsetCoord.ODD, new Hex(-3, 2, 1)));
Tests.equalOffsetcoord("offset_from_cube odd-r", new OffsetCoord(1, -1), OffsetCoord.roffsetFromCube(OffsetCoord.ODD, new Hex(2, -1, -1)));
Tests.equalOffsetcoord("offset_from_cube even-r", new OffsetCoord(-2, 2), OffsetCoord.roffsetFromCube(OffsetCoord.EVEN, new Hex(-3, 2, 1)));
Tests.equalOffsetcoord("offset_from_cube even-r", new OffsetCoord(2, -1), OffsetCoord.roffsetFromCube(OffsetCoord.EVEN, new Hex(2, -1, -1)));
Tests.equalOffsetcoord("offset_from_cube odd-q", new OffsetCoord(-2, 2), OffsetCoord.qoffsetFromCube(OffsetCoord.ODD, new Hex(-2, 3, -1)));
Tests.equalOffsetcoord("offset_from_cube odd-q", new OffsetCoord(-1, -2), OffsetCoord.qoffsetFromCube(OffsetCoord.ODD, new Hex(-1, -1, 2)));
Tests.equalOffsetcoord("offset_from_cube even-q", new OffsetCoord(-2, 2), OffsetCoord.qoffsetFromCube(OffsetCoord.EVEN, new Hex(-2, 3, -1)));
Tests.equalOffsetcoord("offset_from_cube even-q", new OffsetCoord(-1, -1), OffsetCoord.qoffsetFromCube(OffsetCoord.EVEN, new Hex(-1, -1, 2)));
}
```

```java
static public void testOffsetToCube()
{
Tests.equalHex("offset_to_cube odd-r", new Hex(-3, 2, 1), OffsetCoord.roffsetToCube(OffsetCoord.ODD, new OffsetCoord(-2, 2)));
Tests.equalHex("offset_to_cube odd-r", new Hex(2, -1, -1), OffsetCoord.roffsetToCube(OffsetCoord.ODD, new OffsetCoord(1, -1)));
Tests.equalHex("offset_to_cube even-r", new Hex(-3, 2, 1), OffsetCoord.roffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-2, 2)));
Tests.equalHex("offset_to_cube even-r", new Hex(2, -1, -1), OffsetCoord.roffsetToCube(OffsetCoord.EVEN, new OffsetCoord(2, -1)));
Tests.equalHex("offset_to_cube odd-q", new Hex(-2, 3, -1), OffsetCoord.qoffsetToCube(OffsetCoord.ODD, new OffsetCoord(-2, 2)));
Tests.equalHex("offset_to_cube odd-q", new Hex(-1, -1, 2), OffsetCoord.qoffsetToCube(OffsetCoord.ODD, new OffsetCoord(-1, -2)));
Tests.equalHex("offset_to_cube even-q", new Hex(-2, 3, -1), OffsetCoord.qoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-2, 2)));
Tests.equalHex("offset_to_cube even-q", new Hex(-1, -1, 2), OffsetCoord.qoffsetToCube(OffsetCoord.EVEN, new OffsetCoord(-1, -1)));
}
```

--------------------------------

### Deriving Northeast Neighbor for Even-q Offset

Source: https://www.redblobgames.com/grids/hexagons/derive-hex-neighbor-formula.html

Step-by-step derivation of the northeast neighbor formula for an 'even-q' offset grid by converting to cube coordinates, applying an offset, and converting back.

```python
# (1) convert even-q offset to cube coords:
q = col
r = row - (col + (col&1)) / 2
s = -q-r

# (2) apply Δq, Δr, Δs:
q' = q + 1
r' = r - 1
s' = s

# (3) substitute eq (1) into eq (2):
q' = col + 1
r' = row - (col + (col&1)) / 2 - 1
s' = -q'-r'

# (4) convert back into even-q coords:
col' = q'
row' = r' + (q' + (q'&1)) / 2

# (5) substitute eq (3) into eq (4)
col' = col + 1
row' = row  - ( col + (col&1)) / 2 - 1   + (col + 1 + ((col + 1)&1)) / 2
     = row  + (-col - (col&1) - 2) / 2   + (col + 1 +  1 - (col&1)) / 2
     = row  + (-col - (col&1) - 2        +  col + 1 +  1 - (col&1))  / 2
     = row  + (   -2 * (col&1)) / 2
     = row - (col&1)
```

--------------------------------

### Pixel to Hex Coordinates (Mark Steere)

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Converts pixel coordinates (x, y) to axial hex coordinates (q, r) using Mark Steere's elegant method, which involves five `floor()` calls. It transforms coordinates and calculates intermediate values before determining q and r.

```javascript
(x, y) => {
    // Convert to their coordinate system
    y = -y
    // Algorithm from Mark Steere
    let s_to_s = sqrt(3) // "side to side" distance, "w" on my page
    let u = (sqrt(3) * y - x) / 2
    let v = (sqrt(3) * y + x) / 2
    let x_halfcell = floor(2 * x / s_to_s)
    let u_halfcell = floor(2 * u / s_to_s)
    let v_halfcell = floor(2 * v / s_to_s)
    let W = floor((x_halfcell + v_halfcell + 2) / 3)
    let Y = floor((u_halfcell + v_halfcell + 2) / 3)
    return {q: W, r: -Y}
}
```

--------------------------------

### Define Layout structure

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Combines orientation, size, and origin to define the grid layout.

```cpp
struct Layout {
    const Orientation orientation;
    const Point size;
    const Point origin;
    Layout(Orientation orientation_, Point size_, Point origin_)
    : orientation(orientation_), size(size_), origin(origin_) {}
};
```

--------------------------------

### Implement Charles Chambers algorithm

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Full implementation of the Charles Chambers algorithm adapted for the site's coordinate system.

```javascript
(x, y) => {
    // Convert to their coordinate system
    x *= 1/sqrt(3)
    y *= -1/sqrt(3)
    // Algorithm emailed to me from Charles Chambers in 2013
    let temp = floor(x + sqrt(3) * y + 1)
    let q = floor((floor(2*x+1) + temp) / 3)
    let r = floor((temp + floor(-x + sqrt(3) * y + 1))/3)
    return {q, r: -r}
}
```

--------------------------------

### Define Orientation constants

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Predefined constants for pointy and flat-top hex orientations.

```cpp
const Orientation layout_pointy
  = Orientation(sqrt(3.0), sqrt(3.0) / 2.0, 0.0, 3.0 / 2.0,
                sqrt(3.0) / 3.0, -1.0 / 3.0, 0.0, 2.0 / 3.0,
                0.5);
const Orientation layout_flat
  = Orientation(3.0 / 2.0, 0.0, sqrt(3.0) / 2.0, sqrt(3.0),
                2.0 / 3.0, 0.0, -1.0 / 3.0, sqrt(3.0) / 3.0,
                0.0);
```

--------------------------------

### Test Hex Rounding

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the HexRound method on FractionalHex objects, including linear interpolation and rounding based on weighted averages.

```csharp
static public void TestHexRound()
    {
        FractionalHex a = new FractionalHex(0.0, 0.0, 0.0);
        FractionalHex b = new FractionalHex(1.0, -1.0, 0.0);
        FractionalHex c = new FractionalHex(0.0, -1.0, 1.0);
        Tests.EqualHex("hex_round 1", new Hex(5, -10, 5), new FractionalHex(0.0, 0.0, 0.0).HexLerp(new FractionalHex(10.0, -20.0, 10.0), 0.5).HexRound());
        Tests.EqualHex("hex_round 2", a.HexRound(), a.HexLerp(b, 0.499).HexRound());
        Tests.EqualHex("hex_round 3", b.HexRound(), a.HexLerp(b, 0.501).HexRound());
        Tests.EqualHex("hex_round 4", a.HexRound(), new FractionalHex(a.q * 0.4 + b.q * 0.3 + c.q * 0.3, a.r * 0.4 + b.r * 0.3 + c.r * 0.3, a.s * 0.4 + b.s * 0.3 + c.s * 0.3).HexRound());
        Tests.EqualHex("hex_round 5", c.HexRound(), new FractionalHex(a.q * 0.3 + b.q * 0.3 + c.q * 0.4, a.r * 0.3 + b.r * 0.3 + c.r * 0.4, a.s * 0.3 + b.s * 0.3 + c.s * 0.4).HexRound());
    }
```

--------------------------------

### Calculate Cube neighbors

Source: https://www.redblobgames.com/grids/hexagons-v2

Methods to find neighboring hexes using precomputed cube direction vectors.

```pseudocode
var cube_directions = [
    Cube(+1, -1, 0), Cube(+1, 0, -1), Cube(0, +1, -1),   
    Cube(-1, +1, 0), Cube(-1, 0, +1), Cube(0, -1, +1), 
]

function cube_direction(direction):
    return cube_directions[direction]

function cube_neighbor(cube, direction):
    return cube_add(cube, cube_direction(direction))
```

--------------------------------

### Test Hex Line Drawing

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the FractionalHex.HexLinedraw method by comparing the generated list of Hex cells between two points with an expected list.

```csharp
static public void TestHexLinedraw()
    {
        Tests.EqualHexArray("hex_linedraw", new List<Hex>{new Hex(0, 0, 0), new Hex(0, -1, 1), new Hex(0, -2, 2), new Hex(1, -3, 2), new Hex(1, -4, 3), new Hex(1, -5, 4)}, FractionalHex.HexLinedraw(new Hex(0, 0, 0), new Hex(1, -5, 4)));
    }
```

--------------------------------

### Coordinate Conversion Methods

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/Tests.java

Methods for converting between offset, doubled, and cube coordinate systems.

```java
    static public Hex roffsetToCube(int offset, OffsetCoord h)
    {
        int parity = h.row & 1;
        int q = h.col - (int)((h.row + offset * parity) / 2);
        int r = h.row;
        int s = -q - r;
        if (offset != OffsetCoord.EVEN && offset != OffsetCoord.ODD)
        {
            throw new IllegalArgumentException("offset must be EVEN (+1) or ODD (-1)");
        }
        return new Hex(q, r, s);
    }
```

```java
    static public OffsetCoord qoffsetFromQdoubled(int offset, DoubledCoord h)
    {
        int parity = h.col & 1;
        return new OffsetCoord(h.col, (int)((h.row + offset * parity) / 2));
    }
```

```java
    static public DoubledCoord qoffsetToQdoubled(int offset, OffsetCoord h)
    {
        int parity = h.col & 1;
        return new DoubledCoord(h.col, 2 * h.row - offset * parity);
    }
```

```java
    static public OffsetCoord roffsetFromRdoubled(int offset, DoubledCoord h)
    {
        int parity = h.row & 1;
        return new OffsetCoord((int)((h.col + offset * parity) / 2), h.row);
    }
```

```java
    static public DoubledCoord roffsetToRdoubled(int offset, OffsetCoord h)
    {
        int parity = h.row & 1;
        return new DoubledCoord(2 * h.col - offset * parity, h.row);
    }
```

--------------------------------

### Pixel to Hex Coordinates (Eric Gradman)

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Converts pixel coordinates (x, y) to axial hex coordinates (q, r) using an algorithm by Eric Gradman, an implementation of the playtechs algorithm. Requires scaling and matrix transformations.

```javascript
(x, y) => {
    // Convert to their coordinate system
    const SCALE = sqrt(3) / 4
    x /= SCALE
    y /= SCALE
    
    // Algorithm from Eric Gradman, implementation of playtechs
    const R = 2                        // center to edge
    const S = 2 * R / sqrt(3)          // center to vertex
    const T = S / 2                    // "height of triangle" ?
    
    const XM = [[1 / (2*R), -1/S], [1/R, 0]]
    const YM = [[1 / (2*R), 1/S], [-1 / (2*R), 1/S]]

    function floor_dot(matrix, vector) {
        return [
            floor(matrix[0][0] * vector.x + matrix[0][1] * vector.y),
            floor(matrix[1][0] * vector.x + matrix[1][1] * vector.y),
        ]
    }
        
    let [xi, yi] = floor_dot(XM, {x, y})
    let q = floor((xi + yi + 2) / 3)
    let [xj, yj] = floor_dot(YM, {x, y})
    let r = floor((xj + yj + 2) / 3)
    
    return {q, r}
}
```

--------------------------------

### Convert Between Offset and Doubled Coordinates

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Utility methods to translate between offset coordinate systems and doubled coordinate systems.

```csharp
static public OffsetCoord QoffsetFromQdoubled(int offset, DoubledCoord h)
    {
        int parity = h.col & 1;
        return new OffsetCoord(h.col, (int)((h.row + offset * parity) / 2));
    }
```

```csharp
static public DoubledCoord QoffsetToQdoubled(int offset, OffsetCoord h)
    {
        int parity = h.col & 1;
        return new DoubledCoord(h.col, 2 * h.row - offset * parity);
    }
```

```csharp
static public OffsetCoord RoffsetFromRdoubled(int offset, DoubledCoord h)
    {
        int parity = h.row & 1;
        return new OffsetCoord((int)((h.col + offset * parity) / 2), h.row);
    }
```

```csharp
static public DoubledCoord RoffsetToRdoubled(int offset, OffsetCoord h)
    {
        int parity = h.row & 1;
        return new DoubledCoord(2 * h.col - offset * parity, h.row);
    }
```

--------------------------------

### Map Storage Strategies

Source: https://www.redblobgames.com/grids/hexagons-v2

Formulas for mapping axial coordinates (q, r) to array indices for different map shapes.

```pseudocode
Rectangle: array[r][q + floor(r/2)]
```

```pseudocode
Hexagon: array[r][q - max(0, N-r)]
```

```pseudocode
Rhombus: array[r][q]
```

```pseudocode
Down-triangle: array[r][q]
```

```pseudocode
Up-triangle: array[r][q - N+1+r]
```

--------------------------------

### Calculate Charles Chambers algorithm

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Core logic for the Charles Chambers pixel-to-hex conversion algorithm.

```javascript
temp = floor(x + sqrt(3) * y + 1)
q = floor((floor(2*x+1) + temp) / 3);
r = floor((temp + floor(-x + sqrt(3) * y + 1))/3);
```

--------------------------------

### Convert pixel coordinates to fractional hex coordinates

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Calculates the fractional hex coordinates for a given screen point by reversing the layout transformation matrix.

```cpp
FractionalHex pixel_to_hex_fractional(Layout layout, Point p) {
    const Orientation& M = layout.orientation;
    Point pt = Point((p.x - layout.origin.x) / layout.size.x, 
                     (p.y - layout.origin.y) / layout.size.y);
    double q = M.b0 * pt.x + M.b1 * pt.y;
    double r = M.b2 * pt.x + M.b3 * pt.y;
    return FractionalHex(q, r, -q - r);
}
```

--------------------------------

### Run All Hexagonal Grid Tests

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Executes a comprehensive suite of tests for various hexagonal grid functionalities, including arithmetic, directions, neighbors, rotations, and coordinate systems (offset, doubled).

```csharp
static public void TestAll()
    {
        Tests.TestHexArithmetic();
        Tests.TestHexDirection();
        Tests.TestHexNeighbor();
        Tests.TestHexDiagonal();
        Tests.TestHexDistance();
        Tests.TestHexRotateRight();
        Tests.TestHexRotateLeft();
        Tests.TestHexRound();
        Tests.TestHexLinedraw();
        Tests.TestLayout();
        Tests.TestOffsetRoundtrip();
        Tests.TestOffsetFromCube();
        Tests.TestOffsetToCube();
        Tests.TestOffsetToDoubled();
        Tests.TestOffsetFromDoubled();
        Tests.TestDoubledRoundtrip();
        Tests.TestDoubledFromCube();
        Tests.TestDoubledToCube();
    }
```

--------------------------------

### Testing Utilities

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Helper methods for validating coordinate equality in unit tests.

```csharp
static public void EqualHex(String name, Hex a, Hex b)
    {
        if (!(a.q == b.q && a.s == b.s && a.r == b.r))
        {
            Tests.Complain(name);
        }
    }
```

```csharp
static public void EqualOffsetcoord(String name, OffsetCoord a, OffsetCoord b)
    {
```

--------------------------------

### Pixel to Hex Coordinates (BorisTheBrave)

Source: https://www.redblobgames.com/grids/hexagons/more-pixel-to-hex.html

Converts pixel coordinates (x, y) to axial hex coordinates (q, r) using a variant of Justin Pombrio's algorithm. It involves two `ceil`, one `floor`, and two `round` calls, and swaps coordinates for pointy/flat orientation.

```javascript
(x, y) => {
    const edge_length = 1
    function pick_tri(x, y) {
        return [
            ceil(( 1 * x - sqrt(3) / 3 * y) / edge_length),
            floor((    sqrt(3) * 2 / 3 * y) / edge_length) + 1,
            ceil((-1 * x - sqrt(3) / 3 * y) / edge_length),
        ]
    }
    function tri_to_hex(x, y, z) {
        return [
            round((x - z) / 3),
            round((y - x) / 3),
            round((z - y) / 3), // not needed for axial
        ]
    }
    
    let [a, b, c] = pick_tri(y, x) // swap for pointy/flat
    let [q, r, s] = tri_to_hex(a, b, c)
    return {q: r, r: q} // swap for pointy/flat
}
```

--------------------------------

### Test Hex Rotate Left

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the Hex.RotateLeft method by rotating a Hex object and comparing the result with an expected Hex value.

```csharp
static public void TestHexRotateLeft()
    {
        Tests.EqualHex("hex_rotate_left", new Hex(1, -3, 2).RotateLeft(), new Hex(-2, -1, 3));
    }
```

--------------------------------

### Store Map Data in Hash Table

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Demonstrates using an unordered_map to store float values associated with Hex coordinates.

```cpp
unordered_map<Hex, float> heights;
heights[Hex(1, -2, 3)] = 4.3;
cout << heights[Hex(1, -2, 3)];
```

--------------------------------

### Test Hex Diagonal Neighbor

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the Hex.DiagonalNeighbor method by comparing the resulting Hex with an expected value for a given diagonal direction.

```csharp
static public void TestHexDiagonal()
    {
        Tests.EqualHex("hex_diagonal", new Hex(-1, -1, 2), new Hex(1, -2, 1).DiagonalNeighbor(3));
    }
```

--------------------------------

### Test Hex Rotate Right

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Tests the Hex.RotateRight method by rotating a Hex object and comparing the result with an expected Hex value.

```csharp
static public void TestHexRotateRight()
    {
        Tests.EqualHex("hex_rotate_right", new Hex(1, -3, 2).RotateRight(), new Hex(3, -2, -1));
    }
```

--------------------------------

### Offset Coordinate Conversion (C#)

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Provides methods for converting between cube coordinates (Hex) and offset coordinates (OffsetCoord). Supports both even and odd row/column offsets.

```csharp
struct OffsetCoord
{
    public OffsetCoord(int col, int row)
    {
        this.col = col;
        this.row = row;
    }
    public readonly int col;
    public readonly int row;
    static public int EVEN = 1;
    static public int ODD = -1;

    static public OffsetCoord QoffsetFromCube(int offset, Hex h)
    {
        int parity = h.q & 1;
        int col = h.q;
        int row = h.r + (int)((h.q + offset * parity) / 2);
        if (offset != OffsetCoord.EVEN && offset != OffsetCoord.ODD)
        {
            throw new ArgumentException("offset must be EVEN (+1) or ODD (-1)");
        }
        return new OffsetCoord(col, row);
    }


    static public Hex QoffsetToCube(int offset, OffsetCoord h)
    {
        int parity = h.col & 1;
        int q = h.col;
        int r = h.row - (int)((h.col + offset * parity) / 2);
        int s = -q - r;
        if (offset != OffsetCoord.EVEN && offset != OffsetCoord.ODD)
        {
            throw new ArgumentException("offset must be EVEN (+1) or ODD (-1)");
        }
        return new Hex(q, r, s);
    }


    static public OffsetCoord RoffsetFromCube(int offset, Hex h)
    {
        int parity = h.r & 1;
        int col = h.q + (int)((h.r + offset * parity) / 2);
        int row = h.r;
        if (offset != OffsetCoord.EVEN && offset != OffsetCoord.ODD)
        {
            throw new ArgumentException("offset must be EVEN (+1) or ODD (-1)");
        }
        return new OffsetCoord(col, row);
    }

}
```

--------------------------------

### Equality Testing Utility

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/Tests.java

Utility method for verifying hex coordinate equality in tests.

```java
    static public void equalHex(String name, Hex a, Hex b)
    {
        if (!(a.q == b.q && a.s == b.s && a.r == b.r))
        {
```

--------------------------------

### Rectangular Pointy Top Map Class

Source: https://www.redblobgames.com/grids/hexagons/implementation.html

Encapsulation of compact storage and coordinate mapping for a rectangular pointy-top hex grid.

```cpp
template<class T> class RectangularPointyTopMap {
    vector<vector<T>> map;

    int left_, top_;
  public:
    RectangularPointyTopMap(int left, int top, int right, int bottom)
                 : left_(left), top_(top) 
    {
        int height = bottom - top + 1;
        map.resize(height);
        for (int r = 0; r < height; r++) {
            int width = right - left + 1;
            map.emplace_back(width);
        }
    }

    inline T& at(int q, int r) {
        return map[r - top_][q - left_ + (r >> 1)];
    }
};
```

--------------------------------

### Doubled Coordinate Conversions

Source: https://www.redblobgames.com/grids/hexagons/codegen/output/lib.cs

Methods for converting between cube coordinates and doubled coordinate representations.

```csharp
static public DoubledCoord QdoubledFromCube(Hex h)
    {
        int col = h.q;
        int row = 2 * h.r + h.q;
        return new DoubledCoord(col, row);
    }
```

```csharp
public Hex QdoubledToCube()
    {
        int q = col;
        int r = (int)((row - col) / 2);
        int s = -q - r;
        return new Hex(q, r, s);
    }
```

```csharp
static public DoubledCoord RdoubledFromCube(Hex h)
    {
        int col = 2 * h.q + h.r;
        int row = h.r;
        return new DoubledCoord(col, row);
    }
```

```csharp
public Hex RdoubledToCube()
    {
        int q = (int)((col - row) / 2);
        int r = row;
        int s = -q - r;
        return new Hex(q, r, s);
    }
```
Tokens:
Raw