[Freeciv-Dev] Re: (PR#4038) Multiple starting points for PF

["Gregory Berkolaiko" <Gregory.Berkolaiko@xxxxxxxxxxxx>]

On Mon, 5 May 2003, Raimar Falke wrote:

> On Sat, May 03, 2003 at 03:04:31PM -0700, Gregory Berkolaiko wrote:
> > 
> > On Sat, 3 May 2003, Raimar Falke wrote:
> > > 
> > > Ok but then this should be the only way to add starting
> > > positions. I.e. remove this from the parameter struct.
> > 
> > This will break the existing interfaceand will force the user to add the 
> > start by hand in the vast majority of the cases.  I really don't like it.
> > Another possibility is to have pf_reserve_map which is same as 
> > pf_create_map but doesn't put a start position.  But this is exactly the 
> > same as pf_create_map with a boolean argument and then the argument can go 
> > into parameters and this is what I did...
> > 
> > Finally, there is a possibility when a call to add_start position removes 
> > the "default" start position.  So the interface is almost clean but the 
> > implementation will get a bit dirty.  Please advise.
> 
> IMHO there should be:
> 
> struct pf_map *pf_real_create_map(const struct pf_parameter *const parameter);
>   and 
> struct pf_map *pf_create_map(const struct pf_parameter *const parameter, 
>       int start_x, int start_y, int initial_moves_left)
> {
>   struct pf_map *result=pf_real_create_map(parameter);
>   pf_add_start_position(...);
>   return result;
> }

I thought the big reason of having the struct parameter was that we could 
put parameters (funnily enough) in there and avoid having different types 
of function calls...

> > The relation between states is a bit strange.  The problem with enum was 
> > that START is orthogonal to them all so I had to duplicate all 
> > new/processed/waiting in their "start" flavour, producing this:
> >  enum pf_node_status {
> >    NS_UNINIT = 0,           /* memory is calloced, hence zero 
> >                              * means uninitialised */
> >    NS_START,                     /* a starting position of the path-finding
> >                                   * (there could be more than one) */
> >    NS_NEW,                  /* the optimal route isn't found yet */
> >    NS_WAITING,                      /* the optimal route is found,
> >                              * considering waiting */
> >    NS_WAITING_START,             /* WAITING at a START tile */
> >    NS_PROCESSED,                    /* the optimal route is found */
> >    NS_PROCESSED_START            /* same as PROCESSED, but it's START tile 
> >                                   * as well */
> >  };
> >  
> > I think it is ugly :(
> > 
> > Now an additional benefit is that one can now absorb zoc-info into the 
> > same bit-field.  
> > 
> > An alternative is to take START out of status and put it into 
> > the node proper...  And join it with zoc-info into a bit-field for space 
> > saving.
> > 
> > Let me know what you think.
> 
> If this is all about space saving that the current struct is a bad
> starting point:
> 
>   struct pf_node {
>     int cost;                 /* total_MC */
>     int extra_cost;           /* total_EC */
>     utiny_t dir_to_here;              /* direction from which we came */
> 
> gcc will insert here 3 pad bytes.
> 
>     /* Cached values */
>     int extra_tile;           /* EC */
>     utiny_t node_known_type;
>     utiny_t behavior;
>     utiny_t zoc_number;               /* 1 if allied, 2 if my zoc, 0 
> otherwise */
> 
> gcc will insert here another pad byte.
> 
>   };
> 
> I'm for a new "utiny_t flags" with current 2 bits defined. If you have
> rearranged the struct this extra byte will however increase the size
> from 16 to 20 bytes (which is also the current size). If you now think
> that these 4 bytes increase isn't acceptable for 2 extra bits we have
> to go into Rafal-mode ;) and shift and mask the values. In this mode
> we would count the bits: 3 (dir)+ 3 (type) + 2 (behavior) + 2 (zoc) +
> 1 (start) = 11 bits and would see that 1 short int would be enough.

So how about

   struct pf_node {
     int cost;                 /* total_MC */
     int extra_cost;           /* total_EC */
     utiny_t dir_to_here;              /* direction from which we came */

     /* Cached values */
     utiny_t node_known_type;
     utiny_t behavior;
     utiny_t flags;            /* 0th bit START, 1st bit allied, 
                                * 2nd bit our ZoC */
     int extra_tile;           /* EC */
   };

?

It is 16 bytes which is the minimal we can get if we believe what you say 
about gcc padding ;)

I believe that putting zoc-info into a bitfield is ok, because it's mined 
and managed entirely by the PF-module.  It would be less clean to convert 
callback return values to bitfields as well.

G.