卡坦图定居者的数据结构？ [英] Data structure for Settlers of Catan map?
问题描述
我的问题是这是：有一个很好的简单的数据结构，用于存储六边形网格，同时允许快速查找六边形，六边形之间的边缘以及六边形交点处的顶点？我知道一般结构像翼边缘或四边形可以做到这一点，但这似乎是巨大的过度杀伤力。
当您只关心六边形时，存储六边形网格的简单结构是一个矩阵，其中（x，y）处的六边形是（x，y±1），（x±1，y）处的六边形的邻居，对于偶数xs，（x±1，y + 1）或（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）。对于奇数x，将y加1。周围的边缘是（2x，2y），（2x，2y + 1），（2x + 1,2y），（2x + 1,2y + 2），（2x + 2,2y）和（2x + 2,2y + 1），如果x是奇数，则通过添加一个来增加一个y。这给出了给定的边和顶点的常量随机访问六边形（您也可以计算坐标变换以进行反向查找）。
使用一些更简单的公式，您可以从顶点查找边，从顶点读取六边形，你可能需要玩其他的查找游戏。
这样你就可以用数组来代表棋盘，用简单的数学方法进行查找，以便在六角坐标 ，边缘坐标和顶点坐标。
由于该板不能完美地适合（矩形）矩阵，您需要填充几个单元格一些空或无效值，表示与电路板六边形不匹配的边界单元格的对。
Asympto这个方法使用内存线性的十六进制数，并给出任何查找的恒定时间。
这里有一些例子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]; （int i = 0; i< 10; i ++）
for（int j = 0; j< 10 ; j ++）
Hexes [i，j] = new Hex {X = i，Y = j}; （int i = 0; i <22; i ++）
（int j = 0; j <22; j ++）
{
Edges [i，j ] = new Edge {X = i，Y = j};
顶点[i，j] =新的顶点{X = i，Y = j};
}
}
public IEnumerable&Hex GetNeighbors（十六进制十六进制）
{
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（十六进制十六进制）
{
var x = hex.X; var y = hex.Y;
var offset = x％2;
return new []
{
顶点[x，2 * y + offset]，
顶点[x，2 * y + 1 + offset]，
顶点[x，2 * y + 2 + offset]，
顶点[x + 1,2 * y + offset]，
顶点[x + 1,2 * y + 1 + offset]，
顶点[x + 1,2 * y + 2 + offset]，
};
}
public IEnumerable< Edge> GetEdges（十六进制十六进制）
{
var x = hex.X; var y = hex.Y;
var offset = x％2;
return new []
{
边缘[2 * x，2 * y +偏移]，
边缘[2 * x，2 * y + 1 +偏移]，
边缘[2 * x + 1,2 * y +偏移]，
边缘[2 * x + 1,2 * y + 2 +偏移]，
边缘[2 * x + 2 ，2 * y + offset]，
边缘[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 []
{
顶点[x / 2，y]，
顶点[x / 2，y +1]，
};
else
return new []
{
顶点[（x-1）/ 2，y]，
顶点[（x + 1）/ 2，y ]，
};
}
public IEnumerable< Edge> GetEdges（顶点顶点）
{
var x = vertex.X; var y = vertex.Y;
return new []
{
边缘[x * 2，y]，
边[x * 2 + 1，y]，
边[x * 2 -1，y]，
};
}
public IEnumerable< Hex> GetHexes（顶点顶点）
{
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]，
};
}
}
有一些内存无效率，因为几个单元格从不使用，但这不应该是一个问题。记忆消耗量保持在相同的渐近界限。
A while back someone asked me if I knew of a nice way to encode the information for the game Settlers of Catan. This would require storing a hexagonal grid in a way where each hex can have data associated with it. More importantly, though, I would need some way of efficiently looking up vertices and edges on the sides of these hexagons, since that's where all the action is.
My question is this: is there a good, simple data structure for storing a hexagonal grid while allowing for fast lookup of hexagons, edges between hexagons, and vertices at the intersections of hexagons? I know that general structures like a winged-edge or quad-edge could do this, but that seems like massive overkill.
A simple structure to store an hexagonal grid when you care only about hexagons, is a matrix, with an hexagon at (x,y) being a neighbor of hexagons at (x, y±1), (x±1,y), and (x±1,y+1) for even xs or (x±1,y-1) for odd xs. We can evolve this idea to allow fast lookup of edges and vertices.
You add two other matrices to this: one for edges, and another for vertices.
You consider an hexagon at (x,y) delimited by the vertices at positions (x,2y), (x,2y+1), (x,2y+2), (x+1,2y), (x+1,2y+1), and (x+1,2y+2), for even xs. For odd xs, add 1 to the y coordinate. The edges surrounding it are those at (2x,2y), (2x,2y+1), (2x+1, 2y), (2x+1,2y+2), (2x+2,2y), and (2x+2,2y+1), with an additional adjustment to y by adding one if x is odd.
This gives you constant time random access to edges and vertices given an hexagon (and you can work out the coordinate transformations to do the reverse lookup as well).
With some more simple formulas you can lookup edges from vertices, hexes from vertices, and other lookups you may need to play the game.
This way you can represent the board with nothing but arrays and do lookups with simple math to transform between "hexagon coordinates", "edge coordinates", and "vertex coordinates".
Because the board will not fit a (rectangular) matrix perfectly, you will need to fill a couple of cells with some "empty" or "invalid" value, to represent the couple of borderline cells that have mismatch the hexagonal shape of the board.
Asymptotically, this method uses memory linear on the number of hexes, and gives constant time for any lookup.
Here's some example C# code:
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],
};
}
}
There is some memory inefficiency because a few cells are never used, but that shouldn't be a problem. The memory consumption remains under the same asymptotic bound.
这篇关于卡坦图定居者的数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
