[Freeciv-Dev] Re: Tech cost patch v14 (PR#1082)

[Reinier Post <rp@xxxxxxxxxx>]

Some comments from a lazy reader who hasn't playtested the patch.

Your code may be correct now, but I find it hard to understand.

The first reason is the naming.  The function names look quite
interchangeable to me, I can't really see from its name which specific
role a function plays.  It would also help to #define symbolic names
for the tech_cost_style.

The second reason is the use of variables.  All variables are evil,
but as long as I have a very clear idea of the purpose of every variable,
I can check whether it is updated and read correctly.  Your code makes
this hard, especially the following fragment:

+int find_unknown_req_techs(struct player *pplayer, Tech_Type_id tech, int *req)
+  if (tech == A_NONE)
+    return 0;
+
+  if(req[tech]++ || get_invention(pplayer, tech) == TECH_KNOWN)
+    return 0;
+
+  return 1 + find_unknown_req_techs(pplayer, advances[tech].req[0], req)
+    + find_unknown_req_techs(pplayer, advances[tech].req[1], req);
+}

The req[tech] value is updated, and causes recursive updates to the rest
of the req array.  Both req[tech] and the function result appear to
contain something like the number of required techs for 'tech', but they
are not the same.  This is confusing.

You also rely on this function not being called with the wrong req array,
they must be kept seprate for different players.

The code

  if (req[tech]++)

seems wrong: surely you want to increment iff req[tech] was still 0,
but instead you increment only when it was > 0 already.

The whole idea to make this function update an array without clearing it
first is highly suspicious: if you call it twice with the same arguments,
it will produce different results!  And this function is *not* static,
so you have no control over where or when it is called.  This just can't
be a good way to deal with the problem.

+/**************************************************************************
+ Count number of currently unknown requirement technologies for given tech.
+ Uses find_unknown_req_techs to do actual counting.
+**************************************************************************/
+static int num_unknown_req_techs(struct player *pplayer, Tech_Type_id tech) {
+  int counted[A_LAST];
+  int i;
+  for(i=0; i<A_LAST; i++)
+    counted[i] = 0;
+
+  return find_unknown_req_techs(pplayer, tech, counted);
+}
+
+/**************************************************************************
+ Count number of requirements technology has including itself.
+ Cache result to advances[tech].num_reqs.
+**************************************************************************/
+static int num_req_techs_rec(Tech_Type_id tech, int *counted) {
+  if (tech == A_NONE)
+    return 0;
+
+  if(counted[tech]) 
+    return 0;
+
+  counted[tech] = 1;
+
+  return 1 + num_req_techs_rec(advances[tech].req[0], counted) 
+    + num_req_techs_rec(advances[tech].req[1], counted);
+}

Why don't you export one of these?

It would be better to have code in which the variables have a clear meaning.
It should also be clearer which computations are player-specific and which
aren't.

One way to achieve this is to store the incidence matrix of the transitive
closure of the tech tree, computing it once after the tech tree has been
read, and to do all the rest without any auxiliary variables.

Improvised untested code:

static unsigned char the_on_path_to[A_LAST][A_LAST];
/*
 * the_on_path_to[t][u] means that t is (in)directly required for u
 * A_NONE, required for every tech, is included but superfluous
 */

/*
 * computes the_on_path_to[][]
 * call me whenever the tech tree (advances[]) changes
 * standard transitive closure algorithm
*/
void compute_on_path_to(void) {
  Tech_Type_id i,j,k;

  memset(the_on_path_to,(char)0,sizeof(the_on_path_to));
  for (i=A_NONE; i<A_LAST; ++i) {
    the_on_path_to[advances[i],advances[i].req[0]) = 1;
    the_on_path_to[advances[i],advances[i].req[1]) = 1;
  }
  for (k=A_NONE; k<A_LAST; ++k) {
    for (i=A_NONE; i<= k; ++i) {
      for (j=A_NONE; j<=k; ++j) {
        the_on_path_to[i,j] = the_on_path_to[i,k] || the_on_path_to[k,j];
  }
}

int on_path_to(Tech_Type_id t,u) {
  return !!the_on_path_to[t][u];
}

/*
 * the number of advances required to reach tech t, including itself
 */
int num_advances_required_for(Tech_Type_id u) {
  Tech_Type_id t;
  int num;

  for (t=A_FIRST,num=0; t<A_LAST; ++t) {
    if (on_path_to(t,u)) {
      ++num;
    }
  }
  return num;
}

/*
 * the number of advances player requires to reach tech t, including t
 */
int num_advances_player_requires_for(struct player *pplayer, Tech_Type_id u) {
  Tech_Type_id t;
  int num;

  for (t=A_FIRST,num=0; t<A_LAST; ++t) {
    if (on_path_to(t,u) && get_invention(pplayer, t) {
      ++num;
    }
  }
  return num;
}

etc.

BTW can get_invention() be renamed to has_invented()?

-- 
Reinier

tech_cost_style14.diff.gz
Description: Binary data