### Interactive demo

This demo was built on one evening after being kept awake by one too many please-allow-me-to-stay-here-longer-espressos in the café. Thanks for letting us stay!

### On Hexagonal Grids

Unlike regular grids, I’ve struggled a bit at first with understanding how I would map hexagons to arrays. I’ve since realised that you can easily map hexagons into 3 dimensions, and even two dimensions isn’t a problem. The general idea that this approach is following is cube coordinates. If you play around with the demo (and maybe switch the camera), you’ll quickly see that looked at from the right angle, a diagonal “plane” of 3d cubes looks an awful lot like a hex grid. This is what we are going to use to reason about how to distribute coordinates, measure distances, and so on.

#### Coordinates (and Constraints)

To make our lives a little easier, we choose the plane that satisfies the basic constraint

If you play around with the interactive widget up there, you’ll quickly realize that all coordinates on the plane displayed fulfill exactly that equation. It should also give you an intuitive idea what parameters should change when you perform a move in a direction.

#### Distances

The 3D representation allows us to easily reason about distances in the grid. You can see that to each neighbouring cube, the manhattan distance is 2. In the hex grid, the distance would be one. Check for yourself that this is correct for all neighbours of the initial $$0,0,0$$ coordinate.

Thus, we quickly arrive at a concise formula for determining distances of hexagons in the grid in relation to the origin:

#### The obsolete third axis

But, we can go even further. If we can assume that the formula $$x+y+z = 0$$ holds for all our cubes, can simply do some middle school maths and arrive at

So what does this tell us? Since the $$z$$ coordinate is merely a function of $$x$$ and $$y$$, it does not need to be saved in memory, but can be calculated on demand (when it makes sense). This also means that our distance is only dependent on the values of $$x$$ and $$y$$:

If we go back to the graphical representation again (after having developed some intuition for it), we can see that this makes an extreme amount of sense. Observe how each $$x,y$$ coordinate pair already uniquely identifies a cube on our plane. The formula for $$z$$ also holds; again, staring intently at the cubes and axis offsets should give you an intuitive understanding to why that is (Looking at it from the default camera perspective, you should realise that moving one cube away from the camera (into the space) always has to increment the $$z$$ coordinate by one due to the staircase like nature of our plane; conversely, you need to decrease your $$z$$ coordinate whenever you move towards the camera)

So, we can store all grid coordinates in only two dimensions - that’s going to make building implementations a lot easier!

#### A demo implementation

In my Advent of Code repository, you can find two implementations for the HexVector interface which I decided needed to be implemented in order to solve the task given by the AoC challenge. The first version, HexVector3, is a quite low performance prototype that I came up with then and there in the café. It uses a process of coordinate normalisation (leveraging the fact that certain pairs of distances can be fused together into other coordinates, as to always obtain the correct manhattan distance).

The second version, HexVector2, implements the same interface using only two coordinates, while also allowing a conversion to HexVector3.

It’s coding challenge code, so it’s not the most polished thing in the world, but I’m sure it’ll get the point across 😁