data-structures - 卡坦岛定居者 map 的数据结构？

Question

这个问题在这里已经有了答案:





How do I represent a hextile/hex grid in memory?

(9 个回答)


7年前关闭。




不久前有人问我是否知道为游戏 Settlers of Catan 编码信息的好方法。这将需要以一种方式存储六边形网格，其中每个六边形都可以具有与之关联的数据。不过，更重要的是，我需要一些有效地查找这些六边形侧面的顶点和边的方法，因为这就是所有 Action 的所在。

我的问题是:有没有好的，简单 用于存储六边形网格的数据结构，同时允许快速查找六边形、六边形之间的边和六边形交叉处的顶点？我知道像翼边或四边形这样的一般结构可以做到这一点，但这似乎是巨大的矫枉过正。

Answer 1

当您只关心六边形时，存储六边形网格的简单结构是一个矩阵，在 (x,y) 处的六边形是 (x, y±1), (x±1,y) 处的六边形的邻居，和 (x±1,y+1) 用于偶数 xs 或 (x±1,y-1) 用于奇数 xs。我们可以改进这个想法以允许快速查找边和顶点。

您将另外两个矩阵添加到此:一个用于边，另一个用于顶点。

您考虑由 (x,2y)、(x,2y+1)、(x,2y+2)、(x+1,2y)、(x+1) 位置的顶点分隔的 (x,y) 六边形,2y+1) 和 (x+1,2y+2)，对于偶数 xs。对于奇数 xs，在 y 坐标上加 1。围绕它的边是 (2x,2y), (2x,2y+1), (2x+1, 2y), (2x+1,2y+2), (2x+2,2y) 和 (2x +2,2y+1)，如果 x 为奇数，则通过加一对 y 进行额外调整。

这使您可以对给定六边形的边和顶点进行恒定时间随机访问(并且您也可以计算出坐标变换来进行反向查找)。

使用一些更简单的公式，您可以从顶点查找边，从顶点查找六边形，以及玩游戏可能需要的其他查找。

通过这种方式，您可以只用数组来表示电路板，并使用简单的数学进行查找，以在“六边形坐标”、“边缘坐标”和“顶点坐标”之间进行转换。

因为电路板不能完美地拟合(矩形)矩阵，所以您需要用一些“空”或“无效”值填充几个单元格，以表示几个与电路板的六边形形状不匹配的边界单元格。

渐近地，此方法使用与十六进制数线性相关的内存，并为任何查找提供恒定时间。

这是一些示例 C# 代码:

class Board
{
    public readonly Hex[,] Hexes = new Hex[10,10];
    public readonly Edge[,] Edges = new Edge[22,22];
    public readonly Vertex[,] Vertices = new Vertex[22,22];

    public Board()
    {
        for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            Hexes[i,j] = new Hex { X = i, Y = j };
        for(int i = 0; i < 22; i++)
        for(int j = 0; j < 22; j++)
        {
            Edges[i,j] = new Edge { X = i, Y = j };
            Vertices[i,j] = new Vertex { X = i, Y = j };
        }
    }

    public IEnumerable<Hex> GetNeighbors(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2 == 0? +1 : -1;
        return new []
        {
            Hexes[x,y+1],
            Hexes[x,y-1],
            Hexes[x+1,y],
            Hexes[x-1,y],
            Hexes[x+1,y+offset],
            Hexes[x-1,y+offset],
        };
    }
    public IEnumerable<Vertex> GetVertices(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2;
        return new[]
        {
            Vertices[x,2*y+offset],
            Vertices[x,2*y+1+offset],
            Vertices[x,2*y+2+offset],
            Vertices[x+1,2*y+offset],
            Vertices[x+1,2*y+1+offset],
            Vertices[x+1,2*y+2+offset],
        };
    }
    public IEnumerable<Edge> GetEdges(Hex hex)
    {
        var x = hex.X; var y = hex.Y;
        var offset = x % 2;
        return new[]
        {
            Edges[2*x,2*y+offset],
            Edges[2*x,2*y+1+offset],
            Edges[2*x+1,2*y+offset],
            Edges[2*x+1,2*y+2+offset],
            Edges[2*x+2,2*y+offset],
            Edges[2*x+2,2*y+1+offset],
        };
    }
    public IEnumerable<Vertex> GetEnds(Edge edge)
    {
        var x = edge.X; var y = edge.Y;
        if(x % 2 == 0)
            return new[]
            {
                Vertices[x/2,y],
                Vertices[x/2,y+1],
            };
        else
            return new[]
            {
                Vertices[(x-1)/2,y],
                Vertices[(x+1)/2,y],
            };
    }
    public IEnumerable<Edge> GetEdges(Vertex vertex)
    {
        var x = vertex.X; var y = vertex.Y;
        return new []
        {
            Edges[x*2,y],
            Edges[x*2+1,y],
            Edges[x*2-1,y],
        };
    }
    public IEnumerable<Hex> GetHexes(Vertex vertex)
    {
        var x = vertex.X; var y = vertex.Y;
        var xoffset = x % 2;
        var yoffset = y % 2;
        return new[]
        {
            Hexes[x-1,(y+xoffset)/2-1],
            Hexes[x-(1-yoffset)*xoffset,(y-1)/2],
            Hexes[x,(y-xoffset)/2],
        };
    }
}

由于一些单元从未使用过，因此存在一些内存效率低下，但这应该不是问题。内存消耗保持在相同的渐近界限下。