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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Wed, 10 Apr 2002, Raimar Falke wrote:

> On Tue, Apr 09, 2002 at 08:49:53PM +0100, Gregory Berkolaiko wrote:
> > Sorry about the delay in replying.
> > 
> > I read your proposal.  It mostly deals with the path-finding, which is the 
> > structure above the map.  IMO path finding accounts for a quite small 
> > percentage of the map-generation used by the AI.  So I think we should 
> > start from the map.
> 
> I have only choosen the term "path finding" because warmap.[ch] is
> only known to insiders and goto.[ch] was already gone.

I think move cost map is more general.
A lot of warmap usage is about estimating distance, not calculating paths.

> > A question:
> > does pf_get_path_from_map return you the "best path" or a path with 
> > minimal FC and than you'd use pf_get_next_path_from_map to find the best 
> > one?
> 
> The best path has minimal FC. If two paths with the some minimal FC
> are known the decision is made based on turns to target and move
> points left.

This is not an answer to _my_ question.  But forget it, it was immaterial.

> > A comment:
> > as you'll see from my map proposal I'd prefer to get the possibility of a 
> > BMC-callback too.
> 
> What type of scenario could require this? You can even now adjust the
> BMC with extra costs.

Yes, I thought about it, you are right.
The "special" scenarios I had in mind are:
1. Finding the best route for a road from A to B:
first minimize the length of the future road (equiv to BMC being igter), 
than minimize over additional cost arising from the time required to build 
the road.
2. Finding the shortest and safest path for a trireme (see anxious trireme 
bug):
first minimize over the lengths of all "safe" paths (the path is "safe" if 
the unit ends its move next to the shore),
than among these paths find the one which sticks to shore most of the time 
(in case the trireme has to end the move early).
Looking for safe paths would involve returning PF_IGNORE_COST as the 
additional cost for the path which would end the turn away from shore.

This leads to the problem which is hardest to solve IMO:
3. Take into account the possibility to end move early to stay out of 
trouble.

This would be very useful for military unit too.

G.