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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Sat, Sep 29, 2001 at 02:21:25AM -0400, Ross W. Wetmore wrote:
> 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().

I put together a quick'n'dirty program to test your algorithm. However
it doesn't work.

The third algorithm uses float, works and only needs two extra fields:
goto_start_x, goto_start_y.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "SIGDANGER - The System is likely to crash soon"

line_drawing.c
Description: Text document