[Freeciv-Dev] Re: [RFC] Path finding interface #9

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 5 Jun 2002, Raimar Falke wrote:

> On Fri, May 31, 2002 at 09:02:21PM +0200, Raimar Falke wrote:
> > We also have to think about general ideas since it may be possible
> > that another user (auto-explorer, attacking code) has even other
> > requirements.
> 
> Turns out that this is true. Suppose we want to code something which
> maximize unfogged tiles/turn. You can do this with the proposed
> interface. Almost. You add "8-no of unfogged tiles by this step" to
> extra_cost. However you need the path to this step since you shouldn't
> allow to "rediscover" the tiles you discovered in the previous steps.

I'll think about it.  But in any case it does not require more than just 
        move_points_spent + extra_cost
formula.

> It also turns out that the trireme case is equivalent to the planes
> case: in both cases you have a list (or a test) of allowed destination

Mmm, an interesting idea!
Unfortunately, the list of allowed destination is rather big...
Also, the distance between such destination is not always what it seems.

> at the end of turn. Although I have no code I think that the search in
> a search you mentioned is cleaner than the parallel approach. But I
> have to further think about this and code something.

Yes, I like it more too.  I have sketched a refinement of this algorithm, 
it shouldn't be very heavy.

> One last: we can change our "uniform cost search" (aka Dijkstra) into
> an A* algorithm if we let the user specify a heuristic function which
> estimates the cost from one position to the goal. Obviously this can't
> be used for the iterate case. Also on the land moving you have the
> railroad case which cause BMC=0.

Right.  We can use it before rail is discovered and for sea units.

G.