Shortest distance between two points in an $n$-dimensional isometric (triangular) lattice Consider this isometric lattice. This example is two dimensional and of size $(6, 5)$.
Now, the goal is to compute the shortest distance between any two points on the grid given the coordinates for two points. However, a line cannot directly be drawn from the first point to the second - a "connection" between the two points must happen only through points in the grid, and points in the grid can only be connected to one of their six directly adjacent neighbors.
For example, the shortest distances between points $(0, 4)$ and $(0, 1)$, $(1, 2)$ and $(3, 2)$, $(2, 4)$ and $(4, 1)$, $(5, 4)$ and $(5, 1)$ are $3$, $2$, $4$, $3$, as shown in this image.
For two dimensions, I've been able to come up with the following equation to compute the distance between any two points:
$distance = max(0, |\Delta x| - \left\lfloor\dfrac{|\Delta y|}{2}\right\rfloor) + |\Delta y|$
where $\Delta x = x_{2} - x_{1}$ and $\Delta y = y_{2} - y_{1}$ given that the two points under consideration have the coordinates $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$.
Now, I was only able to figure it out for two dimensions, simply because it was possible for me to draw the grid, visualize, and test combinations - I'm still not even sure if it works in all cases.
I have been unable to figure out how to expand this to 3 dimensions, which is a formula that I need. Perhaps a general formula for an $n$ dimensional lattice may also be interesting.
I'm blindly speculating here, but by mindlessly following a similar pattern you'd perhaps get this for three dimensions:
$distance = max(0, |\Delta x| - \left\lfloor\dfrac{|\Delta y|}{2}\right\rfloor-\left\lfloor\dfrac{|\Delta z|}{2}\right\rfloor) + max(0, |\Delta y| - \left\lfloor\dfrac{|\Delta z|}{2}\right\rfloor) + |\Delta z|$
Did I get it right?
It is important to note that when expanding to other dimensions, the quantized nature of the distances must be preserved, i.e., the lattice must be extended in a manner that ensures that distances between any two adjacent points is always equal to the distance between $(0, 0)$ and $(0, 1)$ (hence a triangular lattice). Similarly, the distance between any two points can only be an integer multiple of the distance between $(0, 0)$ and $(0, 1)$.
Insight would be much appreciated.
Thank you very much and I hope you have nice day!
 A: An $n$-dimensional grid $L$ can be created by taking $$L = \{ x \in \mathbb Z^{n+1} \mid x_1 + \ldots +  x_{n+1} = 0\}.$$
The offset between two neighbours in the grid is then $e_j - e_k$ for $j\neq k$ in $\{1, \ldots, n+1\}$ (so any point with exactly one coordinate $1$, one coordinate $-1$ and all others zero).  The distance between a point $x \in L$ and the origin is then the sum of its positive coordinates:
$$d(x, 0) = \sum \{ x_j \mid x_j > 0\}.$$
The distance between two points $x, y \in L$ is the distance of $x-y$ to the origin: $$d(x, y) = d(x - y, 0).$$
The coordinates in your picture are unusual because they are not linear.  This makes it a bit harder to express distances.  In more natural, linear, coordinates, the point $(1,2)$ in the picture would have coordinates $(0,2)$ since it is twice the point $(0, 1)$, etc.
For the case $n=2$, a point expressed in such linear coordinates $(x, y)$ can be mapped to the point $(x, y, -x-y) \in L$.
Let’s do one of your examples.  The points $(2,4)$ and $(4, 1)$ in your picture have linear coordinates $(0, 4)$ and $(4, 1)$ respectively.  The distance between $(0, 4)$ and $(4, 1)$ is $$d\left((0, 4, -4), (4, 1, -5) \right) = d \left((-4, 3, 1), 0 \right) = 3+1 = 4.$$
A: Your formula for two dimensions doesn't work consistently. I have come across this post while researching a similar problem, so for the sake of posterity I would like to add to WimC's answer by noting that one can simply convert from nonlinear coordinates to linear coordinates temporarily and then perform the mentioned calculations. Assuming one can come up with a conversion function of course.
The transformation for the nonlinear coordinates in the given example would be
$$
(x, y) \longrightarrow \left(x - \left\lfloor\frac{y}{2}\right\rfloor, y\right),
$$
after which the formula given by WimC works just fine.
(This probably could've been a comment, but I don't have the reputation for that.)
