[Freeciv-Dev] Re: (PR#2370) Path finding

["Gregory Berkolaiko via RT" <rt@xxxxxxxxxxxxxx>]

Just to redirect the discussion from inlining to actually path finding (as 
stated in the subject).

On Sat, 23 Nov 2002, Raimar Falke via RT wrote:
> 
> The code versions Gregory and I have a now very similar in what they
> do. They however differ in the detail. To get to a version which can
> be put into CVS we have to decide which kind of flexibility we want
> and what kind of techniques we use.

We haven't comapred the code with is_pos_dangerous yet.

> First: inlining. It is critical that this is done. Gregory uses macros
> like
> 
> #define get_turn(map, cost) \
>   ((cost) / (map)->params->move_rate)
> 
> #define get_moves_left(map, cost) \
>   ((map)->params->move_rate \
>    - ((cost) % (map)->params->move_rate))

The above are true macros, should be left alone IMO.

The example below is really a function converted to a macro for 
performance.  Inlining would be more elegant in this case.
Note that it is possible to write this function in about 10 lines rather 
then 23, if needed.  It is also possible to inline it by hand, it's used 
only once.

> #define adjust_cost(map, cost) \
>   if (cost < PF_MAXCOST) { \
>     switch (map->params->turn_mode) { \
>     case TM_NONE: \
>       break; \
>     case TM_AVERAGE: \
>       cost = MIN(cost, map->params->move_rate); \
>       break; \
>     case TM_SAFE: \
>       { \
>         int moves_left = get_moves_left(map, map->lattice[map->xy].cost); \
>         \
>         cost = (cost > moves_left ? moves_left + cost : cost); \
>         break; \
>       } \
>     case TM_LUCK: \
>       { \
>         int moves_left = get_moves_left(map, map->lattice[map->xy].cost); \
>         \
>         cost = (cost > moves_left ? moves_left : cost); \
>         break; \
>       } \
>     } \
>   }
> 
> while I use the inline keyword. Both can provide the same results.

> Second: the speed depends strongly on the size of the node/cell. It is
> currently about 20 bytes. It is possible to cache certain data but
> this make the node/cell larger. I'm using defines:
> 
>   #define CACHE_TILE
>   #define CACHE_ECOT
>   #define CACHE_COP
> 
> to control what is cached. However what should be cached depends on
> how expensive the functions are (we can't tell this for ECOT) and how
> this related to the memory system of the computer. So while currently
> caching the tile is good it may not if we inline the map_get_tile
> function at some point. Should we decide for one? Should we use
> something like the defines above? Any other way?

I think we should cache it for now, and later, when the user base for the 
path finding is more defined, experiment with it some more.  It's easier 
to remove caching than to add it.  And using defines makes code 
less readable.

> Third: while not related to size of the node/cell it is similar to the
> second point: use of a 1D array or use of a 2D array. I also have a
> USE_2D define for this and _at my computer_ the 2D array is faster by
> 4%.

If 2D array is faster, I am all for using it (will convert my code to 
behave accordingly).

> Fourth: how general/special do we want the queue implementation. If we
> for example typedef that the queue works on shorts (16bit, less
> memory) instead of void pointers or int we can get some speed. However
> this makes the queue not general. Also critical (see point 1) is the
> inlining of the queue functions.

I don't believe memory use by queue is significant.  There is also another 
customer for this queue, airgoto.c, but it also uses ints (can be shorts) 
right now.

There is another difference: cost functions.
My code uses call-backs, although (due to vigorous opposition from Raimar) 
they are not configurable from the outside.  To add another cost function, 
it has to be put in the main path_finding file and another option has to 
be created in the pf_parameter.  This is still easier than doing the same 
thing in Raimar's code, where rules are more hardcoded.  Admittedly, there 
is no demand for such extensibility as yet (the only example I can produce 
is calculating the map for a land unit sitting on a transport in the 
middle of the sea -- and this is rather far-fetched).

G.