Data structure for Settlers of Catan map? -
this question has answer here:
a while asked me if knew of nice way encode information game settlers of catan. require storing hexagonal grid in way each hex can have data associated it. more importantly, though, need way of efficiently looking vertices , edges on sides of these hexagons, since that's action is.
my question this: there good, simple data structure storing hexagonal grid while allowing fast lookup of hexagons, edges between hexagons, , vertices @ intersections of hexagons? know general structures winged-edge or quad-edge this, seems massive overkill.
a simple structure store hexagonal grid when care hexagons, matrix, hexagon @ (x,y) being neighbor of hexagons @ (x, y±1), (x±1,y), , (x±1,y+1) xs or (x±1,y-1) odd xs. can evolve idea allow fast lookup of edges , vertices.
you add 2 other matrices this: 1 edges, , vertices.
you consider hexagon @ (x,y) delimited vertices @ positions (x,2y), (x,2y+1), (x,2y+2), (x+1,2y), (x+1,2y+1), , (x+1,2y+2), xs. odd xs, add 1 y coordinate. edges surrounding @ (2x,2y), (2x,2y+1), (2x+1, 2y), (2x+1,2y+2), (2x+2,2y), , (2x+2,2y+1), additional adjustment y adding 1 if x odd.
this gives constant time random access edges , vertices given hexagon (and can work out coordinate transformations reverse lookup well).
with more simple formulas can lookup edges vertices, hexes vertices, , other lookups may need play game.
this way can represent board nothing arrays , lookups simple math transform between "hexagon coordinates", "edge coordinates", , "vertex coordinates".
because board not fit (rectangular) matrix perfectly, need fill couple of cells "empty" or "invalid" value, represent couple of borderline cells have mismatch hexagonal shape of board.
asymptotically, method uses memory linear on number of hexes, , gives constant time lookup.
here's 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 = 0; < 10; i++) for(int j = 0; j < 10; j++) hexes[i,j] = new hex { x = i, y = j }; for(int = 0; < 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 memory inefficiency because few cells never used, shouldn't problem. memory consumption remains under same asymptotic bound.
Comments
Post a Comment