[Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://bugs.freeciv.org/Ticket/Display.html?id=12719 >

After banging on it for a while, here's what I have.

I moved almost all the code into client/techtree_common.c.  The GUI
techtree file became so small I just removed it, and renamed
techtree_common as techtree.  (Side note: repodlgs.c should be split
into one file per dialog.)  I think the old tech list is still useful,
though, and we should have a tabbed selector here so the user can see both.

The techtree.h interface becomes very simple:

  struct techtree;

  struct techtree *create_techtree(void);
  void destroy_techtree(struct techtree *techtree);

  void get_techtree_dimensions(struct techtree *techtree,
                               int *width, int *height);

  void draw_techtree(struct techtree *techtree,
                     struct canvas *pcanvas,
                     int canvas_x, int canvas_y,
                     int tt_x, int tt_y, int w, int h);

with all other logic (including the previously exposed structs) hidden
inside techtree.c.  Very nice.

Note a few FIXME comments here and there.  In particular draw_techtree
doesn't do what it says it does (it's supposed to draw just part of the
techtree, and at the given canvas position - instead it draws the whole
techtree, and at the canvas origin).

We don't have to worry about destroying the techtree inside packhand.c.
 We just destroy it when the science dialog is closed - which includes
any time the client disconnects.  This does mean it must be recomputed
each time the science dialog is reopened (comments in the code claim
this is computationally intensive but I don't notice any slowdown).

The only drawback versus the old patch is the lines are a bit ugly. 
This uses LINE_NORMAL which uses thin_line_gc which apparently is a
little thicker than one pixel.  Of course it should really use
anti-aliasing.

Vasco, please look at the GTK code.  Some of it is pretty ugly (and a
lot of it I didn't look at at all).

----- Future enhancements -----

We probably want this thing to be interactive.  If it were done with a
GTK widget that would be one way.  The other way is to keep it all in
the common code, and using the canvas interface.  In this case we
probably just want a new function added to the interface:

  /* Returns the tech at the given position, or A_NONE */
  Tech_Type_id techtree_get_tech(struct techtree *techtree,
                                 int x, int y);

so the user can click on techs to get help, set the tech goal, set the
current research, etc.

Also we probably want to show the tech goal (along with intermediate
goals) using a different color.  This should be easy (an extra line or
twenty of code to node_color()).

-jason

Index: client/Makefile.am
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/Makefile.am,v
retrieving revision 1.63
diff -u -r1.63 Makefile.am
--- client/Makefile.am  31 Mar 2005 17:28:02 -0000      1.63
+++ client/Makefile.am  9 Apr 2005 03:53:19 -0000
@@ -182,6 +182,8 @@
        options.h       \
        repodlgs_common.c \
        repodlgs_common.h \
+       techtree.c \
+       techtree.h \
        text.c  \
        text.h  \
        tilespec.c      \
Index: client/techtree.c
===================================================================
RCS file: client/techtree.c
diff -N client/techtree.c
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ client/techtree.c   9 Apr 2005 03:53:19 -0000
@@ -0,0 +1,780 @@
+/********************************************************************** 
+   Copyright (C) 2005  The Freeciv Project
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+***********************************************************************/
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <assert.h>
+#include <log.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include "game.h"
+#include "tech.h"
+
+#include "colors_g.h"
+
+#include "techtree.h"
+
+/* FIXME: Should be a separate font. */
+#define FONT_TECHTREE_NODE FONT_TECHTREE_TEXT
+
+/****************************************************************************
+  This struct describes positions of techtree nodes in pixels
+****************************************************************************/
+struct diagram_layout
+{
+  int *node_x;
+  int *node_y;
+  int *node_width;
+  int *node_height;
+
+  /* width and height of entire diagram */
+  int width;
+  int height;
+};
+
+/****************************************************************************
+  This structure desribes a node in a technology tree diagram.
+  A node can by dummy or real. Real node describes a technology.
+****************************************************************************/
+struct tree_node
+{
+  bool is_dummy;
+  Tech_Type_id tech;
+
+  int nrequire;
+  struct tree_node** require;
+
+  int nprovide;
+  struct tree_node** provide;
+
+  /* Note that y means a layer and x ordering in that layer */
+  int x, y;
+
+  /* for general purpose */
+  int number;
+};
+
+/****************************************************************************
+  Structure which describes abstract technology diagram.
+  Nodes are ordered inside layers[] table.
+****************************************************************************/
+struct techtree
+{
+  int num_nodes;
+  struct tree_node **nodes;
+
+  int num_layers;
+  int *layer_size;
+  struct tree_node ***layers;
+
+  struct diagram_layout *layout;
+};
+
+
+/*************************************************************************
+  Add requirement edge to node and provide edge to req
+*************************************************************************/
+static void add_requirement(struct tree_node *node, struct tree_node *req)
+{
+  node->require =
+      fc_realloc(node->require,
+                sizeof(*node->require) * (node->nrequire + 1));
+  node->require[node->nrequire] = req;
+  node->nrequire++;
+
+  req->provide =
+      fc_realloc(req->provide,
+                sizeof(*req->provide) * (req->nprovide + 1));
+  req->provide[req->nprovide] = node;
+  req->nprovide++;
+}
+
+/*************************************************************************
+  Allocate and init new tree node
+*************************************************************************/
+static struct tree_node *new_tree_node(void)
+{
+  struct tree_node *node = fc_malloc(sizeof(*node));
+
+  node->nrequire = 0;
+  node->nprovide = 0;
+  node->require = fc_malloc(1); /* FIXME: this is surely wrong! */
+  node->provide = fc_malloc(1);
+  node->x = -1;
+  node->y = -1;
+  return node;
+}
+
+/****************************************************************************
+  Return minimum size of the rectangle on the diagram which
+  corresponds to the given node
+****************************************************************************/
+static void node_rectangle_minimum_size(struct tree_node *node, int *width,
+                                       int *height)
+{
+  if (node->is_dummy) {
+    *width = *height = 1;
+  } else {
+    get_text_size(width, height, FONT_TECHTREE_NODE,
+                 get_tech_name(game.player_ptr, node->tech));
+    *width += 2;
+    *height += 8;
+  }
+}
+
+/****************************************************************************
+  Calculate rectangles position and size from current tech_tree
+****************************************************************************/
+static struct diagram_layout* calculate_diagram_layout(struct techtree *tree)
+{
+  struct diagram_layout* layout = fc_malloc(sizeof(*layout));
+  int i;
+  int layer;
+  int layer_offs;
+  struct tree_node* node;
+  
+  layout->node_x = fc_malloc(tree->num_nodes * sizeof(*layout->node_x));
+  layout->node_y = fc_malloc(tree->num_nodes * sizeof(*layout->node_y));
+  layout->node_width = fc_malloc(tree->num_nodes * 
sizeof(*layout->node_width));
+  layout->node_height = fc_malloc(tree->num_nodes * 
sizeof(*layout->node_height));
+
+  /* calculate minimum size of rectangle for each node */
+  for (i = 0; i < tree->num_nodes; i++) {
+    node_rectangle_minimum_size(tree->nodes[i],
+      &layout->node_width[i], &layout->node_height[i]);
+    tree->nodes[i]->number = i;
+  }
+  
+  /* calculate height of the diagram. There should be at least 10 pixels
+   * beetween any two nodes */
+  layout->height = 0;
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    int h_sum = 0;
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      node = tree->layers[layer][i];
+      h_sum += layout->node_height[node->number];
+      if (i < tree->layer_size[layer] - 1) {
+       h_sum += 10;
+      }
+    }
+    if (h_sum > layout->height) {
+      layout->height = h_sum;
+    }
+  }
+  
+  /* calculate maximum width of node for each layer and enlarge other nodes 
+   * calculate x offsets
+   */
+  layer_offs = 0;
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    int max_width = 0;
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      node = tree->layers[layer][i];
+      if (max_width < layout->node_width[node->number]) {
+        max_width = layout->node_width[node->number];
+      }
+    }
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      node = tree->layers[layer][i];
+      layout->node_width[node->number] = max_width;
+      layout->node_x[node->number] = layer_offs;
+    }
+    if (layer != tree->num_layers - 1)  {
+      layer_offs += max_width * 5 / 4 + 80;
+    } else {
+      layer_offs += max_width;
+    }
+  }
+  layout->width = layer_offs;
+
+  /* Calculate y-position of nodes on the diagram 
+   * Distribute nodes steadily  
+   */
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    int y = 0;
+    int h_sum = 0;
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      node = tree->layers[layer][i];
+      h_sum += layout->node_height[node->number];
+    }
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      node = tree->layers[layer][i];
+      layout->node_y[node->number] = y;
+      y += layout->node_height[node->number];
+      if (tree->layer_size[layer] > 1) {
+       y += (layout->height - h_sum) / (tree->layer_size[layer] - 1) - 1;
+      }
+    }
+  }
+  return layout;
+}
+
+/****************************************************************************
+  Free memory associated with this diagram_layout
+****************************************************************************/
+static void free_diagram_layout(struct diagram_layout* layout)
+{
+  free(layout->node_x);
+  free(layout->node_y);
+  free(layout->node_width);
+  free(layout->node_height);
+  free(layout);
+}
+
+/*************************************************************************
+  Create a "dummy" tech tree from current ruleset.  This tree is then
+  fleshed out further (see create_techtree).
+*************************************************************************/
+static struct techtree *create_dummy_techtree(void)
+{
+  /* Doesn't include dummy edges (?) */
+  struct techtree *tree = fc_malloc(sizeof(*tree));
+  struct advance *advance;
+  int j;
+  struct tree_node *nodes[game.num_tech_types];
+
+  tech_type_iterate(tech) {
+    if (!tech_exists(tech) || tech == A_NONE) {
+      nodes[tech] = NULL;
+      continue;
+    }
+    nodes[tech] = new_tree_node();
+    nodes[tech]->is_dummy = FALSE;
+    nodes[tech]->tech = tech;
+  }
+  tech_type_iterate_end;
+
+  tech_type_iterate(tech) {
+    if (!tech_exists(tech)) {
+      continue;
+    }
+    advance = &advances[tech];
+    if (advance->req[0] != A_NONE && advance->req[1] != A_LAST) {
+      if ((advance->req[1] != A_NONE
+          && !is_tech_a_req_for_goal(game.player_ptr, advance->req[0],
+                                     advance->req[1]))
+         || advance->req[1] == A_NONE) {
+       add_requirement(nodes[tech], nodes[advance->req[0]]);
+      }
+
+      if (advance->req[1] != A_NONE) {
+       if (!is_tech_a_req_for_goal
+           (game.player_ptr, advance->req[1], advance->req[0])) {
+         add_requirement(nodes[tech], nodes[advance->req[1]]);
+       }
+      }
+    }
+  } tech_type_iterate_end;
+
+  tree->nodes = fc_malloc(game.num_tech_types * sizeof(*tree->nodes));
+  j = 0;
+  tech_type_iterate(tech) {
+    if (nodes[tech]) {
+      tree->nodes[j] = nodes[tech];
+      assert(tech_exists(tree->nodes[j]->tech));
+      j++;
+    }
+  }
+  tech_type_iterate_end;
+  tree->num_nodes = j;
+  tree->layers = NULL;
+
+  tree->layout = NULL;
+
+  return tree;
+}
+
+/*************************************************************************
+  Free all memory used by tech_tree struct
+*************************************************************************/
+void destroy_techtree(struct techtree *tree)
+{
+  int i;
+  for (i = 0; i < tree->num_nodes; i++) {
+    struct tree_node *node = tree->nodes[i];
+    free(node->require);
+    free(node->provide);
+    free(node);
+  }
+  free(tree->nodes);
+  if (tree->layers) {
+    for (i = 0; i < tree->num_layers; i++) {
+      free(tree->layers[i]);
+    }
+    if (tree->layer_size) {
+      free(tree->layer_size);
+    }
+  }
+  if (tree->layout) {
+    free_diagram_layout(tree->layout);
+  }
+  free(tree);
+}
+
+/*************************************************************************
+  Compute the longest path from this tree_node to the node with 
+  no requirements. Store the result int node->y
+*************************************************************************/
+static int longest_path(struct tree_node *node)
+{
+  int max, i;
+  if (node->y != -1) {
+    return node->y;
+  }
+  max = -1;
+  for (i = 0; i < node->nrequire; i++) {
+    if (longest_path(node->require[i]) > max) {
+      max = longest_path(node->require[i]);
+    }
+  }
+  node->y = max + 1;
+  return node->y;
+}
+
+/*************************************************************************
+  Compute longest_path for all nodes, thus prepare longest path layering
+*************************************************************************/
+static void longest_path_layering(struct techtree *tree)
+{
+  int i;
+  for (i = 0; i < tree->num_nodes; i++) {
+    if (tree->nodes[i]) {
+      longest_path(tree->nodes[i]);
+    }
+  }
+}
+
+/*************************************************************************
+  Find the largest value of y amongst children of the given node
+*************************************************************************/
+static int max_provide_layer(struct tree_node *node)
+{
+  int i;
+  int max = node->y;
+  for (i = 0; i < node->nprovide; i++) {
+    if (node->provide[i]->y > max) {
+      max = node->provide[i]->y;
+    }
+  }
+  return max;
+}
+
+/*************************************************************************
+  Create new tree which has dummy nodes added. The source tree is 
+  completely copied, you can freely deallocate it.
+*************************************************************************/
+static struct techtree *add_dummy_nodes(struct techtree *tree)
+{
+  struct techtree *new_tree;
+  int num_dummy_nodes = 0;
+  int k, i, j;
+
+  /* Count dummy nodes to be added */
+  for (i = 0; i < tree->num_nodes; i++) {
+    int mpl;
+    if (tree->nodes[i] == NULL) {
+      continue;
+    }
+    mpl = max_provide_layer(tree->nodes[i]);
+    if (mpl > tree->nodes[i]->y + 1) {
+      num_dummy_nodes += mpl - tree->nodes[i]->y - 1;
+    }
+  }
+
+  /* create new tree */
+  new_tree = fc_malloc(sizeof(*new_tree));
+  new_tree->nodes =
+      fc_malloc(sizeof(new_tree->nodes) *
+               (tree->num_nodes + num_dummy_nodes));
+  new_tree->num_nodes = tree->num_nodes + num_dummy_nodes;
+  
+  /* copy normal nodes */
+  for (i = 0; i < tree->num_nodes; i++) {
+    new_tree->nodes[i] = new_tree_node();
+    new_tree->nodes[i]->is_dummy = FALSE;
+    new_tree->nodes[i]->tech = tree->nodes[i]->tech;
+    new_tree->nodes[i]->y = tree->nodes[i]->y;
+    tree->nodes[i]->number = i;
+  }
+  
+  /* allocate dummy nodes */
+  for (i = 0; i < num_dummy_nodes; i++) {
+    new_tree->nodes[i + tree->num_nodes] = new_tree_node();
+    new_tree->nodes[i + tree->num_nodes]->is_dummy = TRUE;
+  }
+  /* k points to the first unused dummy node */
+  k = tree->num_nodes;
+
+  for (i = 0; i < tree->num_nodes; i++) {
+    struct tree_node *node = tree->nodes[i];
+    int mpl;
+
+    assert(!node->is_dummy);
+
+    mpl = max_provide_layer(node);
+
+    /* if this node will have dummy as ancestors, connect them in a chain */
+    if (mpl > node->y + 1) {
+      add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
+      for (j = node->y + 2; j < mpl; j++) {
+       add_requirement(new_tree->nodes[k + j - node->y - 1],
+                       new_tree->nodes[k + j - node->y - 2]);
+      }
+      for (j = node->y + 1; j < mpl; j++) {
+       new_tree->nodes[k + j - node->y - 1]->y = j;
+      }
+    }
+
+    /* copy all edges and create edges with dummy nodes */
+    for (j = 0; j < node->nprovide; j++) {
+      int provide_y = node->provide[j]->y;
+      if (provide_y == node->y + 1) {
+        /* direct connection */
+       add_requirement(new_tree->nodes[node->provide[j]->number],
+                       new_tree->nodes[i]);
+      } else {
+        /* connection through dummy node */
+       add_requirement(new_tree->nodes[node->provide[j]->number],
+                       new_tree->nodes[k + provide_y - node->y - 2]);
+      }
+    }
+
+    if (mpl > node->y + 1) {
+      k += mpl - node->y - 1;
+      assert(k <= new_tree->num_nodes);
+    }
+  }
+  new_tree->layers = NULL;
+
+  return new_tree;
+}
+
+/*************************************************************************
+  Calculate layers[] and layer_size[] fields of tree.
+  There should be y value calculated for each node.
+  Nodes will be put into layers in no particular order.
+*************************************************************************/
+static void set_layers(struct techtree *tree)
+{
+  int i;
+  int num_layers = 0;
+  
+  /* count total number of layers */
+  for (i = 0; i < tree->num_nodes; i++) {
+    if (tree->nodes[i]->y > num_layers) {
+      num_layers = tree->nodes[i]->y;
+    }
+  }
+  num_layers++;
+  tree->num_layers = num_layers;
+
+  {
+    /* counters for x */
+    int T[num_layers];
+
+    tree->layers = fc_malloc(sizeof(*tree->layers) * num_layers);
+    tree->layer_size = fc_malloc(sizeof(*tree->layer_size) * num_layers);
+    for (i = 0; i < num_layers; i++) {
+      T[i] = 0;
+      tree->layer_size[i] = 0;
+    }
+    for (i = 0; i < tree->num_nodes; i++) {
+      tree->layer_size[tree->nodes[i]->y]++;
+    }
+
+    for (i = 0; i < num_layers; i++) {
+      tree->layers[i] =
+         fc_malloc(sizeof(*tree->layers[i]) * tree->layer_size[i]);
+    }
+    for (i = 0; i < tree->num_nodes; i++) {
+      struct tree_node *node = tree->nodes[i];
+      tree->layers[node->y][T[node->y]] = node;
+      node->x = T[node->y];
+      T[node->y]++;
+    }
+  }
+}
+
+struct node_and_float {
+  struct tree_node *node;
+  float value;
+};
+
+static int cmp_func(const void *_a, const void *_b)
+{
+  struct node_and_float *a, *b;
+  a = (struct node_and_float *) _a;
+  b = (struct node_and_float *) _b;
+  if (a->value > b->value) {
+    return 1;
+  }
+  if (a->value < b->value) {
+    return -1;
+  }
+  return 0;
+}
+
+/*************************************************************************
+  Simple heuristic: Sort nodes on the given layer by the average x-value
+  of its' parents.
+*************************************************************************/
+static void barycentric_sort(struct techtree *tree, int layer)
+{
+  struct node_and_float T[tree->layer_size[layer]];
+  int i, j;
+  float v;
+
+  for (i = 0; i < tree->layer_size[layer]; i++) {
+    struct tree_node *node = tree->layers[layer][i];
+    T[i].node = node;
+    v = 0.0;
+    for (j = 0; j < node->nrequire; j++) {
+      v += node->require[j]->x;
+    }
+    if (node->nrequire > 0) {
+      v /= (float) node->nrequire;
+    }
+    T[i].value = v;
+  }
+  qsort(T, tree->layer_size[layer], sizeof(*T),
+       cmp_func);
+
+  for (i = 0; i < tree->layer_size[layer]; i++) {
+    tree->layers[layer][i] = T[i].node;
+    T[i].node->x = i;
+  }
+}
+
+/*************************************************************************
+  Calculate number of edge crossings beetwen layer and layer+1
+*************************************************************************/
+static int count_crossings(struct techtree *tree, int layer)
+{
+  int layer1_size = tree->layer_size[layer];
+  int layer2_size = tree->layer_size[layer + 1];
+  
+  int X[layer2_size];
+  int i, j, k;
+  int sum = 0;
+
+
+  for (i = 0; i < layer2_size; i++) {
+    X[i] = 0;
+  }
+
+  for (i = 0; i < layer1_size; i++) {
+    struct tree_node *node = tree->layers[layer][i];
+    for (j = 0; j < node->nprovide; j++) {
+      sum += X[node->provide[j]->x];
+    }
+    for (j = 0; j < node->nprovide; j++) {
+      for (k = 0; k < node->provide[j]->x; k++) {
+       X[k]++;
+      }
+    }
+  }
+
+  return sum;
+}
+
+/*************************************************************************
+  Swap positions of two nodes on the same layer
+*************************************************************************/
+static void swap(struct techtree *tree, int layer, int x1, int x2)
+{
+  struct tree_node *node1 = tree->layers[layer][x1];
+  struct tree_node *node2 = tree->layers[layer][x2];
+  tree->layers[layer][x1] = node2;
+  tree->layers[layer][x2] = node1;
+  node1->x = x2;
+  node2->x = x1;
+}
+
+/*************************************************************************
+  Try to reduce the number of crossings by swapping two nodes and checking
+  if it improves the situation.
+*************************************************************************/
+static void improve(struct techtree *tree)
+{
+  int crossings[tree->num_layers - 1];
+  int i, x1, x2, layer;
+
+  for (i = 0; i < tree->num_layers - 1; i++) {
+    crossings[i] = count_crossings(tree, i);
+  }
+
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    int layer_size = tree->layer_size[layer];
+    int layer_sum = 0;
+    if (layer > 0) {
+      layer_sum += crossings[layer - 1];
+    }
+    if (layer < tree->num_layers - 1) {
+      layer_sum += crossings[layer];
+    }
+
+    for (x1 = 0; x1 < layer_size; x1++) {
+      for (x2 = x1 + 1; x2 < layer_size; x2++) {
+       int new_crossings = 0;
+       int new_crossings_before = 0;
+       swap(tree, layer, x1, x2);
+       if (layer > 0) {
+         new_crossings_before += count_crossings(tree, layer - 1);
+       }
+       if (layer < tree->num_layers - 1) {
+         new_crossings += count_crossings(tree, layer);
+       }
+       if (new_crossings + new_crossings_before > layer_sum) {
+         swap(tree, layer, x1, x2);
+       } else {
+         layer_sum = new_crossings + new_crossings_before;
+         if (layer > 0) {
+           crossings[layer - 1] = new_crossings_before;
+         }
+         if (layer < tree->num_layers - 1) {
+           crossings[layer] = new_crossings;
+         }
+       }
+      }
+    }
+  }
+}
+
+/*************************************************************************
+  Generate optimized tech_tree from current ruleset
+*************************************************************************/
+struct techtree *create_techtree(void)
+{
+  struct techtree *tree1, *tree2;
+  int i, j;
+
+  tree1 = create_dummy_techtree();
+  longest_path_layering(tree1);
+  tree2 = add_dummy_nodes(tree1);
+  destroy_techtree(tree1);
+  set_layers(tree2);
+  
+  /* It's good heuristics for beginning */
+  for (j = 0; j < 20; j++) {
+    for (i = 0; i < tree2->num_layers; i++) {
+      barycentric_sort(tree2, i);
+    }
+  }
+  
+  /* Now burn some CPU */
+  for (j = 0; j < 20; j++) {
+    improve(tree2);
+  }
+
+  tree2->layout = calculate_diagram_layout(tree2);
+
+  return tree2;
+}
+
+/****************************************************************************
+  Give the dimensions of the techtree.
+****************************************************************************/
+void get_techtree_dimensions(struct techtree *techtree,
+                            int *width, int *height)
+{
+  *width = techtree->layout->width;
+  *height = techtree->layout->height;
+}
+
+/****************************************************************************
+  Return a background color of node's rectangle
+****************************************************************************/
+static enum color_std node_color(struct tree_node *node)
+{
+  if (!node->is_dummy) {
+    if (game.player_ptr->research->researching == node->tech) {
+      return COLOR_STD_CYAN;
+    } else if (get_invention(game.player_ptr, node->tech) == TECH_KNOWN) {
+      return COLOR_STD_GROUND;
+    } else if (get_invention(game.player_ptr, node->tech) ==
+              TECH_REACHABLE) {
+      return COLOR_STD_YELLOW;
+    } else {
+      return COLOR_STD_RED;
+    }
+  } else {
+    return COLOR_STD_BLACK;
+  }
+
+}
+
+/****************************************************************************
+  Draw the techtree diagram!
+
+  This draws the given portion of the techtree diagram (given by
+  (tt_x,tt_y) and (w,h) onto the canvas at position (canvas_x, canvas_y).
+****************************************************************************/
+void draw_techtree(struct techtree *tree,
+                  struct canvas *pcanvas,
+                  int canvas_x, int canvas_y,
+                  int tt_x, int tt_y, int w, int h)
+{
+  int i, j, k;
+  struct diagram_layout* current_layout = tree->layout;
+
+  /* draw the diagram */
+  for (i = 0; i < tree->num_layers; i++) {
+    for (j = 0; j < tree->layer_size[i]; j++) {
+      struct tree_node *node = tree->layers[i][j];
+      int startx, starty, endx, endy, width, height;
+
+      startx = current_layout->node_x[node->number];
+      starty = current_layout->node_y[node->number];
+      width = current_layout->node_width[node->number];
+      height = current_layout->node_height[node->number];
+
+      canvas_put_rectangle(pcanvas, COLOR_STD_BLACK,
+                          startx, starty, width, height);
+
+      if (!node->is_dummy) {
+       const char *text = get_tech_name(game.player_ptr, node->tech);
+       int text_w, text_h;
+
+       /* Print color rectangle with text inside. */
+       canvas_put_rectangle(pcanvas, node_color(node),
+                            startx + 1, starty + 1,
+                            width - 2, height - 2);
+       get_text_size(&text_w, &text_h, FONT_TECHTREE_NODE, text);
+
+       canvas_put_text(pcanvas,
+                       startx + (width - text_w) / 2,
+                       starty + (height - text_h) / 2,
+                       FONT_TECHTREE_NODE, COLOR_STD_BLACK, text);
+      }
+
+      /* Draw all outgoing edges */
+      startx = current_layout->node_x[node->number]
+       + current_layout->node_width[node->number];
+      starty = current_layout->node_y[node->number]
+       + current_layout->node_height[node->number] / 2;
+      for (k = 0; k < node->nprovide; k++) {
+       struct tree_node *dest_node = node->provide[k];
+
+       endx = current_layout->node_x[dest_node->number];
+       endy = current_layout->node_y[dest_node->number]
+         + current_layout->node_height[dest_node->number] / 2;
+
+       canvas_put_line(pcanvas, COLOR_STD_BLACK, LINE_NORMAL,
+                       startx, starty, endx - startx, endy - starty);
+      }
+    }
+  }
+}
Index: client/techtree.h
===================================================================
RCS file: client/techtree.h
diff -N client/techtree.h
--- /dev/null   1 Jan 1970 00:00:00 -0000
+++ client/techtree.h   9 Apr 2005 03:53:19 -0000
@@ -0,0 +1,32 @@
+/********************************************************************** 
+   Copyright (C) 2005  The Freeciv Project
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2, or (at your option)
+   any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+***********************************************************************/
+
+#ifndef FC__TECHTREE_H
+#define FC__TECHTREE_H
+
+#include "canvas_g.h"
+
+struct techtree;
+
+struct techtree *create_techtree(void);
+void destroy_techtree(struct techtree *techtree);
+
+void get_techtree_dimensions(struct techtree *techtree,
+                            int *width, int *height);
+
+void draw_techtree(struct techtree *techtree,
+                  struct canvas *pcanvas,
+                  int canvas_x, int canvas_y,
+                  int tt_x, int tt_y, int w, int h);
+
+#endif
Index: client/gui-gtk-2.0/canvas.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/gui-gtk-2.0/canvas.c,v
retrieving revision 1.2
diff -u -r1.2 canvas.c
--- client/gui-gtk-2.0/canvas.c 28 Mar 2005 16:59:14 -0000      1.2
+++ client/gui-gtk-2.0/canvas.c 9 Apr 2005 03:53:20 -0000
@@ -263,8 +263,14 @@
 }
 
 static PangoLayout *layout;
-static PangoFontDescription **fonts[FONT_COUNT] = {&main_font,
-                                                  &city_productions_font};
+static struct {
+  PangoFontDescription **font;
+  bool shadowed;
+} fonts[FONT_COUNT] = {
+  {&main_font, TRUE},
+  {&city_productions_font, TRUE},
+  {&city_productions_font, FALSE} /* FIXME: should use separate font */
+};
 
 /****************************************************************************
   Return the size of the given text in the given font.  This size should
@@ -280,7 +286,7 @@
     layout = pango_layout_new(gdk_pango_context_get());
   }
 
-  pango_layout_set_font_description(layout, *fonts[font]);
+  pango_layout_set_font_description(layout, *fonts[font].font);
   pango_layout_set_text(layout, text, -1);
 
   pango_layout_get_pixel_extents(layout, &rect, NULL);
@@ -311,12 +317,18 @@
   }
 
   gdk_gc_set_foreground(civ_gc, colors_standard[color]);
-  pango_layout_set_font_description(layout, *fonts[font]);
+  pango_layout_set_font_description(layout, *fonts[font].font);
   pango_layout_set_text(layout, text, -1);
 
   pango_layout_get_pixel_extents(layout, &rect, NULL);
-  gtk_draw_shadowed_string(pcanvas->v.pixmap,
-                          toplevel->style->black_gc, civ_gc,
-                          canvas_x,
-                          canvas_y + PANGO_ASCENT(rect), layout);
+  if (fonts[font].shadowed) {
+    gtk_draw_shadowed_string(pcanvas->v.pixmap,
+                            toplevel->style->black_gc, civ_gc,
+                            canvas_x,
+                            canvas_y + PANGO_ASCENT(rect), layout);
+  } else {
+    gdk_draw_layout(pcanvas->v.pixmap, civ_gc,
+                   canvas_x, canvas_y + PANGO_ASCENT(rect),
+                   layout);
+  }
 }
Index: client/gui-gtk-2.0/repodlgs.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/gui-gtk-2.0/repodlgs.c,v
retrieving revision 1.82
diff -u -r1.82 repodlgs.c
--- client/gui-gtk-2.0/repodlgs.c       6 Apr 2005 17:36:15 -0000       1.82
+++ client/gui-gtk-2.0/repodlgs.c       9 Apr 2005 03:53:20 -0000
@@ -45,28 +45,25 @@
 #include "options.h"
 #include "packhand_gen.h"
 #include "control.h"
+#include "techtree.h"
 #include "text.h"
 
+#include "canvas.h"
 #include "repodlgs_common.h"
 #include "repodlgs.h"
 
 /******************************************************************/
 
 static void create_science_dialog(bool make_modal);
-static void science_help_callback(GtkTreeView *view,
-                                 GtkTreePath *arg1,
-                                 GtkTreeViewColumn *arg2,
-                                 gpointer data);
 static void science_change_callback(GtkWidget * widget, gpointer data);
 static void science_goal_callback(GtkWidget * widget, gpointer data);
-
 /******************************************************************/
 static struct gui_dialog *science_dialog_shell = NULL;
 static GtkWidget *science_label;
 static GtkWidget *science_current_label, *science_goal_label;
 static GtkWidget *science_change_menu_button, *science_goal_menu_button;
 static GtkWidget *science_help_toggle;
-static GtkListStore *science_model[3];
+static GtkWidget *science_drawing_area;
 static int science_dialog_shell_is_modal;
 static GtkWidget *popupmenu, *goalmenu;
 
@@ -165,13 +162,57 @@
 }
  
 
+/****************************************************************************
+  Draw the invalidated portion of the techtree.
+****************************************************************************/
+static void update_science_drawing_area(GtkWidget *widget, gpointer data)
+{
+  /* FIXME: this currently redraws everything! */
+  struct canvas canvas = {.type = CANVAS_PIXMAP,
+                         .v.pixmap = GTK_LAYOUT(widget)->bin_window};
+  struct techtree *techtree = g_object_get_data(G_OBJECT(widget), "techtree");
+  int width, height;
+
+  get_techtree_dimensions(techtree, &width, &height);
+  draw_techtree(techtree, &canvas, 0, 0, 0, 0, width, height);
+}
+
+/****************************************************************************
+  Return main widget of new technology diagram.
+  This is currently GtkScrolledWindow 
+****************************************************************************/
+static GtkWidget *create_techtree_diagram(void)
+{
+  GtkWidget *sw;
+  struct techtree *techtree = create_techtree();
+  int width, height;
+
+  get_techtree_dimensions(techtree, &width, &height);
+
+  sw = gtk_scrolled_window_new(NULL, NULL);
+  science_drawing_area = gtk_layout_new(NULL, NULL);
+  g_object_set_data_full(G_OBJECT(science_drawing_area), "techtree",
+                         techtree,
+                        (GDestroyNotify)destroy_techtree);
+  g_signal_connect(G_OBJECT(science_drawing_area), "expose_event",
+                  G_CALLBACK(update_science_drawing_area), NULL);
+                        
+  gtk_layout_set_size(GTK_LAYOUT(science_drawing_area), width, height);
+
+  gtk_container_add(GTK_CONTAINER(sw), science_drawing_area);
+  gtk_scrolled_window_set_policy(GTK_SCROLLED_WINDOW(sw),
+                                GTK_POLICY_AUTOMATIC,
+                                GTK_POLICY_AUTOMATIC);
+  return sw;
+}
+
 /****************************************************************
 ...
 *****************************************************************/
 void create_science_dialog(bool make_modal)
 {
   GtkWidget *frame, *hbox, *w;
-  int i;
+  GtkWidget *science_diagram;
 
   gui_dialog_new(&science_dialog_shell, GTK_NOTEBOOK(top_notebook));
   gui_dialog_set_title(science_dialog_shell, _("Science"));
@@ -227,39 +268,9 @@
 
   w = gtk_label_new("");
   gtk_box_pack_start(GTK_BOX(hbox), w, TRUE, FALSE, 0);
-
-  sw = gtk_scrolled_window_new(NULL, NULL);
-  gtk_scrolled_window_set_policy(GTK_SCROLLED_WINDOW(sw),
-      GTK_POLICY_AUTOMATIC, GTK_POLICY_ALWAYS);
-  gtk_box_pack_start(GTK_BOX(science_dialog_shell->vbox), sw, TRUE, TRUE, 5);
-
-  hbox = gtk_hbox_new(TRUE, 0);
-  gtk_scrolled_window_add_with_viewport(GTK_SCROLLED_WINDOW(sw), hbox);
-
-
-  for (i=0; i<ARRAY_SIZE(science_model); i++) {
-    GtkWidget *view;
-    GtkTreeSelection *selection;
-    GtkCellRenderer *renderer;
-    GtkTreeViewColumn *column;
-
-    science_model[i] = gtk_list_store_new(1, G_TYPE_STRING);
-    view = gtk_tree_view_new_with_model(GTK_TREE_MODEL(science_model[i]));
-    gtk_box_pack_start(GTK_BOX(hbox), view, TRUE, TRUE, 0);
-    gtk_widget_set_name(view, "small font");
-    selection = gtk_tree_view_get_selection(GTK_TREE_VIEW(view));
-    g_object_unref(science_model[i]);
-    gtk_tree_view_columns_autosize(GTK_TREE_VIEW(view));
-    gtk_tree_view_set_headers_visible(GTK_TREE_VIEW(view), FALSE);
-
-    renderer = gtk_cell_renderer_text_new();
-    column = gtk_tree_view_column_new_with_attributes(NULL, renderer,
-       "text", 0, NULL);
-    gtk_tree_view_append_column(GTK_TREE_VIEW(view), column);
-
-    g_signal_connect(view, "row_activated",
-       G_CALLBACK(science_help_callback), NULL);
-  }
+  
+  science_diagram = create_techtree_diagram();
+  gtk_box_pack_start(GTK_BOX(science_dialog_shell->vbox), science_diagram, 
TRUE, TRUE, 0);
 
   gui_dialog_show_all(science_dialog_shell);
 
@@ -329,30 +340,6 @@
 /****************************************************************
 ...
 *****************************************************************/
-static void science_help_callback(GtkTreeView *view,
-                                 GtkTreePath *arg1,
-                                 GtkTreeViewColumn *arg2,
-                                 gpointer data)
-{
-  GtkTreeModel *model = gtk_tree_view_get_model(view);
-
-  if (GTK_TOGGLE_BUTTON(science_help_toggle)->active) {
-    GtkTreeIter it;
-    char *s;
-
-    gtk_tree_model_get_iter(model, &it, arg1);
-    gtk_tree_model_get(model, &it, 0, &s, -1);
-    if (*s != '\0') {
-      popup_help_dialog_typed(s, HELP_TECH);
-    } else {
-      popup_help_dialog_string(HELP_TECHS_ITEM);
-    }
-  }
-}
-
-/****************************************************************
-...
-*****************************************************************/
 static gint cmp_func(gconstpointer a_p, gconstpointer b_p)
 {
   const gchar *a_str, *b_str;
@@ -386,7 +373,7 @@
 void science_dialog_update(void)
 {
   if(science_dialog_shell) {
-  int i, j, hist;
+  int i, hist;
   char text[512];
   GtkWidget *item;
   GList *sorting_list = NULL, *it;
@@ -398,12 +385,10 @@
     return;
   }
 
-  gtk_label_set_text(GTK_LABEL(science_label), science_dialog_text());
-
-  for (i=0; i<ARRAY_SIZE(science_model); i++) {
-    gtk_list_store_clear(science_model[i]);
-  }
+  gtk_widget_queue_draw(science_drawing_area);
 
+  gtk_label_set_text(GTK_LABEL(science_label), science_dialog_text());
+  
   /* collect all researched techs in sorting_list */
   for(i=A_FIRST; i<game.num_tech_types; i++) {
     if ((get_invention(game.player_ptr, i)==TECH_KNOWN)) {
@@ -413,19 +398,6 @@
 
   /* sort them, and install them in the list */
   sorting_list = g_list_sort(sorting_list, cmp_func);
-  for(i=0; i<g_list_length(sorting_list); i++) {
-    GtkTreeIter it;
-    GValue value = { 0, };
-
-    j = GPOINTER_TO_INT(g_list_nth_data(sorting_list, i));
-    gtk_list_store_append(science_model[i%ARRAY_SIZE(science_model)], &it);
-
-    g_value_init(&value, G_TYPE_STRING);
-    g_value_set_static_string(&value, get_tech_name(game.player_ptr, j));
-    gtk_list_store_set_value(science_model[i%ARRAY_SIZE(science_model)], &it,
-       0, &value);
-    g_value_unset(&value);
-  }
   g_list_free(sorting_list);
   sorting_list = NULL;
 
@@ -578,6 +550,7 @@
        g_list_index(sorting_list, GINT_TO_POINTER(hist)));
   g_list_free(sorting_list);
   sorting_list = NULL;
+ 
   }
 }
 
Index: client/include/canvas_g.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/include/canvas_g.h,v
retrieving revision 1.3
diff -u -r1.3 canvas_g.h
--- client/include/canvas_g.h   28 Mar 2005 16:59:15 -0000      1.3
+++ client/include/canvas_g.h   9 Apr 2005 03:53:20 -0000
@@ -54,6 +54,7 @@
 enum client_font {
   FONT_CITY_NAME,
   FONT_CITY_PROD,
+  FONT_TECHTREE_TEXT,
   FONT_COUNT
 };
 void get_text_size(int *width, int *height,