Complete.Org: Mailing Lists: Archives: freeciv-dev: November 2001:
[Freeciv-Dev] Re: Reproducable core dump (PR#1051)

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: jdorje@xxxxxxxxxxxxxxxxxxxxx, freeciv-dev@xxxxxxxxxxx
Cc: bugs@xxxxxxxxxxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Reproducable core dump (PR#1051)
From: Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>
Date: Tue, 27 Nov 2001 15:30:42 +0000 (GMT)

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,

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

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.


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

GIF image

GIF image

[Prev in Thread] Current Thread [Next in Thread]