Advertisement
  1. Game Development
  2. Game Development
Gamedevelopment

Hexagonal Character Movement Using Axial Coordinates

by
Difficulty:IntermediateLength:LongLanguages:
Final product image
What You'll Be Creating

In the first part of the series, we explored the different coordinate systems for hexagonal tile-based games with the help of a hexagonal Tetris game. One thing you may have noticed is that we are still relying on the offset coordinates for drawing the level onto the screen using the levelData array. 

You may also be curious to know how we could determine the axial coordinates of a hexagonal tile from the pixel coordinates on the screen. The method used in the hexagonal minesweeper tutorial relies on the offset coordinates and is not a simple solution. Once we figure this out, we will proceed to create solutions for hexagonal character movement and pathfinding.

1. Converting Coordinates Between Pixel and Axial

This will involve some math. We will be using the horizontal layout for the entire tutorial. Let's start by finding a very helpful relationship between the regular hexagon's width and height. Please refer to the image below.

Hexagonal tile its angles  lengths are displayed

Consider the blue regular hexagon on the left of the image. We already know that all the sides are of equal length. All the interior angles are 120 degrees each. Connecting each corner to the centre of the hexagon will yield six triangles, one of which is shown using red lines. This triangle has all the internal angles equal to 60 degrees. 

As the red line splits the two corner angles in the middle, we get 120/2=60. The third angle is 180-(60+60)=60 as the sum of all angles within the triangle should be 180 degrees. Thus essentially the triangle is an equilateral triangle, which further means that each side of the triangle has the same length. So in the blue hexagon the two red lines, the green line and each blue line segment are of the same length. From the image, it is clear that the green line is hexTileHeight/2.

Proceeding to the hexagon on the right, we can see that as the side length is equal to hexTileHeight/2, the height of the top triangular portion should be hexTileHeight/4 and the height of the bottom triangular portion should be hexTileHeight/4, which totals to the full height of the hexagon, hexTileHeight

Now consider the small right-angled triangle in the top left with one green and one blue angle. The blue angle is 60 degrees as it is the half of the corner angle, which in turn means that the green angle is 30 degrees (180-(60+90)). Using this information, we arrive at a relationship between the height and width of the regular hexagon.

Converting Axial to Pixel Coordinates

Before we approach the conversion, let's revisit the image of the horizontal hexagonal layout where we have highlighted the row and column in which one of the coordinates remains the same.

Horizontal hexagonal layout with rows and columns highlighted where coordinates remain same

Considering the screen y value, we can see that each row has a y offset of 3*hexTileHeight/4, while going down on the green line, the only value that changes is i. Hence, we can conclude that the y pixel value only depends on the axial i coordinate.

Where s is the side length, which was found to be hexTileHeight/2.

The screen x value is a bit more complicated than this. When considering the tiles within a single row, each tile has an x offset of hexTileWidth, which clearly depends only on the axial j coordinate. But each alternative row has an additional offset of hexTileWidth/2 depending on the axial i coordinate.

Again considering the green line, if we imagine it was a square grid then the line would have been vertical, satisfying the equation x=j*hexTileWidth. As the only coordinate that changes along the green line is i, the offset will depend on it. This leads us to the following equation.

So here we have them: the equations to convert axial coordinates to screen coordinates. The corresponding conversion function is as below.

The revised code for drawing the hexagonal grid is as follows.

Converting Pixel to Axial Coordinates

Reversing those equations with the simple substitution of one variable will lead us to the screen to axial conversion equations.

Although the required axial coordinates are integers, the equations will result in floating point numbers. So we will need to round them off and apply some corrections, relying on our main equation x+y+z=0. The conversion function is as below.

Check out the interactive element, which uses these methods to display tiles and detect taps.

2. Character Movement

The core concept of character movement in any grid is similar. We poll for user input, determine the direction, find the resulting position, check if the resulting position falls inside a wall in the grid, else move the character to that position. You may refer to my isometric character movement tutorial to see this in action with respect to isometric coordinate conversion. 

The only things that are different here are the coordinate conversion and the directions of motion. For a horizontally aligned hexagonal grid, there are six available directions for motion. We could use the keyboard keys A, W, E, D, X, and Z for controlling each direction. The default keyboard layout matches the directions perfectly, and the related functions are as below.

The diagonal directions of motion make an angle of 60 degrees with the horizontal direction. So we can directly calculate the new position using trigonometry by using Cos 60 and Sine 60. From this movementVector, we find out the new resulting position and check if it falls inside a wall in the grid as below.

We add the movementVector to the hero position vector to get the new position for the hero sprite's centre. Then we find the position of the four corners of the hero sprite and check if those are colliding. If there are no collisions, then we set the new position to the hero sprite. Let's see that in action.

Usually, this kind of free-flowing motion is not allowed in a grid-based game. Typically, characters move from tile to tile, that is, tile centre to tile centre, based on commands or tap. I trust that you can figure the solution out by yourself.

3. Pathfinding

So here we are on the topic of pathfinding, a very scary topic for some. In my previous tutorials I never tried to create new pathfinding solutions but always preferred to use readily available solutions which are battle tested. 

This time, I am making an exception and will be reinventing the wheel, mainly because there are various game mechanics possible and no single solution would benefit all. So it is handy to know how the whole thing is done in order to churn out your own custom solutions for your game mechanic. 

The most basic algorithm that is used for pathfinding in grids is Dijkstra's Algorithm. We start at the first node and calculate the costs involved in moving to all the possible neighbour nodes. We close the first node and move to the neighbour node with the lowest cost involved. This is repeated for all the non-closed nodes till we reach the destination. A variant of this is the A* algorithm, where we also use a heuristic in addition to the cost. 

A heuristic is used to calculate the approximate distance from the current node to the destination node. As we do not really know the path, this distance calculation is always an approximation. So a better heuristic will always yield a better path. Now, that being said, the best solution need not be the one which yields the best path as we need to consider the resource usage and performance of the algorithm as well, when all the calculations need to be done in real time or once per update loop. 

The easiest and simplest heuristic is the Manhattan heuristic or Manhattan distance. In a 2D grid, this is actually the distance between the start node and end node as the crow flies, or the number of blocks we need to walk.

Hexagonal Manhattan Variant

For our hexagonal grid, we need to find a variant for the Manhattan heuristic to approximate the distance. As we are walking on the hexagonal tiles, the idea is to find the number of tiles we need to walk over to reach the destination. Let me show you the solution first. Please move the mouse over the interactive element below to see how far away the other tiles are from the tile under the mouse.

In the example above, we find the tile under the mouse and find the distance of all other tiles from it. The logic is to find the difference of i and j axial coordinates of both tiles first, say di and dj. Find the absolute values of these differences, absi and absj, as distances are always positive. 

We notice that when both di and dj are positive and when both di and dj are negative, the distance is absi+absj. When di and dj are of opposite signs, the distance is the bigger value among absi and absj. This leads to the heuristic calculation function getHeuristic as below.

One thing to notice is that we are not considering if the path is really walkable or not; we just assume that it is walkable and set the distance value. 

Finding the Hexagonal Path

Let's proceed with pathfinding for our hexagonal grid with the newly found heuristic method. As we will be using recursion, it will be easier to understand once we breakdown the core logic of our approach. Each hexagonal tile will have a heuristic distance and a cost value associated with it.

  • We have a recursive function, say findPath(tile), which takes in one hexagonal tile, which is the current tile. Initially this will be the starting tile.
  • If the tile is equal to the end tile, the recursion ends and we have found the path. Else we proceed with the calculation.
  • We find all the walkable neighbours of the tile. We will loop through all the neighbour tiles and apply further logic to each of them unless they are closed.
  • If a neighbour is not previously visited and not closed, we find the distance of the neighbour tile to the end tile using our heuristic. We set the neighbour tile's cost to current tile's cost + 10. We set the neighbour tile as visited. We set the neighbour tile's previous tile as the current tile. We do this for a previously visited neighbour as well if the current tile's cost + 10 is less than that neighbour's cost.
  • We calculate the total cost as the sum of the neighbour tile's cost value and the heuristic distance value. Among all the neighbours, we select the neighbour which gives the lowest total cost and call findPath on that neighbour tile.
  • We set the current tile to closed so that it won't be considered anymore.
  • In some cases, we'll fail to find any tile which satisfies the conditions, and then we close the current tile, open the previous tile, and redo.

There is an obvious failure condition in the logic when more than one tile satisfies the conditions. A better algorithm will find all the different paths and select the one with the shortest length, but we won't be doing that here. Check the pathfinding in action below.

For this example, I am calculating neighbours differently than in the Tetris example. When using axial coordinates, the neighbour tiles have coordinates which are higher or lower by a value of 1.

The findPath recursive function is as below.

It may require further and multiple reading to properly understand what is going on, but believe me, it is worth the effort. This is only a very basic solution and could be improved a lot. For moving the character along the calculated path, you can refer to my isometric path following tutorial

Marking the path is done using another simple recursive function, paintPath(tile), which is first called with the end tile. We just mark the previousNode of the tile if present.

Conclusion

With the help of all the three hexagonal tutorials I have shared, you should be able to get started with your next awesome hexagonal tile-based game. 

Please be advised that there are other approaches as well, and there's a lot of further reading out there if you are up for it. Please do let me know through the comments if you need anything more to be explored in relation to hexagonal tile-based games. 

Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.