Settlers of Catan地图的数据结构？

Question

不久前有人问我是否知道一种很好的方法来编码游戏Settlers of Catan的信息.这将需要以每个十六进制可以具有与其相关联的数据的方式存储六边形网格.更重要的是,我需要一些方法来有效地查找这些六边形的边上的顶点和边缘,因为这是所有动作的所在.

我的问题是:是否有一个好的,简单的数据结构用于存储六边形网格,同时允许快速查找六边形,六边形之间的边缘和六边形交叉点处的顶点？我知道像边缘或四边形这样的一般结构可以做到这一点,但这看起来像是大规模的矫枉过正.

Answer 1

当你所关心的简单结构来存储一个六角形网格仅约六边形,是一个矩阵,在(X,Y)是在六边形的相邻的六边形(X,Y为±1),(X±1,y)时,和(x±1,y + 1)表示偶数xs或(x±1,y-1)表示奇数xs.我们可以发展这个想法,以允许快速查找边和顶点.

您可以为此添加另外两个矩阵:一个用于边,另一个用于顶点.

你考虑在(x,y)由位置(x,2y),(x,2y + 1),(x,2y + 2),(x + 1,2y),(x + 1)处的顶点界定的六边形,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为奇数,则通过加1来对y进行额外调整.

这使您可以在给定六边形的情况下随机访问边和顶点(并且您可以计算出坐标转换以进行反向查找).

使用一些更简单的公式,您可以从顶点,顶点的十六进制以及您可能需要玩游戏的其他查找中查找边.

通过这种方式,您可以使用数组表示电路板,并使用简单的数学运算进行查找,以在"六边形坐标","边缘坐标"和"顶点坐标"之间进行转换.

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

渐近地,此方法对hexes的数量使用内存线性,并为任何查找提供恒定的时间.

这是一些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],
        };
    }
}

存在一些内存效率低下的问题,因为从未使用过一些单元,但这应该不是问题.内存消耗保持在相同的渐近范围内.