[Freeciv-Dev] Re: goto cleanup

[Thue Janus Kristensen <thue@xxxxxxx>]

On Tue, 23 May 2000, Falk Hueffner wrote:
> Thue Janus Kristensen <thue@xxxxxxx> writes:
> 
> > Once again - getting close to acceptable.
> > 
> > Does:
> > -Remove code from find_the_shortest_path that tried made sure units
> > moving from a transport could move due to ZOC. (units can always move fro
> > ocean onto land.)
> > -Rewrite/remove horribly tangled dir_ok/dir_ect.
> > -integrate the used parts of some functions into the part of
> > find_the_shortest_path that used them (each only used a small part), and
> > move the functions to aiunit.c as they were used by other functions there.
> > -Rewrite the handling of RR loops. I am not wholly sure how they were
> > avoided before, but from what I could understand this is at least as
> > smart.
> > -Rename lots of variables
> > -Document document document.
> 
> Thanks for cleaning this up a bit. I have some comments:
> 
> The comments mention the algorithm is A*, but that is not possible
> because railroads defeat any lower bound for target distance. It
> actually looks like Dijkstra's algorithm to me.

Umm, I am actually not very knowledgeable about algoritm names, I will
trust your name :).

> The code for loop detections seems very complicated. Also, couldn't
> "Assign a cost >0 (1) to movement on RR in the opposite direction of
> the +destination" lead to nonoptimal solutions?

Yep. But no worse than those that are in the current goto. They actually
seem to be equivalent when testing. (I know the loop detection is not
optimal, as I also said in the comments, but it is better than the old
one).
An example where it will take a nonoptimal path is this:
(R:RailRoad r:road)

rRr
RrR
RrR
Rrr
rrr
On this small map, numbering from top left going from 2,2 to 4,1 will
choose a path that goes (2,2)->(3,1)/(3,2)->(4,1) instead of following
the RR all the way. (going twice in the wrong direction gives an extra
cost of 2, and the differnce between the chosen and the optimal path is
only 1 in movecost...)

Anyway, the main point of this patch was to document and clean up,
so that other people that wanted to modify and tinker would have a chance
of understanding it (and want to, once they saw how dumb it was :) ),
which seems to have succeded :).

> I wonder if it wouldn't be easier to simply add a small constant to
> the move costs on every move (with maxMoves * constant < 1). That
> would also have the nice effect that for costwise equivalent paths, it
> would choose the one with the least number of moves. This could be
> implemented either with floats or by pre-shifting the move costs by,
> say, 16 and using 1 as constant.
>
>       Falk
Yes, that would actually be a nice simple solution. 16 would be
a bit much since the warmap use chars for movecosts and therefore have a
maximum of 255. (it would be nice for GOTOs to be longer than 20 tiles
max...) We could use a smaller constant or change the warmap to use
shorts. Since changing to shorts in the case of a maximally sized
200x100 map would only take 20KB I propose we do that.
I guess this will also remove some calculation in dir_ok(), also nice!

Will you make an updated patch or shall I?

-Thue