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

[Jason Short <jshort@xxxxxxxxxxxxxx>]

--On Monday, July 07, 2003 12:14:17 -0500 Mike Kaufman 
<kaufman@xxxxxxxxxxxxxxxxxxxxxx> wrote:
> 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.
It is fallable; it depends on which city is chosen as the "first".  For 
instance if you have a group of cities around x=75 and another around x=5, 
but have one lone city out at x=40 (an unlikely situation, but certainly 
not impossible), if the x=40 city is chosen as the first you'll still get 
40 as your centroid instead of 0.
And what if you have an even scattering of cities?  Can you even say that 
there is a centroid of the civilization in that case?  When wrapping is 
involved, I think there is no clear answer.
IMO it is better to look at the average distance from the cities of one 
civilization to that of another.  Distance is a clearly defined concept.
jason