I'm looking for the most efficient way to generate a hexagonal grid for multiple purposes; games, maps, art, midi, whatever.

I have tried many solutions with a bit of success, but for some reason I was never convinced that they were as efficient or concise as they could have been. Here are a couple of grids I've used to help think about it.









I have mainly used Processing to try ideas but post whatever code you think would work best. TIA

2/1/2013 7:42:59 PM

have you looked at graph databases? I feel like you could easily define a grid via vertex and edge rules, though I'm not sure the drawing would come out how you like

2/1/2013 7:56:11 PM

Hmm no I haven't. Could you elaborate?

2/1/2013 8:03:01 PM

http://en.wikipedia.org/wiki/Graph_database

2/1/2013 8:15:18 PM

I meant with code, but thanks. Checking it out.

2/1/2013 8:33:46 PM

are you just looking to generate the vertex coordinates? what's your input to the algorithm?

if i were solving this, i'd start with say 2 (x,y) coordinates representing the segment closest to the origin, and a matrix of 1s representing how many grids the pattern extended (or you could simplify that if you just need a continuous pattern of N x M grids). are those acceptable input parameters?

[Edited on February 1, 2013 at 9:20 PM. Reason : .]

2/1/2013 8:55:40 PM

I would say
loop to offset even/odd rows { (odd, even even even, ...)}
for (int x=0; x<row.length(); x+=2){vertex = new vertex(x,y)} }

then fill logic for edges

[Edited on February 1, 2013 at 9:58 PM. Reason : .]

2/1/2013 9:47:14 PM

Here is what I'm trying right now. A lot of it isn't necessary but I'm just using different grids as a guide for now. I need to make another list of vectors from the grid of vectors I have now and do like you said alternating even and odd, or just different mod operations. I'm just making the best grid I can and slimming down the code from there.

Quote :

" float n; float a, b; float r = width; float alt = (0.5 * sqrt(3)) * 20; float alt2 = alt*2; ArrayList pvl; PVector p; void setup() { size(740, 740); smooth(); pvl = new ArrayList(); for (float y2 = 0; y2 < height; y2+=alt2) { for (float x2 = 0; x2 < width; x2+=40) { pvl.add(new PVector(x2, y2)); } } } void draw() { background(200); a = 5*PI/3 ; b = (4*PI)/3 ; for (int x = -width; x < width*2; x+=20) { lineAngle(x, 0, a, 2000); lineAngle(x, 0, b, 2000); for (float y = 0; y < height*2; y+=alt) { lineAngle(0, y, 0, 1001); } } pushStyle(); strokeWeight(2); stroke(#00FF00); for (int i = 0; i < pvl.size(); i++) { p = (PVector)pvl.get(i); point(p.x, p.y); if ((i%19)%2==1) { if (i%2==0) ellipse(p.x, p.y, 8, 8); } } popStyle(); } void lineAngle(float x, float y, float angle, float length) { line(x, y, x+cos(angle)*length, y-sin(angle)*length); } "

[Edited on February 1, 2013 at 11:33 PM. Reason : messy]

2/1/2013 11:31:09 PM

Seems like you could use vector math and vector processors to make this insanely processor efficient.

Just start with a matrix of your first shape, then use matrix transforms to blast through the rest.

That's what SIMD units are for.

[Edited on February 1, 2013 at 11:41 PM. Reason : ]

2/1/2013 11:40:03 PM

Isn't that essentially what an ArrayList of PVectors is? Or should I do a multi-dimensional array of PVectors?

2/2/2013 12:42:18 AM

Maybe, but I haven't looked too closely but you should be doing matrix translate and scale operations, and it looks like you're just appending tiles one at a time?

It should take lg(n) operations to generate n tiles.

Start with a set of points for one tile, duplicate it recursively until you have the tiles you need, then draw the resulting vertices.

There may even be a faster way with vector algebra, but I'd have to think about it more...

2/2/2013 1:09:29 PM

Yeah I haven't taken Linear Algebra yet, but I dabbled when I was trying to learn GLSL. Maybe I should try it with that since it has several built-in variables for doing matrix/vector math.

2/2/2013 2:29:02 PM

%!
% hpi = hexes per inch
/hpi 1 def

/scf 72 52 div hpi div def
/mx 612 scf div cvi def
/my 792 scf div cvi def

scf scf scale
0.25 scf div setlinewidth

0 90 mx {
/x exch def
0 52 my {
/y exch def
newpath
x y moveto
15 26 rlineto
-15 26 rlineto
15 -26 rmoveto
30 0 rlineto
15 26 rlineto
-15 -26 rmoveto
15 -26 rlineto
30 0 rlineto
stroke
} for
} for

showpage

2/12/2013 2:06:52 PM

The pygame library might have some helpful stuff in it.

2/12/2013 2:11:06 PM

^^ ooooh, that's a new thing i just learned. Very intriguing...

2/12/2013 4:40:55 PM