likes
comments
collection
share

Hexagonal Grids 六边形 Grid 编程全解

作者站长头像
站长
· 阅读数 32
Mar 2013, updated in Mar 2015

Geometry

Angles

Coordinate Systems

Now let’s assemble hexagons into a grid. With square grids, there’s one obvious way to do it. With hexagons, there are multiple approaches. I recommend using cube coordinates as the primary representation. Use either axial or offset coordinates for map storage, and displaying coordinates to the user.

Offset coordinates

The most common approach is to offset every other column or row. Columns are named col or q. Rows are named row or r. You can either offset the odd or the even column/rows, so the horizontal and vertical hexagons each have two variants.

Cube coordinates

The cube coordinates are a reasonable choice for a hex grid coordinate system. The constraint is that x + y + z = 0 so the algorithms must preserve that. The constraint also ensures that there’s a canonical coordinate for each hex.

There are many different valid cube hex coordinate systems. Some of them have constraints other than x + y + z = 0. I’ve shown only one of the many systems. You can also construct cube coordinates with x-y, y-z, z-x, and that has its own set of interesting properties, which I don’t explore here.

“But Amit!” you say, “I don’t want to store 3 numbers for coordinates. I don’t know how to store a map that way.”

Axes

Offset coordinates are the first thing people think of, because they match the standard cartesian coordinates used with square grids. Unfortunately one of the two axes has to go “against the grain”, and ends up complicating things. The cube and axial systems go “with the grain” and have simpler algorithms, but slightly more complicated map storage. There’s also another system, called interlaced or doubled, that I haven’t explored here; some people say it’s easier to work with than cube/axial.

Offset Cube Axial

The axis is the direction in which that coordinate increases. Perpendicular to the axis is a line where that coordinate stays constant. The grid diagrams above show the perpendicular line.

Coordinate conversion

It is likely that you will use axial or offset coordinates in your project, but many algorithms are simpler to express in cube coordinates. Therefore you need to be able to convert back and forth.

Axial coordinates

Axial coordinates are closely connected to cube coordinates. Axial discards the third coordinate and cube calculates the third coordinate from the other two:

function cube_to_axial(cube):
    var q = cube.x
    var r = cube.z
    return Hex(q, r)

function axial_to_cube(hex):
    var x = hex.q
    var z = hex.r
    var y = -x-z
    return Cube(x, y, z)

Offset coordinates

Determine which type of offset system you use; *-r are pointy top; *-q are flat top:

  •  odd-r  shoves odd rows by +½ column
  •  even-r  shoves even rows by +½ column
  •  odd-q  shoves odd columns by +½ row
  •  even-q  shoves even columns by +½ row
function cube_to_oddr(cube):
      col = cube.x + (cube.z - (cube.z&1)) / 2
      row = cube.z
      return Hex(col, row)

function oddr_to_cube(hex):
      x = hex.col - (hex.row - (hex.row&1)) / 2
      z = hex.row
      y = -x-z
      return Cube(x, y, z)

Implementation note: I use a&1 (bitwise and) instead of a%2 (modulo) to detect whether something is even (0) or odd (1), because it works with negative numbers too. See a longer explanation on my implementation notes page.

Neighbors

Given a hex, which 6 hexes are neighboring it? As you might expect, the answer is simplest with cube coordinates, still pretty simple with axial coordinates, and slightly trickier with offset coordinates. We might also want to calculate the 6 “diagonal” hexes.

Offset coordinates

With offset coordinates, the change depends on where in the grid we are. If we’re on an offset column/row then the rule is different than if we’re on a non-offset column/row.

As above, we’ll build a table of the numbers we need to add to col and row. However this time there will be two arrays, one for odd columns/rows and one for even columns/rows. Look at (1,1) on the grid map above and see how col and row change as you move in each of the six directions. Then do this again for (2,2). The tables and code are different for each of the four offset grid types, so pick a grid type to see the corresponding code.

Using the above lookup tables is the easiest way to to calculate neighbors. It’s also possible to derive these numbers, for those of you who are curious.

Diagonals

Distances

Cube coordinates

Axial coordinates

In the axial system, the third coordinate is implicit. Let’s convert axial to cube to calculate distance:

function hex_distance(a, b):
    var ac = axial_to_cube(a)
    var bc = axial_to_cube(b)
    return cube_distance(ac, bc)

If your compiler inlines axial_to_cube and cube_distance, it will generate this code:

function hex_distance(a, b):
    return (abs(a.q - b.q) 
          + abs(a.q + a.r - b.q - b.r)
          + abs(a.r - b.r)) / 2

There are lots of different ways to write hex distance in axial coordinates, but no matter which way you write it, axial hex distance is derived from the Mahattan distance on cubes. For example, the “difference of differences” described here results from writing a.q + a.r - b.q - b.r as a.q - b.q + a.r - b.r, and using “max” form instead of the “divide by two” form of cube_distance. They’re all equivalent once you see the connection to cube coordinates.

Offset coordinates

As with axial coordinates, we’ll convert offset coordinates to cube coordinates, then use cube distance.

function offset_distance(a, b):
    var ac = offset_to_cube(a)
    var bc = offset_to_cube(b)
    return cube_distance(ac, bc)

We’ll use the same pattern for many of the algorithms: convert hex to cube, run the cube version of the algorithm, and convert any cube results back to hex coordinates (whether axial or offset).

Line drawing

Putting these together to draw a line from A to B:

function lerp(a, b, t): // for floats
    return a + (b - a) * t

function cube_lerp(a, b, t): // for hexes
    return Cube(lerp(a.x, b.x, t), 
                lerp(a.y, b.y, t),
                lerp(a.z, b.z, t))

function cube_linedraw(a, b):
    var N = cube_distance(a, b)
    var results = []
    for each 0 ≤ i ≤ N:
        results.append(cube_round(cube_lerp(a, b, 1.0/N * i)))
    return results

More notes:

  • There are times when cube_lerp will return a point that’s just on the edge between two hexes. Then cube_round will push it one way or the other. The lines will look better if it’s always pushed in the same direction. You can do this by adding an “epsilon” hex Cube(1e-6, 1e-6, -2e-6) to one or both of the endpoints before starting the loop. This will “nudge” the line in one direction to avoid landing on edge boundaries.
  • The DDA Algorithm on square grids sets N to the max of the distance along each axis. We do the same in cube space, which happens to be the same as the hex grid distance.
  • The cube_lerp function needs to return a cube with float coordinates. If you’re working in a statically typed language, you won’t be able to use the Cube type but instead could define FloatCube, or inline the function into the line drawing code if you want to avoid defining another type.
  • You can optimize the code by inlining cube_lerp, and then calculating B.x-A.x, B.x-A.y, and 1.0/N outside the loop. Multiplication can be turned into repeated addition. You’ll end up with something like the DDA algorithm.
  • I use axial or cube coordinates for line drawing, but if you want something for offset coordinates, take a look at this article.
  • There are many variants of line drawing. Sometimes you’ll want “super cover”. Someone sent me hex super cover line drawing code but I haven’t studied it yet.

Movement Range

Coordinate range

Intersecting ranges

Obstacles

Rotation

Rings

Field of view

There are many different ways to define what’s “visible”. Do you want to be able to see the center of the other hex from the center of the starting hex? Do you want to see any part of the other hex from the center of the starting point? Maybe any part of the other hex from any part of the starting point? Are there obstacles that occupy less than a complete hex? Field of view turns out to be trickier and more varied than it might seem at first. Start with the simplest algorithm, but expect that it may not compute exactly the answer you want for your project. There are even situations where the simple algorithm produces results that are illogical.

Clark Verbrugge’s guide describes a “start at center and move outwards” algorithm to calculate field of view. Also see the Duelo project, which has an an online demo of directional field of view and code on Github. Also see my article on 2d visibility calculation for an algorithm that works on polygons, including hexagons. For grids, the roguelike community has a nice set of algorithms for square grids (see this and this and this); some of them might be adapted for hex grids.

Hex to pixel

For hex to pixel, it’s useful to review the size and spacing diagram at the top of the page.

Axial coordinates

If you have a matrix library, this is a simple matrix multiplication; however I’ll write the code out without matrices here. For the x = q, z = r axial grid I use in this guide, the conversion is:

function hex_to_pixel(hex):
    x = size * sqrt(3) * (hex.q + hex.r/2)
    y = size * 3/2 * hex.r
    return Point(x, y)
Axial coordinates: flat top or pointy top

The matrix approach will come in handy later when we want to convert pixel coordinates back to hex coordinates. All we will have to do is invert the matrix. For cube coordinates, you can either use cube basis vectors (x, y, z), or you can convert to axial first and then use axial basis vectors (q, r).

Offset coordinates

For offset coordinates, we need to offset either the column or row number (it will no longer be an integer).

function oddr_offset_to_pixel(hex):
    x = size * sqrt(3) * (hex.col + 0.5 * (hex.row&1))
    y = size * 3/2 * hex.row
    return Point(x, y)
Offset coordinates:   odd-r  even-r  odd-q  even-q 

Unfortunately offset coordinates don’t have basis vectors that we can use with a matrix. This is one reason pixel-to-hex conversions are harder with offset coordinates.

Another approach is to convert the offset coordinates into cube/axial coordinates, then use the cube/axial to pixel conversion. By inlining the conversion code then optimizing, it will end up being the same as above.

Pixel to Hex

One of the most common questions is, how do I take a pixel location (such as a mouse click) and convert it into a hex grid coordinate? I’ll show how to do this for axial or cube coordinates. For offset coordinates, the simplest thing to do is to convert the cube to offset at the end.

-606-615-624-633-642-651-660-5-16-505-514-523-532-541-550-56-1-4-26-4-15-404-413-422-431-440-45-1-46-2-3-36-3-25-3-14-303-312-321-330-34-1-35-2-36-3-2-46-2-35-2-24-2-13-202-211-220-23-1-24-2-25-3-26-4-1-56-1-45-1-34-1-23-1-12-101-110-12-1-13-2-14-3-15-4-16-50-660-550-440-330-220-11xyz01-102-203-304-405-506-61-651-541-431-321-211-1010-111-212-313-414-515-62-642-532-422-312-202-1-120-221-322-423-524-63-633-523-413-303-2-13-1-230-331-432-533-64-624-514-404-3-14-2-24-1-340-441-542-65-615-505-4-15-3-25-2-35-1-450-551-66-606-5-16-4-26-3-36-2-46-1-560-6
  1. First we invert the hex to pixel conversion. This will give us a fractional hex coordinate, shown as a small blue circle in the diagram.
  2. Then we find the hex containing the fractional hex coordinate, shown as the highlighted hex in the diagram.

There are many other ways to convert pixel to hex; see this page for the ones I know of.

Rounding to nearest hex

Sometimes we'll end up with a floating-point cube coordinate (x, y, z), and we’ll want to know which hex it should be in. This comes up in line drawing and pixel to hex. Converting a floating point value to an integer value is called rounding so I call this algorithm cube_round.

With cube coordinates, x + y + z = 0, even with floating point cube coordinates. So let’s round each component to the nearest integer, (rx, ry, rz). However, although x + y + z = 0, after rounding we do not have a guarantee that rx + ry + rz = 0. So we reset the component with the largest change back to what the constraint rx + ry + rz = 0 requires. For example, if the y-change abs(ry-y) is larger than abs(rx-x) and abs(rz-z), then we reset ry = -rx-rz. This guarantees that rx + ry + rz = 0. Here’s the algorithm:

function cube_round(cube):
    var rx = round(cube.x)
    var ry = round(cube.y)
    var rz = round(cube.z)

    var x_diff = abs(rx - cube.x)
    var y_diff = abs(ry - cube.y)
    var z_diff = abs(rz - cube.z)

    if x_diff > y_diff and x_diff > z_diff:
        rx = -ry-rz
    else if y_diff > z_diff:
        ry = -rx-rz
    else:
        rz = -rx-ry

    return Cube(rx, ry, rz)

For non-cube coordinates, the simplest thing to do is to convert to cube coordinates, use the rounding algorithm, then convert back:

function hex_round(hex):
    return cube_to_axial(cube_round(axial_to_cube(hex)))

The same would work if you have oddr, evenr, oddq, or evenq instead of axial.

Implementation note: cube_round and hex_round take float coordinates instead of int coordinates. If you’ve written a Cube and Hex class, they’ll work fine in dynamically languages where you can pass in floats instead of ints, and they’ll also work fine in statically typed languages with a unified number type. However, in most statically typed languages, you’ll need a separate class/struct type for float coordinates, and cube_round will have type FloatCube → Cube. If you also need hex_round, it will be FloatHex → Hex, using helper function floatcube_to_floathex instead of cube_to_hex. In languages with parameterized types (C++, Haskell, etc.) you might define Cube<T> where T is either int or float. Alternatively, you could write cube_round to take three floats as inputs instead of defining a new type just for this function.

Map storage in axial coordinates

One of the common complaints about the axial coordinate system is that it leads to wasted space when using a rectangular map; that's one reason to favor an offset coordinate system. However all the hex coordinate systems lead to wasted space when using a triangular or hexagonal map. We can use the same strategies for storing all of them.

Notice in the diagram that the wasted space is on the left and right sides of each row (except for rhombus maps) This gives us three strategies for storing the map:

  1. Ignore the problem. Use a dense array with nulls or some other sentinel at the unused spaces. At most there’s a factor of two for these common shapes; it may not be worth using a more complicated solution.
  2. Use a hash table instead of dense array. This allows arbitrarily shaped maps, including ones with holes. When you want to access the hex at q,r you access hash_table(hash(q,r)) instead. Encapsulate this into the getter/setter in the grid class so that the rest of the game doesn’t need to know about it.
  3. Slide the rows to the left, and use variable sized rows. In many languages a 2D array is an array of arrays; there’s no reason the arrays have to be the same length. This removes the waste on the right. In addition, if you start the arrays at the leftmost column instead of at 0, you remove the waste on the left.

    To do this for arbitrary convex shaped maps, you’d keep an additional array of “first columns”. When you want to access the hex at q,r you access array[r][q - first_column[r]] instead. Encapsulate this into the getter/setter in the grid class so that the rest of the game doesn’t need to know about it. In the diagram first_column is shown on the left side of each row.

    If your maps are fixed shapes, the “first columns” can be calculated on the fly instead of being stored in an array.

    • For rectangle shaped maps, first_column[r] == -floor(r/2), and you’d end up accessing array[r][q + r/2], which turns out to be equivalent to converting the coordinates into offset grid coordinates.
    • For triangle shaped maps as shown here, first_column[r] == 0, so you’d access array[r][q] — how convenient! For triangle shaped maps that are oriented the other way (not shown in the diagram), it’s array[r][q+r].
    • For hexagon shaped maps of radius N, where N = max(abs(x), abs(y), abs(z), we have first_column[r] == -N - min(0, r). You’d access array[r][q + N + min(0, r)]. However, since we’re starting with some values of r < 0, we also have to offset the row, and use array[r + N][q + N + min(0, r)].
    • For rhombus shaped maps, everything matches nicely, so you can use array[r][q].

Wraparound maps

Pathfinding

More

I have an guide to implementing your own hex grid library, including sample code in C++, Java, C#, Javascript, Haxe, and Python.

The code that powers this page is written in a mixture of Haxe and Javascript: Cube.hx, Hex.hx, Grid.hx, ScreenCoordinate.hx, ui.js, and cubegrid.js (for the cube/hex animation). However, if you are looking to write your own hex grid library, I suggest instead looking at my guide to implementation.

There are more things I want to do for this guide. I’m keeping a list on Trello. Do you have suggestions for things to change or add? Comment below.

转载自:https://juejin.cn/post/6844903497234645006
评论
请登录