[Freeciv-Dev] Re: find_the_shortest_path()

[Gregory Berkolaiko <gberkolaiko@xxxxxxxxxxx>]

Hi Jason,

First of all I am glad that somebody other than me is looking at
gotohand.c  There is a lot to be cleaned up there.  But caution must be
exercised.


 --- Jason Dorje Short <jshort@xxxxxxxxxxxxx> wrote: 
> /*
> To avoid RR loops (which may cause find_a_direction() to move a unit in
> cute little cycles forever and ever...), when we have more than one
> path
> to a tile and the second one is via RR (move_cost 0), we do NOT mark
> the
> extra path.
> */
> 
> However, Dijkstra's algorithm doesn't have this problem since any time
> the point is encountered a second time and the movement cost is no less
> it is not considered a second time.  Later on [2] we have:

AFAI understand find_the_shortest_path maps all possible paths of the
same length to a destination.  For flexibility reasons.  Client-side
gotos don't have to be that flexible: they can always ask the human for
help.

>       if (warmap.cost[x1][y1] <= warmap.cost[x][y])
>         continue; /* No need for all the calculations. Note that this also
> excludes
>                      RR loops, ie you can't create a cycle with the same 
> move_cost
> */
> 
> which makes the first comment wrong (or at least misleading).

no, both comments are correct. the algorithm will mark two equivalent
pahts unless the last step of the second path has movecost 0.

> Second, there is a lot of reptition in the function [3, 4 5]:

there are some crucial differences, e.g. warmap.cost and warmap.seacost
(which I think you got wrong in your patch).  But yes it can be handled
in one block.

Best,
G.

>       /* Add the route to our warmap if it is worth keeping */
>       total_cost = move_cost + warmap.cost[x][y];
>       if (total_cost < maxcost) {
>           if (warmap.cost[x1][y1] > total_cost) {
>             warmap.cost[x1][y1] = total_cost;
>             add_to_mapqueue(total_cost, x1, y1);
>             local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>           } else if (warmap.cost[x1][y1] == total_cost) {
>             local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>           }
>         }
> 
>       /* Add the route to our warmap if it is worth keeping */
>       if (total_cost < maxcost) {
>         if (warmap.seacost[x1][y1] > total_cost) {
>           warmap.seacost[x1][y1] = total_cost;
>           add_to_mapqueue(total_cost, x1, y1);
>           local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         } else if (warmap.seacost[x1][y1] == total_cost) {
>           local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         }
>       }
> 
>       /* Add the route to our warmap if it is worth keeping */
>       total_cost = move_cost + warmap.cost[x][y];
>       if (total_cost < maxcost) {
>         if (warmap.cost[x1][y1] > total_cost) {
>           warmap.cost[x1][y1] = total_cost;
>           add_to_mapqueue(total_cost, x1, y1);
>           local_vector[x1][y1] = 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         } else if (warmap.cost[x1][y1] == total_cost) {
>           local_vector[x1][y1] |= 1 << DIR_REVERSE(dir);
>           freelog(LOG_DEBUG,
>                   "Co-Candidate: %s from (%d, %d) to (%d, %d), cost %d",
>                   dir_get_name(dir), x, y, x1, y1, total_cost);
>         }
>       }
> 
> These three code blocks are nearly identical, and could easily be
> replaced by a function add_route_to_warmap() or some such.
> 
> 
> Finally, how exactly does find_the_shortest_path() differ from
> create_goto_map() in client/goto.c [6]?  Comments there indicate some
> differences, but nothing that is actually worth duplicating most of the
> code for.  A lot of the server's code is duplicated by the client, and
> there are no comments (here, at least) on why this is being done. 
> AFAICT create_goto_map is used to create the goto vectors used by the
> client (those shown when you manually do a "goto" with a unit), and it
> looks like the preferred direction of travel (in case there are several
> equally good ones) is pretty much arbitrary.
> 
> 
> [1] http://www.freeciv.org/lxr/source/server/gotohand.c#L605
> [2] http://www.freeciv.org/lxr/source/server/gotohand.c#L697
> [3] http://www.freeciv.org/lxr/source/server/gotohand.c#L748
> [4] http://www.freeciv.org/lxr/source/server/gotohand.c#L815
> [5] http://www.freeciv.org/lxr/source/server/gotohand.c#L857
> [6] http://www.freeciv.org/lxr/source/client/goto.c#L305
> 
> 
> jason
>  

____________________________________________________________
Do You Yahoo!?
Get your free @yahoo.co.uk address at http://mail.yahoo.co.uk
or your free @yahoo.ie address at http://mail.yahoo.ie