[Freeciv-Dev] finding distance from one player to another

[Mike Kaufman <kaufman@xxxxxxxxxxxxxxxxxxxxxx>]

this recently came up in Per's ai diplomacy patch.
His method is a poor metric and slow. Here's a better method:

We want to find the centroid of a nation. We arbitarily choose to take city
positions as our points of interest. We could weight each coordinate with
respect to city size, although that complicates matters in the method
presented.

Ordinarily, we could simply average the city coordinates to get our
centroid, but unfortunately, map wrapping is against us. Consider a map
with a width of 80. If a nation has a group of cities around x=10 and x=70
then simple averaging will yield our centroid at x=40 instead of the proper
x=0.

The solution is to use the map_distance_vector function.

x_{ave} = 1/N ( \sum_{i=2}^N (x_i - x_1) + N x_1 )

  int i, xave = 0, yave = 0;
  int x0, y0;
  int N = city_list_size(&pplayer->cities);
  struct city *first = city_list_get(&pplayer->cities, 0)

  x0 = first->x;
  y0 = first->y;
  
  for (i = 1; i < N; i++) {
    struct city *pcity = city_list_get(&pplayer->cities, i);
    int x, y;

    map_distance_vector(&x, &y, x0, y0, pcity->x, pcity->y);    

    xave += x;
    yave += y;
  }

  xave = 1 / N * xave + N * x0;
  yave = 1 / N * yave + N * y0;

this should give the centroid of a nation.
to find the distance from one player to another, do this once for each
nation and the use real_map_distance() to find the distance between the two
centroids.

Weighting presents a bit of an issue since we are summing differences, but
with a little thought could probably be done.

-mike