Distance between two grid cells, with no diagonal

Question

I've been working on a small project for some days, everything was working fine until I changed my "map" implementation to be the same as in the game (Dofus) I'm based on (it's a little helper for the community).

Basically, I've a grid layout rotated at 45° (see image below), contructed from top left to bottom right. Every cell as an xIndex and zIndex to represent where it is (xIndex ; zIndex) on the image, and I just want to get the distance between two cells, without traveling diagonally.

As I tried to explain on the picture:

• GetDistanceBetweenTiles(A, B) should be 3

• GetDistanceBetweenTiles(A, C) should be 5

• GetDistanceBetweenTiles(B, C) should be 2

I found the "Manhattan distance" which looks like it is what I want, but it's not giving me the values above.

Here is the code:

private int GetDistanceBetweenTiles(MovableObject a, MovableObject b)
{      
    //int dist = Mathf.Abs(a.xIndex - b.xIndex) + Mathf.Abs(a.zIndex - b.zIndex);
    int minX = a.xIndex < b.xIndex ? a.xIndex : b.xIndex;
    int maxX = a.xIndex > b.xIndex ? a.xIndex : b.xIndex;
    int minZ = a.zIndex < b.zIndex ? a.zIndex : b.zIndex;
    int maxZ = a.zIndex > b.zIndex ? a.zIndex : b.zIndex;

    int distX = (maxX - minX);
    int distZ = (maxZ - minZ);

    int dist = Mathf.Abs(maxX - minX) + Mathf.Abs(maxZ - minZ);

    print($"Distance between {a.name} and {b.name} is {dist}");

    return dist;
}

Any help would be gladly appreciated.

If it can help, here is the project working with the first map implementation I did (but not translated yet).

Answer 1

The "No-Maths" solution

I maybe have a workaround solution for you. I'm kind of a lazy person and very bad in maths ... so I usually let Unity do the maths for me in situations like yours ;)

For that you would need one dedicated GameObject that is rotated in the way that it represents the grid "rotation" so 0,45,0.

Then - since your tiles move always in steps of exactly 1 just in the rotated coordinate system - you could inetad of using an index based distance rather directly compare the absolute positions using Transform.InverseTransformPoint in order to get the positions relative to that rotated object.

InverseTransformPoint retuns as said the given world position in the local space of the used transform so that if the object was originally placed at e.g. x=1, z=1 in our rotated local space it will have the position z=1.1414..., x=0.

I simply attached this component to my rotated object .. actually I totate in Awake just to be sure ;)

public class PositionsManager : MonoBehaviour
{
    // I know .. singleton pattern .. buuu
    // but that's the fastest way to prototype ;)
    public static PositionsManager Singleton;

    private void Awake()
    {
        // just for making sure this object is at world origin
        transform.position = Vector3.zero;

        // rotate the object liek you need it
        // possible that in your case you rather wanted -45°
        transform.eulerAngles = new Vector3(0, 45, 0);

        // since InverseTransformPoint is affacted by scale
        // just make sure this object has the default scale
        transform.localScale = Vector3.one;

        // set the singleton so we can easily access this reference
        Singleton = this;
    }

    public Vector2Int GetDistance(Transform from, Transform to)
    {
        var localPosFrom = transform.InverseTransformPoint(from.position);
        var localPosTo = transform.InverseTransformPoint(to.position);

        // Now you can simply get the actual position distance and return 
        // them as vector2 so you can even still see the components
        // seperately
        var difference = localPosTo - localPosFrom;

        // since you are using X-Z not X-Y you have to convert the vector "manually"
        return new Vector2Int(Mathf.RoundToInt(difference.x), Mathf.RoundToInt(difference.z));
    }

    public int GetAbsoluteDistance(Transform from, Trasnform to)
    {
        var difference = GetDistance(from, to);

        return Mathf.Abs(difference.x) + Mathf.Abs(difference.y);
    }
}

Now when you need to get the absolute distance you could simply do

var difference = PositionsManager.Singleton.GetDistance(objectA.transform, objectB.transform);
var absoluteDistance = PositionsManager.Singleton.GetAbsoluteDistance(objectA.transform, objectB.transform);

---

Little Demo (used a chess board drawer since I had that ^^)

---

The maths solution

It just came to me while writing the upper explenation:

You already know your steps between the tiles: It is allways Mathf.Sqrt(2)!

So again you could simply use the absolute positions in your world and compare them like

private float Sqrt2;

private void Awake()
{
    Sqrt2 = Mathf.Sqrt(2);
}

...

  // devide the actual difference by Sqrt(2)
  var difference = (objectA.position - objectB.position) / Mathf.Sqrt(2);
  // again set the Vector2 manually since we use Z not Y
  // This step is optional if you anyway aren't interrested in the Vector2
  // distance .. jsut added it for completeness
  // You might need the rounding part though
  var fixedDifference = new Vector2Int(Mathf.RoundToInt(difference.x), Mathf.RoundToInt(difference.z));

  // get the absolute difference
  var absoluteDistance = Mathf.Abs(fixedDifference.x) + Mathf.Abs(fixedDifference.y);

...

still completely without having to deal with the indexes at all.

Answer 2

Let make new coordinates in inclined rows with simple formulae:

row = z/2 - x   ("/" for **integer division**)
col = z - row

Now we can just calculate Manhattan distance as

abs(row2 - row1) + abs(col2 - col1)

For your example

x   z       r   c  
4,  2  =>  -3,  5
1,  4  =>   1,  4 
distance = (1-(-3)) + (5-4) = 4 + 1 = 5

To explain: your grid rotated by 45 degrees:

  0  1  2  3  4  5  6  7  8    \column   

              40|41               row -4
           30|31|42|43            row -3   
        20|21|32|33|44|45         row -2
     10|11|22|23|34|35|46|47      row -1  
  00|01|12|13|24|15|36|37|48      row 0
     02|03|14|15|26|27|38         row 1
        04|05|16|17|28            row 2
           06|07|18               row 3