# Need help with an algorithm

This site uses cookies. By continuing to browse this site, you are agreeing to our Cookie Policy.

• # Need help with an algorithm

I am translating a hex based board game into a turn based 2D computer game. The map will be a hex grid with vertical hexes. I know how to convert from pixels to hex when the user clicks on a hex but I am having trouble figuring out the center location of a hex. I would like to develop a routine that when passed a hex location ex. row 1, hex 1, I can return the center pixel of that hex for the placement of the tile. Can anyone help me out? I tried a few sites on the internet and learned about hex based games but found nothing on calculating the center point of a hex.
• To make sure I understand, you are already able to zero in on which hex the mouse is clicked on?

How are your hexes represented in code? Is each hex an indivdual object, or are you making a mathematical assumption about a tesselation of hexes?
• Yes I am able to figure out the hex based upon the pixel clicked. I have a class called CHex that has as members, int row and int col. I then have an array as such CHex map[# of rows][# of cols].
• are row and col the only properties of class CHex? If so, then you have two choices: 1) perform a mathematical assumption given your row and col on where the center of the hex is or 2) since you are already drawing those Hexes, and you have a means of mouse-picking them, add more members to class CHex that include a member variable that denotes the positional center of the CHex object.

My vote is option 2, even though you may be duplicating data. Then your flow of data would be along the lines of....
mouse position -> CHex object -> center location.

Is there any particular reason why you can't store the center location within the CHex object while you are forming the grid? (i.e. CHex::SetCenter ?)

The post was edited 1 time, last by Kain ().

• I thought of that but it means that I have to know each center of the hex myself and store it in a table where I am reading the row and col information from. I was just hoping to calculate the center on the fly based on knowing the row and col.
• So you're set on option 1, eh? ok. Any chance you can post a pic of the grid? This forum accepts attachments if you zip them.
• Unfortunately even zipped the bmp is huge as the game map is huge. I can tell you the dimensions though of each hex. The hex is 61 pixels wide by 71 pixels high. The dimensions of the center portion of the hex are 61 pixels wide by 33 pixels high. There is a East, west, NW, NE, SW, SE side to the hex.
• In order to go from row,col to hex center, we'd need to know how the hexes are arranged in relation to each other. So are adjacent rows and columns staggered as in a honeycomb? What is the overall shape of the hex grid? Is it rectangular or do they form one giant hex? If it is rectangular, what do the corners look like? Is row 0 staggered left of row 1 or right of row 1? Is col 0 staggered higher than col 2 or lower than col 2? Might you be able to take a snapshot of each of the four corners of that grid and zip them up into this thread?
• BTW, the reason I'm asking so many questions is because deriving a formula for your algorithm sounds really fun
• Here is a small piece of the upper left hand corner of the map. I scanned the board map into the computer and then I am bringing the map into Photoshop and creating a layer over it. I will then color the map using Photoshop and then delete the bottom layer. It was too complicated of a map to create from scratch on the computer and the publisher of the board game did not have an electronic version of the map.
• Hmmm, if you're going to scan the paper map into digital form, then there's a high chance that a mathematical calculation of the hex's center will be inconsistent with the graphical representation due to variances in the digital conversion process of the physical medium.

This formula will be an approximation of that graphical transfer at best.

Correct me if I'm wrong on these known values:
• Center00 - The constant center x,y position of the Hex at row0, column0
• Center11 - The constant center x,y position of the Hex at row1, column1. Hex11 is diagonally adjacent to Hex00.
• dX = Center11.x - Center00.x;
• dY = Center11.y - Center00.y;
• r - the integer row index of the Hex, corresponds to y position. If two Hexes are in the same row, then y position is the same for those two. Two Hexes in adjacent rows cannot be in the same column.
• c - the integer column index of the Hex, corresponds to x position. If two Hexes are in the same column, the x position is the same for those two. Two Hexes in adjacent columns cannot be in the same row.

Goal: Find the x,y position of the center of the Hex denoted by the given r and c.

Solution:

### Source Code

1. Center.x = c * dX + Center00.x;
2. Center.y = r * dY + Center00.y;

So that's it... although we can make some further assumptions about dX, dY, and Center11 if we assume that the hexagons are regular polygons (all sides equivalent) and that we know the length of one side of that hexagon. Let's call that length of a single side, L.

We also know that each angle on the Hex is 120-degrees. We know this because if you draw a line from the center of the Hex to make six triangles, you get six equilateral triangles, based on the fact that 360/6 = 60 and all angle in a triangle must add up to 180.

So now, if you slice the vertical Hex with two horizontal lines, you get three sections. We know that the height of the center section is L, because that is the length of a side. The height of the top and bottom portions will both be the same. Since we know the relevant angles and L, we can use trigonometry to yield the following height for the each non-middle portion of the Hex:

### Source Code

1. L * sin(30 degrees)

We know that sin(30 degrees) = 0.5

### Source Code

1. L / 2

This brings the total height of the vertical Hex to

### Source Code

1. Height = L + 2*(L / 2) = 2*L

If you plug in your L value of 33 pixels, you get a height of 66 pixels. Since you've previous indicated tht the Hex is 71 pixels high, then we already have a measurement error somewhere, either in the value of L or your measured overall height for a single Hex.

The overall width of a single Hex can also be solved with trigonometry knowing that the top portion is made from 2 back-to-back 30-60-90 triangles:

### Source Code

1. Width = 2 * L * sin(60 degrees)

Plugging your value of L into the formula yields

### Source Code

1. Width = 2 * 33 * sin(60 degrees) = 57.157676649772950686405729269694

This is inconsistent with your measured value of 61 pixels wide.

Looking at that bitmap you provided, we can say that

### Source Code

1. dX = Width/2
2. dX = 2 * L * sin(60 degrees) /2
3. dX = L * sin(60 degrees)
4. dY = MiddleHeight/2 + TopHeight + MiddleHeight/2
5. dY = MiddleHeight + TopHeight
6. dY = L + L/2

Since your algorithm will be dependent on having the most accurate possible values for your dX and dY constant, your best bet is to calculate those values based on aggregate data.

So let's say that your maximum value of r and c are rMax and cMax. Find the center of the Hex at these maximum values.

### Source Code

1. CenterMax.x = cMax * dX + Center00.x;
2. CenterMax.y = rMax * dY + Center00.y;

### Source Code

1. (CenterMax.x - Center00.x) / cMax = dX;
2. (CenterMax.y - Center00.y) / rMax = dY;

At this point, I realize that all that trigonometry is only useful if you want to get an accurate depiction of L based on your measured values of dX and dY.

### Source Code

1. dX / sin(60 degrees) = L
2. 2 * dY / 3 = L

or if you just want to see if your calculated values of dX and dY are mathematically accurate:

### Source Code

1. dX / sin(60 degrees) = 2 * dY / 3

Gosh, I really hope I answered the right question. Reguardless, this was kind of fun.

The post was edited 2 times, last by Kain ().