[Freeciv-Dev] Re: [PATCH] Cleaned up magic code ingotohand.c (PR#944)

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

At 01:25 AM 01/09/10 -0400, Jason Dorje Short wrote:
>"Ross W. Wetmore" wrote:
>However, I think an even better algorithm might be possible.  Your
>algorithm is a huge improvement, but will still result in the unit
>traveling in either a cartesian direction or a diagonal one to get to a
>place where it's a straight cartesian/diagonal route:
>
>  
>X****
>     *
>      *
>       Y
>
>or
>
>X
> *
>  *
>   *
>    ***Y

Not quite. You need to apply the algorithm interatively, and this
makes the example you have below impossible without saving the initial
position as well as leading you astray in understanding mine.

The one I have will move either diagonally or in a cartesian direction
until it hits the 2x+y or various flavours borderline. The first (few) 
steps are actually the same ones you get in the "correct" path below. 
After it hits the borderline, it will look like the one you have below 
except coming in on a slightly shifted angle/ray the rest of the way in, 
always making the last step in a cartesian direction. Note the borderline 
in question is maybe easier spotted by thinking about the target point 
walking in towards you in reverse direction steps.

>The "best" algorithm, I think, would have a unit traveling into as close
>to a straight line as possible:
>
>X
> **
>   **
>     **
>       Y
>
>I believe this algorithm would be substantially more complicated,
>though, whereas yours should still be pretty simple.

The problem is that you need to step the short direction once every
long/short tiles with an interesting offset to the first one. It is
actually easier to work back from the middle of the walk.

When you call this function in an iterative loop, you lose the overall
information needed to do this, and start with a fresh step each time
which now wants the spacing every (long-1)/short tiles.

And the algorithm is in fact simpler than the current implementations
if you look at it in the submitted patches. It takes up a page because
of the various diagrams trying to explain each if clause. I really
should start using the Syela style to maintain consistency with the
codebase and keep things "simpler".

If you saved the long/short ratio, and replaced the "2" in 2x < y
tests, you would have the "correct" algorithm, I think.

The difference in doing it "right" may reduce the discrepancy between
the ares of the various octants, or make it more closely match a circle
rather than a square. But the map distances are not pythagorean, and
the current system is probably the closest to evening this aspect out.

>jason

Cheers,
RossW