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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

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:
> [...]
> >The more I think about this the more I'm convinced that an line
> >drawing at the start instead of incremental calls to
> >straightest_direction is the best solution here. This can be done with
> >Bresenham's line drawing algorithm. What do you think about this?
> 
> If you think a straightest_line() is useful, then it can easily be
> written.

Ack.

> But I would probably not use straightest_direction() iteratively to
> get straightest_line() unless there was some overriding reason and
> exactness didn't really count.

Ack. It won't use straightest_direction, but would be a
re-implementation using the starting point, the end point and the
current position to determine the next step.

> That still doesn't mean that there isn't a use for straightest_direction().
> 

> For example the drunkard's walk for explorers might possibly want to
> determine straightest_direction() at each point to determine when it
> had hit a turning point.

I'm very sure that this can be done using the normal dijkstra with a
certain cost function.

> Or somebody might do a 1-2-1 random move in the straightest
> direction and those either side of it. Or one might use
> straightest_direction for a body_guard where an exact line will
> probably never be followed more than a turn or so.

No idea about these.

> 
> The two functions are different.
> 
> >I admit that your method matches the ideal line more closely (however
> 
> No, it matches the starting move more closely. straightest_direction()
> returns a single dir value, not a line (sequence of dir values).
> 
> Plot an example where you are further away from the 2:1 line and try
> to iterate a few moves. You will basically move in one direction (the 
> straightest at each point) until you hit the 2:1 line closer in and then 
> follow a pattern like the above.
> 
> >I think this isn't really necessary). The question is now what other
> >differences exists in other cases between your method and the ideal
> >line? Can you prove that your algorithm will always match the ideal
> >line?
> 

> None of the methods match the ideal line because none of them carry
> the residual over an iteration cycle. 
> 
> But then this is NOT A ROUTINE TO PLOT LINES, it is to point a 
> direction.

I know.

> >What happens if F_IGTER is used if GOTO_MOVE_STRAIGHTEST is passed to
> >the goto method? This should also generate a "straight" line. How
> >straight is this line?
> 

> No again.  The routine is called straightest_DIRECTION().

I know but in the end we want a straight line. straightest_direction
is only a helper. And as it turns out, a bad helper.

> >We have spend so much time at this that I see two options:
> > - do small changes to the current method (s/5/NORTH/...) because it
> > isn't used much and nobody has ever reported a bug wrt this
> > - do it right
> 
> The corecleanup routine does it "right" in the strict definition of 
> what the routine claims it is supposed to do.
> 
> >Applying a solution which is better than the current but still isn't
> >ideal isn't the right way to do after we spend this much time
> >discussing it.
> 
> If you want a line drawing routine, there are other algorithms and 
> solutions, but this is NOT A LINE DRAWING ROUTINE.
> 
> You already have the ideal solution for this routine.
> 
> [...]

[ snip stuff about other topologies ]

We can do this stuff latter.

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)