<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 | | | | | | A | | | | | | B |
> - - - -
> 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
Freeciv-dev mailing list