Complete.Org: Mailing Lists: Archives: freeciv-dev: April 2002:
[Freeciv-Dev] Re: [RFC] Move cost map interface
Home

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: "Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>
Cc: Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>, freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: [RFC] Move cost map interface
From: Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>
Date: Tue, 16 Apr 2002 09:31:46 +0200
Reply-to: rf13@xxxxxxxxxxxxxxxxxxxxxx

On Mon, Apr 15, 2002 at 09:20:40PM -0400, Ross W. Wetmore wrote:
> At 04:22 PM 02/04/15 +0100, Gregory Berkolaiko wrote:
> Raimar can perhaps think about what he wants beyond the shortest path, 
> and how this should be recovered from the warmap data which *might* entail
> storing more than just a simple cost result.

Currently only the timing data.

> >I think Raimar's code does it, storing everything in pf_parameter.
> 
> Good. Just so long as it doesn't start creeping into warmap code and is
> only used by the costfn (or post-processing function) that it is designed
> for. My understanding is that pf_paramter was becoming "the-one-and-only-
> true-way-to-parameterize-all-costfns" - that would be a mistake.

pf_parameter is the one and only way to customize the path finding (I
dislike the term warmap). I'm not sure what you mean with costfn but
the path findind has a cost function for the basic move cost (well in
fact is uses map_move_cost or something similar with a different
interface). You can specify extra cost functions. The user of the path
finding core is free to choose these extra cost functions.

> >> You know the range of costs. It is a parameter to the warmap (maxcost).
> >
> >yes, but each "primary cost" is refined by PF_BMC_FACTOR "secondary 
> >costs", so you get MAX_COST * PF_BMC_FACTOR = 255 * 100
> 
> There are several answers to this. First 100K is not a big chunk of if
> that is what you need. Second, most warmaps use THRESHOLD or something
> on the order of 72 as maxcost if you dynamically allocate this. Third
> is you can use a sorted bucket if you think that the bucket queue depth
> is on average a small number ... yada, yada, yada.
> 
> And last is consider what the finer granularity really means, and is it
> worth it. As an example, if this is not a cummulative cost, but computed
> at a given point, then you only need 255 buckets, and you use the finer
> granularity to set the appropriate direction. 25500 buckets is only
> important if you can accumulate differences across buckets/steps which 
> actually goes against the normal Freeciv move process i.e. an integral 
> rounded cost.

This number (255*100) is just wrong. The BMC is limited to <=3 (for
mountains)*SINGLE_MOVE. The EC is unlimited. Also PF_BMC_FACTOR isn't
set in stone. If we need a finer grain we increase it. If a lower
value speed things up considerably we descrease it.

> >> >I don't quite understand the use of the below.  But one day I'll grow up 
> >> >to it ;)
> >> 
> >> Hint: the retcode is probably the switch value used in the STD 
> >>       hardcoded/preprocessed elements in warmap.next_location, or
> >>       an unresolved sub-case they didn't handle.
> >> 
> >> Hint 2: read it as pseudo-code and not valid C code.
> >
> >Yes but why should any such processing be done in the "user code"?
> 
> Because Raimar (and you and I) are not particularly good at writing
> general library code that will handle all future possibilities. If the
> processing internals are in a canned warmap routine, the user can't
> modify it, spends a lot of time discussing the size of our brains and 
> immediate family ancestry then goes off and rewrites a completely new 
> buggy version of his/her own or worse adds it to the existing canned 
> code bloating warmap ad nauseum. If the processing exposes the internal 
> switch for the user to insert extra specialized code into, the user is 
> happy and thinks we were all really wise people to make such a useful 
> thing - and only breaks his/her routine in the process.

I don't know what internal switchs you mean but the extra cost
callback should be enough to customize the result. Gregory seems to
prefer that the caller checks for exit.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I heard if you play the NT-4.0-CD backwards, you get a satanic message."
 "That's nothing, if you play it forward, it installs NT-4.0"


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