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.

## Hexagonal Character Movement Using Axial Coordinates

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.

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.

```
tan 30 = opposite side/adjacent side;
1/sqrt(3) = (hexTileHeight/4)/(hexTileWidth/2);
hexTileWidth = sqrt(3)*hexTileHeight/2;
hexTileHeight = 2*hexTileWidth/sqrt(3);
```

### 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.

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.

```
y= (3*hexTileHeight/4)*i;
y = 3/2*s*i;
```

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.

```
x=j*hexTileWidth+(i*hexTileWidth/2);
= j* sqrt(3)*hexTileHeight/2 + i* sqrt(3)*hexTileHeight/4;
= sqrt(3)*s*(j+ (i/2));
```

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

```
var rootThree=Math.sqrt(3);
var sideLength=hexTileHeight/2;
function axialToScreen(axialPoint){
var tileX=rootThree*sideLength*(axialPoint.y+(axialPoint.x/2));
var tileY=3*sideLength/2*axialPoint.x;
axialPoint.x=tileX;
axialPoint.y=tileY;
return axialPoint;
}
```

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

```
for (var i = 0; i < levelData.length; i++)
{
for (var j = 0; j < levelData[0].length; j++)
{
axialPoint.x=i;
axialPoint.y=j;
axialPoint=offsetToAxial(axialPoint);
screenPoint=axialToScreen(axialPoint);
if(levelData[i][j]!=-1){
hexTile= new HexTileNode(game, screenPoint.x, screenPoint.y, 'hex', false,i,j,levelData[i][j]);
hexGrid.add(hexTile);
}
}
}
```

### 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.

```
i=y/(3/2*s);
j=(x-(y/sqrt(3)))/s*sqrt(3);
```

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.

```
function screenToAxial(screenPoint){
var axialPoint=new Phaser.Point();
axialPoint.x=screenPoint.y/(1.5*sideLength);
axialPoint.y=(screenPoint.x-(screenPoint.y/rootThree))/(rootThree*sideLength);
var cubicZ=calculateCubicZ(axialPoint);
var round_x=Math.round(axialPoint.x);
var round_y=Math.round(axialPoint.y);
var round_z=Math.round(cubicZ);
if(round_x+round_y+round_z===0){
screenPoint.x=round_x;
screenPoint.y=round_y;
}else{
var delta_x=Math.abs(axialPoint.x-round_x);
var delta_y=Math.abs(axialPoint.y-round_y);
var delta_z=Math.abs(cubicZ-round_z);
if(delta_x>delta_y && delta_x>delta_z){
screenPoint.x=-round_y-round_z;
screenPoint.y=round_y;
}else if(delta_y>delta_x && delta_y>delta_z){
screenPoint.x=round_x;
screenPoint.y=-round_x-round_z;
}else if(delta_z>delta_x && delta_z>delta_y){
screenPoint.x=round_x
screenPoint.y=round_y;
}
}
return screenPoint;
}
```

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.

```
function moveLeft(){
movementVector.x=movementVector.y=0;
movementVector.x=-1*speed;
CheckCollisionAndMove();
}
function moveRight(){
movementVector.x=movementVector.y=0;
movementVector.x=speed;
CheckCollisionAndMove();
}
function moveTopLeft(){
movementVector.x=-0.5*speed;//Cos60
movementVector.y=-0.866*speed;//sine60
CheckCollisionAndMove();
}
function moveTopRight(){
movementVector.x=0.5*speed;//Cos60
movementVector.y=-0.866*speed;//sine60
CheckCollisionAndMove();
}
function moveBottomRight(){
movementVector.x=0.5*speed;//Cos60
movementVector.y=0.866*speed;//sine60
CheckCollisionAndMove();
}
function moveBottomLeft(){
movementVector.x=-0.5*speed;//Cos60
movementVector.y=0.866*speed;//sine60
CheckCollisionAndMove();
}
```

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.

```
function CheckCollisionAndMove(){
var tempPos=new Phaser.Point();
tempPos.x=hero.x+movementVector.x;
tempPos.y=hero.y+movementVector.y;
var corner=new Phaser.Point();
//check tl
corner.x=tempPos.x-heroSize/2;
corner.y=tempPos.y-heroSize/2;
if(checkCorner(corner))return;
//check tr
corner.x=tempPos.x+heroSize/2;
corner.y=tempPos.y-heroSize/2;
if(checkCorner(corner))return;
//check bl
corner.x=tempPos.x-heroSize/2;
corner.y=tempPos.y+heroSize/2;
if(checkCorner(corner))return;
//check br
corner.x=tempPos.x+heroSize/2;
corner.y=tempPos.y+heroSize/2;
if(checkCorner(corner))return;
hero.x=tempPos.x;
hero.y=tempPos.y;
}
function checkCorner(corner){
corner=screenToAxial(corner);
corner=axialToOffset(corner);
if(checkForOccuppancy(corner.x,corner.y)){
return true;
}
return false;
}
```

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.

```
getHeuristic=function(i,j){
j=(j-(Math.floor(i/2)));
var di=i-this.originali;
var dj=j-this.convertedj;
var si=Math.sign(di);
var sj=Math.sign(dj);
var absi=di*si;
var absj=dj*sj;
if(si!=sj){
this.heuristic= Math.max(absi,absj);
}else{
this.heuristic= (absi+absj);
}
}
```

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.

```
function getNeighbors(i,j){
//coordinates are in axial
var tempArray=[];
var axialPoint=new Phaser.Point(i,j);
var neighbourPoint=new Phaser.Point();
neighbourPoint.x=axialPoint.x-1;//tr
neighbourPoint.y=axialPoint.y;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
neighbourPoint.x=axialPoint.x+1;//bl
neighbourPoint.y=axialPoint.y;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
neighbourPoint.x=axialPoint.x;//l
neighbourPoint.y=axialPoint.y-1;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
neighbourPoint.x=axialPoint.x;//r
neighbourPoint.y=axialPoint.y+1;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
neighbourPoint.x=axialPoint.x-1;//tr
neighbourPoint.y=axialPoint.y+1;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
neighbourPoint.x=axialPoint.x+1;//bl
neighbourPoint.y=axialPoint.y-1;
populateNeighbor(neighbourPoint.x,neighbourPoint.y,tempArray);
return tempArray;
}
```

The `findPath`

recursive function is as below.

```
function findPath(tile){//passes in a hexTileNode
if(Phaser.Point.equals(tile,endTile)){
//success, destination reached
console.log('success');
//now paint the path.
paintPath(tile);
}else{//find all neighbors
var neighbors=getNeighbors(tile.originali,tile.convertedj);
var newPt=new Phaser.Point();
var hexTile;
var totalCost=0;
var currentLowestCost=100000;
var nextTile;
//find heuristics & cost for all neighbors
while(neighbors.length){
newPt=neighbors.shift();
hexTile=hexGrid.getByName("tile"+newPt.x+"_"+newPt.y);
if(!hexTile.nodeClosed){//if node was not already calculated
if((hexTile.nodeVisited && (tile.cost+10)<hexTile.cost) ||
!hexTile.nodeVisited){//if node was already visited, compare cost
hexTile.getHeuristic(endTile.originali,endTile.originalj);
hexTile.cost=tile.cost+10;
hexTile.previousNode=tile;//point to previous node
hexTile.nodeVisited=true;
hexTile.showDifference();//display heuristic & cost
}else continue;
totalCost=hexTile.cost+hexTile.heuristic;
if(totalCost<currentLowestCost){//select the next neighbour with lowest total cost
nextTile=hexTile;
currentLowestCost=totalCost;
}
}else{
console.log('node closed');
}
}
tile.nodeClosed=true;
if(nextTile!==null){
findPath(nextTile);//call algo on the new tile
nextTileToCall=nextTile;
}else{
if(tile.previousNode!==null){
//current tile is now closed, open previous tile and redo.
tile.previousNode.cost-=10;
tile.previousNode.nodeClosed=false;
findPath(tile.previousNode);//call algo on the previous tile
nextTileToCall=tile.previousNode;
}else{
//no path
nextTileToCall=null;
}
}
}
}
```

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.

```
function paintPath(tile){
tile.markDirty();
if(tile.previousNode!==null){
paintPath(tile.previousNode);
}
}
```

## 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.