Zeshoek Helpers¶

Doelstelling¶

Het doel was om een collectie van functies te maken waarmee wij gemakkelijk verschillende operaties met zeshoeken en zeshoekige grids kunnen doen.

Toegepaste oplossing¶

Dit zijn allemaal implementaties van de formules van Red Blob Games^{(RedBlobGames, 2021)}. Daarom raad ik aan om de bron zelf te lezen om meer gedetailleerde informatie te krijgen.

HexVector¶

public struct HexVector()
{
    public int q = 0;

    public int r = 0;

    public int s
    {
        get => -q-r;
        set { q += value - s; }
    }

Hier zijn conversie methods zodat HexVector ook de andere coördinaat systemen voor zeshoeken support.

    public Vector2 offset
    {
        get => new(
            q + (r - (r&1))/2,
            r
        );
        set {
            var x = (int)value.X;
            var y = (int)value.Y;

            q = x - (y - (y&1))/2;
            r = y;
        }
    }

    public static HexVector FromAxial(int q, int r)
        => new()
        {
            q = q,
            r = r
        };

    public static HexVector FromAxial(float q, float r)
    {
        var s = -q-r;

        var qRound = Math.Round(q);
        var rRound = Math.Round(r);
        var sRound = Math.Round(s);

        var qDiff = Math.Abs(q - qRound);
        var rDiff = Math.Abs(r - rRound);
        var sDiff = Math.Abs(s - sRound);

        if (qDiff > rDiff && qDiff > sDiff)
        {
            qRound = -rRound-sRound;
        }
        else if (rDiff > sDiff)
        {
            rRound = -qRound-sRound;
        }

        return FromAxial((int)qRound, (int)rRound);
    }

    public static HexVector FromCube(int q, int r, int s)
    {
        if (q + r + s != 0)
        {
            throw new ArgumentException($"Sum of cube coordinates must be 0, instead it is {q+r+s}.", nameof(s));
        }

        return FromAxial(q, r);
    }

    public static HexVector FromCube(float q, float r, float s)
    {
        if (Math.Abs(q + r + s) >= 1f)
        {
            throw new ArgumentException($"Sum of cube coordinates must be less than 1 away from 0, instead it is {q+r+s}.", nameof(s));
        }

        return FromAxial(q, r);
    }

    public static HexVector FromOffset(Vector2 offset)
        => new()
        {
            offset = offset
        };

Hier zijn allemaal constanten voor de verschillende richtingen dat je op kan gaan op een zeshoekige grid. Het is net zoals Vector2.Up bijvoorbeeld, maar op een zeshoekige grid heb je natuurlijk veel meer richtingen.

    public static class DirectionVectors
    {
        public static readonly HexVector Left = FromAxial(-1, 0);
        public static readonly HexVector Right = FromAxial(1, 0);
        public static readonly HexVector TopLeft = FromAxial(0, -1);
        public static readonly HexVector TopRight = FromAxial(1, -1);
        public static readonly HexVector BottomLeft = FromAxial(-1, 1);
        public static readonly HexVector BottomRight = FromAxial(0, 1);

        public readonly static HexVector[] All = [
            Right, TopRight, TopLeft, Left, BottomLeft, BottomRight
        ];
    }

    public static class DiagonalDirectionVectors
    {
        public static readonly HexVector Top = FromAxial(1, -2);
        public static readonly HexVector Bottom = FromAxial(-1, 2);
        public static readonly HexVector TopLeft = FromAxial(-1, -1);
        public static readonly HexVector TopRight = FromAxial(2, -1);
        public static readonly HexVector BottomLeft = FromAxial(-2, 1);
        public static readonly HexVector BottomRight = FromAxial(1, 1);

        public readonly static HexVector[] All = [
            TopRight, Top, TopLeft, BottomLeft, Bottom, BottomRight
        ];
    }

    public List<HexVector> GetNeighbours()
    {
        var center = this;

        return DirectionVectors
            .All
            .Select(v => center + v)
            .ToList();
    }

    public List<HexVector> GetDiagonalNeighbours()
    {
        var center = this;

        return DiagonalDirectionVectors
            .All
            .Select(v => center + v)
            .ToList();
    }

    public int HexMagnitude()
        => (Math.Abs(q) + Math.Abs(r) + Math.Abs(s)) / 2;

    public static HexVector Lerp(HexVector a, HexVector b, float t)
        => FromAxial(
            MathExtras.Lerp((float)a.q, b.q, t),
            MathExtras.Lerp((float)a.r, b.r, t)
        );

    public static List<HexVector> GetLine(HexVector start, HexVector end)
    {
        var n = (start - end).HexMagnitude();
        var results = new List<HexVector>(n);

        for (var i = 0; i < n; i++)
        {
            results.Add(Lerp(start, end, 1f/n * i));
        }

        return results;
    }

    public static int CountInRing(int radius)
        => radius == 0 ? 1 : radius * 6;

Met deze CountInRange method had ik wat problemen. Ik wou een method waarmee ik het aantal tiles kon berekenen zodat ik in GetInRange van te voren de lijst met de juiste grootte kon maken, zodat het niet hoeft te resize wat onnodig langzaam is.

Eerst na wat zoeken kwamen ik op deze formule, maar door de $\Sigma$ is het wel minder efficiënt dan ik eigenlijk zou willen.

\[ \large 1 + \sum_{n=1}^r 6n \]

De dag erna had ik een doorbraak en vond de formule $\Large \frac{n(n-1)}2$ wat de som berekent voor alle gehele positieve getallen kleiner dan $n$. Deze heb ik uiteindelijk vereenvoudigd hieronder. Ook heb ik $r = n+1$ gedaan omdat wij de som van alle gehele positieve getallen kleiner en gelijk aan $n$ willen.

\[ \begin{align} 1 &+ 6\frac{r(r+1)}{2} \\ = 1 &+ 6 \cdot \frac12 r(r+1) \\ = 1 &+ \frac62 r(r+1) \\ = 1 &+ 3r(r+1) \end{align} \]

    public static int CountInRange(int range)
        => 1 + 3 * (range+1) * range;

    public static List<HexVector> GetInRange(int range, HexVector? center = null)
    {
        var middle = center ?? new HexVector();
        var results = new List<HexVector>(CountInRange(range));

        for (var q = -range; q <= range; q++)
        {
            for (var r = Math.Max(-range, -q-range); r <= Math.Min(range, -q+range); r++)
            {
                results.Add(middle + FromAxial(q, r));
            }
        }

        return results;
    }

Deze specifieke implementatie was wat moeilijker. Dit was omdat er voor qrs_{min en max} alleen stond $q - N$ en $q + N$, terwijl er meer dan één q r en s zijn. Na wat testen is het toch gelukt.

    public static List<HexVector> GetInIntersectingRanges(HexVector a, int rangeA, HexVector b, int rangeB)
    {
        var results = new List<HexVector>(CountInRange(Math.Min(rangeA, rangeB)));

        var qMin = Math.Max(a.q - rangeA, b.q - rangeB);
        var qMax = Math.Min(a.q + rangeA, b.q + rangeB);

        var rMin = Math.Max(a.r - rangeA, b.r - rangeB);
        var rMax = Math.Min(a.r + rangeA, b.r + rangeB);

        var sMin = Math.Max(a.s - rangeA, b.s - rangeB);
        var sMax = Math.Min(a.s + rangeA, b.s + rangeB);

        for (var q = qMin; q <= qMax; q++)
        {
            for (var r = Math.Max(rMin, -q-sMax); r <= Math.Min(rMax, -q-sMin); r++)
            {
                results.Add(FromAxial(q, r));
            }
        }

        return results;
    }

    public static List<HexVector> GetRing(int radius, HexVector? center = null)
    {
        var middle = center ?? new HexVector();
        var results = new List<HexVector>(CountInRing(radius));

        var current = middle + DirectionVectors.All.ElementAt(4) * radius;

        foreach (var direction in DirectionVectors.All)
        {
            for (var i = 0; i < radius; i++)
            {
                results.Add(current);
                current += direction;
            }
        }

        return results;
    }

    public HexVector RotateClockwise()
        => FromAxial(-r, -s);

    public HexVector RotateAntiClockwise()
        => FromAxial(-s, -q);

    public HexVector ReflectQ()
        => FromAxial(q, s);

    public HexVector ReflectR()
        => FromAxial(s, r);

    public HexVector ReflectS()
        => FromAxial(r, q);

Hier hebben we nog overrides voor standaard methods, zoals operaties en het veranderen van de vector naar een leesbare string.

    public static HexVector operator +(HexVector a) => a;

    public static HexVector operator -(HexVector a) => FromAxial(-a.q, -a.r);

    public static HexVector operator +(HexVector a, HexVector b)
        => FromAxial(a.q + b.q, a.r + b.r);

    public static HexVector operator -(HexVector a, HexVector b)
        => a + (-b);

    public static HexVector operator *(HexVector a, int b)
        => FromAxial(a.q * b, a.r * b);

    public static bool operator ==(HexVector a, HexVector b)
        => a.q == b.q && a.r == b.r;

    public static bool operator !=(HexVector a, HexVector b)
        => !(a == b);


    public override bool Equals(object other)
    {
        if (!other.GetType().IsAssignableTo(typeof(HexVector)))
        {
            return false;
        }

        return this == (HexVector)other;
    }

    public override int GetHashCode()
        => HashCode.Combine(q, r);

    public override string ToString()
        => $"({q}, {r}, {s})";
}

Voor de meeste methods heb ik ook niet statische versies, in de vorm van:

public DezelfdeReturnType DezelfdeMethodNaam(HexVector dezelfdeArgumenten)
    => DezelfdeMethodNaam(this, dezelfdeArgumenten);

Ik heb ze weggelaten uit dit document omdat het anders veel te lang zou zijn.

HashGrid¶

Als eerste een paar algemene methods dat veel lijken om dezelfde methods in List<> en Dictionary<> zelf. Dit is met een abstracte base class zodat wij potentieel en gemakkelijk andere soorten grids kunnen gebruiken.

public class HashHexGrid<T> : BaseHexGrid<T>
{
    protected Dictionary<HexVector, T> grid = new();

    public override IEnumerable<T> Values => grid.Values;

    public override T? ElementAt(HexVector pos)
    {
        var gotValue = grid.TryGetValue(pos, out var value);

        return gotValue ? value : default;
    }

    public override void Add(HexVector pos, T value)
        => grid.Add(pos, value);

    public override void Clear()
        => grid.Clear();

Deze methods zijn gedefinieerd in BaseHexGrid zelf. Deze zijn net zoals alles in HexVector implementaties van de bronnen^{(Red Blob Games, 2021)}.

    public virtual Vector2 HexToPos(HexVector hex)
        => new Vector2(
            (float)(Math.Sqrt(3) * hex.q + Math.Sqrt(3) * hex.r),
            3f/2f * hex.r
        );

    public virtual HexVector PosToHex(Vector2 pos)
        => HexVector.FromAxial(
            (float)(Math.Sqrt(3)/3 * pos.X - 1f/3 * pos.Y),
            2f/3f * pos.Y
        );
}

Klassendiagram¶

classDiagram class HexVector { +int q +int r +GetS() int +GetAsOffset() Vector2 +FromAxial(q, r) HexVector$ +FromCube(q, r, s) HexVector$ +FromOffset(offset) HexVector$ +GetNeighbours() List~HexVector~ +GetDiagonalNeighbours() List~HexVector~ +HexMagnitude() int +Lerp(a, b, t) HexVector$ +GetLine(a, b, t) List~HexVector~$ +CountInRing(radius) int$ +CountInRange(range) int$ +GetInRange(range, center?) List~HexVector~$ +GetRandomInRange(random, range, center?) HexVector$ +GetInIntersectingRanges(a, rangeA, b, rangeB) List~HexVector~$ +GetRing(radius, center?) List~HexVector~$ +RotateClockwise() HexVector +RotateAntiClockwise() HexVector +ReflectQ() HexVector +ReflectR() HexVector +ReflectS() HexVector } BaseHexGrid --> HexVector class BaseHexGrid~T~ { +HexToPos(hex) Vector* +PosToHex(pos) HexVector* +GetValues() IENumerable~T~* +GetEnumerator() IEnumerator~KeyValuePair~HexVector; T~~* +ElementAt(pos) T?* +Add(pos, value)* +Remove(pos) bool* +Clear()* } HashHexGrid --> HexVector HashHexGrid --|> BaseHexGrid class HashHexGrid~T~ { +GetValues() IENumerable~T~ +GetEnumerator() IEnumerator~KeyValuePair~HexVector; T~~ +ElementAt(pos) T? +Add(pos, value) +Remove(pos) bool +Clear() }

Bronnen¶

C# documentation. (z.d.) learn.microsoft.com.
Laatst geraadpleegd op 26 februari 2024, van https://learn.microsoft.com/en-uk/dotnet/csharp/
Red Blob Games. (2021, oktober). Hexagonal Grids. redblobgames.com.
Laatst geraadpleegd op 28 februari 2024, van https://www.redblobgames.com/grids/hexagons/

Laatst geüpdatet: March 11, 2024
Gecreëerd: February 27, 2024