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

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

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. 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.

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. 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.

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.

>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().

>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.

[...]
>> Just for fun ... if you wanted to do the same thing for a hexagonal
>> 6 coordinate direction system (for the moment not changing the 
>
>I haven't thought about the case and will only start thinking about
>this if somebody shows code or at least a proposal for this. However I
>think that the scalar methods will run without changes (with slight
>differences from the ideal line).

You can express the necessary changes in data as opposed to code for the
algorithms shown with minor changes. 

But you can't do this for the scalar product methods without similar 
changes and data parameterization. Certainly you haven't even started
to think about a direct method to determine the appropriate hextant or
whatever. Plus all your dot products are hard coded in x,y coordinates, 
so they aren't applicable to a generalized system.

I think the best solution to go general is to put in the best algorithm
for octants, and finish cleaning up and implementing the 4 rectangular 
wrap flavours for this.

Then do something twisted like isometric in a parallel tree until the
changes become obvious and you have everything pretty much worked out.
One can start moving in the generalized^2 changes where they make sense 
until you get close enough to do the final resync for this.

These at least are supported or nearly supported in the rest of the Freeciv 
codebase. And there are problems to be resolved in just getting this all
locked up tight.

But don't think you have a wonderful general solution - you don't really
even in the O(n) example :-).

>       Raimar
>
>-- 
> email: rf13@xxxxxxxxxxxxxxxxx
> "The two rules for success in life are:
>  1) Never tell them everything you know."

Cheers,
RossW
=====