[Freeciv-Dev] Re: [RFC] Path finding implementation.

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Mon, 29 Jul 2002, Raimar Falke wrote:

> On Mon, Jul 29, 2002 at 09:08:31PM +0100, Gregory Berkolaiko wrote:
> > On Mon, 29 Jul 2002, Raimar Falke wrote:
> > 
> > > On Mon, Jul 29, 2002 at 08:29:00PM +0100, Gregory Berkolaiko wrote:
> > > > On Mon, 29 Jul 2002, Raimar Falke wrote:
> > > > 
> > > > > On Mon, Jul 29, 2002 at 07:50:17PM +0100, Gregory Berkolaiko wrote:
> > > > > > > > Why do you need two plain maps?
> > > > > > > 
> > > > > > > I expected this question ;) We need to find the paths to all 
> > > > > > > positions
> > > > > > > which are reachable in this turn. However for these paths we need 
> > > > > > > to
> > > > > > > use the original cost and cop functions. But these don't guarantee
> > > > > > > that we get first get all position of this turn and after this 
> > > > > > > all the
> > > > > > > positions of the next one. So we need a second map with a simple 
> > > > > > > cop
> > > > > > > which takes only the turn into account.
> > > > > > > 
> > > > > > > > > > The only reference to is_dangerous_position I found was 
> > > > > > > > > > assert(is_dangerous_position == NULL), so the support is 
> > > > > > > > > > switched off.  
> > > > > > > > > > Maybe it was an older version?
> > > > > > > > > 
> > > > > > > > > > I still think that user-suuplied COP is useless.  It does 
> > > > > > > > > > not solve any of 
> > > > > > > > > > the problems, why should it be there?
> > > > > > > > 
> > > > > > > > It's a valid question, please don't ignore it.  You mentioned 
> > > > > > > > the explorer 
> > > > > > > > mode which needs EC only.  Please explain what you mean in more 
> > > > > > > > detail.
> > > > > > > 
> > > > > > > I reworked the explorer completely. It doesn't need ec2 anymore.
> > > > > > > 
> > > > > > > Take the case from above: we need the get_ECOT of the original
> > > > > > > parameter set because this will discard us a lot of positions
> > > > > > > (remember BMC of unknown is 0). But we can't use the original
> > > > > > > get_COP. We want our which only takes turns into account.
> > > > > > 
> > > > > > Please correct me if I am wrong.  Are you saying that you don't 
> > > > > > need 
> > > > > > "flexible" COP for explorer anymore?  Where would you need it then 
> > > > > > (I 
> > > > > > don't believe that you really need in for explorer either)?  So far 
> > > > > > it's 
> > > > > > only causing problems, like these two maps above.
> > > > > 
> > > > > I didn't make myself clear: it is the solution (it is needed) and not
> > > > > the problem for the is_dangerous_position != NULL case above.
> > > 
> > > > The solution of what problem?  Ensuring that the positions come at you 
> > > > ordered only by the time required to reach them?  The standard COP that 
> > > > I 
> > > > suggest we use ensures exactly that, 
> > > 
> > > > provided the user doesn't supply some crazy ECOT function.
> > > 
> > > And that is the point. The user can specify any ECOT function he
> > 
> > This will mess up the calculation.  But so will any non-standard choice of 
> > COP.
> 
> Which calculation? We had this issue between valid and useful COP
> before.

Exactly.  And it seems to be pretty much the only issue left.  It is still 
my strong opinion that out of multitude of possible COPs only one is 
useful and the rest are not valid.  And I asked you for examples defeating 
this.  It seems that the safe-path-finding is the only example.  I claim 
that it will be resolved as well by the standard (and valid) COP.

> 
> > > want. What would really solve this is splitting of ECOT into
> > > you-are-not-allowed-to-go-here (the current PF_IGNORE_COST case) and
> > > the "real" ECOT. Since we are only interested in the pruning
> > > capabilities of the ECOT function for the first plain map.
> > 
> > I thought about it.
> > There should be 
> > PF_IGNORE_EXTRA_COST = MAX_INT
> > PF_MAX_EXTRA_COST = sqrt(MAX_INT)
> 
> > PF_MAX_EXTRA_COST is really a conversion constant, between move
> > points and extra cost points.
> 
> In other words: PF_BMC_FACTOR.

Mmmm.  Right.

> > so the name is not good, EC can be bigger than
> > PF_MAX_EXTRA_COST, but it will effectively mean that we'd prefer a longer
> > but safer route.  Although I am not a big fan of this practice, I
> > regocnize it might be useful.
> > 
> > But the EC supplied to safe-path routine should not exceed 
> > PF_MAX_EXTRA_COST
> 
> I don't see how this will solve the problem above.

What is the problem above, maybe we are talking about different problems?
Is it "to ensure that the frontier tiles will be dequeued basing on the 
time that it takes to reach them, i.e. a tile that is (k+1)turns away will 
never be considered before a tile k turns away" ?


> > > >  Here's an extract from my earlier email:
> > > > > Here is a summary of my position anyway:
> > > > > 1. In TM_NONE turn and moves_left are useless.
> > > > > 2. In TM_MIN or MAX, BMC is useless and the only combination of turns 
> > > > > and 
> > > > > moves_left that is good for anything is
> > > > >       moves_spent = (turns+1)*move_rate - moves_left
> > > > > 3. Thus we can define a universal quantity
> > > > >       cost = (tm == TM_NONE ? BMC : (turns+1)*move_rate - moves_left)
> > > > > which is the only sensible quantity there is.
> > > > > 4. cost + EC is your cop
> > > >      ^^^^^^^^^
> > > > Mistake here.
> > > > The universal COP is 
> > > >    cost * MAX_EXTRA_COST_OF_PATH + EC
> > > > 
> > > > where MAX_EXTRA_COST_OF_PATH can be rather high (sqrt of MAX_INT).
> 
> > > > > > It is easy to fix your algorithm though.  For this we need to 
> > > > > > provide an
> > > > > > extra functionality: non-transit (NT) tiles.  Those are the tiles 
> > > > > > that
> > > > > > will be returned by the iteration (thus put into the queue/heap) 
> > > > > > but won't
> > > > > > be processed (think about ships targeting shore).  There are three 
> > > > > > ways of 
> > > > > > doing it:
> > > > > > 
> > > > > > 1. BMC call-backs, which will check if the origin tile is NT and 
> > > > > > return MAXCOST in this case, thus forbidding exit from the tile.  
> > > > > > It's not 
> > > > > > very elegant and means that the adj_dir_iterate will still be run 
> > > > > > on an NT
> > > > > > tile but will just get no new segments out of it.
> > > > > > 2. Special call-back is_transit or something
> > > > > > 3. Passing a boolean arg to pf_next, which is equivalent to having 
> > > > > > the 
> > > > > > call-back in the body of the while(pf_next(map)){ }  cycle
> > > > > 
> > > > > 
> > > > > > Once we have this in place, just mark all _safe_ tiles as NT in the
> > > > > > auxilliary path finding in your algorithm to avoid unnecessarily
> > > > > > deep searching.
> > > > > 
> > > > > IMHO this is wrong since the "micro" path to a safe position can use
> > > > > other safe positions.
> > > > 
> > > > think about simple dijkstra, we walk over safe positions step by step.
> > > > "micro" paths are those which start and end in safe positions, 
> > > 
> > > > have only unsafe positions in-between
> > > 
> > > Nack.
> > > 
> > > > and arrive to dest before end of turn.
> > > 
> > > # - land
> > >   - water
> > > a-i: safe
> > > 1-9: unsafe
> > > 
> > > 123456789
> > > abcdefghi
> > > #########
> > > 
> > > We want to go from b to h (4 steps are allowed, full moves at the
> > > start, all costs are equal). A valid micro path for the first turn is
> > > also b-c-4-e. This path has the same "rights" as b-3-4-e. Which one
> > > will be choosen depend on the cost but both can be selected with the
> > > right cost.
> > 
> > Let's say b-c-4-e is shorter than others.  You allege that with my 
> > modification it will never be found, right?
> > 
> > Well, when b is processed (using your expand(), but modified), location c 
> > will be put in the queue.  When c is processed micro path c-4-e will be 
> > found, thus the whole path b-c-4-e will be found in due time.
> 
> I didn't touch the path finding code in weeks so I may be wrong but:
> if the micro path b-c is put into the queue means that the unit will
> wait at c a turn. Which is not the same as going from b to e in one

If this is so, it's wrong (but your code looks right).  b-c put in 
the queue should mean the the unit will _consider_the_possibility_ of 
waiting at c a turn.

> turn.

G.