[Freeciv-Dev] Re: [RFC] Move cost map interface

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, Apr 11, 2002 at 05:14:23PM +0100, Gregory Berkolaiko wrote:
> I think there are only 4 issues remaining:
> 1. Calculating # of turns.
> 2. Returning path with every new location (aka performance killa)
> 3. Taking into account possibility of waiting.
> 4. Special type of map "city map".
> 
> To minimize traffic let's discuss all in one email.
> 
> 1. We assume that my formula / algorithm works: we can get minimum number 
> of turns, maximum number of turns and "average" number of turns.  I object 
> to calculating all of these.  It's another useless performance killa.  Let 
> the caller decide what kind of info he wants (AI votes for average).  
> It can be implemented in 2 ways:
> (a) 
> enum num_turns_mode {
>   NTM_MAXIMAL, NTM_AVERAGE, NTM_MINIMAL
> } turns_mode;
> 
> in pf_parameter.
> 
> Than a hard-coded switch in cm_process_location or whatever is it's 
> equivalent.
> 
> (b) 
> three callbacks giving corrections to BCM to account for the turns mode 
> used.  the callbacks must be supplied with {x, y, dir, pf_map_t}, the rest 
> can be calculated.
> 
> I vote for (a), as I don't see any other possible turns modes and the 
> hard-coded is the fastest.

I'm also for (a) with the extention to have a "int turns[3];" in the
result. Which is calculated is controlled by ORing NTM_s together.

> 2.  pf_get_next_path would contain 2 parts AFAICS:
> getting the next nearest location and backtracking from it to calculate 
> the path leading to it.  The second part can be separated into a function 
> which the user may choose to call or not.  There is no reason to force 
> user to call it as this information is unnecessary for the most AI 
> calculations (why'd you want to know a path to a location you don't want 
> to go to?).
> 
> And I object vehemently to the attitude "let's ignore performance issues 
> now and later we'll see".

We already have the method to calculate the path: pf_get_path_from_map.

Problem: (x,y) does _NOT_ exactly describe a path. Because there is
"(4,5) with 1 moves left" and (4,5) and waited a turn and now 3 moves
left". But I agree that from a performance point of view the path is
unneeded. Solution? Adding an result moves_left to pf_get_next_path
and also moves_left as a parameter to pf_get_path_from_map?

> 3. The possibility of waiting must be switchable on by a special parameter, 
> consider_waiting, as it is not necessary in most cases.  we may choose to 
> provide for an extra callback is_location_safe, to bring down overhead in 
> the case when consider_waiting is TRUE.

But this extra parameter consider_waiting is not needed because it is
the same as "is_location_safe != NULL".

> 4. Special "city map" type is the cheapest way to have a map incorporating 
> information usable by all types of units.  If we choose to do away with it, 
> we'd face the necessity of calculating 4 maps per city: for units with 
> speed 1, 2, 3 and IGTER units.  What happens if someone starts hacking 
> rulesets is sad to visualize.  I think that "city map" is an acceptable 
> estimation for AI use.  In really serious cases (in such case the unit 
> type will be known) AI can make another map for this particular unit.  
> "Non-exact" is not synonymous with "useless".

Can you please explain to me the properties of a city_map? What costs
does it calculate?

> If you send me the latest of your path_finding?.h, I'll have a go at it 
> tomorrow.

Attached.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "Life is too short for reboots."

path_finding4.h
Description: Text document