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

["Raimar Falke via RT" <rt@xxxxxxxxxxxxxx>]

On Sun, Nov 24, 2002 at 06:35:02AM -0800, Gregory Berkolaiko via RT wrote:
> 
> 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.

I also haven't done any work about the two dangerous
implementations. I want to get something finished and into the
tree. Even if this means that we have to change the dangerous
implementation later.

> > 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.

"true macros"?

> 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.

Will it than conform to the style guide?

> It is also possible to inline it by hand, it's used only once.

Yes possible.

> > #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.

And for the experiment we should readd the defines?

> > 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).

_at my computer_

> > 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.

Inlining of queue functions?

> 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).

I think that you loose some speed with your cost functions. All should
be inlined. BUT if you inline you seperate function it should look
like:

...inline normal_move_unit(...) {
....
}

...get_cost(...)
{
  switch(type) {
  case NORMAL_MOVE:
    return normal_move_unit(...);
  case ....
....
}

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I do feel kind of sorry for Microsoft. Their attornies and marketing
  force must have tons of ulcers trying to figure out how to beat (not
  just co-exist with) a product that has no clearly defined (read
  suable) human owner, and that changes on an hourly basis like the
  sea changes the layout of the sand on a beach. Severely tough to
  fight something like that."
    -- David D.W. Downey at linux-kernel