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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Tue, 30 Jul 2002, Raimar Falke wrote:

> On Tue, Jul 30, 2002 at 01:06:34PM +0100, Gregory Berkolaiko wrote:
> > 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:
> > > > 
> > > > 
> > > > 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" ?
> 
> Yes this is the problem. Ok I try it another time: we have a position
> and want all (micro) paths from this position which end in a safe
> position in this turn. If they can go over safe tiles or not isn't the
> problem here. We need the user-supplied ECOT because the path choosen
> needs it. However this user-supplied ECOT can return such big ECOT
> that a tile at (k+1)-turn is returned before a k-turn tile is
> returned. It doesn't depend how you choose the ECOT and the COP
> function. It was a design goal that you can compensate big ECOT with a
> turn and vice versa.

Don't you think that asking a user to supply ECOT not exceeding 
PF_BMC_FACTOR when also supplying is_position_dangerous call-back is 
quite reasonable?


> 
> > > > > >  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.
> 
> At least the code is like I think:
>  possible_neighbour->turn =
>    pf_last_position(&possible_neighbour->path_from_prev)->turn + 1;
> 
> You may now argue that the interface is incorrect or the
> implementation.

Not incorrect but suboptimal.  Never mind for now.  I was just confused by 
the the two calls to expand from macro_get_next_position

G.