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

[Raimar Falke <rf13@xxxxxxxxxxxxxxxxx>]

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:
> > > 
> > > > 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" ?

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.

> > > > >  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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 Windows: Where do you want to go today?
 Linux: Where do you want to go tomorrow?
 BSD: Are you guys coming or what?