Hexagonal coordinate system

[NickThissen]

Hi,

I have always wanted to write a simple version of the Settlers of Catan game and I keep finding myself coming back to it after giving up...

This time I thought I'd start with a solid basis, and I think this would be an interesting problem to post here...

As most of you probably know, the Settlers of Catan game has a hexagonal grid of tiles:
http://www.mrbass.org/games/sea3d/01startinggame.jpg

I have tried implementing hexagonal tiles in WPF (though I think I'm staying with Winforms this time, not important though) where I simply drew the tiles as rows, where each odd tile in the row was offset by half the tile height. That works quite well for drawing the game board in itself, but as I found out, it is a giant pain to draw the game pieces on this board, because finding their positions (where to draw them) is quite difficult... If you are not familiar with the game, read on, you will understand why quickly.



So, I want to come up with a solid basis that allows me to easily find the X and Y coordinates of the position where I want to draw a game piece, based on (1) a tile coordinate and (2) a special position on that tile.


For numbering the tiles, I have done a quick search on hexagonal coordinate systems, and this seems to be the easiest numbering system. Basically a skewed x,y system, such as this:

The blue tiles are the boundaries of the playing board (they depict water). White tiles in between the blue boundaries are playing tiles, white tiles outside of the blue boundaries aren't really part of the board, but doesn't really matter.

As you can see each tile has a unique coordinate (x,y).

The problem is that the game needs to draw pieces on various positions along any of these tiles. I've depicted this here:


The red dots are the (center) positions where I need to draw game pieces, the red rectangles depict rectangles that I will have to draw.


My problem now is two-fold

(1) How would I number these positions in a clever way?
For example, suppose I want to reference the bottom-right corner of the hexagon at position (-1,2). I could give each corner a number (0-5), such that the bottom-right corner would for example be 5 (see image). Then the corner I need is at position (-1,2,5), meaning tile (-1,2) and corner 5.

Of course, these corners share tiles. Corner 5 (bottom-right) of tile (-1,2) is the same point as corner 1 of tile (-1,1) and corner 3 of tile (0,1).
(-1,2,5) = (-1,1,1) = (0,1,3).

There must be some kind of mathematical relation between these corners, yet I can't find it. This system seems really redundant and inefficient.


(2) How do I transform these hexagonal coordinates into traditional (x,y) orthogonal coordinate system used by winforms, so I can draw images there?

For example, suppose I want to draw an image on the bottom-left corner of tile (0,-1), that would be hexagonal position (0,-1,4). How does (0,-1,4) transform to (x,y) in orthogonal coordinates? I'll need some kind of transformation to transform (a,b,c) in hexagonal coordinates to (x,y) in orthogonal coordinates.

Of course, I could derive this transformation with the system I currently devised, but I doubt my system is very efficient, there must be a better way?



I thought this was an interesting problem to post here. I will continue working on this, but if anyone has anything to say about it, please! As I said, my system is probably not very good, if anyone knows a better system that would be great....

Thanks!

[NickThissen]

Just to clarify, my ultimate goal is to come up with something that I can use (in VB.NET code, for example) like this:

Dim tilePosition As TilePosition = New TilePosition(-1, 2, 5) 'tile (-1,2), corner 5
Dim position As Point = TileToPoint(tilePosition)
 
e.Graphics.DrawImage(img, position)

Private Function TileToPoint(ByVal tilePosition As TilePosition) As Point
   Dim x As Integer = SomeFancyFormula(tilePosition.A, tilePosition.B, tilePosition.C)
   Dim y As Integer = SomeOtherFancyFormula(tilePosition.A, tilePosition.B, tilePosition.C)
   Return New Point(x, y)
End Function

[Milk]

I've had a play with this (I think following your WPF post) although I was working with a system at 90° to yours.

From what I remember I had a class which stored the cell size, the width of the hex grid, and each hex cell in a flat 1D array. It had some methods to convert the cell index into inverted y Cartesian coordinates and visa versa. I can't look it up now without disturbing a sleeping guest but I will have a look tomorrow.

[Logophobic]

For center of tile:

x = 3 * Tile.x
y = 2 * Tile.y + Tile.x

Add to this an offset for the corner:

( 2,  0) for corner 0
( 1,  1) for corner 1
(-1,  1) for corner 2
(-2,  0) for corner 3
(-1, -1) for corner 4
( 1, -1) for corner 5

Return scaled value:

Return New Point(x * 100, y * 173)

[NickThissen]

I've had a play with this (I think following your WPF post) although I was working with a system at 90° to yours.

From what I remember I had a class which stored the cell size, the width of the hex grid, and each hex cell in a flat 1D array. It had some methods to convert the cell index into inverted y Cartesian coordinates and visa versa. I can't look it up now without disturbing a sleeping guest but I will have a look tomorrow.

Thanks! Most sources I find seem to use the rotated system. I suppose it doesn't really matter, but I'd like to use my system since that's what the game uses. The logic is the same in the end though so I should be able to adapt...

For center of tile:

x = 3 * Tile.x
y = 2 * Tile.y + Tile.x

Add to this an offset for the corner:

( 2,  0) for corner 0
( 1,  1) for corner 1
(-1,  1) for corner 2
(-2,  0) for corner 3
(-1, -1) for corner 4
( 1, -1) for corner 5

Return scaled value:

Return New Point(x * 100, y * 173)

Thanks. That would be the easy way out. The problem here is that you are putting the corners of your hexagonal tiles on a rectangular grid. As far as I know that's impossible for real hexagons. Your hexagons are slightly 'squashed'. If you use hexagons where each side length is the same (there's probably a word for that...) then you can't put the points on a square grid so your 'formulas' become very different, right?



I found a new source that does seem to say something about the corners as well. Most sources I found deal only with the hexagonal tiles themselves but not the location of the corners, center, origin, etc. This one does:
http://jemgine.omnisu.com/?page_id=412
Seems like a good start.

[Milk]

hmm, I did not get all that far now I've had a look although there is some logic that might be useful.

I always prefer to work with one dimensional arrays, it is a little bit of extra work but it often ends up with simpler code. The following images show what I mean.

Grid with an even width of 2


Grid with an odd width of 3


Logic to find adjoining indexes. y&1 <--bitwise And


The red dot in 3rd image is the tile rendering point I would want to derive from the index (i), all other points relating to that hex cell are simple offsets from that point.

The relationship between the green grid of rectangles and hex grid is what I was looking at to convert coordinates, the yellow lines indicate a zone where and extra calculation is needed determine which hex row the point falls into.

I'll look at this some more later...

[NickThissen]

I have gotten a bit further with some code based on the last source I gave. I have a class Hexagon that has a couple properties such as Center, Origin (top-left point, actually outside the hexagon) and a property Corners which returns an array with the 6 corner points. All these properties are of type Vector which is basically a Point except with double values (X and Y). Besides these a Hexagon also has a property I and J which indicate the tile coordinate in the system I decided with in my first image (except that the origin (0,0) is at the top-left now).

Every value can be calculated from the 'radius' of the hexagons, which is the distance between the center and either of the vertices.


From this I have been able to draw a map of hexagons and even draw some points on the vertices and in the center of the hexagons. I'd say that is pretty much all I need as far as drawing the grid goes. The next step is handling mouse events, I want to know when a user clicks in the center of a tile, or on a vertex (and on which vertex), or on an edge (and which edge). I'll look at that later... It shouldn't be too hard, I have the coordinates of the vertices, all I need is to check if the mouse click is within a certain radius of them. Then I can loop through my list of hexagons, and for each hexagon I check each Corner coordinate. If that coordinate is within a certain amount of radius from the mouse click, I consider that vertex clicked. That should give me 3 hexagons that match this condition (unless I'm at the edge of the grid).

[Logophobic]

...you are putting the corners of your hexagonal tiles on a rectangular grid. As far as I know that's impossible for real hexagons. Your hexagons are slightly 'squashed'.

It is possible, my image is proof. The scaled value I gave as an example stretches the grid vertically, resulting in regular hexagons on a rectangular grid.

If you use hexagons where each side length is the same (there's probably a word for that...) then you can't put the points on a square grid so your 'formulas' become very different, right?

The word is 'regular' and means not only equal side lengths, but also equal angles. While it is true that the points of regular hexagons cannot be placed on a square grid, the square grid still provides an accurate representation of the hexagon grid. My 'formula' accounts for this in returning a scaled value:

Return New Point(x * 100, y * 173)