[Freeciv-Dev] Re: directional system: more magic code cleanups

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Sep 18, 2001 at 11:57:06PM -0400, Ross W. Wetmore wrote:
> Attached is a copy of straightest_dir with yet another explanation 
> of the algorithm embedded as comments in hopes that repetition will
> eventually penetrate those that still haven't got it :-).
> 
> Note that to choose one of 8 directions, the absolute minimum work
> is 3 binary compares, so there is still room for improvement in the
> attached algorithm.

[ The following mail is off topic and a negative example that you can
optimize too much. It just shows that I like a good problem. ]

The fastest version I can think of goes like this:

{
   int diff_x=....
   int diff_y=....

#define K 65536

// M1=tan(pi/8)*K
#define M1 27146

// M2=tan(pi/2-pi-8)*K=(K*K)/M1
#define M2 158218

  int xpos=(diff_x>0);
  int ypos=(diff_y>0);

  assert(!(diff_x==0 && diff_y==0));

  if(diff_x==0)
     if(ypos) return SOUTH;
     else     return NORTH;

  int m=abs((diff_y*K)/diff_x);

  if(m<M1)
     if(xpos) return EAST;
     else     return WEST;
  if(m>M2)
     if(ypos) return SOUTH;
     else     return NORTH;

  if(xpos)
     if(ypos) return SOUTHEAST;
     else     return NORTHEAST;
  else
     if(ypos) return SOUTHWEST;
     else     return NORTHWEST;
}

So this method will only use one multiplication (which the comiler
will translate to "clear.w;swap" or at least a shift) and one "real"
division. The translation of the remaining tests to some bit
operations is left to the reader as an exercise.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "There are three ways to get something done. Do it yourself, hire someone
  to do it for you or forbid your kids to do it."