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: freeciv-dev@xxxxxxxxxxx
Cc: bugs@xxxxxxxxxxxxxxxxxxx
Subject: [Freeciv-Dev] Re: Reproducable core dump (PR#1051)
From: jdorje@xxxxxxxxxxxxxxxxxxxxx
Date: Tue, 27 Nov 2001 11:25:42 -0800 (PST)

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,

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.

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.


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