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

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

 --- jdorje@xxxxxxxxxxxxxxxxxxxxx wrote: 
> 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.

You are right.  One can fix that, but the fix will decrease the speed so
it's arguable whether the result will be any faster than your pure A*.

Let's stick to A*.

More on your patch will follow.

G.

__________________________________________________
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