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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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:

[..]

> >
> >Exactly.  I could not fully understand your description below, so I will 
> >give the two methods that I invented yesterday, I suspect they are 
> >equivalent to your one (scroll down):
> 
> I think they are cousins at least. A little more inbreeding and we may
> have either a super-species or one with a permanent genetic defect.

:)

> >Notation: MP == move points.
> >
> >%%%%%
> >
> >Method G.1:
> >
> >Do the conventional warmap, recording at safe tiles the shortest time to 
> >get there and the direction.
> >
> >Unsafe tiles should be split into 6 (where 6 is the max MP of the 
> >unit), indexed by j = 1..6.   For an unsafe tile D, in D[j] we record the 
> >shortest time and direction to get to D while still having j MP left.
> 
> I think this actually caches the stall computation and backtrack 
> selection moving forward, rather than doing it everytime you backtrack
> in my case. It is constant time, and will win if there are more than 
> 6 safe tiles found after the danger segment, which is almost a given.
> 
> So this is a very good refinement.
> 
> >Thus in the attached picture g[6] will contain time=18, dir=c,
> >g[4] will contain time=8, dir d and g[2] won't contain anything.
> 
> I would probably fill in 5, 3, 1 and 0 with values so you could do a 

with what values?

> lookup based on what you need vs a search, but this is noise level
> optimization and might change depending on the actual code/usage.
> 
> >Any move from safe S to unsafe D will potentially generate two entries at 
> >D: for just moving to S with whatever moves you have left and for camping 
> >at S overnight and then moving.
> 
> I don't think the method is complete. You need to move beyond the first
> unsafe point to a subsequent safe point for the data to actually be used,
> or in the above, you need additional data at D to make the final choice. 
> This doesn't seem to go far enough to talk about this - so it is part 1
> with the next as part 2 rather than a completely separate method, no?

No, G.1 and G.2 are two separate methods.  Yes, you are right I did not 
escribe what happens on D - D and D - S transitions.  I will try to 
rewrite it in full in a separate message.

[..]

> >%%%%%
> >
> >Method G.2:
> >
> >On any arrival to unsafe tile D we go into a small sub-Dijkstra with the
> >aim to get through the unsafe cluster.  Let's do an example:
> >
> >We first arrive to g from O with 3 MP left.  Consider g: we can get to 
> >h with 2 MP left.  Consider h: cannot get anywhere withour staying 
> >overnight at h --- don't record anything.
> >
> >....
> >
> >At last we arrive to g from c with 6 MP left.  At h we are with 5 MP.  
> >>From h we can now get to X with 0 MP left, which is okay since X is safe.  
> >We can also get to unsafe j which we do not record.
> >
> >This can be implemented by setting up a second queue with higher priority 
> >irrespectful of the distance to tile.  In the example above this queue 
> >will be holding h (from time to time).
> 
> 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.

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

Ah, I see.  I dont think it will work.  Let me draw some more pictures...

> Because you are correctly computing the minimum movecost path for stepping
> along the unsafe route, and always *adding* penalties as soon as you reach 
> a safe tile, you can do this within the current Dijkstra loop. The key
> point is that the movecost for a safe tile beyond the unsafe segment will
> include the stall and/or higher cost of the alternate back route. If you
> can reach this point during subsequent Dijkstra steps with a lesser cost
> not going through the unsafe path, this will happen normally.
> 
> If you have a chain of such unsafe tiles each with its own indexed list
> then you may end up walking back a number of steps, failing to find
> something, falling back up through the walk to take the next best case
> at a higher level until you eventually find an unsafe segment that is
> shorter than a single move.
> 
> [Aside]
> Note, if you are going to this level to track move boundaries for 
> unsafe moves, you also want to do it for safe ones, i.e. if you arrive 
> at a point with less than enough movepoints to continue 100% of the 
> time, you want to add a stall time to the movecost into this next tile. 
> This of course means that your unit move turns are accurately given 
> by the movecost values at every tile point in the warmap.
> [/Aside]

Yes, this is done in "maximum" turn mode in the (future) cost-map 
implementation.

> Unless you omitted something, G1 didn't look past the initial unsafe
> tile, and didn't do any operation to actually use the data it stored.
> So it wasn't complete until you did the G2 computation for this.

Yes, I did omit things...

Okay, now I need to draw more graphs, as I have uneasy feeling about my 
G.2 algorithm.

G.