[Freeciv-Dev] Re: [RFC] Path finding interface #9

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Attached is the result of my graph-drawing.

Just for the reference, the problem is: The traveller covers 6 miles a day 
and is not allowed to stay overnight on the road or in the cities marked 
red.  Find the shortest path going from A to B.

I think the graph now encompasses all problematic aspects of such
path-finding.  The most prominent feature is that the shortest routes no
longer form a tree.  An immediate consequence is that more information has
to be stored, in particular at vertex X, to provide for easy path
selection once you have the cost-map ready.

The other, already mentioned, features are:
* Ignoring danger and doing Dijkstra will give you paths you cannot take
* You have to take into account the possibility of waiting (at vertex b in 
this example).


Enjoy,
G.

On Mon, 27 May 2002, Ross W. Wetmore wrote:

> At 12:50 PM 02/05/27 +0100, you wrote:
> >On Sun, 26 May 2002, Ross W. Wetmore wrote:
> >
> >> At 08:30 PM 02/05/25 +0100, Gregory Berkolaiko wrote:
> >> >On Sat, 25 May 2002, Ross W. Wetmore wrote:
> 
> >> First, you don't need to do a "sub-Dijkstra". As in my example, you just
> >> need to mark the unsafe tiles as "invalid" meaning you can't stop there
> >> and continue normally. Any subsequent updates that would require you to
> >> stop or stall at such a tile would be dropped or equivalently have a
> >> MAX_COST value.
> >
> >I think I do need a sub-Dijkstra but maybe we disagree because we are 
> >talking about slightly different algorithms.
> 
> You might. It is decidedly murky to me at this point, and I am too lazy
> to draw my own graphs. See below ...
> 
> >> But when you do reach a safe tile from an unsafe one, you have to do more
> >> than just accumulate the single step move_cost. You need to step back 
> >> through all the unsafe path segment until 1) you run out of MP, or 2) you
> >> reach g and index back to the "safe" way to enter g given the accumulated
> >> steps for the unsafe path segment. At this point, if you find you need to
> >> stall before entering g, then you add this stall time to the movecost at
> >> the unsafe tile (i.e. at the end of the path segment, not at g).
>        ^^^^^^
> 
> Just in case I was misleading you here, this should maybe have been 
> "safe" tile. It is the final "unsafe to safe" movecost, which you then 
> store at the "safe" tile if it is less than the one already there, i.e.
> according to the normal rules.
> 
> >Ah, I see.  I dont think it will work.  Let me draw some more pictures...
> 
> It gets messy with a chain of unsafe moves, because the movecost on
> exit of the segment needs to backtrack for the least cost path, and 
> this involves at least a lookup at the unsafe segment start if not a 
> stall. You can get into the unsafe path segment in many ways, some
> of which may not have been computed yet.
> 
> The last statement may be the one that forces one to do *something*.
> It would come about if you computed a movecost through an unsafe
> segment. Then a little later you found a way into the segment (at a 
> later tile?) that was less than via the stalled value at g, but of
> course more than the simple count through g (this being the Dijkstra 
> invariant condition).
> 
> Nobody at the point where you enter the danger segment sees any decrease
> in cost, so no tile is "rescheduled" along this path. If you haven't
> yet reached the unsafe to safe exit step, you will be fine and when it
> comes up for processing you will have all the prerequites. But if it
> has come up, then it will never be recomputed, at least down the 
> danger segment.
> 
> There may be other ways for things to fail. The fact is that you are
> breaking the Dijkstra condition that says shortest path moves are 
> always computed first. When you eventually start to add the stalls
> and different routes, you have computed a long path move through a
> tile before its shortest one reaches the tile. But of course this is
> only for one of the ways through the unsafe segment, others might be
> fine.
> 
> So you need to compute to at least the maximum stall + entry cost
> at any point in the danger segment before you compute any exit
> steps from it to make sure you have all the cases for the backtrack
> step. But this might mean that some point beyond the safe tile has
> already been computed. 
> 
> So you need to modify this to make sure you have computed all costs 
> less than the step out cost before you can complete it. This may mean 
> holding a queue of sub-Dijkstra steps (not full tile adjacent iterates) 
> until the last minute before committing them to the main algorithm - or 
> something like that.
> 
> But I am mumbling ... must be brain strain.
> 
> [...]
> >Okay, now I need to draw more graphs, as I have uneasy feeling about my 
> >G.2 algorithm.
> 
> Yeah, there are a few loose ends of DNA to pin down for super status.
> 
> >G.
> 
> Cheers,
> RossW
> =====
> 
> 
>

waiting2.gif
Description: GIF image