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

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

Some general comments first.

Notation ... read costmap for warmap since I'm usually 
conservative about name changes until they are univerally 
accepted and defined. Use thing-a-ma-jig is you want to 
preserve fuzziness in the name/concept for now.

The interface that warmaps code needs to use to ask for a cost
is pretty simple and shouldn't ever contain details of how to
compute steps. Auxiliary functions (and/or object data associated
with each *individual* one) need to provide the basic interface
but should keep all internal details for their specific case
outside of the warmap (i.e. costmap) structure. At most you
should provide a pointer to auxiliary data struct along with
the pointer to costfn() in the warmap, but do not go into any
detail on just what goes in here. That is private to the given
instance of cost function. In C++ terms, the costfn and its
private data are not accessible to the warmap class.

Since end code provides costfns to the warmap, it also knows
which (class of) costfn is being used. If you have accessory
methods to the costfn for specific purposes beyond the bare
warmap needs, then the code inside the warmap loop can call
these (directly). Do not pollute the warmap interface with
indirections to specific costfn extensions, i.e. fall prey 
to Raimar's mistakes.

What is missing is a set of initialization functions to set
(and query) parameters in the basic warmap. This extends the
warmap.initialize() in the previous code examples, and is 
reasonably broken out into a get_warmap(), set_warmap() and
then maybe (re)init_warmap() to actually process any 
parameters and (re)start from a fresh queue/location. The
things you added to the top of find_the_shortest_path() 
should give you a first cut at what set_warmap() needs to do.
In general you are still mixing warmap and costfn parameters
below, rather than maintaining a strict separation.

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.

The reverse process to get the final shortest path in find_*()
is an example of an ancillary function.

In general you want to run the warmap cycle and put any special
stop or condition code (like using extension costfn() methods)
inside the loop. But it might be useful to define a limited set
of standard conditions/code for internal manipulations, or a 
standard set of methods/macros to use so people don't have to 
reimplement the basic stuff each time. Think template maybe ...

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)
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
reason is that warmaps generate cost values used to sort entries
back into the queue on each process operation. a bucket list keeps
track of the head/tail entries for each cost list. There is *no*
sort time for either insert or remove operations on these lists, 
just an appropriate indexed lookup. A Bucket list/queue is just
a vector of head/tail indices, so pqueue could hold it, but the
advantage of restricting the warmap to only using this sort of 
method is pretty high. Idiots will use a Qsort or some other 
horrific example if not controlled here.

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

A cache of pre-allocated warmaps returning a partially initialized
(i.e. remove all previous usage dregs) warmap would be nice.

Think *very* carefully before you add anything to a public interface
and try to push details off into the private costfns and their data
objects as far as possible.

Cheers,
RossW
=====

At 08:55 PM 02/04/09 +0100, you wrote:
>Attached is my go at the unified move cost map generation.
>Comments are in the code.
>
>G.
>
>Attachment Converted: "c:\program files\eudora\attach\costmap.h"
>

/* Copyright and ifdefs come here */



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

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

/* Access functions */
int location_get_x(struct location *);
int location_get_y(struct location *);

... Yes, although the single index_to_map_pos(&x,&y,index) is better.

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

/******************** HRM The Cost Map ******************/

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

/* Generic move cost function 
 * Can pass some more info using void * 
 * (it will probably need pplayer, moverate, what else?)
 * Will probably return pointer to the static internal 
 * struct movecost */
typedef struct movecost * (COSTFN)(struct location *from,
                                   struct location *to, 
                                   void *);

... Private to specialized costfn objects. But there might be a
... hierarchically ordered set of costfn/map classes for code
... reuse and conceptual grouping.

struct costmap {
  struct location[XMAX][YMAX]; /* the map itself */
  struct pqueue *queue;        /* priority queue for holding 
                                * accessible (but not yet processed) 
                                * locations */
... See the general section.

  enum maptype {
    UNITLAND, UNITSEA,
    CITYLAND, CITYSEA, 
    CUSTOM 
  } type;                      /* type of the map */
  void *object;                /* the city / unit for which the map
                                * is generated; the type should be 
                                * clear from the maptype */
  int orig_x, orig_y;          /* the origin of the map */
  COSTFN *cost_function;       /* supplied only if type == CUSTOM */
}

... map_type is costfn specific, as an index into the multiple map case.
... the remaining 3 should be warmap parameters settable via set_warmap().

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

 * 2. Unit is used for info such as moverate and igter, NOT to get
 *    orig_[xy]

... Private costfn parameter (but probably present in almost every case).

 * 3. More info can be recorded in this struct, like moverate... 
 *    IGTER can have their own maptype 

... Yes.

 * 4. Separation between "traditional" cost functions and "custom" 
 *    cost functions is done for performance.  At first wqe can make 
 *    all of them CUSTOM, and then try inlining them */

... Yes. See generic for switch STD and EXTended sections.

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

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

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

/* Generating the full map -- includes creation and generation */
struct costmap *cm_get_in_full(int x, int y, struct maptype, 
                               void *object, COSTFN *);

... See generic. This is the bare canned loop, i.e.. internal switch
... is only STD cases therefore empty.

/* Cleanup */
void cm_destroy(struct costmap *);

... Or put_warmap() which can return it to a cache in some 
... implementations.

/* NOTES:
 * 1. cm_process_next_location can probably be incorporated into 
 * the beginning of cm_get_next_location.  Thinking... */

... Yes, but you neeed to provide it with a valid old location
... which then gets updated. It is the difference between a 
... while and a for loop.

/* 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?
...
... WAYPT[] get_path(struct costmap *, int x0, int y0, int x1, int y1);
... int get_path_cost(struct costmap *, int x0, int y0, int x1, int y1);
... int get_total_cost(struct costmap *, int x1, int y1);
...
... One should think carefully about the dual point case though as there
... are restrictions on what points one might be able to use as x0,y0, 
... i.e. only sub_paths of the original warmap generation are valid here
... Or there would be an implicit reset and recompute under teh covers.

Cheers,
RossW
=====