[Bug Report] Wrong result got from get_distance method for torus continuous space

[simonchx]

def get_distance(self, pos_1, pos_2):
      """ Get the distance between two point, accounting for toroidal space.

      Args:
          pos_1, pos_2: Coordinate tuples for both points.

      """
      pos_1 = np.array(pos_1)
      pos_2 = np.array(pos_2)
      if self.torus:
          pos_1 = (pos_1 - self.center) % self.size
          pos_2 = (pos_2 - self.center) % self.size
      return np.linalg.norm(pos_1 - pos_2)

Above is the get_distance method for continuous space in mesa 0.8.1.

Although I'm not clear about the algorithm here, when my input is

pos_1 = (50, 40)
pos_2 = (50, 50)
size = (100, 100)
torus = True

I got the result 90 rather than 10.
So I wonder if there is any problem about this algorithm.

[FinlandBreakfast]

I personally haven't used the built in get_distance method since I write my own based on agent capability: euclidean, manhattan, etc. I believe the following code might work, I ran it with a couple use cases.

def get_distance(self, pos_1, pos_2):
      """ Get the distance between two point, accounting for toroidal space.

      Args:
          pos_1, pos_2: Coordinate tuples for both points.

      """
      pos_1 = np.array(pos_1)
      pos_2 = np.array(pos_2)
      dist_1 = np.linalg.norm(pos_1 - pos_2)
      if self.torus:
          pos_1 = (pos_1 - self.center) % self.size
          pos_2 = (pos_2 - self.center) % self.size
      dist_2 = np.linalg.norm(pos_1 - pos_2)
      
      return min(dist_1, dist_2)

Hope this helps.

[simonchx]

@clmerlos Thanks for your reply.
Yes, the version you provided works well.
Hope mesa would fix it in the next version.

[jackiekazil]

I ran the tests with both versions and they both pass.
https://github.com/projectmesa/mesa/blob/master/tests/test_space.py#L34-L43

I applied both versions to Flockers example and they both run in the same manner.

It is impossible I made a mistake along the way, but I don't see the issue.
Can you provide me with explicit instructions on how to recreate it?

[simonchx]

@jackiekazil Thanks for your reply.

pos_4 = (20, -5)
pos_5 = (20, -15)
assert self.space.get_distance(pos_4, pos_5) == 10

As I tried, this test failed. I got the result 40 rather than 10.

Hope this would help.

[jackiekazil]

@simonchx can you take a look at the change that I submitted? #425 ... does it look good to you?

[simonchx]

@jackiekazil Thanks for the change. This one seems to work well.

[rht]

The reason why it is 40 for #410 (comment) test case, given the params x_max = 70, y_max = 20, x_min = -30, y_min = -30, x_center = 20, y_center = -5, width = 100, height = 50: for the y coordinate, y = -15 - (-5) = -10 and -10 modulo 50 is 40 instead of -10.

I think the less opaque solution is to multiply the size with a sign of the x and y coordinate.

if self.torus:
    pos_1 -= self.center
    pos_1 = pos_1 % np.sign(pos_1) * self.size
    pos_2 -= self.center
    pos_2 = pos_2 % np.sign(pos_2) * self.size

[rht]

40 is outside the range of y_max = 20.

[simonchx]

@rht Thanks for your reply.

First, there are some bugs.
I got this first.

pos_1 -= self.center
TypeError: Cannot cast ufunc subtract output from dtype('float64') to dtype('int64') with casting rule 'same_kind'

And the computation order of

pos_1 % np.sign(pos_1) * self.size

will go from left to right, which may not what you want, I think.

After change your code to

pos_1 = np.array(pos_1)
pos_2 = np.array(pos_2)
if self.torus:
    pos_1 = np.abs(pos_1 - self.center) % self.size
    pos_2 = np.abs(pos_2 - self.center) % self.size
return np.linalg.norm(pos_1 - pos_2)

it started to work but failed at the test

pos_6 = (-30, -29)
pos_7 = (-30, -4)
assert self.space.get_distance(pos_6, pos_7) ==  25

Your code got the result 23 rather than 25.

[simonchx]

@clmerlos @jackiekazil
I just tried to do a complete test for @clmerlos 's code and the original version in mesa 0.77.
And the former failed at

pos_6 = (-30, -29)
pos_7 = (21, -5)
assert self.space.get_distance(pos_6, pos_7) ==  np.sqrt(49 ** 2 + 24 ** 2)

It got the result np.sqrt(49 ** 2 + 26 ** 2).

Although I still cannot be sure whether the latter is always right.

The following is my test code.

import numpy as np
import math


def code_from_rth (center, size, torus, pos_1, pos_2):
    pos_1 = np.array(pos_1)
    pos_2 = np.array(pos_2)
    if torus:
        pos_1 = np.abs(pos_1 - center) % size
        pos_2 = np.abs(pos_2 - center) % size
    return np.linalg.norm(pos_1 - pos_2)


def code_from_clmerlos (center, size, torus, pos_1, pos_2):
    pos_1 = np.array(pos_1)
    pos_2 = np.array(pos_2)
    dist_1 = np.linalg.norm(pos_1 - pos_2)
    if torus:
        pos_1 = (pos_1 - center) % size
        pos_2 = (pos_2 - center) % size
    dist_2 = np.linalg.norm(pos_1 - pos_2)
    return min(dist_1, dist_2)


def code_from_mesa_077(center, size, torus, pos_1, pos_2):
    x1, y1 = pos_1
    x2, y2 = pos_2
    if not torus:
        dx = x1 - x2
        dy = y1 - y2
    else:
        d_x = abs(x1 - x2)
        d_y = abs(y1 - y2)
        dx = min(d_x, size[0] - d_x)
        dy = min(d_y, size[1] - d_y)
    return math.sqrt(dx ** 2 + dy ** 2)


if __name__ == '__main__':
    center = np.array((20, -5))
    size = np.array((100, 50))
    torus = True

    for i in range(-30, 71, 1):
        for j in range(-30, 21, 1):
            for k in range(i, 71, 1):
                for l in range(j, 21, 1):
                    print(i, j, k, l)
                    try:
                        # assert code_from_rth(center, size, torus, np.array((i, j)), np.array((k, l))) == code_from_clmerlos(center, size, torus, np.array((i, j)), np.array((k, l)))
                        assert code_from_clmerlos(center, size, torus, np.array((i, j)), np.array((k, l))) == code_from_mesa_077(center, size, torus, np.array((i, j)), np.array((k, l)))
                    except AssertionError:
                        # print('code from rth got the result: ', code_from_rth(center, size, torus, np.array((i, j)), np.array((k, l))))
                        print('code from clmerlos got the result: ', code_from_clmerlos(center, size, torus, np.array((i, j)), np.array((k, l))))
                        print('code from mesa_077 got the result: ', code_from_mesa_077(center, size, torus, np.array((i, j)), np.array((k, l))))
                        raise AssertionError

[rht]

@simonchx you can't remove the sign from pos_1 and pos_2, since later or pos_1 - pos_2 is a vector operation.

My fix would be to replace -= with this:

pos_1 = pos_1 - self.center
...
pos_2 = pos_2 - self.center

[simonchx]

@rht

you can't remove the sign from pos_1 and pos_2, since later or pos_1 - pos_2 is a vector operation.

Sorry for that, yes, the sign is needed here.

And the first bug gets fixed after the change you provided.

However, still your code and some fixation I tried failed in some situation.
So, could you please provide a version of your code that could pass the following tests?

pos_1 = (-30, -30)
pos_2 = (-30, -4)
assert self.space.get_distance(pos_1, pos_2) == 24

pos_3 = (-30, -29)
assert self.space.get_distance(pos_1, pos_3) == 1
assert self.space.get_distance(pos_2, pos_3) == 25

pos_4 = (-30, -5)
assert self.space.get_distance(pos_3, pos_4) == 24

[simonchx]

@jackiekazil By comparing results with the basic algorithm below, I'm sure that the get_distance method in mesa 0.77 is the only right one by now.

def code_for_basic(center, size, torus, pos_1, pos_2):
    if not torus:
        return np.linalg.norm(pos_1 - pos_2)
    else:
        distance_list = np.zeros(9)
        for i in range(3):
            for j in range(3):
                pos_1_temp = pos_1 + np.array(((i-1) * size[0], (j-1) * size[1]))
                distance_list[i*3+j] = np.linalg.norm(pos_1_temp - pos_2)
        return distance_list.min()