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

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

Ok, here is a slight refinement of your proposal in pseudocode form. 

(It is disgusting how easily I can be sucked into an intriguing puzzle :-).

0)  Fix straightest_dir() according to the current (exact) algorithm for 
    determining a direction at a given point. It has nothing to do with 
    lines and is useful for what it does, so you certainly don't want to 
    (ab)use its signature.

1)  Add a (pointer to) struct goto_block to the unit struct or wherever
    struct goto_block {
      int   count;               /* total count remaining     */
      short step;                /* step value for counting   */
      short dx, dy;              /* slope or delta in x and y */
    };

2)  Define a new function straightest_line_init() like this

    static int straightest_line_init(
        struct goto_block *gblk,
        int src_x, int src_y, int dest_x, int dest_y)
    {
        int abs_x, abs_y;

        gblk->dx = dest_x - src_x;
        abs_x = ABS(gblk->dx);
        gblk->dy = dest_y - src_y;
        abs_y = ABS(gblk->dy);

        if( abs_x < abs_y ) {
            gblk->count = (( abs_x == 0 ) ? 1 : gblk->dx) * gblk->dy;
            gblk->step  = gblk->count / abs_y;
            gblk->count+= gblk->step / 2;
        } else {
            assert( abs_x != 0 );
            gblk->count = (( abs_y == 0 ) ? 1 : gblk->dy) * gblk->dx;
            gblk->step  = gblk->count / abs_x;
            gblk->count+= gblk->step / 2;
        }
    }
    I'll let you figure out what comments seem reasonable, but note
    the half step makes the line pass through the centre point between
    the src and dest, or as close to it as possible with an odd step.

3)  Define a new function straightest_line_next() like this

    static int straightest_line_next(
        struct goto_block *gblk,
        int *dir_x, int *dir_y)
    {   int cur_x, cur_y, next_x, next_y;

        cur_x = gblk->count / (gblk->y == 0 ? 1 : gblk->dy);
        cur_y = gblk->count / (gblk->x == 0 ? 1 : gblk->dx);

        gblk->count -= gblk->step;

        next_x = gblk->count / (gblk->y == 0 ? 1 : gblk->dy);
        next_y = gblk->count / (gblk->x == 0 ? 1 : gblk->dx);

        *dir_x = next_x - cur_x;
        *dir_y = next_y - cur_y;

        return (gblk->count * gblk->step > 0);
    }
    This is basically your algorithm, but without the "search t"
    O(n) step that you always manage to sneak in, it caches "t"
    as the count.

    Note it is not really optimized, because one of the x or y
    point determinations will be a unit vector, and the other will
    flip between 0 and a unit direction depending on the way in 
    which the successive divisions truncate. If you can figure out
    an easy way to determine which, half the above operations get
    replaced by a single fixed assignment on every call, i.e. one
    value is a constant +/-1 for the whole goto operation.

This is more like a LINE_STEP() algorithm, but I think that is what
you were looking for.

But as you can see, its semantics and use are really quite different
from straightest_direction().

Cheers,
RossW
=====

At 09:45 AM 01/09/28 +0200, Raimar Falke wrote:
>On Thu, Sep 27, 2001 at 11:49:11PM -0400, Ross W. Wetmore wrote:
>> At 10:34 AM 01/09/27 +0200, Raimar Falke wrote:
[...]
>So my proposal stands:
> - adding server-only goto_start_x, goto_start_y to struct unit
> - changing straightest_direction to:
>    [ l(start,end,t) is the point of the ideal line from start to end
>    for a given parameter t]
>    - search t so that l(t)==current position
>    - increase t so that the next position is revealed
>    - return get_direction_for_step(current_pos,next_pos)
>
>What do you think? The changes are small IMHO. The solution is
>perfect.
>
>       Raimar
>-- 
> email: rf13@xxxxxxxxxxxxxxxxx
>  reality.sys corrupt. Reboot Universe? (y,n,q)