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

[Gregory Berkolaiko <Gregory.Berkolaiko@xxxxxxxxxxxx>]

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.
2. The struct warmap will be "hidden", so I don't see why we cannot store 
some info there.
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)
(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).  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.

> What would be nice is a set of ancillary functions to take a 
> computed warmap, and extract a (set of) shortest paths, iterate
> a set of points with given cost range, etc. This allows one to
> reuse a warmap without recomputing the costs part.

Raimar's proposal provides these.

I don't quite understand the use of the below.  But one day I'll grow up 
to it ;)

> 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 could be a generic warmap loop function that handled STD
> cases only and ran the whole warmap to stop conditions for cases
> where you didn't want to code the details explicitly. Or it might
> take a per costfn() callback function that basically implemented 
> the internal switch body and replaced the standard switch processing.
> This is effectively what the current (really_)generate_warmap() do.
> 


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

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


> You *really* need to use a bucket list as the queue object. The

see above


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

> 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

> /********************* Individual Cost *******************/
> /* costs can be anything, but usually cost1 is the basic move cost and
>  * cost2 is a penalty due to exposure to various dangers
>  * can easily increase number of additional costs, if necessary */
> struct movecost {
>   int cost1;
>   int cost2;
> }
> 
> ... I don't see a real need for this in the warmap part. It is a 
> ... costfn specific, and therefore arbitrary object. It could be
> ... a part of a costfn object. It could be the struct cost in the 
> ... generic cost_tile as 
>     struct cost_tile<TEMPLATE> {
>       ushort_t next;
>       uchar_t  fromdir;
>       uchar_t  destdir;
>       struct cost<TEMPLATE> {
>         int  result;     /* this is the only element warmaps understand */
>         int  costtype[MAX_MAP_TYPE];
>           ...  some other costfn specific extensions
>       }
>     };

agree


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

> /* Might also need this 
>  * (not sure about usage of const, 
>  * here I want to prevent changing the pointer's contents */
> const struct movecost *location_get_cost(struct location *);
> 
> ... Use an index rather than a pointer to location. The base object
> ... into which you index then becomes a useful level of indirection.

yep

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

> /* NOTES:
>  * 1. Instead of "object" we can have two pointers to unit and city, 
>  *    with only one being non-NULL at any time
> 
> ... Only value is bugwards compatibility, no?

yes :)

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

> /* Cost map generating functions */
> /* Creation / init */
> struct costmap *cm_create(int x, int y, struct maptype, 
>                            void *object, COSTFN *);
> 
> ... See generic ... basically this is just warmap_init(), right.
> ... Or maybe get_warmap() which includes allocation.

yes, it's get_warmap.

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

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

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

G.