Manhattan distance for a 2d toroid

Question

for the last 1.5 hours I've been struggling to write a function to calculate manhattan distance for a square toroid (like playing the classic snake game without walls).

What I have (coding it in JavaScript)

function getManhattanDistance( node1, node2, size )
{
    size = parseInt( size / 2 );
    var dist1 = Math.abs( node1.x - node2.x );
    var dist2 = Math.abs( node1.y - node2.y );

    if ( dist1 < size && dist2 < size )
    {
        return dist1 + dist2;
    }

    if ( dist1 >= size )
    {
        var x1 = Math.min( node1.x, node2.x );
        var x2 = Math.max( node1.x, node2.x );
        x1 += size;
        if ( dist2 < size )
        {
            return Math.abs( x1 - x2 ) + dist2;
        }
        var y1 = Math.min( node1.y, node2.y );
        var y2 = Math.max( node1.y, node2.y );
        y1 += size;
        return Math.abs( x1 - x2 ) + Math.abs( y1 - y2 );
    }

    var y1 = Math.min( node1.y, node2.y );
    var y2 = Math.max( node1.y, node2.y );
    y1 += size;
    return dist1 + Math.abs( y1 - y2 );

}

I wrote some tests on what this does on a 5*5 toroid:

Manhattance distance 0,1; 2,2 is 1 should be 3 Manhattance distance 2,2; 0,1 is 1 should be 3 Manhattance distance 2,1; 3,4 is 2 should be 2 Manhattance distance 3,4; 2,1 is 2 should be 2 Manhattance distance 2,1; 4,4 is 1 should be 5 Manhattance distance 4,4; 2,1 is 1 should be 5

Thank you, guys!

Answer 1

If I understand your problem correctly, you can "walk" in x-direction either directly from x1 to x2 (abs(x1 - x2) steps), or wrap around in increasing x-direction (size + x2 - x1 steps) or in decreasing x-direction (x1 - x2 + size steps).

Therefore the difference in x-direction is

 dx = min ( abs(x1 - x2) , size + x2 - x1, x1 - x2 + size)

and similarly

 dy = min ( abs(y1 - y2) , size + y2 - y1, y1 - y2 + size)

and finally the Manhattan distance

 dist = dx + dy

Update: Another way to look at it is that the distance in x-direction is either abs(x2-x1) if you don't wrap around, or size - abs(x2-x1) if you wrap around. Therefore

 dx = min ( abs(x2 - x1) , size - abs(x2 - x1) )

which is a more symmetric way of expressing it.

Update: Final JavaScript Function:

function getToroidManhattanDistance( node1, node2, size )
{
    var dx = Math.min( Math.abs( node1.x - node2.x ), size - Math.abs( node2.x - node1.x ) );
    var dy = Math.min( Math.abs( node1.y - node2.y ), size - Math.abs( node2.y - node1.y ) );
    return dx + dy;    
}