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

[jdorje@xxxxxxxxxxxxxxxxxxxxx]

Gregory Berkolaiko wrote:

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

Interesting.  It then becomes a "modified A* search".  But does it 
assure that the shortest path is always found?  This is a key quality of 
A*.  I think your algorithm may not do this in situations where there 
are enemy units in the way.  You might make a large detour at the end 
rather than a small detour at the beginning to avoid unusable airspace.
Under my most recent patch, this change could be accomplished by adding 
another real_map_distance() right before adding the element to the 
queue.  The earlier calculations should remain unchanged.  It'd be a 
pretty simple change to make.
jason