Stolen from a post by Samson @ 'poly
Distance = (Xdistance + Ydistance)/2 + ( | Xdistance - Ydistance | )/4
If the coordinates of point A are (Xa, Ya) and the coordinates of point B are (Xb, Yb), then the absolute difference between Y coordinates is:
Ydistance = |Ya - Yb|.
Or, in other words, simply subtract the smaller Y value from the larger one.
On a FLAT map, the Xdistance value is found the same way:
Xdistance = |Xa - Xb|.
On a ROUND map, however, there will be two values which express the horizontal distance between two points: |Xa - Xb| and (C - |Xa - Xb|) where C is the circumference of the map. These values represent the X distances between the two points obtained by traveling East or West respectively. The Xdistance value used in calculating Civ2 distances is the smaller of these two numbers. Thus:
Xdistance = SmallerOf( |Xa - Xb| , (C - |Xa - Xb|) )
This calculation is easier to do in practice than it is to formally describe.
For example, given two points A(23, 71) and B( 84, 12) on a medium map (50 x 80),
where the circumference is 100:
Ydistance = 71 - 12 = 59.
Xdistance = SmallerOf( 84 - 23 , 100 - (84-23) = SmallerOf( 61, 39) = 39
Distance = (39 + 59)/2 + (|39 - 59|)/4 = 98/2 + 20/4 = 49 + 5 = 54