Complete.Org: Mailing Lists: Archives: freeciv-dev: April 2005:
[Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram
Home

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

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: mstefek@xxxxxxxxx
Subject: [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram
From: "Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>
Date: Sat, 9 Apr 2005 10:15:23 -0700
Reply-to: bugs@xxxxxxxxxxx

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

Mateusz Stefek wrote:
> <URL: http://bugs.freeciv.org/Ticket/Display.html?id=12719 >
> 
>>[jdorje - Sat Apr 09 04:08:31 2005]:
>>
>>After banging on it for a while, here's what I have.
>>
> 
> Hey, I've just finished writing something similar. :)
> 
> I removed diagram_layout struct, now it is merged with tech_tree.
> (there are node_x and node_y fields in tree_node struct).
> 
> I added symetrize function() - it really makes the diagram
> look better.
> 
> I made it interactive, and center on current research.
> Techs which are required for the technology goal are bolded and so are
> they
> 
> Your patch is ok - just copy the symetrize() function and 
> button_released_event_callback()

I copied over your new parts into my patch (including the removal of the 
layout struct, much better).  I changed the behavior of buttons slightly 
(LMB sets research *and* research goal, RMB opens help).  I kept my 
coloration method for the research goal (instead of your bold method 
which might require a new line_type).

Here's the result.  I'm happy with it.

Few issues remain (maybe):

- The old list could still be of use.  Maybe we should keep it around in 
tabbed form (techtree in one tab and list in the other).

- Button behavior may not be intuitive.  Maybe there should be text at 
the top "left-click to set research, right-click for help".

- Centering doesn't work when researching future techs (A_FUTURE, should 
centering on rightmost part of diagram) or when no tech goal is set 
(A_NONE, should center on left-most available tech, maybe).

- Lines are a bit ugly (it uses LINE_NORMAL which is thin_line_gc) and 
have no anti-aliasing.

- Support for other GUIs (easy to add later).

-jason

? tech_diagram_7.diff
? client/techtree_common.c
? client/techtree_common.h
? client/gui-gtk-2.0/foo
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 17:07:00 -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 17:07:00 -0000
@@ -0,0 +1,871 @@
+/********************************************************************** 
+   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 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 layer, order;
+
+  /* Coordinates of the rectangle on the diagram */
+  int node_x, node_y, node_width, node_height;
+
+  /* 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;
+
+  int diagram_width, diagram_height;
+};
+
+
+/*************************************************************************
+  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->layer = -1;
+  node->order = -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;
+  }
+}
+
+/****************************************************************************
+  Move nodes up and down without changing order but making it more 
+  symetrical. Gravitate towards parents average position
+****************************************************************************/
+static void symetrize(struct techtree* tree)
+{
+  int layer;
+  int i, j;
+  
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      struct tree_node* node = tree->layers[layer][i];
+      int v, node_y, node_height;
+      if (node->nrequire == 0) {
+        continue;
+      }
+      v = 0;
+      for (j = 0; j < node->nrequire; j++) {
+        struct tree_node* node_require = node->require[j];
+        v += node_require->node_y + node_require->node_height / 2;
+      }
+      v /= node->nrequire;
+      node_y = node->node_y;
+      node_height = node->node_height;
+      if (v < node_y + node_height / 2) {
+        if (node_y <= 0) {
+         continue;
+       }
+       if (i > 0) {
+         struct tree_node* node_above = tree->layers[layer][i-1];
+         if (node_above->node_y
+             + node_above->node_height >= node_y - 11) {
+           continue;
+         }
+       }
+       node_y--;
+      } else if (v > node_y + node_height / 2) {
+        if (node_y + node_height >= tree->diagram_height - 1) {
+         continue;
+       }
+       if (i < tree->layer_size[layer] - 1) {
+         struct tree_node* node_below = tree->layers[layer][i+1];
+         if (node_y + node_height >= node_below->node_y - 11) {
+           continue;
+         }
+       }
+       node_y++;
+      }
+      node->node_y = node_y;
+    }
+  }
+}
+
+/****************************************************************************
+  Calculate rectangles position and size from current tech_tree
+****************************************************************************/
+static void calculate_diagram_layout(struct techtree *tree)
+{
+  int i, layer, layer_offs;
+
+  /* calculate minimum size of rectangle for each node */
+  for (i = 0; i < tree->num_nodes; i++) {
+    struct tree_node *node = tree->nodes[i];
+
+    node_rectangle_minimum_size(tree->nodes[i],
+      &node->node_width, &node->node_height);
+    node->number = i;
+  }
+  
+  /* calculate height of the diagram. There should be at least 10 pixels
+   * beetween any two nodes */
+  tree->diagram_height = 0;
+  for (layer = 0; layer < tree->num_layers; layer++) {
+    int h_sum = 0;
+
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      struct tree_node *node = tree->layers[layer][i];
+
+      h_sum += node->node_height;
+      if (i < tree->layer_size[layer] - 1) {
+       h_sum += 10;
+      }
+    }
+    tree->diagram_height = MAX(tree->diagram_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++) {
+      struct tree_node *node = tree->layers[layer][i];
+
+      max_width = MAX(max_width, node->node_width);
+    }
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      struct tree_node *node = tree->layers[layer][i];
+
+      node->node_width = max_width;
+      node->node_x = layer_offs;
+    }
+    if (layer != tree->num_layers - 1)  {
+      layer_offs += max_width * 5 / 4 + 80;
+    } else {
+      layer_offs += max_width + 10;
+    }
+  }
+  tree->diagram_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++) {
+      struct tree_node *node = tree->layers[layer][i];
+
+      h_sum += node->node_height;
+    }
+    for (i = 0; i < tree->layer_size[layer]; i++) {
+      struct tree_node *node = tree->layers[layer][i];
+
+      node->node_y = y;
+      y += node->node_height;
+      if (tree->layer_size[layer] > 1) {
+       y += (tree->diagram_height - h_sum)
+         / (tree->layer_size[layer] - 1) - 1;
+      }
+    }
+  }
+
+  for (i = 0; i < tree->diagram_height; i++) {
+    symetrize(tree);
+  }
+}
+
+/*************************************************************************
+  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;
+
+  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);
+    }
+  }
+  free(tree);
+}
+
+/*************************************************************************
+  Compute the longest path from this tree_node to the node with 
+  no requirements. Store the result int node->order
+*************************************************************************/
+static int longest_path(struct tree_node *node)
+{
+  int max, i;
+  if (node->order != -1) {
+    return node->order;
+  }
+  max = -1;
+  for (i = 0; i < node->nrequire; i++) {
+    if (longest_path(node->require[i]) > max) {
+      max = longest_path(node->require[i]);
+    }
+  }
+  node->order = max + 1;
+  return node->order;
+}
+
+/*************************************************************************
+  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->order;
+  for (i = 0; i < node->nprovide; i++) {
+    if (node->provide[i]->order > max) {
+      max = node->provide[i]->order;
+    }
+  }
+  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]->order + 1) {
+      num_dummy_nodes += mpl - tree->nodes[i]->order - 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]->order = tree->nodes[i]->order;
+    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->order + 1) {
+      add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
+      for (j = node->order + 2; j < mpl; j++) {
+       add_requirement(new_tree->nodes[k + j - node->order - 1],
+                       new_tree->nodes[k + j - node->order - 2]);
+      }
+      for (j = node->order + 1; j < mpl; j++) {
+       new_tree->nodes[k + j - node->order - 1]->order = j;
+      }
+    }
+
+    /* copy all edges and create edges with dummy nodes */
+    for (j = 0; j < node->nprovide; j++) {
+      int provide_y = node->provide[j]->order;
+      if (provide_y == node->order + 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->order - 2]);
+      }
+    }
+
+    if (mpl > node->order + 1) {
+      k += mpl - node->order - 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]->order > num_layers) {
+      num_layers = tree->nodes[i]->order;
+    }
+  }
+  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]->order]++;
+    }
+
+    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->order][T[node->order]] = node;
+      node->layer = T[node->order];
+      T[node->order]++;
+    }
+  }
+}
+
+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]->layer;
+    }
+    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->layer = 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]->layer];
+    }
+    for (j = 0; j < node->nprovide; j++) {
+      for (k = 0; k < node->provide[j]->layer; k++) {
+       X[k]++;
+      }
+    }
+  }
+
+  return sum;
+}
+
+/*************************************************************************
+  Swap positions of two nodes on the same layer
+*************************************************************************/
+static void swap(struct techtree *tree, int layer, int layer1, int layer2)
+{
+  struct tree_node *node1 = tree->layers[layer][layer1];
+  struct tree_node *node2 = tree->layers[layer][layer2];
+
+  tree->layers[layer][layer1] = node2;
+  tree->layers[layer][layer2] = node1;
+  node1->layer = layer2;
+  node2->layer = layer1;
+}
+
+/*************************************************************************
+  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);
+  }
+
+  calculate_diagram_layout(tree2);
+
+  return tree2;
+}
+
+/****************************************************************************
+  Give the dimensions of the techtree.
+****************************************************************************/
+void get_techtree_dimensions(struct techtree *techtree,
+                            int *width, int *height)
+{
+  if (width) {
+    *width = techtree->diagram_width;
+  }
+  if (height){
+    *height = techtree->diagram_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;
+
+  /* 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 = node->node_x;
+      starty = node->node_y;
+      width = node->node_width;
+      height = node->node_height;
+
+      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 = node->node_x + node->node_width;
+      starty = node->node_y + node->node_height / 2;
+      for (k = 0; k < node->nprovide; k++) {
+       struct tree_node *dest_node = node->provide[k];
+
+       endx = dest_node->node_x;
+       endy = dest_node->node_y + dest_node->node_height / 2;
+
+       canvas_put_line(pcanvas, COLOR_STD_BLACK, LINE_NORMAL,
+                       startx, starty, endx - startx, endy - starty);
+      }
+    }
+  }
+}
+
+/****************************************************************************
+  Return the tech ID at the given position of the techtree (or A_NONE).
+****************************************************************************/
+Tech_Type_id get_tech_on_techtree(struct techtree *tree, int x, int y)
+{
+  int i;
+
+  for (i = 0; i < tree->num_nodes; i++) {
+    struct tree_node *node = tree->nodes[i];
+
+    if (node->is_dummy) {
+      continue;
+    }
+    if (node->node_x <= x && node->node_y <= y
+        && node->node_x + node->node_width > x
+       && node->node_y + node->node_height > y) {
+      return node->tech;
+    }
+  }
+  return A_NONE;
+}
+
+/****************************************************************************
+  Return the position of the given tech on the techtree.  Return TRUE iff
+  it was found.
+****************************************************************************/
+bool find_tech_on_techtree(struct techtree *tree, Tech_Type_id tech,
+                          int *x, int *y, int *w, int *h)
+{
+  int i;
+
+  for (i = 0; i < tree->num_nodes; i++) {
+    struct tree_node *node = tree->nodes[i];
+    if (!node->is_dummy && node->tech == tech) {
+      if (x) {
+       *x = node->node_x;
+      }
+      if (y) {
+       *y = node->node_y;
+      }
+      if (w) {
+       *w = node->node_width;
+      }
+      if (h) {
+       *h = node->node_height;
+      }
+      return TRUE;
+    }
+  }
+  return FALSE;
+}
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 17:07:00 -0000
@@ -0,0 +1,36 @@
+/********************************************************************** 
+   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);
+
+Tech_Type_id get_tech_on_techtree(struct techtree *techtree, int x, int y);
+bool find_tech_on_techtree(struct techtree *techtree, Tech_Type_id tech,
+                          int *x, int *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 17:07:00 -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 17:07:01 -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;
 
@@ -163,7 +160,100 @@
     gui_dialog_destroy(science_dialog_shell);
   }
 }
- 
+
+/****************************************************************************
+ Change tech goal, research or open help dialog
+****************************************************************************/
+static void button_release_event_callback(GtkWidget *widget,
+                                         GdkEventButton *event,
+                                          gpointer *data)
+{
+  struct techtree *tree = g_object_get_data(G_OBJECT(widget), "techtree");
+  int x = event->x, y = event->y;
+  Tech_Type_id tech = get_tech_on_techtree(tree, x, y);
+
+  if (tech == A_NONE) {
+    return;
+  }
+  if (event->button == 1) {
+    /* LMB: set research or research goal */
+    switch (get_invention(game.player_ptr, tech)) {
+    case TECH_REACHABLE:
+      dsend_packet_player_research(&aconnection, tech);
+      break;
+    case TECH_UNKNOWN:
+      dsend_packet_player_tech_goal(&aconnection, tech);
+      break;
+    case TECH_KNOWN:
+      break;
+    }
+  } else if (event->button == 3) {
+    /* RMB: get help */
+    /* FIXME: this should work for ctrl+LMB or shift+LMB (?) too */
+    popup_help_dialog_typed(get_tech_name(game.player_ptr, tech), HELP_TECH);
+  }
+}
+
+/****************************************************************************
+  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();
+  GtkAdjustment* adjustment;
+  int width, height;
+  int x;
+
+  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);
+  g_signal_connect(G_OBJECT(science_drawing_area), "button-release-event",
+                   G_CALLBACK(button_release_event_callback), NULL);
+  gtk_widget_add_events(science_drawing_area,
+                        GDK_BUTTON_RELEASE_MASK | GDK_BUTTON2_MOTION_MASK | 
+                       GDK_BUTTON3_MOTION_MASK);
+                        
+  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);
+
+  adjustment = gtk_scrolled_window_get_hadjustment(GTK_SCROLLED_WINDOW(sw));
+  
+  /* Center on currently researched node */
+  if (find_tech_on_techtree(techtree, game.player_ptr->research->researching,
+                           &x, NULL, NULL, NULL)) {
+    /* FIXME: this is just an approximation */
+    gtk_adjustment_set_value(adjustment, x - 100);
+  }
+
+  return sw;
+}
 
 /****************************************************************
 ...
@@ -171,7 +261,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 +317,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 +389,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 +422,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 +434,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 +447,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 +599,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 17:07:01 -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,

[Prev in Thread] Current Thread [Next in Thread]