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

["Raimar Falke" <rf13@xxxxxxxxxxxxxxxxx>]

On Sat, May 03, 2003 at 03:04:31PM -0700, Gregory Berkolaiko wrote:
> 
> On Sat, 3 May 2003, Raimar Falke wrote:
> 
> > On Sat, May 03, 2003 at 06:39:39AM -0700, Gregory Berkolaiko wrote:
> > > 
> > > But I want to have a possibility of adding more starting positions while 
> > > pf-iteration is running.  The idea behind it is this:
> > > suppose you are on a boat near continent 1 and want to find a way to the 
> > > city inland.  To do it you first find the way to all the beaches by boat, 
> > > then put these beaches into a next map as starting positions and then 
> > > iterate the second map to find the second segment of your path.
> > > 
> > > But if you are quite close to your destination already, you don't want to 
> > > find the paths to _all_ the beaches first.  You want to start the second 
> > > iteration as soon as possible, so you can break it early!  So the second 
> > > iteration should already be running while the first is finding paths to 
> > > beaches further and further away...
> > 
> > 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;
}

> > > Anyway, nonwithstanding this, here is a patch which changes the
> > > status of a tile from enum to a bit-vector.  It also introduces new
> > > flag S_START to denote a start position but there is no possibility
> > > of multiple starts yet.
> > 
> > With an enum you can't come across a NS_WAITING|NS_PROCESSED but you
> > can now. These states aren't orthogonal so bits are not the right
> > abstraction. Or not?
> 
> 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.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "We just typed make..."
    -- Stephen Lambrigh, Director of Server Product Marketing at Informix,
                         about porting their Database to Linux