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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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.

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

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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Despite all the medical advances of the 20th century, the mortality 
  rate remains unchanged at 1 death per person."