Explanation of formula for distance between triangles in a triangular grid Lets say you have a triangle similar to the one below, with each triangle numbered $(N, i) $ where $N$ is the row number and $i$ is the position within the row.

From any triangle, you are allowed to move to any triangle which shares an edge with her current triangle. This can be seen in the diagram:

As an example, it takes 3 moves to get from (3, 3) to (2, 2).

How would you find a formula to find the number of moves it takes to get from a triangle specified by the coordinates $(a_i, a_j)$ to another triangle specified by coordinates $(b_i, b_j)$?
When looking for a solution to this problem online I found this monstrous formula:
$$\left| a_{i}-b_{i} \right|\; +\; \left| \left( a_{i}-\left\lfloor \frac{a_{j}}{2} \right\rfloor \right)-\left( b_{i}-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right) \right|\; +\; \left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}+1}{2} \right\rfloor \right|$$
but I have no idea how they came up with this. I believe this is some variant of taxicab/manhatan geometry except with triangle instead of rectangles. 
Could someone please try to explain/prove why this formula is valid?

I believe that the first addend, $|a_i - b_i|$ comes from the observation that to get from any triangle $(a_i, a_j)$ to $(b_i, b_j)$ you must make $|a_i - b_i|$ moves downward (or upward depending on the order). The other two addends combined seem to give the number of moves left/right (depending on the position), but I cannot figure out the intuition/logic behind why it works.
 A: The formula is True if the distance $d(a,b)= 0$.
Let's say it is True for any distance $<n$.
If you have to 2 points a,b and $d(a,b)=n+1$ with $a_i\geq b_i$
If $b_j$ is odd, t least one of the 3 is True:


*

*$d(a, (b_i, b_j-1)) = n$

*$d(a, (b_i, b_j+1)) = n$

*$d(a, (b_i+1, b_j)) = n$


can see graphically that


*

*$d(a, (b_i+1, b_j)) > d(a,b)$ using $a_i\geq b_i$

*$d(a, (b_i, b_j+1)) \geq d(a, (b_i, b_j-1))$ if $a_j+1\geq b_j$


So, with the 2 assumptions, $d(a,b) = d(a, (b_i, b_j-1))+1$:
$$d(a,b) = \left| a_{i}-b_{i} \right|\; +\; \left| \left( a_{i}-\left\lfloor \frac{a_{j}}{2} \right\rfloor \right)-\left( b_{i}-\left\lfloor \frac{b_{j}-1}{2} \right\rfloor \right) \right|\; +\; \left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right|+1$$


*

*$b_j$ is odd so $\left\lfloor \frac{b_{j}-1}{2} \right\rfloor = \left\lfloor \frac{b_{j}}{2} \right\rfloor$

*$a_j+1\geq b_j$ so $\left| \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor \right|+1 = \left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}}{2} \right\rfloor +1 = \left|\left\lfloor \frac{a_{j}+1}{2} \right\rfloor-\left\lfloor \frac{b_{j}+1}{2} \right\rfloor \right|$


and so the formula is True for $a_i\geq b_i$ and $b_j$ odd. I claim you can do the same with $b_j$ even and use symmetry to close the case
A: Consider a triangle labeled $(i,j)$ somewhere deep in the larger triangle.
The triangle $(i,j)$ is connected to $(i,j-1),$ $(i,j+1),$
and exactly one other triangle: $(i+1,j+1)$ if $j$ is odd, $(i-1,j-1)$ if $j$ is even.
Already this is getting trickier than ordinary Manhattan/taxicab distance,
because different locations have links in different directions.
We can simplify things a bit by considering only even values of $j$ at first;
this means we must make an even number of moves, since any single move changes
$j$ from even to odd or odd to even.
The nice thing about this is that if you do two moves starting at $(i,j)$
where $j$ is even, you end up at one of the following six places:
$(i-1,j-2),$ $(i-1,j),$ $(i,j-2),$ $(i,j+2),$ $(i+1,j),$ or $(i+1,j+2).$
And since you wind up at a triangle whose second coordinate is even,
you can repeat any sequence of the same set of moves.
(We can consider how to deal with odd values of $j$ later.)
Now let's consider a minimal sequence of moves 
from $(a_i,a_j)$ to $(b_i,b_j),$ where $a_i \le b_i.$
If $a_j \le b_j \le a_j + 2(b_i - a_i),$ then we can build such a sequence from
$b_i - a_i$ pairs of moves such that each pair of moves takes some $(i,j)$ to
either $(i+1,j)$ or $(i+1,j+2).$ But if $b_j < a_j$ then we must use
$b_i - a_i$ pairs of moves that take some $(i,j)$ to $(i+1,j)$ and
some additional pairs of moves that take $(i,j)$ to $(i,j-2),$
while if $b_j > a_j + 2(b_i - a_i)$ we must use $b_i - a_i$ pairs of moves
from $(i,j)$ to $(i+1,j+2)$ and additional moves from $(i,j)$ to $(i,j+2).$
Note that only the number of moves in each direction matters, 
not the exact sequence of the moves.
Now we have the beginning of a formula for the "distance" between two triangles, 
although we are restricted at this time to even values of $a_j$ and $b_j$ and
to the case $a_i < b_i.$ We could write the number of moves this way:
$$
d((a_i,a_j),(b_i,b_j)) = \begin{cases}
 2|b_i - a_i| + |b_j - a_j| & \mbox{if } b_j < a_j, \\
 2|b_i - a_i| & \mbox{if } a_j \le b_j \le a_j + 2(b_i - a_i), \\
 2|b_i - a_i| + |b_j - (a_j + 2(b_i - a_i))| & \mbox{if } b_j > a_j + 2(b_i - a_i).
\end{cases} 
$$
So this is a function that looks like an absolute value function except for the
constant part between $a_j$ and $a_j + 2(b_i - a_i).$
A function like that can be defined by adding a constant to the arithmetic mean of two
absolute value functions. 
(Try graphing $f(x) = n + \frac 12(|x-p|+|x-q|)$ to see how this works.)
It turns out that we can rewrite our "distance" function 
(with the same restrictions as before) like this:
$$\begin{eqnarray}
d((a_i,a_j),(b_i,b_j)) 
& = & |b_i - a_i| + \frac 12 \left(|b_j - a_j| + |b_j - (a_j + 2(b_i - a_i))|\right) \\
& = & |b_i - a_i| + \left|\frac{b_j}{2} - \frac{a_j}{2}\right|
 + \left|\left(\frac{b_j}{2} - b_i\right) - \left(\frac{a_j}{2} - a_i\right)\right| \\
& = & |a_i - b_i|
 + \left|\left(a_i - \frac{a_j}{2}\right) - \left(b_i - \frac{b_j}{2}\right)\right|
 + \left|\frac{b_j}{2} - \frac{a_j}{2}\right|.
\end{eqnarray}$$
The first line of this sequence of equations comes from the observation that the
function looks like the arithmetic mean of two absolute values plus a constant
(the constant turns out to be $|b_i - a_i|$), and the next two lines come from
distributing the factor of $\frac 12$ and rearranging terms.
The result looks a lot like the "monstrous" formula except that it does not use the
"floor" function and never adds $1$ to either $a_j$ or $b_j.$
Now we may notice something interesting: if we simply rename our two triangles so
that the triangle formerly labeled $(a_i,a_j)$ is now labeled $(b_i,b_j)$
and the former $(b_i,b_j)$ is now $(a_i,a_j),$
we can evaluate the "distance" between the triangles using the same formula
except that $a_i$ and $b_i$ are swapped and $a_j$ and $b_j$ are swapped;
but when we do that, each of the three absolute values remains the same.
So our formula, which we developed for the case $a_i \le b_i,$
works just as well for $b_i \le a_i,$ 
and we can therefore dispense with the restriction $a_i \le b_i,$
and have only the restriction that $a_j$ and $b_j$ are even.
It is easy to confirm that when $a_j$ and $b_j$ are both even, the "monstrous"
formula is exactly equal to the formula for $d((a_i,a_j),(b_i,b_j))$ written above.
It remains only to see what happens when either $a_j$ or $b_j$ (or both) can be odd.
We can do this by seeing what happens to the number of moves
if we add $1$ to $a_j,$ to $b_j,$ or to both.
Generally, adding $1$ to just one of the $j$ coordinates either increases or
decreases the number of moves by $1$, while a symmetry argument shows that
adding $1$ to both $a_j$ and $b_j$ leaves the number of moves unchanged.
Further investigation shows that when we add $1$ to just one $j$ coordinate,
the number of moves decreases if this change brings $a_j$ and $b_j$ closer together,
but increases if $a_j$ and $b_j$ become further apart.
Now we observe that if when $a_j$ is even, we can replace $\frac{a_j}{2}$
with either $\left\lfloor\frac{a_j}{2}\right\rfloor$
or $\left\lfloor\frac{a_j+1}{2}\right\rfloor$
without changing the value of the formula, but if $a_j$ is odd, then
$\left\lfloor\frac{a_j+1}{2}\right\rfloor = \left\lfloor\frac{a_j}{2}\right\rfloor + 1.$
Something similar happens with $b_j.$
So we can replace $\frac{a_j}{2}$ with $\left\lfloor\frac{a_j}{2}\right\rfloor$
in places where we want to have no effect from adding $1$ to $a_j,$
but $\left\lfloor\frac{a_j+1}{2}\right\rfloor$
in places where we want to insert an extra term of $1$ when adding $1$ to $a_j,$
and a similar tactic applies to $\frac{b_j}{2}.$
By examination (and trial and error if necessary) we can confirm that we
want to make exactly the changes that are shown in the "monstrous" formula.
Having derived the formula in such a manner, one would be well advised to attempt a
more formal proof such as the one devised by Bilou06, to ensure there are no
false assumptions or other errors in the derivation.
It seems to me the "monstrous" formula is about as neat as a formula for this
"distance" can get. The apparent complexity of the formula arises from the
complexity of the way our scheme for numbering the triangles interacts with
the way the triangles are connected--which is to say, not very neatly.
(Note that the two "axes" are treated very differently, and there is all that
odd-even nonsense governing who is connected to whom.)
Contrast this with Manhattan (taxicab) distance, where the way we number the
grid points goes practically hand-in-hand with the way we measure the distance;
that's why the Manhattan distance formula is so much simpler.
