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

["Ross W. Wetmore" <rwetmore@xxxxxxxxxxxx>]

At 04:22 PM 02/04/15 +0100, Gregory Berkolaiko wrote:
>Ross,
>
>Why is it so hard to read your emails?  Requires a lot of mental effort. 

Exercise is always good for you ...
 
>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).

There is a saying about feeding a man a fish or teaching him how to fish 
...

Your earlier warmap version in the corecleanups is a pretty good start, as
were a number of the costfns. The switch examples from a couple emails ago
give you an idea of how programmers might code the exit conditions or any
internal operations and the general structure of processing flow.

What was missing is generalizing the warmap_initialize() to allow one to
preset the (very few) parameters for a chosen costfn or canned internal
controls. And the concept of how to set up a costfn with its parameters.
With this a lot of the first part of find_the_shortest_path() reduces to
a few standardized setup sequences.

Note setting up a costfn with its paramaters should be independent of the
warmap code, and private to a particular costfn. It is not unreasonable
to have sets of similar costfns that share a lot of similar setup and 
perhaps code, but it is not required, and not advisable if it slows 
down the cost computation too much. The costfn "object" which consists
of the methods the warmap calls and the data that parameterizes it for
this particular instance (i.e. instance data or local data) are all that
one really need to input to the warmap_initialize() steps.

You also needed to figure out whether to add the local_vector ops to the
core warmap, or have it fall out into the external user switch for such 
things. You could always have two get_next_locations(), one that was
just for cost/result, and the second that tracked the directions.

At this point you run your warmap until you hit the termination point or
cost cycle containing it (to make sure you get all the possibilities).

Then you need Raimar's pf_get_*() without all the parameters to just do
the reverse walk of the warmap to generate the vector of waypoints. The
data for this is the recorded cost results and the direction vector, but
mostly just the local_vector. This now depends on nothing but the warmap 
output.

If you want pf_get_*() to return sets of approximately equivalent paths
then you need to choose not the local_vector direction but other directions
for the backstep which are "equivalent" where equivalence may be the base 
move_cost result (independently of a secondary weight factor).

Raimar can perhaps think about what he wants beyond the shortest path, 
and how this should be recovered from the warmap data which *might* entail
storing more than just a simple cost result. Note the costfn *could* leave 
little packets of private data results at each point of invocation that
a corresponding specialized pf_get_*() knew how to interpret and make use 
of.

But you would need to explain why you wouldn't have local_vector make the
*right* choice if you only want a single path, and/or flag multiple
directions if there were options during the main cycle.

And note that none of this prevents you from picking arbitrary points 
within the computed warmap and running pf_get_*() to generate the least
cost (where cost is the warmap value) paths from there. Thus a city horse
map only needs to be computed once and used for any subsequent plans for
2 move fast units to attack from the city or move back to it - at least
until the terrain changes within the warmap bounds, or you need to deal
with transitory effects like ZOC.

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

Good. Just so long as it doesn't start creeping into warmap code and is
only used by the costfn (or post-processing function) that it is designed
for. My understanding is that pf_paramter was becoming "the-one-and-only-
true-way-to-parameterize-all-costfns" - that would be a mistake.

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

Good ... seeing is first step. Now go back, reread book :-). 

Instance (or local) data and methods are the two main components to any
object. "C" object programming may expose all the warts, and not be 
particularly easy to encapsulate in clean ways, but basic object techniques
are still good things to master, and the programming patterns they expose
are good ways to quickly generate code without reinventing the wheel.

Instance data means passing a warmap/costmap struct * to routines rather
than using a single global memory for all calculations. If you do the
former you can have as many warmap calculations in progress simultaneously
as you have memory resources to handle.

Same thing for costfn instance data, i.e. local data for a particular
costfn runtime step.

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

There are several answers to this. First 100K is not a big chunk of if
that is what you need. Second, most warmaps use THRESHOLD or something
on the order of 72 as maxcost if you dynamically allocate this. Third
is you can use a sorted bucket if you think that the bucket queue depth
is on average a small number ... yada, yada, yada.

And last is consider what the finer granularity really means, and is it
worth it. As an example, if this is not a cummulative cost, but computed
at a given point, then you only need 255 buckets, and you use the finer
granularity to set the appropriate direction. 25500 buckets is only
important if you can accumulate differences across buckets/steps which 
actually goes against the normal Freeciv move process i.e. an integral 
rounded cost.

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

Good, we are all right(-minded) dextrous folks, no sinisters here among
the rabbis promoting religious dissent :-).

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

The bucket is a head and tail index into the costmap, or 2 shorts.

>> >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"?

Because Raimar (and you and I) are not particularly good at writing
general library code that will handle all future possibilities. If the
processing internals are in a canned warmap routine, the user can't
modify it, spends a lot of time discussing the size of our brains and 
immediate family ancestry then goes off and rewrites a completely new 
buggy version of his/her own or worse adds it to the existing canned 
code bloating warmap ad nauseum. If the processing exposes the internal 
switch for the user to insert extra specialized code into, the user is 
happy and thinks we were all really wise people to make such a useful 
thing - and only breaks his/her routine in the process.

The user should be able to write costfns and insert termination or
processing code. What's left is canned library.

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

Plan for it and it might come to pass.

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

Okay, 5 lines each with reasonable style guide form :-).

Replace the free() in cm_destroy() with add_to_freelist(). If there are
more than <blort> in the list, trim the list to <smaller-blort> by free().

0 static struct warmap *list[<blort>];
0 static int nlist;

cm_destroy(warmap) {
    ...
1 if( nlist >= <blort> ) 
2 do { 
*   free(list[--nlist]); 
3 } while ( nlist > <smaller-blort> );
4 list[nlist++] = warmap;
    ...
}

Replace the fc_malloc() in cm_create() with get_from_list() and clean().
If there are none in the list then fc_malloc().

cm_create() {
    ...
5 if( nlist <= 0 ) 
*   warmap = fc_malloc(sizeof(struct warmap));
6 else
7   memset((warmap = list[--nlist]), 0, sizeof(warmap));
    ...
}

>> >> /********* 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?

Yes, except that it is isn't "internal". It is the index into the warmap
vector. index_to_map(&x, &y, xy) can be used to unpack it if needed.

In my world-view, index corresponds to native coordinates, or the compact
(linear) storage of any map-like object.

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

An alternative or two is always a good things to have in one's pocket.

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

Just do the first part processing of the above switch inside the 
get_next_location() call, and return the switch index for the default:
case. What you return on a STD processed case is 1) the switch index
in case the user wants to do more processing, or 2) a new index value
which reflects the processed state, like STOP_CODE.

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

I agree. It is much nicer to be able to code what you need inline for this.

>> 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.
>
>Attachment Converted: "c:\program files\eudora\attach\warmap1.c"

Cheers,
RossW
=====