[Freeciv-Dev] Re: [RFC] Move cost map interface

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

Ross,

Why is it so hard to read your emails?  Requires a lot of mental effort.  
And still I don't understand much of what you say.  But I usually 
understand you code much better.  So 
(1) can I ask you to have a go at Raimar's find_route.h (or write one from 
scratch, or from your warmap.c, attached).

And I'll answer the parts that I can ;)

On Fri, 12 Apr 2002, Ross W. Wetmore wrote:

> At 01:56 PM 02/04/12 +0100, Gregory Berkolaiko wrote:
> >On Thu, 11 Apr 2002, Ross W. Wetmore wrote:
> >
> >> Some general comments first.
> >
> >2. The struct warmap will be "hidden", so I don't see why we cannot store 
> >some info there.
> 
> Only if the warmap treats it as opaque data, i.e. pure storage or caching.
> But in that case, I agree. 

I think Raimar's code does it, storing everything in pf_parameter.

> You need to store both costfn() (pure method) and instance data to emulate 
> a C++ class object in C, if one wants a model concept/justification.

errr.  I saw the words "instance data" in a complicated book once...

> >3. Qsort is not going to be in.  Priority queue (log(n)) is my choice due 
> >to the following problems with the bucket list:
> >(a) we don't know in advance how big the range of costs will be, and it 
> >can be very big (fx around 255*100 in the current Raimar's proposal, and I 
> >wouldn't call it excessive)
> 
> You know the range of costs. It is a parameter to the warmap (maxcost).

yes, but each "primary cost" is refined by PF_BMC_FACTOR "secondary 
costs", so you get MAX_COST * PF_BMC_FACTOR = 255 * 100

> >(b) the only mistake in warmap.c was in the bucket list: sometimes 
> >locations might be moved from one bucket to another (with a lower cost -- 
> >when we find a new better route). 
> 
> Only if your warmap code is buggy. Dijkstra's algorithm *always* chooses
> lower cost routes first. If you are talking about buggy bucket list code
> that doesn't unlink an old entry properly when ading/moving it, then fix 
> the bug :-).

No, Dijkstra is correct and unlinking is correct and my warmap code is 
correct too ("You are right, Dovid, and you are right Menashe"  
"But Rabbi, it cannot be so that both arguing parties are right!?!?"
"And you too are right, Mendele...")

We start at O.  The shortest path O->A cost 5.  The shortest path O->B 
cost 7.  The next considered location is A and C is a neighbour of A and 
the cost of the move A->C is 6.  It's the first time we arrived to C, so C 
is put in bucket number 5+6 = 11, it's "next" link set to NULL.  Then, as 
we process more tiles, something else (X) comes to bucket 11 and is 
recorded after location C.  C.next now points to X.
Then we process tile B.  From B we can also get to C and the cost of the 
move is 1.  Since 7+1 < 11, we now assign new cost to C and put it to 
bucket 8.  C's "next" link is set to NULL.  Oops.

Here we need to remove C from bucket 11 first.  

> > So just "next" index is not enough, 
> >each bucket must be a doubly-linked list.  Altogether it might add up to 
> >kill the log(n) factor we are winning.
> 
> No, the performance from walking the bucket to unlink a singly-linked
> list element on the (rare) occasions where this happens is probably
> noise compared to the overhead of other list forms.

Maybe.  Still I don't really fancy having a vector of 100*255 pointers (or 
ints).  How much is it?

> >I don't quite understand the use of the below.  But one day I'll grow up 
> >to it ;)
> 
> Hint: the retcode is probably the switch value used in the STD 
>       hardcoded/preprocessed elements in warmap.next_location, or
>       an unresolved sub-case they didn't handle.
> 
> Hint 2: read it as pseudo-code and not valid C code.

Yes but why should any such processing be done in the "user code"?

> >> There could be an option control and bitflag in the costmap data
> >> with a set of enumerated return movecosts to the next_location()
> >> that dealt with the standard cases, leaving the coder only to add
> >> particular extensions for esoteric costfns to the internal warmap
> >> loop. 
> >> 
> >>   warmap = get_warmap(...);
> >>   set_warmap(PARM_TYPE, value);
> >>    ...
> >>   for (warmap.init(...);
> >>        (retcode = warmap.next_location(...) != STOP_CODE);
> >>        warmap.process_location(...)) {
> >>     switch(retcode) {
> >>      case STD[1:n]:
> >>        /* already handled inside the next_location() ...
> >>           optional as to how/ whether you might want to extend 
> >>           it here. */
> >>         break;
> >>      case COSTFN_SPECIFIC[1:n]:
> >>        /* additional/extensible costfn return choices go here */
> >>        /* only means something wrt to particular costfn used. */
> >>         break;
> >>     }
> >>   }

> >There is a great advantage I see in this approach:
> >after you've computed the whole map, these links "next" and "prev" order 
> >the locations in the "right" order, so you can make another iterate 
> >without computing any new costs.
> 
> Reusable costmaps that contain *all* pertinent data is the only sensible
> solution really. One should bite the bullet and ditch the current entry
> concept code. This is also much less overhead to run and maintain.

Mmm.  If it's going to be used, yes.

> >> A cache of pre-allocated warmaps returning a partially initialized
> >> (i.e. remove all previous usage dregs) warmap would be nice.
> >
> >too advanced for now
> 
> But neat ... right? 
> 
> Implementation is only about 5 extra lines of code to cm_create*()
> and/or cm_destroy*(), too.

can't visualise it.

> >> /********* Individual Position / Location / Tile ********/
> >> 
> >> struct location {
> >>   int x, y;                    /* coordinates */
> >>   struct movecost travelcost;  /* cost to get here */
> >>   char from;                   /* where we came from 
> >>                                 * (bitmap holding directions) */
> >>   enum queue_status status;    /* holds various queue related info */
> >> }
> >> 
> >> ... See the generic comments. This is a bad way to go. Change the
> >> ... current queue philosophy instead :-).
> >
> >please explain.
> 
> See the previous comment on entries.
>   x,y    unneeded. It is faster to compute than manage the storage issues.
>          And should use a single index for most internal operations anyway.

what do we return in get_next_location then?  The internal index?

>   *cost  most costfns only need one, some need many, so needs to go into
>          a costfn specific class/struct, or at least be open ended storage
>          after the fixed elements/header part.
>   from   also need dest
>   status ??? if this is next that is fine

in the example above, if we remove C from bucket 11, this is unneeded 

> I'll wait to see how expensive your priority queue system becomes, but
> I would still start with the bucket implementation based on integral
> returned costs, and upgrade it to something else when it is needed.

we'll see :)

> Realistically, I think the basic warmap generation loop is pretty much
> the simple examples above with the switch handling all the complexity.
> The trick is to do a fast canned internal switch part and export the
> remaining "default:" cases to arbitrary user code which can be written
> as oneoffs anywhere.
> 
> If there are a number of "common" exported switch cases being written
> everywhere, then those can be promoted into the STD set over time.

The above is complicated...  Maybe (1)?

> There are two parts to switch cases. 
> 
> 1)  call the *right* costfn() - I really think this should be pushed
>     back into a wrapped costfn which allows full program control and
>     clean interface separation.
> 
> 2)  termination conditions - this is the real point at which code
>     becomes diverse and you want inline control. I suppose this could
>     be checkfn() like the costfn(), but somehow I like to see the
>     actual code at this point from a readability/debugging aspect.
>     If you add this as a checkfn(), then *any* warmap loop devolves to
>     the single 3 line for, I think - total black magic to call though.

I tried to supply the termination condition to the warmap once.  It looked 
right ugly.

> Hopefully the goal is to refine understanding and implementation, and
> to learn not just to doggedly fight for the sake of arguing or ego :-).

Definitely it is.  I try not to defend follies even if they are of my own 
making ;)

Best,
G.

warmap.c
Description: Text document