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

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

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

Jason Short wrote:

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

This patch does that.

The only problem is we run out of "regular" colors and have to resort to 
using RACEN colors.  This should all be cleaned up someday - lots of 
code uses COLOR_STD_GROUND or COLOR_STD_RACE5 assuming it gives a 
particular color.  We already have 22 colors so there's no harm adding a 
few more.  In particular the player colors should probably not be 
hard-coded as enumerated values but should be determined by the tileset.

Again, a screenshot should tell it all: 
http://bugs.freeciv.org/Ticket/Attachment/94277/60278/techtree.png.

-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 04:37:26 -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 04:37:26 -0000
@@ -0,0 +1,796 @@
+/********************************************************************** 
+   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;
+    }
+    
+    if (get_invention(game.player_ptr, node->tech) == TECH_KNOWN) {
+      return COLOR_STD_GROUND;
+    }
+
+    if (is_tech_a_req_for_goal(game.player_ptr, node->tech,
+                              game.player_ptr->ai.tech_goal)
+       || node->tech == game.player_ptr->ai.tech_goal) {
+      if (get_invention(game.player_ptr, node->tech) == TECH_REACHABLE) {
+       return COLOR_STD_RACE8;
+      } else {
+       return COLOR_STD_RACE3;
+      }
+    }
+
+    if (get_invention(game.player_ptr, node->tech) == TECH_REACHABLE) {
+      return COLOR_STD_YELLOW;
+    }
+
+    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;
+
+  /* FIXME: this always draws the entire techtree. */
+  assert(canvas_x == tt_x && canvas_y == tt_y);
+
+  /* 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 04:37:26 -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 04:37:26 -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 04:37:26 -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 04:37:27 -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,