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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, Sep 26, 2001 at 11:19:30PM -0400, Ross W. Wetmore wrote:
> At 10:23 AM 01/09/26 +0200, Raimar Falke wrote:
> >On Wed, Sep 26, 2001 at 12:36:19AM -0400, Ross W. Wetmore wrote:
> >> At 10:19 AM 01/09/25 +0200, Raimar Falke wrote:
> >> >On Tue, Sep 25, 2001 at 03:11:26AM -0400, Ross W. Wetmore wrote:
> >> >> At 09:12 AM 01/09/24 +0200, Raimar Falke wrote:
> >> >Ok. However every piece of code which will get into cvs will be
> >> >reformatted.
> >> 
> >> You obfuscated by you, right?
> >
> >Indent.
> 
> Your indent methods or technique have been commented on as not being 
> quite like any others. And when they take code that is in conformance
> with K&R 2 and do interesting things with it, the effort seems to have
> other purposes.
> 
> Even if you are honestly trying to standardize the code, it is like
> applying trig functions to a job without really understanding why they
> don't always work. Automation is really not foolproof, especially if
> used foolishly or misapplied.
> 
> Besides, you really should not touch patches except to fix major issues.
> This means that sequences of patches can be rolled in and out smoothly
> and the record of patches reflects what the submitter actually did, as
> opposed to what was done to the code by someone with less knowledge and 
> understanding. Following this rul would have saved a few extra bug fixes
> that I know of.
> 
> There are a few issues like this that still need to be straightened out :-).

Indent will only change the syntactic appearance of the code. It won't
change any semantic. I will continue to indent all code which I
apply. As you may have noticed I try to understand all code which I apply.

> >> >Ok. From a test game:
> >> >
> >> >2: src=(43,4) dest=50,7)
> >> >2:   orig=SE, jason=SE, ross=E, raimar=SE, raimar2=SE
> >> >
> >> >So we see that diff_x=7 diff_y=3. So we have a gradient of
> >> >m=diff_y/diff_x=3/7.
> >> >
> >> >Now comes the tricky part where your error is: which gradient is the
> >> >border between the SE part and the E part? I think your answer would
> >> >be 0.5. Probably because m=1 divides the quadrant. And 1/2 would
> >> >quarter the quadrant. THIS IS WRONG. The correct gradient is
> >> >tan(pi/8)=0.4142... It is now no surprise that the gradient from above
> >> >m=3/7=0.42857... is between 0.4142 and 0.5.
> >> 
> >> Raimar LOOK AT your numbers. You need to move 7 east and 3 south. It
> >> should be clear as mud that the straightest direction looks like this
> >> with the first move to the EAST.
> >> 
> >>  0 1 . . . . . .
> >>  . . 2 3 . . . .
> >>  . . . . 4 5 . .
> >>  . . . . . . 6 7
> >> 
> >> Your trig functions are clearly a bit out of whack. Do you know why?
> >
> >
> >Doing the example with pencil and paper:
> >
> >  0 . . . . . . .
> >  . 1 2 3 . . . .
> >  . . . . 4 5 . .
> >  . . . . . . 6 7
> >
> >But why is your solution better? Because it is symmetrical?
> 
> Actually it is because it more closely follows the straightest direction
> (which is what is drawn in the diagram). Both of our methods may do 
> something quite different when applied iteratively in the general case. 
> 
> Aside:
>   This is because they start from the iterated position and lose any  
>   past recollection of partial moves into the next tile, i.e. after the 
>   first move above, you should be 3/7 in y following the true straightest
>   line, but iterating effectively resets you back to 0 in y, i.e you 
>   start each subsequent step with a clean slate.

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?

I admit that your method matches the ideal line more closely (however
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?

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?

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

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.

> But the method is to return the "straightest direction at any given 
> point", so with that strictest interpretation mine is doing exactly 
> that except for the 50-50 case in which it always chooses the diagonal.
> 
> If you renamed the method almost_straightest_direction() yours would
> then be equally valid.
> 
> This may illustrate a bit better how close the last two methods are.
> Feel free to uncryptic mine along these lines if it stills seems so 
> foreign, or conversely optimize yours by fixing a few of the tests and
> code flow to eliminate redundancies and extra computations :-).
> 
> If you change my method to do something like this, you can get it
> to duplicate yours (with just two more integer multiplies). I've 
> expressed a couple of things in terms you used that may require 
> outside tweaks if you try to apply this pseudo code fragment literally.
> 
> if (delta_y < delta_x) {
>   if (delta_y * 65K < delta_x * (TAN_PI/8 * 65K))
>     nn = !(xpos) ? 7 : 1;
> } else {
>   if (delta_x * 65K < delta_y * (TAN_PI/8 * 65K))
>     nn = !(ypos) ? 3 : 5;
> }
> 
> Aside: Note the outer 'if' is not strictly required, but it balances
>        the load between x vs y so you only do one of the multiply
>        tests in any particular case (+1 if vs ~3/4 x 2 '*').
> 
> This just determines which of the 4 cartesian directions you are 
> "closest" to, with the fall throughs defaulting back to the diagonal
> moves as in the original code (these are trivially recorded as
> (!xpos)*4 + (!ypos)*2 in the earlier two compare sets). Note the
> original code effectively has the TAN term set to "almost 0" though
> it does this a little more verbosely in code paths.
> 
> The index positions here are arbitrary (and local to this routine)
> in the same way xpos and ypos are. They are just a way to record the 
> 8 possible outcomes currently in the form ...
> 
>   6 3 2
>   7 x 1
>   4 5 0
> 
> Since this needs to be reported back in a particular direction
> system the last step was to "translate" by returning tx[index], 
> i.e. tx[0] = DIR8_SOUTHEAST, tx[1] = DIR8_EAST ...
> 
> >Yes it may be difficult to work with me but I have to understand
> >it. But I feel I'm really close now. Have some patience.
> >
> >     Raimar
> >
> >-- 
> > email: rf13@xxxxxxxxxxxxxxxxx
> > Make a software that is foolproof, and only fools will want to use it.
> 
> 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).

        Raimar

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