[Freeciv-Dev] Re: Reproducable core dump (PR#1051)

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

Re: air_goto_patch

An idea:

The A* search as you do it,

add_to_mapqueue(cost + real_map_distance(x1, y1, dest_x, dest_y), x1,
y1);

will be of order O(n^2) even if there are no units between src and dest. 
It is illustrated on Fig.1 (src = O, dest = X, numbers are the
add_to_mapqueue values, blue correspond to the tiles added to the
mapqueue and never removed from it, black correspond to
added+taken+processed)

If, instead, you do

add_to_mapqueue(cost + 2*real_map_distance(x1, y1, dest_x, dest_y), 
                x1, y1);

the search will be of order O(n), at least in the best case, as
illustrated by Fig.2 (same notations).

Please check it, I'm not 100% sure I took everything into account.

The straightest_direction search will still be faster, if it succeeds,
which will be the case most of the time.

G.

 --- jdorje@xxxxxxxxxxxxxxxxxxxxx wrote: 
[...]
> I don't see the point of having separate cases for a depth-first-search
> 
> (sans backtracking) and a full warmap search.  An A* search should have
> 
> all the good points of both (although it will use more memory than the 
> depth-first, but I don't think that's an issue).  However, it will be 
> significantly slower than the current algorithm (though still O(n) in 
> cases where the simple algotirhm would succeed), so perhaps it's 
> worthwhile to leave in the simple algorithm.
> 
> In either case, though, the warmap-style search should be an A* search.
> 
>   We have a simple minimum distance estimator, so we might as well use
> it.
> 
> 
> Okay, forget all that.  The new patch gets rid of the goto cleanly, and
> 
> also cleans up the code quite nicely (and I've tried to comment 
> thoroughly).  It includes the quick-search, but it's been trimmed down 
> even more.  The full search has been changed to an A*.  I'm a bit
> unsure 
> of the "known" checking, though: the code will refuse to send the plane
> 
> through an unknown tile, but will happily send the plane over a known, 
> fogged tile assuming no enemy is there.  But this assumption is bad:
> for 
> instance you shouldn't send the plane over a known city (although it 
> will most likely be okay since you'll realize the mistake once you get 
> in sight of the city, but...).  I'm not quite sure how to handle this.
[...]

__________________________________________________
Do You Yahoo!?
Everything you'll ever need on one web page from News and Sport to Email and 
Music Charts
http://uk.my.yahoo.com