<URL: http://bugs.freeciv.org/Ticket/Display.html?id=37820 >

I believe from an earlier discussion with Sam and Jason in Nov 2006
that the pathfinder does a flood-fill type search which works like a
simple form of a pruned A* search mostly like you described it below.
I'm not sure whether a smarter distance estimator can be used that
would reduce the space searched towards the opposite direction a bit.
You would have to disable railroads for the purpose of getting
different trading distances(road quality) and pruning, that is e.g.
set them to 1/6 move cost.

On 3/17/07, (Eddie_Anderson) <[EMAIL PROTECTED]> wrote:
> <URL: http://bugs.freeciv.org/Ticket/Display.html?id=37820 >
> Per Inge Mathisen <[EMAIL PROTECTED]> wrote:
> >On Fri, 9 Mar 2007, (Eddie_Anderson) wrote:
> >>    This is an experimental patch.  It replaces "real map distance"
> >> (RMD) with pathfinder (PF) distance in the calculation of "waste /
> >> corruption by distance from the capital".
> >IIRC, no. Remember that the straight path may not be the longest, so we
> >need to do an exhaustive search to find the guaranteed shortest path.
>     OK.  Here's another question (and maybe PF already does this):
>     Do you know if PF prunes the search if the distance exceeds
> a given value?  What I was thinking is this:  If the real map
> distance (RMD) is 6, then we could pass that as a parameter to PF.
> In effect, we tell PF that we don't care about any path that is
> longer than RMD.
>     E.g. assume that we ask PF to find a path from A to B.
>              C
>              -
>          C |   |   |
>          -   -   -   -
>      C |   |   |   |   |   | A |   |   |   |   |   | B |
>          -   -   -   -
>          C |   |
>              -
>              C
>     The RMD between A and B is 6.  Now PF starts its search.  Assume
> that PF starts following a road the leads to the left of A (one that
> takes it further away from B).
>     Assuming that road movement is still 3 tiles/turn, then once PF
> reaches a point 12 tiles away from B (represented by the C points),
> then PF should stop evaluating that path (because the best possible
> path (i.e. all road tiles) from that point would take the rest of
> the 6 turns to get back to the destination).
>     Until PF gets to one of the C points, it still might find a
> path that way that takes less than 6 turns.  But once PF reaches a
> C tile, is PF smart enough to abandon that path and look elsewhere?
>     Of course, this assumes that no railroads have been built yet.
> With railroads offering unlimited movement, PF pruning might be
> useless.

Freeciv-dev mailing list

Reply via email to