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

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

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.

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

G.