This question already has answers here:
How do I represent a hextile/hex grid in memory?
（9个答案）
5年前关闭。
不久前有人问我是否知道一种很好的方法来编码Catan游戏Settlers。这将需要以每个十六进制都可以具有与之关联的数据的方式存储六边形网格。不过，更重要的是，我需要一种有效地查找这些六边形侧面上的顶点和边缘的方法，因为这是所有动作的所在。
我的问题是：是否存在一个好的，简单的数据结构来存储六边形网格，同时允许快速查找六边形，六边形之间的边以及六边形相交处的顶点？我知道像翼边或四边这样的一般结构都可以做到这一点，但这似乎是过大的杀伤力。
内存效率低下，因为从未使用过几个单元，但这不应该成为问题。内存消耗保持在相同的渐近范围内。
（9个答案）
5年前关闭。
不久前有人问我是否知道一种很好的方法来编码Catan游戏Settlers。这将需要以每个十六进制都可以具有与之关联的数据的方式存储六边形网格。不过，更重要的是，我需要一种有效地查找这些六边形侧面上的顶点和边缘的方法，因为这是所有动作的所在。
我的问题是：是否存在一个好的，简单的数据结构来存储六边形网格，同时允许快速查找六边形，六边形之间的边以及六边形相交处的顶点？我知道像翼边或四边这样的一般结构都可以做到这一点，但这似乎是过大的杀伤力。
最佳答案
当您只关心六边形时，用于存储六边形网格的一种简单结构是矩阵，其中（x，y）处的六边形是（x，y±1），（x±1，y）处的六边形的邻居，对于偶数xs为（x±1，y + 1），对于奇数xs为（x±1，y-1）。我们可以发展这个想法，以允许快速查找边缘和顶点。
您还向其中添加了两个矩阵：一个矩阵用于边，另一个矩阵在顶点。
您考虑在（x，y）处由位置（x，2y），（x，2y + 1），（x，2y + 2），（x + 1,2y），（x + 1 ，2y + 1）和（x + 1,2y + 2），甚至xs。对于奇数xs，将1加到y坐标。围绕它的边缘是（2x，2y），（2x，2y + 1），（2x + 1、2y），（2x + 1,2y + 2），（2x + 2,2y）和（2x + 2,2y + 1），如果x为奇数，则加y，从而对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],
};
}
}
内存效率低下，因为从未使用过几个单元，但这不应该成为问题。内存消耗保持在相同的渐近范围内。
10-06 14:09