<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 Freeciv-dev@gna.org https://mail.gna.org/listinfo/freeciv-dev