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

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

At 01:56 PM 02/04/12 +0100, Gregory Berkolaiko wrote:
>On Thu, 11 Apr 2002, Ross W. Wetmore wrote:
>
>> Some general comments first.
>
>same here:
>1. The cost(war)map computation is very performace-critical.  So we need 
>to balance generality and performace here.  That's why I advocate having a 
>few built-in cost functions, to cut the function call overhead.

No problem here. This was my statement as well. The first derivative
though is that such STD elements should be carefully limited. 

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

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.

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

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

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

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

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

>
>> In general you *do* *not* want too hardcode costmap dimensions
>> such as movecost[XMAX][YMAX]. Use an indexed list (i.e. vector)
>
>Why not? (I genuinly don't know the reasons)

Try your bucket list logic out here :-).

Vectors are a good dynamic allocation object, arrays are not.

>> for all internal storage of this sort and provide map_to_index() 
>> plus index_to_map() conversion routines to unpack locations into 
>> 2-D coordinates.
>

>> Ditch any separate queue entry objects like in the current code.
>> Each costmap location should contain a next index used to chain
>> it into the (bucket) lists, and there is no need to store x,y
>> values as the indexed location gives this implicitly. You 
>> probably want a uchar_t from,dest; for iterating forwards and 
>> backwards through the final map, as well as ushort_t next; and 
>> int cost (or maybe struct cost to hold costfn specific extensions). 
>> This makes up your basic struct cost_tile where a vector of 
>> cost_tiles == a cost_map contains all the useful/necessary warmap 
>> generated data that you might want to save for reuse. (The rest of 
>> the warmap parameterization can be shared or reproduced as needed 
>> with little or no effort).
>
>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.

If we repeat this often enough to ourselves in the forest, will others 
hear ???

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

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

This is close for a cost_tile element. But it looked more like it was also
a queue storage entry in the old queuing system. The old queue system is
the real bad way to go.

>> /* Type of the map */
>> enum maptype {
>>   UNITLAND, UNITSEA, CITYLAND, CITYSEA, CUSTOM 
>> }
>> 
>> ... Private to the costfns. A costfn with multiple maps is perhaps
>> ... useful, but may never be required. All this saves is the overhead
>> ... of warmap parameter headers (i.e. multiple warmaps vs one warmap
>> ... with multiple cost_maps).
>
>these are my "built-in costfunctions"
>so maptype is actually built_in_costfn_type

Ok, but this is specific to a single particular costfn (wrapper) that
gets called and multiplexes to a number of cases. Warmap should not
understnd or know about such concepts to keep separation of interfaces
pure. 

The wrapper costfn is a trivial alternative to keep things straight.

>> /* The comparison function for the priority queue.
>>  * We might have to put it into the costmap structure, in case some
>>  * very exotic costs emerge */
>> int priority_cmp_function(struct location *from, struct location *to);
>> 
>> ... ??? internal costfn. pqueue is sorted by final cost *only*, and
>> ... cost is returned as an index into buckets (some of which might be 
>> ... special, i.e. MAXCOST ... MAXCOST-n, maybe.
>
>here I wanted to preserve some level of abstraction: didn't want to 
>enforce some function f_cost: (cost1, cost2) -> final_cost
>Why?  Because N^2 can be easily ordered lexicographically:
>       (x1, y1) > (x2, y2) 
>               if (x1 > x2) or (x1 == x2 and y1 > y2)
>but there is no order-preserving function (x, y) -> N
>(there are order-preserving functions (x, y) -> R though,
>here N are natural numbers, R are reals).

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.

It looks like the storage/parameter elements are almost equivalent
(which would be good) so things might be interchangeable w/o too much
rewrite pain.

>> /* Iterators -- only useful if you think you will terminate early */
>> struct location *cm_get_next_location(struct costmap *);
>> void cm_process_next_location(struct costmap *);
>> 
>> ... No! this is the basic internal structure exposed as a template
>> ... interface. Most non-standard implementations should use this and
>> ... *only* a very few such cases should be promoted to supported
>> ... public canned routines.
>
>okay if you say so :)
>it makes me only happier.

If you are happy, it makes me only happier too ...

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.

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.

>> /* Access functions */
>> int cm_get_cost1(struct costmap *, int x, int y);
>> int cm_get_cost2(struct costmap *, int x, int y);
>> 
>> ... Cost1 is the base costfn method used by the warmap. I'm not sure
>> ... you ever want to expose get_cost_[n](), rather there is an index
>> ... in the costmap for the multiple variety that both decides and/or
>> ... chooses the right internal costfn algorithm. Warmap code should
>> ... never need to understand this level of detail.
>> 
>> /* I don't think anything like this would be needed... */
>> int cm_get_total_cost(struct costmap *, int x, int y);
>> 
>> ... This could be part of a set of costmap ancillary functions, where
>> ... the orig_x, orig_y is implicit, maybe?
>
>no I meant total_cost as a combination of cost1 and cot2

If this is a functional decomposition of a costfn() into an explicit
expression in the warmap, I think you just want to treat this as a 
particular costfn with the function expression handled internally.

>Thanks for your comments.  It was quite hard to argue with them...
>
>G.

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

Nice to see this happen for a change.

Cheers,
RossW
=====