Math Question

I’ve got a problem for you math types out there, I’m hoping you can help me out with.

I’m currently writing a video game in my spare time (which is copious at the moment, due to difficulties finding anyone willing to pay me to make video games). The game uses a hex grid for movement, like this one. Except bigger - about 4000 hexes. Each hex has a number, starting with the upper leftmost hex, and going down each column. I use that number to place the player’s token on the map. I also want to use this for movement, which should be pretty simple. If the player moves up one hex, decrease his location by one. If he goes down a hex, increase it by one. It’s the diagonals that are tricky, and this is where I’ve run into a problem: my columns aren’t all the same length. The even columns are all one hex shorter than the odd columns. If they were all the same length, I could handle the diagonals by adding or subtracting the length of the column (plus or minus one, as necessary). But the alternating lengths means that I need to use a different formula if I’m moving from an even column, or an odd column.

So, here’s my question. Given a grid consisting of X hexagons, with each column in the grid alternating between being Y hexes long, and Y-1 hexes long, is there a way to determine if a given number is in an odd column, or an even column?

(I realize the easiest answer would be to just make all the columns the same length. Unfortunately, it’s too late to change that now, without having to substantially rework other portions of the game.)

A simple such predicate might be
(x mod (2*Y-1)) >= Y

But, if it’s not too late, adding a Y’th dummy entry to the short rows, and masking it out as needed might be simpler.

(BTW, once upon a time I developed various software and techniques specific to hexagon grid.)

SPI, back in the 1970’s, solved it by giving each hex a four digit number. Hex 1712 was twelve down in the 17th row across.

How do you number across columns? If I’m in hex 1, that’s the (say) upper left hex. Hex 2 is the one below that. Hex 3, the one below that, etc. Hex Y is the bottom-most hex in the first column.

Is hex Y+1 the top hex in the second column?

If so, you can determine the column of hex n by repeatedly, and alternatingly, adding Y, and Y-1, until you get a sum greater than n.

Say Y is 50, so your columns alternate between 50 and 49 hexes in height.

Take hex 189.

50? Too small: not in column 1.
50 + 49 = 99. Too small: not in column 2.
50 + 49 + 50 = 149. Too small: not in column 3.
50 + 49 + 50 + 49 = 198. Aha! Greater than 189, and in column 4.

198 - 189 = 9. n is the 9th hex down, in column 4.

Easy loop algorithm.

And I’ve probably completely misunderstood your question. And also been ninjaed six ways to Sunday!

ETA: and counted wrong, to boot!

NETA: You probably handle even/odd rows differently to get different diagonal indexing formulae. This wasn’t necessary in my routines: dummy cells were added to make all rows “smell the same.”

Question: Square grids have well known names for the four directions: {Left, Top, Right, Bottom} or {W, N, E, S}. AFAIK, there are no good names for the six directions in a hex grid.

Unfortunately, it is too late. The hex grid serves as a fog of war over a map of the city the player is exploring. When he enters a hex, the hex turns transparent, revealing the city underneath. Unfortunately, I’ve already written a ton of content for encounters in the city, which are tied to the hexes. If I even out the rows, the hexes with the encounters are no longer going to be over the proper buildings on the map. I could go back and renumber all the encounters, but that would be an enormous pain in the ass - and the third time I’ve had to do it already. :smack:

Compass directions work fine - just leave out two of them, depending on the orientation of the hexes. I’m using NW, N, NE, SE, S, SW.

Yep. The four digit numbering solution is good - I’ve seen it used on paper hex maps in table top gaming before. Keeping the hexes sequential makes it much easier to store and access them from an array, though. The 1574th hex in the array is hex number 1574.

You may have totally misunderstood my question, but you still gave me a useful answer!

Thanks to both of you for the help!

That’s the same approach I used, but I’d call it “fine” only for small values of “fine.” :wink:

In a 12-direction topology I’d not be ashamed to use signs of the Zodiac! But I’ve never stumbled on a sextet or hexad that seemed similarly appropriate.

First consider the grid as if the even column is shifted down , all the way down out from being between the odd columns, and actually moved over a lit to be directly below the odd column…so we now have half the number of columns, and each pseudo-column is then of size 2Y - 1.

x divide (2Y -1 ) (truncated divide) tells us which pseudo-column x is in.
x mod (2Y -1 ) ( mod … the remainder) tells us where in the pseudo-column x is ,

And decode the “where”… ( 0 to Y-1) being the odd column, and (Y to 2Y-2 ) being the even column.

You probably qualify for some sort of prize for subject-vs-(username - 1). :smiley:

But with a four-digit numbering system, hex 0739 is just the (7,39) hex in a 2-D array. What’s hard about that?

Sure, it means you potentially have unused entries in the 2-D array if your borders aren’t rectangular, but so what? Memory is cheap these days; the hours programmers spend figuring out how to code and then debug things like your question are not cheap, generally.

A 2-D array makes it much easier to resize the map, or fiddle with the borders, without having to renumber everything. And when you realize that on a 2-D map, identifying a location with a pair of numbers makes more sense than a single number, you can free yourself to do things like, for instance, making the center of the map (0,0) and going negative one way and positive the other, or allowing for multiple maps by adding a third number to the array.