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

["Mateusz Stefek" <mstefek@xxxxxxxxx>]

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

The attached screenshot tells everything. 
 
This doesn't look like diagrams in commercial games, but it is step 
forward. I belive that with good tileset support it could look much 
better. 
 
There are many improvements which should/could be considered: 
- icons in rectangles 
- tooltips 
- making the diagram interactive 
- recentering on current tech goal 
- beter algorithm for dividing tree into layers 
 
I tried to divide the code into three parts: combinatorial, 
calculating layout and drawing. It should be easy to add improvements 
into one part without touching the rest. 
-- 
mateusz

diff -urN -Xfreeciv/diff_ignore freeciv/client/gui-gtk-2.0/Makefile.am 
changed/client/gui-gtk-2.0/Makefile.am
--- freeciv/client/gui-gtk-2.0/Makefile.am      2005-03-25 08:53:38.000000000 
+0100
+++ changed/client/gui-gtk-2.0/Makefile.am      2005-04-02 09:35:55.000000000 
+0200
@@ -85,6 +85,8 @@
        spaceshipdlg.h  \
        sprite.c        \
        sprite.h        \
+       techtree.c      \
+       techtree.h      \
        wldlg.c         \
        wldlg.h 
 
diff -urN -Xfreeciv/diff_ignore freeciv/client/gui-gtk-2.0/repodlgs.c 
changed/client/gui-gtk-2.0/repodlgs.c
--- freeciv/client/gui-gtk-2.0/repodlgs.c       2005-03-25 08:53:38.000000000 
+0100
+++ changed/client/gui-gtk-2.0/repodlgs.c       2005-04-03 12:33:03.000000000 
+0200
@@ -49,24 +49,19 @@
 
 #include "repodlgs_common.h"
 #include "repodlgs.h"
+#include "techtree.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 int science_dialog_shell_is_modal;
 static GtkWidget *popupmenu, *goalmenu;
 
@@ -171,7 +166,7 @@
 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 +222,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 +294,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 +327,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;
@@ -397,13 +338,11 @@
   if (is_report_dialogs_frozen()) {
     return;
   }
+  
+  update_techtree_diagram();
 
   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]);
-  }
-
+  
   /* 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 +352,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 +504,7 @@
        g_list_index(sorting_list, GINT_TO_POINTER(hist)));
   g_list_free(sorting_list);
   sorting_list = NULL;
+ 
   }
 }
 
diff -urN -Xfreeciv/diff_ignore freeciv/client/gui-gtk-2.0/techtree.c 
changed/client/gui-gtk-2.0/techtree.c
--- freeciv/client/gui-gtk-2.0/techtree.c       1970-01-01 01:00:00.000000000 
+0100
+++ changed/client/gui-gtk-2.0/techtree.c       2005-04-03 12:35:34.000000000 
+0200
@@ -0,0 +1,323 @@
+/********************************************************************** 
+   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 <math.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <gtk/gtk.h>
+#include <gdk/gdkkeysyms.h>
+
+#include "log.h"
+
+#include "fcintl.h"
+#include "game.h"
+#include "government.h"
+#include "packets.h"
+#include "shared.h"
+#include "support.h"
+
+#include "chatline_common.h"
+#include "cityrep.h"
+#include "civclient.h"
+#include "climisc.h"
+#include "clinet.h"
+#include "control.h"
+#include "colors.h"
+#include "dialogs.h"
+#include "gui_main.h"
+#include "gui_stuff.h"
+#include "helpdlg.h"
+#include "mapview_common.h"
+#include "options.h"
+#include "packhand_gen.h"
+#include "control.h"
+#include "techtree_common.h"
+#include "text.h"
+
+#include "canvas.h"
+
+#include "techtree.h"
+
+static void update_science_drawing_area(GtkWidget * w, gpointer data);
+static GtkWidget *science_drawing_area;
+static void node_rectangle_minimum_size(struct tree_node *node, int *width,
+                                       int *height);
+/****************************************************************************
+  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;
+};
+
+/****************************************************************************
+  Calculate rectangles position and size from current tech_tree
+****************************************************************************/
+static struct diagram_layout* calculate_diagram_layout()
+{
+  struct tech_tree* tree = get_current_tech_tree();
+  struct diagram_layout* layout = fc_malloc(sizeof(struct diagram_layout));
+  int i;
+  int layer;
+  int layer_offs;
+  struct tree_node* node;
+  
+  layout->node_x = fc_malloc(tree->num_nodes * sizeof(int));
+  layout->node_y = fc_malloc(tree->num_nodes * sizeof(int));
+  layout->node_width = fc_malloc(tree->num_nodes * sizeof(int));
+  layout->node_height = fc_malloc(tree->num_nodes * sizeof(int));
+
+  /* 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);
+}
+
+/****************************************************************************
+  Return main widget of new technology diagram.
+  This is currently GtkScrolledWindow 
+****************************************************************************/
+GtkWidget *create_techtree_diagram(void)
+{
+  GtkWidget *sw;
+  struct diagram_layout* diagram =  calculate_diagram_layout();
+  
+  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), "current_layout",
+                         (gpointer) diagram,
+                        (GDestroyNotify)free_diagram_layout);
+  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),
+                      diagram->width,
+                     diagram->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;
+}
+
+/****************************************************************************
+  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 = 0;
+  } else {
+    get_text_size(width, height, FONT_CITY_PROD,
+                 get_tech_name(game.player_ptr, node->tech));
+    *width += 2;
+    *height += 8;
+  }
+}
+
+
+/****************************************************************************
+  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 diagram
+****************************************************************************/
+static void update_science_drawing_area(GtkWidget * w,
+                                        gpointer data)
+{
+  struct tree_node *node;
+  int i, j;
+  GdkWindow *window = GTK_LAYOUT(science_drawing_area)->bin_window;
+  GdkGC *gc = gdk_gc_new(window);
+  struct tech_tree* tree = get_current_tech_tree();
+
+  struct diagram_layout* current_layout =
+    g_object_get_data(G_OBJECT(science_drawing_area), "current_layout");
+
+
+  /* draw the diagram */
+  for (i = 0; i < tree->num_layers; i++) {
+    for (j = 0; j < tree->layer_size[i]; j++) {
+      node = tree->layers[i][j];
+      int startx, starty, endx, endy;
+      int 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];
+      
+      gdk_gc_set_foreground(gc, colors_standard[node_color(node)]);
+      gdk_draw_rectangle(window, gc, TRUE,
+                        startx, starty, width, height);
+                        
+      gdk_gc_set_foreground(gc, colors_standard[COLOR_STD_BLACK]);
+      gdk_draw_rectangle(window, gc, FALSE,
+                        startx, starty, width, height);
+      if (!node->is_dummy) {
+        /* Print text inside the rectangle */
+       static PangoLayout *layout;
+       if (layout == NULL) {
+         layout = pango_layout_new(gdk_pango_context_get());
+       }
+       pango_layout_set_font_description(layout, city_productions_font);
+       pango_layout_set_text(layout,
+                             get_tech_name(game.player_ptr, node->tech),
+                             -1);
+       gdk_draw_layout(window, gc, startx + 1, starty + 1, layout);
+      }
+      
+      /* 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;
+      int k;
+      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;
+       gdk_draw_line(window, gc, startx, starty, endx, endy);
+      }
+    }
+  }
+}
+
+/****************************************************************************
+  Refresh the tech tree diagram
+****************************************************************************/
+void update_techtree_diagram(void)
+{
+  if (GTK_LAYOUT(science_drawing_area)->bin_window) {
+    GdkRectangle rect;
+    rect.x = 0;
+    rect.y = 0;
+    rect.width = 100000;
+    rect.height = 100000;
+    gdk_window_invalidate_rect(GTK_LAYOUT(science_drawing_area)->
+                              bin_window, &rect, FALSE);
+  }
+}
diff -urN -Xfreeciv/diff_ignore freeciv/client/gui-gtk-2.0/techtree.h 
changed/client/gui-gtk-2.0/techtree.h
--- freeciv/client/gui-gtk-2.0/techtree.h       1970-01-01 01:00:00.000000000 
+0100
+++ changed/client/gui-gtk-2.0/techtree.h       2005-04-02 12:47:44.000000000 
+0200
@@ -0,0 +1,20 @@
+/********************************************************************** 
+   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__TECH_TREE_H
+#define FC__TECH_TREE_H
+#include <gtk/gtk.h>
+GtkWidget* create_techtree_diagram(void);
+void update_techtree_diagram(void);
+#endif
+ 
+
diff -urN -Xfreeciv/diff_ignore freeciv/client/Makefile.am 
changed/client/Makefile.am
--- freeciv/client/Makefile.am  2005-03-25 08:53:36.000000000 +0100
+++ changed/client/Makefile.am  2005-04-01 11:08:42.000000000 +0200
@@ -180,6 +180,8 @@
        options.h       \
        repodlgs_common.c \
        repodlgs_common.h \
+       techtree_common.c \
+       techtree_common.h \
        text.c  \
        text.h  \
        tilespec.c      \
diff -urN -Xfreeciv/diff_ignore freeciv/client/packhand.c 
changed/client/packhand.c
--- freeciv/client/packhand.c   2005-03-29 11:59:41.000000000 +0200
+++ changed/client/packhand.c   2005-04-02 09:58:27.000000000 +0200
@@ -64,6 +64,7 @@
 #include "plrdlg_g.h"
 #include "repodlgs_g.h"
 #include "spaceshipdlg_g.h"
+#include "techtree_common.h"
 #include "tilespec.h"
 #include "wldlg_g.h"
 
@@ -2080,6 +2081,7 @@
 
   tileset_free_city_tiles(tileset, game.styles_count);
   ruleset_data_free();
+  free_current_tech_tree();
 
   ruleset_cache_init();
 
diff -urN -Xfreeciv/diff_ignore freeciv/client/techtree_common.c 
changed/client/techtree_common.c
--- freeciv/client/techtree_common.c    1970-01-01 01:00:00.000000000 +0100
+++ changed/client/techtree_common.c    2005-04-03 12:41:15.000000000 +0200
@@ -0,0 +1,525 @@
+/********************************************************************** 
+   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 "techtree_common.h"
+
+/*************************************************************************
+  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(struct tree_node *) * (node->nrequire + 1));
+  node->require[node->nrequire] = req;
+  node->nrequire++;
+
+  req->provide =
+      fc_realloc(req->provide,
+                sizeof(struct tree_node *) * (req->nprovide + 1));
+  req->provide[req->nprovide] = node;
+  req->nprovide++;
+}
+
+/*************************************************************************
+  Allocate and init new tree node
+*************************************************************************/
+static struct tree_node *new_tree_node()
+{
+  struct tree_node *node = fc_malloc(sizeof(struct tree_node));
+  node->nrequire = 0;
+  node->nprovide = 0;
+  node->require = fc_malloc(1);
+  node->provide = fc_malloc(1);
+  node->x = -1;
+  node->y = -1;
+  return node;
+}
+
+/*************************************************************************
+  Create tech tree from current ruleset
+  There is no dummy edges and layers[] tables aren't set
+  Don't include redundant edges.
+*************************************************************************/
+static struct tech_tree *create_tech_tree(void)
+{
+  struct tech_tree *tree = fc_malloc(sizeof(struct tech_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(struct tree_node *));
+  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;
+  return tree;
+}
+
+/*************************************************************************
+  Free all memory used by tech_tree struct
+*************************************************************************/
+static void free_tech_tree(struct tech_tree *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);
+    }
+  }
+  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 tech_tree *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 tech_tree *add_dummy_nodes(struct tech_tree *tree)
+{
+  struct tech_tree *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(struct tech_tree));
+  new_tree->nodes =
+      fc_malloc(sizeof(struct tree_node *) *
+               (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 tech_tree *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(struct tree_node **) * num_layers);
+    tree->layer_size = fc_malloc(sizeof(int) * 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(struct tree_node *) * 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 tech_tree *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(struct node_and_float),
+       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 tech_tree *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 tech_tree *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 tech_tree *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
+*************************************************************************/
+static struct tech_tree *generate_tech_tree(void)
+{
+  struct tech_tree *tree1, *tree2;
+  int i, j;
+
+  tree1 = create_tech_tree();
+  longest_path_layering(tree1);
+  tree2 = add_dummy_nodes(tree1);
+  free_tech_tree(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);
+  }
+  return tree2;
+}
+
+static struct tech_tree *current_tech_tree;
+
+/*************************************************************************
+  Return current optimized tree based on current ruleset
+*************************************************************************/
+struct tech_tree *get_current_tech_tree(void)
+{
+  if (current_tech_tree == NULL) {
+    current_tech_tree = generate_tech_tree();
+  }
+  return current_tech_tree;
+}
+
+/*************************************************************************
+  Release current tech tree. Next call to get_cuurent_tech_tree will
+  recalculate tech tree
+*************************************************************************/
+void free_current_tech_tree(void)
+{
+  if (current_tech_tree) {
+    free_tech_tree(current_tech_tree);
+    current_tech_tree = NULL;
+  }
+}
diff -urN -Xfreeciv/diff_ignore freeciv/client/techtree_common.h 
changed/client/techtree_common.h
--- freeciv/client/techtree_common.h    1970-01-01 01:00:00.000000000 +0100
+++ changed/client/techtree_common.h    2005-04-03 12:43:09.000000000 +0200
@@ -0,0 +1,59 @@
+/********************************************************************** 
+   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_COMMON_H
+#define FC__TECHTREE_COMMON_H
+#include <assert.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include <game.h>
+#include <tech.h>
+
+/****************************************************************************
+  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 tech_tree {
+    int num_nodes;
+    struct tree_node** nodes;
+
+    int num_layers;
+    int* layer_size;
+    struct tree_node*** layers;
+};
+
+
+void free_current_tech_tree(void);
+struct tech_tree* get_current_tech_tree(void);
+#endif