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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

I like the scalar product as a way to reduce the code flow noise
plus reduce the possibility of getting one of the tests or magic
numbers wrong.

The key elements of this are that any point in the 4 quadrants 
is reduced to a diagonal unit vector, and only if you are on one 
of the cartesian axes do you get a cartesian unit vector.

Thus most of the time, straightest direction implemented by these
diff tests will return a diagonal move. And the iterated walk is
to march down the diagonal, then in along the cartesian direction.

In a true straightest direction, you would start off in whichever
of the two, diagonal or cartesian was larger, doing a step in the
shorter of the two, every so often.

If you want a trivial example, pick a point one square away from
a cartesian axis like WEST 3 NORTH 1. dir_ok will let you move
NORTHEAST which is actually moving further away. If you did a 
proper scalar product, this would be negative. On the otherhand
moving SOUTH is in fact disallowed. Its full scalar product is
still negative, but in point of fact takes you no further away 
in map moves. WEST 3, NORTH 1 should produce a cartesian first
move for straightest direction, where NE, E and SE are disallowed.

The problem isn't so much that this happens, but that because you
have such a large discrepancy between the way in which you choose
4 of the coordinate directions vs the other 4, this happens a lot.

To reiterate, it is the tri-state diff tests that muck you up.

So the existing algorithm is clearly *not* the straightest direction
and similarly, dir_ok will often return bogus values.

If Raimar takes a look at the submitted patch, and the last few emails
with Jason, maybe he will change his mind about whether there is some
value in the one he hasn't quite yet figured out :-).

Cheers,
RossW
=====

At 02:46 PM 01/09/17 +0200, Raimar Falke wrote:
>On Mon, Sep 17, 2001 at 12:01:50PM +0100, Gregory Berkolaiko wrote:
>>  --- Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx> wrote: 
>> > On Mon, Sep 17, 2001 at 11:13:03AM +0100, Gregory Berkolaiko wrote:
>> > > there is a nice mathematical way to code dir_ok:
>> > > if diff_x, diff_y and dir are what they are in the current function
>> > > then the "scalar product"
>> > > 
>> > >         diff_x*DIR_DX[dir] + diff_y*DIR_DY[dir]
>> > > 
>> > > is positive whenever direction is ok.  And you don't need any
>> > switches.
>> > 
>> > Very nice. Good spotting. For clarity: s/positive/>=0/. There may be
>> 
>> oops! I thought only 3 directions are ok
>> obviously I didn't read the comment :(
>
>I also haven't read the comment but tried the code by hand.
>
>> > extra documentation about this (for a given diff vector there are
>> > exactly 5 directions ok. These are centered around the given diff
>> > vector. The "outmost" still valid directions are orthogonal to the
>> > given diff vector. scalar product bla bla ...)
>> > 
>> > > However Ross' patch might be more advanced than this.
>> > 
>> > No I don't think so ;)
>> 
>> well, I think he had some crafty way to implement straightest direction
>> and then he would compare dir with the straightest_dir.  This cuts out
>> the computation of diff_x and diff_y and can therefore be faster / more
>> portable.  Anyway, let's wait until he wakes up and checks his mail :)
>
>I think the code should be changed as follow:
>
>int dir_ok(int src_x, int src_y, int dest_x, int dest_y, int dir, int
only_straightest /* this will make only 3 dirs ok */)
>{
>  int diff_x, diff_y,scalar_product;
>
>  if (dest_x > src_x) {
>    diff_x = dest_x-src_x < map.xsize/2 ? 1 : -1;
>  } else if (dest_x < src_x) {
>    diff_x = src_x-dest_x < map.xsize/2 ? -1 : 1;
>  } else { /* dest_x == src_x */
>    diff_x = 0;
>  }
>  if (dest_y != src_y)
>    diff_y = dest_y > src_y ? 1 : -1;
>  else
>    diff_y = 0;
>
>  scalar_product=diff_x*DIR_DX[dir] + diff_y*DIR_DY[dir];
>  if(only_straightest)
>       return scalar_product>0;
>  else
>        return scalar_product>=0;
>}
>
>-        if (restriction == GOTO_MOVE_STRAIGHTEST && dir == straight_dir)
>+        if (restriction == GOTO_MOVE_STRAIGHTEST && dir_ok(x, y, dest_x,
dest_y,dir,1))
>          move_cost /= SINGLE_MOVE;
>
>And remove straightest_direction.
>
>       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."
>
>