client/reqtree.c

   1 /**********************************************************************
   2  Freeciv - Copyright (C) 2005-2007 - The Freeciv Project
   3    This program is free software; you can redistribute it and/or modify
   4    it under the terms of the GNU General Public License as published by
   5    the Free Software Foundation; either version 2, or (at your option)
   6    any later version.
   7
   8    This program is distributed in the hope that it will be useful,
   9    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11    GNU General Public License for more details.
  12 ***********************************************************************/
  13
  14 #ifdef HAVE_CONFIG_H
  15 #include <fc_config.h>
  16 #endif
  17
  18 #include <stdarg.h>
  19 #include <string.h>
  20
  21 /* utility */
  22 #include "log.h"
  23
  24 /* common */
  25 #include "government.h"
  26 #include "improvement.h"
  27 #include "research.h"
  28 #include "tech.h"
  29
  30 /* client */
  31 #include "client_main.h"
  32 #include "options.h"
  33 #include "tilespec.h"
  34 #include "reqtree.h"
  35
  36 #include "colors_g.h"
  37 #include "sprite_g.h"
  38
  39 /*
  40  * Hierarchical directed draph drawing for Freeciv's technology tree
  41  *
  42  *
  43  * \     Layer 0    /          \    Layer 1    /   \  Layer 2  /
  44  *  vvvvvvvvvvvvvvvv            vvvvvvvvvvvvvvv     vvvvvvvvvvv
  45  *
  46  * +-----------------+          +-------------+    +----------+
  47  * |    Alphabeth    |----------| Code of Laws|----| Monarchy |
  48  * +-----------------+          +-------------+   /+----------+
  49  *                                               /
  50  * +-----------------+             Dummy node  /
  51  * |Ceremonial Burial|-----------=============/
  52  * +-----------------+
  53  *
  54  * ^ node_y
  55  * |
  56  * |
  57  * |    node_x
  58  * +-------->
  59  */
  60
  61
  62
  63 /****************************************************************************
  64   This structure desribes a node in a technology tree diagram.
  65   A node can by dummy or real. Real node describes a technology.
  66 ****************************************************************************/
  67 struct tree_node {
  68   bool is_dummy;
  69   Tech_type_id tech;
  70
  71   /* Incoming edges */
  72   int nrequire;
  73   struct tree_node **require;
  74
  75   /* Outgoing edges */
  76   int nprovide;
  77   struct tree_node **provide;
  78
  79   /* logical position on the diagram */
  80   int order, layer;
  81
  82   /* Coordinates of the rectangle on the diagram in pixels */
  83   int node_x, node_y, node_width, node_height;
  84
  85   /* for general purpose */
  86   int number;
  87 };
  88
  89 /****************************************************************************
  90   Structure which describes abstract technology diagram.
  91   Nodes are ordered inside layers[] table.
  92 ****************************************************************************/
  93 struct reqtree {
  94   int num_nodes;
  95   struct tree_node **nodes;
  96
  97   int num_layers;
  98   /* size of each layer */
  99   int *layer_size;
 100   struct tree_node ***layers;
 101
 102   /* in pixels */
 103   int diagram_width, diagram_height;
 104 };
 105
 106
 107 /****************************************************************************
 108   Edge types for coloring the edges by type in the tree
 109 ****************************************************************************/
 110 enum reqtree_edge_type {
 111   REQTREE_EDGE = 0,     /* Normal, "unvisited" */
 112   REQTREE_READY_EDGE,
 113   REQTREE_KNOWN_EDGE,   /* Both nodes known, "visited" */
 114   REQTREE_ACTIVE_EDGE,
 115   REQTREE_GOAL_EDGE     /* Dest node is part of goal "future visited" */
 116 };
 117
 118 /*************************************************************************
 119   Add requirement edge to node and provide edge to req
 120 *************************************************************************/
 121 static void add_requirement(struct tree_node *node, struct tree_node *req)
 122 {
 123   fc_assert_ret(node != NULL);
 124   fc_assert_ret(req != NULL);
 125
 126   node->require =
 127       fc_realloc(node->require,
 128                  sizeof(*node->require) * (node->nrequire + 1));
 129   node->require[node->nrequire] = req;
 130   node->nrequire++;
 131
 132   req->provide =
 133       fc_realloc(req->provide,
 134                  sizeof(*req->provide) * (req->nprovide + 1));
 135   req->provide[req->nprovide] = node;
 136   req->nprovide++;
 137 }
 138
 139 /*************************************************************************
 140   Allocate and initialize new tree node
 141 *************************************************************************/
 142 static struct tree_node *new_tree_node(void)
 143 {
 144   struct tree_node *node = fc_malloc(sizeof(*node));
 145
 146   node->nrequire = 0;
 147   node->nprovide = 0;
 148   node->require = NULL;
 149   node->provide = NULL;
 150   node->order = -1;
 151   node->layer = -1;
 152   return node;
 153 }
 154
 155 /****************************************************************************
 156   Return minimum size of the rectangle in pixels on the diagram which
 157   corresponds to the given node
 158 ****************************************************************************/
 159 static void node_rectangle_minimum_size(struct tree_node *node,
 160                                         int *width, int *height)
 161 {
 162   int max_icon_height; /* maximal height of icons below the text */
 163   int icons_width_sum; /* sum of icons width plus space between them */
 164   struct sprite* sprite;
 165   int swidth, sheight;
 166
 167   if (node->is_dummy) {
 168     /* Dummy node is a straight line */
 169     *width = *height = 1;
 170   } else {
 171     get_text_size(width, height, FONT_REQTREE_TEXT,
 172                   research_advance_name_translation
 173                       (research_get(client_player()), node->tech));
 174     *width += 2;
 175     *height += 8;
 176
 177     max_icon_height = 0;
 178     icons_width_sum = 5;
 179
 180     if (gui_options.reqtree_show_icons) {
 181       /* units */
 182       unit_type_iterate(unit) {
 183         if (advance_number(unit->require_advance) != node->tech) {
 184           continue;
 185         }
 186         sprite = get_unittype_sprite(tileset, unit, direction8_invalid());
 187         get_sprite_dimensions(sprite, &swidth, &sheight);
 188         max_icon_height = MAX(max_icon_height, sheight);
 189         icons_width_sum += swidth + 2;
 190       } unit_type_iterate_end;
 191
 192       /* buildings */
 193       improvement_iterate(pimprove) {
 194         requirement_vector_iterate(&(pimprove->reqs), preq) {
 195           if (VUT_ADVANCE == preq->source.kind
 196            && advance_number(preq->source.value.advance) == node->tech) {
 197             sprite = get_building_sprite(tileset, pimprove);
 198             /* Improvement icons are not guaranteed to exist */
 199             if (sprite) {
 200               get_sprite_dimensions(sprite, &swidth, &sheight);
 201               max_icon_height = MAX(max_icon_height, sheight);
 202               icons_width_sum += swidth + 2;
 203             }
 204           }
 205         } requirement_vector_iterate_end;
 206       } improvement_iterate_end;
 207
 208       /* governments */
 209       governments_iterate(gov) {
 210         requirement_vector_iterate(&(gov->reqs), preq) {
 211           if (VUT_ADVANCE == preq->source.kind
 212            && advance_number(preq->source.value.advance) == node->tech) {
 213             sprite = get_government_sprite(tileset, gov);
 214             get_sprite_dimensions(sprite, &swidth, &sheight);
 215             max_icon_height = MAX(max_icon_height, sheight);
 216             icons_width_sum += swidth + 2;
 217           }
 218         } requirement_vector_iterate_end;
 219       } governments_iterate_end;
 220     }
 221
 222     *height += max_icon_height;
 223     if (*width < icons_width_sum) {
 224       *width = icons_width_sum;
 225     }
 226   }
 227 }
 228
 229 /****************************************************************************
 230   Move nodes up and down without changing order but making it more
 231   symetrical. Gravitate towards parents average position.
 232 ****************************************************************************/
 233 static void symmetrize(struct reqtree* tree)
 234 {
 235   int layer;
 236   int i, j;
 237
 238   for (layer = 0; layer < tree->num_layers; layer++) {
 239     for (i = 0; i < tree->layer_size[layer]; i++) {
 240       struct tree_node *node = tree->layers[layer][i];
 241       int v, node_y, node_height;
 242
 243       if (node->nrequire == 0) {
 244         continue;
 245       }
 246       v = 0;
 247       for (j = 0; j < node->nrequire; j++) {
 248         struct tree_node *node_require = node->require[j];
 249
 250         v += node_require->node_y + node_require->node_height / 2;
 251       }
 252       v /= node->nrequire;
 253       node_y = node->node_y;
 254       node_height = node->node_height;
 255       if (v < node_y + node_height / 2) {
 256         if (node_y <= 0) {
 257           continue;
 258         }
 259         if (i > 0) {
 260           struct tree_node *node_above = tree->layers[layer][i - 1];
 261
 262           if (node_above->node_y
 263               + node_above->node_height >= node_y - 11) {
 264             continue;
 265           }
 266         }
 267         node_y--;
 268       } else if (v > node_y + node_height / 2) {
 269         if (node_y + node_height >= tree->diagram_height - 1) {
 270           continue;
 271         }
 272         if (i < tree->layer_size[layer] - 1) {
 273           struct tree_node* node_below = tree->layers[layer][i + 1];
 274
 275           if (node_y + node_height >= node_below->node_y - 11) {
 276             continue;
 277           }
 278         }
 279         node_y++;
 280       }
 281       node->node_y = node_y;
 282     }
 283   }
 284 }
 285
 286 /****************************************************************************
 287   Calculate rectangles position and size from the tree.
 288   Logical order should already be calculated.
 289 ****************************************************************************/
 290 static void calculate_diagram_layout(struct reqtree *tree)
 291 {
 292   int i, layer, layer_offs;
 293
 294   /* calculate minimum size of rectangle for each node */
 295   for (i = 0; i < tree->num_nodes; i++) {
 296     struct tree_node *node = tree->nodes[i];
 297
 298     node_rectangle_minimum_size(tree->nodes[i],
 299                                 &node->node_width, &node->node_height);
 300     node->number = i;
 301   }
 302
 303   /* calculate height of the diagram. There should be at least 10 pixels
 304    * beetween any two nodes */
 305   tree->diagram_height = 0;
 306   for (layer = 0; layer < tree->num_layers; layer++) {
 307     int h_sum = 0;
 308
 309     for (i = 0; i < tree->layer_size[layer]; i++) {
 310       struct tree_node *node = tree->layers[layer][i];
 311
 312       h_sum += node->node_height;
 313       if (i < tree->layer_size[layer] - 1) {
 314         h_sum += 10;
 315       }
 316     }
 317     tree->diagram_height = MAX(tree->diagram_height, h_sum);
 318   }
 319
 320   /* calculate maximum width of node for each layer and enlarge other nodes
 321    * to match maximum width
 322    * calculate x offsets
 323    */
 324   layer_offs = 0;
 325   for (layer = 0; layer < tree->num_layers; layer++) {
 326     int max_width = 0;
 327
 328     for (i = 0; i < tree->layer_size[layer]; i++) {
 329       struct tree_node *node = tree->layers[layer][i];
 330
 331       max_width = MAX(max_width, node->node_width);
 332     }
 333
 334     for (i = 0; i < tree->layer_size[layer]; i++) {
 335       struct tree_node *node = tree->layers[layer][i];
 336
 337       node->node_width = max_width;
 338       node->node_x = layer_offs;
 339     }
 340
 341     /* space between layers should be proportional to their size */
 342     if (layer != tree->num_layers - 1)  {
 343       layer_offs += max_width * 5 / 4 + 80;
 344     } else {
 345       layer_offs += max_width + 10;
 346     }
 347   }
 348   tree->diagram_width = layer_offs;
 349
 350   /* Once we have x positions calculated we can
 351    * calculate y-position of nodes on the diagram
 352    * Distribute nodes steadily.
 353    */
 354   for (layer = 0; layer < tree->num_layers; layer++) {
 355     int y = 0;
 356     int h_sum = 0;
 357
 358     for (i = 0; i < tree->layer_size[layer]; i++) {
 359       struct tree_node *node = tree->layers[layer][i];
 360
 361       h_sum += node->node_height;
 362     }
 363     for (i = 0; i < tree->layer_size[layer]; i++) {
 364       struct tree_node *node = tree->layers[layer][i];
 365
 366       node->node_y = y;
 367       y += node->node_height;
 368       if (tree->layer_size[layer] > 1) {
 369         y += (tree->diagram_height - h_sum)
 370           / (tree->layer_size[layer] - 1) - 1;
 371       }
 372     }
 373   }
 374
 375   /* The symetrize() function moves node by one pixel per call */
 376   for (i = 0; i < tree->diagram_height; i++) {
 377     symmetrize(tree);
 378   }
 379 }
 380
 381
 382 /*************************************************************************
 383   Create a "dummy" tech tree from current ruleset.  This tree is then
 384   fleshed out further (see create_reqtree). This tree doesn't include
 385   dummy edges. Layering and ordering isn't done also.
 386
 387   If pplayer is given, add only techs reachable by that player to tree.
 388 *************************************************************************/
 389 static struct reqtree *create_dummy_reqtree(struct player *pplayer,
 390                                             bool show_all)
 391 {
 392   const struct research *presearch = research_get(pplayer);
 393   struct reqtree *tree = fc_malloc(sizeof(*tree));
 394   int j;
 395   struct tree_node *nodes[advance_count()];
 396
 397   nodes[A_NONE] = NULL;
 398   advance_index_iterate(A_FIRST, tech) {
 399     if (!valid_advance_by_number(tech)) {
 400       nodes[tech] = NULL;
 401       continue;
 402     }
 403     if (pplayer && !show_all
 404         && !research_invention_reachable(presearch, tech)) {
 405       /* Reqtree requested for particular player and this tech is
 406        * unreachable to him/her. */
 407       nodes[tech] = NULL;
 408       continue;
 409     }
 410     nodes[tech] = new_tree_node();
 411     nodes[tech]->is_dummy = FALSE;
 412     nodes[tech]->tech = tech;
 413   } advance_index_iterate_end;
 414
 415   advance_index_iterate(A_FIRST, tech) {
 416     struct advance *padvance = valid_advance_by_number(tech);
 417     Tech_type_id tech_one, tech_two;
 418
 419     if (!padvance) {
 420       continue;
 421     }
 422     if (nodes[tech] == NULL) {
 423       continue;
 424     }
 425
 426     tech_one = advance_required(tech, AR_ONE);
 427     tech_two = advance_required(tech, AR_TWO);
 428
 429     if (!show_all && A_NONE != tech_one
 430         && A_LAST != tech_two && A_NONE != tech_two
 431         && (nodes[tech_one] == NULL || nodes[tech_two] == NULL)) {
 432       /* Print only reachable techs. */
 433       continue;
 434     }
 435
 436     /* Formerly, we used to remove the redundant requirement nodes (the
 437      * technologies already included in the requirements of the other
 438      * requirement).  However, it doesn't look like a good idea, because
 439      * a player can steal any technology independently of the technology
 440      * tree. */
 441     if (A_NONE != tech_one && A_LAST != tech_two) {
 442       add_requirement(nodes[tech], nodes[tech_one]);
 443       if (A_NONE != tech_two) {
 444         add_requirement(nodes[tech], nodes[tech_two]);
 445       }
 446     }
 447   } advance_index_iterate_end;
 448
 449   /* Copy nodes from local array to dynamically allocated one.
 450    * Skip non-existing entries */
 451   tree->nodes = fc_calloc(advance_count(), sizeof(*tree->nodes));
 452   j = 0;
 453   advance_index_iterate(A_FIRST, tech) {
 454     if (nodes[tech]) {
 455       fc_assert_action(valid_advance_by_number(nodes[tech]->tech), continue);
 456       tree->nodes[j++] = nodes[tech];
 457     }
 458   } advance_index_iterate_end;
 459   tree->num_nodes = j;
 460   tree->layers = NULL;
 461
 462   return tree;
 463 }
 464
 465 /*************************************************************************
 466   Free all memory used by tech_tree struct
 467 *************************************************************************/
 468 void destroy_reqtree(struct reqtree *tree)
 469 {
 470   int i;
 471
 472   for (i = 0; i < tree->num_nodes; i++) {
 473     free(tree->nodes[i]->require);
 474     free(tree->nodes[i]->provide);
 475     free(tree->nodes[i]);
 476   }
 477   free(tree->nodes);
 478   if (tree->layers) {
 479     for (i = 0; i < tree->num_layers; i++) {
 480       free(tree->layers[i]);
 481     }
 482     if (tree->layer_size) {
 483       free(tree->layer_size);
 484     }
 485   }
 486   free(tree);
 487 }
 488
 489 /*************************************************************************
 490   Compute the longest path from this tree_node to the node with
 491   no requirements. Store the result in node->layer.
 492 *************************************************************************/
 493 static int longest_path(struct tree_node *node)
 494 {
 495   int max, i;
 496
 497   if (node->layer != -1) {
 498     return node->layer;
 499   }
 500   max = -1;
 501   for (i = 0; i < node->nrequire; i++) {
 502     max = MAX(max, longest_path(node->require[i]));
 503   }
 504   node->layer = max + 1;
 505   return node->layer;
 506 }
 507
 508 /*************************************************************************
 509   Compute longest_path for all nodes, thus prepare longest path layering
 510 *************************************************************************/
 511 static void longest_path_layering(struct reqtree *tree)
 512 {
 513   int i;
 514
 515   for (i = 0; i < tree->num_nodes; i++) {
 516     if (tree->nodes[i]) {
 517       longest_path(tree->nodes[i]);
 518     }
 519   }
 520 }
 521
 522 /*************************************************************************
 523   Find the largest value of layer amongst children of the given node
 524 *************************************************************************/
 525 static int max_provide_layer(struct tree_node *node)
 526 {
 527   int i;
 528   int max = node->layer;
 529
 530   for (i = 0; i < node->nprovide; i++) {
 531     if (node->provide[i]->layer > max) {
 532       max = node->provide[i]->layer;
 533     }
 534   }
 535   return max;
 536 }
 537
 538 /*************************************************************************
 539   Create new tree which has dummy nodes added. The source tree is
 540   completely copied, you can freely deallocate it.
 541 *************************************************************************/
 542 static struct reqtree *add_dummy_nodes(struct reqtree *tree)
 543 {
 544   struct reqtree *new_tree;
 545   int num_dummy_nodes = 0;
 546   int k, i, j;
 547
 548   /* Count dummy nodes to be added */
 549   for (i = 0; i < tree->num_nodes; i++) {
 550     int mpl;
 551
 552     if (tree->nodes[i] == NULL) {
 553       continue;
 554     }
 555     mpl = max_provide_layer(tree->nodes[i]);
 556     if (mpl > tree->nodes[i]->layer + 1) {
 557       num_dummy_nodes += mpl - tree->nodes[i]->layer - 1;
 558     }
 559   }
 560
 561   /* create new tree */
 562   new_tree = fc_malloc(sizeof(*new_tree));
 563   new_tree->nodes =
 564       fc_malloc(sizeof(new_tree->nodes) *
 565                 (tree->num_nodes + num_dummy_nodes));
 566   new_tree->num_nodes = tree->num_nodes + num_dummy_nodes;
 567
 568   /* copy normal nodes */
 569   for (i = 0; i < tree->num_nodes; i++) {
 570     new_tree->nodes[i] = new_tree_node();
 571     new_tree->nodes[i]->is_dummy = FALSE;
 572     new_tree->nodes[i]->tech = tree->nodes[i]->tech;
 573     new_tree->nodes[i]->layer = tree->nodes[i]->layer;
 574     tree->nodes[i]->number = i;
 575   }
 576
 577   /* allocate dummy nodes */
 578   for (i = 0; i < num_dummy_nodes; i++) {
 579     new_tree->nodes[i + tree->num_nodes] = new_tree_node();
 580     new_tree->nodes[i + tree->num_nodes]->is_dummy = TRUE;
 581   }
 582   /* k points to the first unused dummy node */
 583   k = tree->num_nodes;
 584
 585   for (i = 0; i < tree->num_nodes; i++) {
 586     struct tree_node *node = tree->nodes[i];
 587     int mpl;
 588
 589     fc_assert_action(!node->is_dummy, continue);
 590
 591     mpl = max_provide_layer(node);
 592
 593     /* if this node will have dummy as ancestors, connect them in a chain */
 594     if (mpl > node->layer + 1) {
 595       add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
 596       for (j = node->layer + 2; j < mpl; j++) {
 597         add_requirement(new_tree->nodes[k + j - node->layer - 1],
 598                         new_tree->nodes[k + j - node->layer - 2]);
 599       }
 600       for (j = node->layer + 1; j < mpl; j++) {
 601         new_tree->nodes[k + j - node->layer - 1]->layer = j;
 602       }
 603     }
 604
 605     /* copy all edges and create edges with dummy nodes */
 606     for (j = 0; j < node->nprovide; j++) {
 607       int provide_y = node->provide[j]->layer;
 608
 609       if (provide_y == node->layer + 1) {
 610         /* direct connection */
 611         add_requirement(new_tree->nodes[node->provide[j]->number],
 612                         new_tree->nodes[i]);
 613       } else {
 614         /* connection through dummy node */
 615         add_requirement(new_tree->nodes[node->provide[j]->number],
 616                         new_tree->nodes[k + provide_y - node->layer - 2]);
 617       }
 618     }
 619
 620     if (mpl > node->layer + 1) {
 621       k += mpl - node->layer - 1;
 622       fc_assert(k <= new_tree->num_nodes);
 623     }
 624   }
 625   new_tree->layers = NULL;
 626
 627   return new_tree;
 628 }
 629
 630 /*************************************************************************
 631   Calculate layers[] and layer_size[] fields of tree.
 632   There should be layer value calculated for each node.
 633   Nodes will be put into layers in no particular order.
 634 *************************************************************************/
 635 static void set_layers(struct reqtree *tree)
 636 {
 637   int i;
 638   int num_layers = 0;
 639
 640   /* count total number of layers */
 641   for (i = 0; i < tree->num_nodes; i++) {
 642     num_layers = MAX(num_layers, tree->nodes[i]->layer);
 643   }
 644   num_layers++;
 645   tree->num_layers = num_layers;
 646
 647   {
 648     /* Counters for order - order number for the next node in the layer */
 649     int T[num_layers];
 650
 651     tree->layers = fc_malloc(sizeof(*tree->layers) * num_layers);
 652     tree->layer_size = fc_malloc(sizeof(*tree->layer_size) * num_layers);
 653     for (i = 0; i < num_layers; i++) {
 654       T[i] = 0;
 655       tree->layer_size[i] = 0;
 656     }
 657     for (i = 0; i < tree->num_nodes; i++) {
 658       tree->layer_size[tree->nodes[i]->layer]++;
 659     }
 660
 661     for (i = 0; i < num_layers; i++) {
 662       tree->layers[i] =
 663           fc_malloc(sizeof(*tree->layers[i]) * tree->layer_size[i]);
 664     }
 665     for (i = 0; i < tree->num_nodes; i++) {
 666       struct tree_node *node = tree->nodes[i];
 667
 668       tree->layers[node->layer][T[node->layer]] = node;
 669       node->order = T[node->layer];
 670       T[node->layer]++;
 671     }
 672   }
 673 }
 674
 675 struct node_and_float {
 676   struct tree_node *node;
 677   float value;
 678 };
 679
 680 /*************************************************************************
 681   Comparison function used by barycentric_sort.
 682 *************************************************************************/
 683 static int cmp_func(const void *_a, const void *_b)
 684 {
 685   const struct node_and_float *a = _a, *b = _b;
 686
 687   if (a->value > b->value) {
 688     return 1;
 689   }
 690   if (a->value < b->value) {
 691     return -1;
 692   }
 693   return 0;
 694 }
 695
 696 /*************************************************************************
 697   Simple heuristic: Sort nodes on the given layer by the average x-value
 698   of its' parents.
 699 *************************************************************************/
 700 static void barycentric_sort(struct reqtree *tree, int layer)
 701 {
 702   struct node_and_float T[tree->layer_size[layer]];
 703   int i, j;
 704   float v;
 705
 706   for (i = 0; i < tree->layer_size[layer]; i++) {
 707     struct tree_node *node = tree->layers[layer][i];
 708
 709     T[i].node = node;
 710     v = 0.0;
 711     for (j = 0; j < node->nrequire; j++) {
 712       v += node->require[j]->order;
 713     }
 714     if (node->nrequire > 0) {
 715       v /= (float) node->nrequire;
 716     }
 717     T[i].value = v;
 718   }
 719   qsort(T, tree->layer_size[layer], sizeof(*T),
 720         cmp_func);
 721
 722   for (i = 0; i < tree->layer_size[layer]; i++) {
 723     tree->layers[layer][i] = T[i].node;
 724     T[i].node->order = i;
 725   }
 726 }
 727
 728 /*************************************************************************
 729   Calculate number of edge crossings beetwen layer and layer+1
 730 *************************************************************************/
 731 static int count_crossings(struct reqtree *tree, int layer)
 732 {
 733   int layer1_size = tree->layer_size[layer];
 734   int layer2_size = tree->layer_size[layer + 1];
 735   int X[layer2_size];
 736   int i, j, k;
 737   int sum = 0;
 738
 739   for (i = 0; i < layer2_size; i++) {
 740     X[i] = 0;
 741   }
 742
 743   for (i = 0; i < layer1_size; i++) {
 744     struct tree_node *node = tree->layers[layer][i];
 745
 746     for (j = 0; j < node->nprovide; j++) {
 747       sum += X[node->provide[j]->order];
 748     }
 749     for (j = 0; j < node->nprovide; j++) {
 750       for (k = 0; k < node->provide[j]->order; k++) {
 751         X[k]++;
 752       }
 753     }
 754   }
 755
 756   return sum;
 757 }
 758
 759 /*************************************************************************
 760   Swap positions of two nodes on the same layer
 761 *************************************************************************/
 762 static void swap(struct reqtree *tree, int layer, int order1, int order2)
 763 {
 764   struct tree_node *node1 = tree->layers[layer][order1];
 765   struct tree_node *node2 = tree->layers[layer][order2];
 766
 767   tree->layers[layer][order1] = node2;
 768   tree->layers[layer][order2] = node1;
 769   node1->order = order2;
 770   node2->order = order1;
 771 }
 772
 773 /*************************************************************************
 774   Try to reduce the number of crossings by swapping two nodes and checking
 775   if it improves the situation.
 776 *************************************************************************/
 777 static void improve(struct reqtree *tree)
 778 {
 779   int crossings[tree->num_layers - 1];
 780   int i, x1, x2, layer;
 781
 782   for (i = 0; i < tree->num_layers - 1; i++) {
 783     crossings[i] = count_crossings(tree, i);
 784   }
 785
 786   for (layer = 0; layer < tree->num_layers; layer++) {
 787     int layer_size = tree->layer_size[layer];
 788     int layer_sum = 0;
 789
 790     if (layer > 0) {
 791       layer_sum += crossings[layer - 1];
 792     }
 793     if (layer < tree->num_layers - 1) {
 794       layer_sum += crossings[layer];
 795     }
 796
 797     for (x1 = 0; x1 < layer_size; x1++) {
 798       for (x2 = x1 + 1; x2 < layer_size; x2++) {
 799         int new_crossings = 0;
 800         int new_crossings_before = 0;
 801
 802         swap(tree, layer, x1, x2);
 803         if (layer > 0) {
 804           new_crossings_before += count_crossings(tree, layer - 1);
 805         }
 806         if (layer < tree->num_layers - 1) {
 807           new_crossings += count_crossings(tree, layer);
 808         }
 809         if (new_crossings + new_crossings_before > layer_sum) {
 810           swap(tree, layer, x1, x2);
 811         } else {
 812           layer_sum = new_crossings + new_crossings_before;
 813           if (layer > 0) {
 814             crossings[layer - 1] = new_crossings_before;
 815           }
 816           if (layer < tree->num_layers - 1) {
 817             crossings[layer] = new_crossings;
 818           }
 819         }
 820       }
 821     }
 822   }
 823 }
 824
 825 /*************************************************************************
 826   Generate optimized tech_tree from current ruleset.
 827   You should free it by destroy_reqtree.
 828
 829   If pplayer is not NULL, techs unreachable to that player are not shown.
 830 *************************************************************************/
 831 struct reqtree *create_reqtree(struct player *pplayer, bool show_all)
 832 {
 833   struct reqtree *tree1, *tree2;
 834   int i, j;
 835
 836   tree1 = create_dummy_reqtree(pplayer, show_all);
 837   longest_path_layering(tree1);
 838   tree2 = add_dummy_nodes(tree1);
 839   destroy_reqtree(tree1);
 840   set_layers(tree2);
 841
 842   /* It's good heuristics for beginning */
 843   for (j = 0; j < 20; j++) {
 844     for (i = 0; i < tree2->num_layers; i++) {
 845       barycentric_sort(tree2, i);
 846     }
 847   }
 848
 849   /* Now burn some CPU */
 850   for (j = 0; j < 20; j++) {
 851     improve(tree2);
 852   }
 853
 854   calculate_diagram_layout(tree2);
 855
 856   return tree2;
 857 }
 858
 859 /****************************************************************************
 860   Give the dimensions of the reqtree.
 861 ****************************************************************************/
 862 void get_reqtree_dimensions(struct reqtree *reqtree,
 863                             int *width, int *height)
 864 {
 865   if (width) {
 866     *width = reqtree->diagram_width;
 867   }
 868   if (height){
 869     *height = reqtree->diagram_height;
 870   }
 871 }
 872
 873 /****************************************************************************
 874   Return a background color of node's rectangle
 875 ****************************************************************************/
 876 static enum color_std node_color(struct tree_node *node)
 877 {
 878   if (!node->is_dummy) {
 879     struct research *research = research_get(client_player());
 880
 881     if (!research) {
 882       return COLOR_REQTREE_KNOWN;
 883     }
 884
 885     if (!research_invention_reachable(research, node->tech)) {
 886       return COLOR_REQTREE_UNREACHABLE;
 887     }
 888
 889     if (!research_invention_gettable(research, node->tech, TRUE)) {
 890       if (research_goal_tech_req(research, research->tech_goal, node->tech)
 891           || node->tech == research->tech_goal) {
 892         return COLOR_REQTREE_GOAL_NOT_GETTABLE;
 893       } else {
 894         return COLOR_REQTREE_NOT_GETTABLE;
 895       }
 896     }
 897
 898     if (research->researching == node->tech) {
 899       return COLOR_REQTREE_RESEARCHING;
 900     }
 901
 902     if (TECH_KNOWN == research_invention_state(research, node->tech)) {
 903       return COLOR_REQTREE_KNOWN;
 904     }
 905
 906     if (research_goal_tech_req(research, research->tech_goal, node->tech)
 907         || node->tech == research->tech_goal) {
 908       if (TECH_PREREQS_KNOWN == research_invention_state(research,
 909                                                          node->tech)) {
 910         return COLOR_REQTREE_GOAL_PREREQS_KNOWN;
 911       } else {
 912         return COLOR_REQTREE_GOAL_UNKNOWN;
 913       }
 914     }
 915
 916     if (TECH_PREREQS_KNOWN == research_invention_state(research,
 917                                                        node->tech)) {
 918       return COLOR_REQTREE_PREREQS_KNOWN;
 919     }
 920
 921     return COLOR_REQTREE_UNKNOWN;
 922   } else {
 923     return COLOR_REQTREE_BACKGROUND;
 924   }
 925
 926 }
 927
 928
 929 /****************************************************************************
 930   Return the type for an edge between two nodes
 931   if node is a dummy, dest_node can be NULL
 932 ****************************************************************************/
 933 static enum reqtree_edge_type get_edge_type(struct tree_node *node,
 934                                             struct tree_node *dest_node)
 935 {
 936   struct research *research = research_get(client_player());
 937
 938   if (dest_node == NULL) {
 939     /* assume node is a dummy */
 940     dest_node = node;
 941   }
 942
 943   /* find the required tech */
 944   while (node->is_dummy) {
 945     fc_assert(node->nrequire == 1);
 946     node = node->require[0];
 947   }
 948
 949   /* find destination advance by recursing in dest_node->provide[]
 950    * watch out: recursion */
 951   if (dest_node->is_dummy) {
 952     enum reqtree_edge_type sum_type = REQTREE_EDGE;
 953     int i;
 954
 955     fc_assert(dest_node->nprovide > 0);
 956     for (i = 0; i < dest_node->nprovide; ++i) {
 957       enum reqtree_edge_type type = get_edge_type(node, dest_node->provide[i]);
 958       switch (type) {
 959       case REQTREE_ACTIVE_EDGE:
 960       case REQTREE_GOAL_EDGE:
 961         return type;
 962       case REQTREE_KNOWN_EDGE:
 963       case REQTREE_READY_EDGE:
 964         sum_type = type;
 965         break;
 966       default:
 967         /* no change */
 968         break;
 969       };
 970     }
 971     return sum_type;
 972   }
 973
 974   if (!research) {
 975     /* Global observer case */
 976     return REQTREE_KNOWN_EDGE;
 977   }
 978
 979   if (research->researching == dest_node->tech) {
 980     return REQTREE_ACTIVE_EDGE;
 981   }
 982
 983   if (research_goal_tech_req(research, research->tech_goal, dest_node->tech)
 984       || dest_node->tech == research->tech_goal) {
 985     return REQTREE_GOAL_EDGE;
 986   }
 987
 988   if (TECH_KNOWN == research_invention_state(research, node->tech)) {
 989     if (TECH_KNOWN == research_invention_state(research, dest_node->tech)) {
 990       return REQTREE_KNOWN_EDGE;
 991     } else {
 992       return REQTREE_READY_EDGE;
 993     }
 994   }
 995
 996   return REQTREE_EDGE;
 997 }
 998
 999 /****************************************************************************
1000   Return a stroke color for an edge between two nodes
1001   if node is a dummy, dest_node can be NULL
1002 ****************************************************************************/
1003 static enum color_std edge_color(struct tree_node *node,
1004                                  struct tree_node *dest_node)
1005 {
1006   enum reqtree_edge_type type = get_edge_type(node, dest_node);
1007   switch (type) {
1008   case REQTREE_ACTIVE_EDGE:
1009     return COLOR_REQTREE_RESEARCHING;
1010   case REQTREE_GOAL_EDGE:
1011     return COLOR_REQTREE_GOAL_UNKNOWN;
1012   case REQTREE_KNOWN_EDGE:
1013     /* using "text" black instead of "known" white/ground/green */
1014     return COLOR_REQTREE_TEXT;
1015   case REQTREE_READY_EDGE:
1016     return COLOR_REQTREE_PREREQS_KNOWN;
1017   default:
1018     return COLOR_REQTREE_EDGE;
1019   };
1020 }
1021
1022 /****************************************************************************
1023   Draw the reqtree diagram!
1024
1025   This draws the given portion of the reqtree diagram (given by
1026   (tt_x,tt_y) and (w,h) onto the canvas at position (canvas_x, canvas_y).
1027 ****************************************************************************/
1028 void draw_reqtree(struct reqtree *tree, struct canvas *pcanvas,
1029                   int canvas_x, int canvas_y,
1030                   int tt_x, int tt_y, int w, int h)
1031 {
1032   int i, j, k;
1033   int swidth, sheight;
1034   struct sprite* sprite;
1035   struct color *color;
1036
1037   /* draw the diagram */
1038   for (i = 0; i < tree->num_layers; i++) {
1039     for (j = 0; j < tree->layer_size[i]; j++) {
1040       struct tree_node *node = tree->layers[i][j];
1041       int startx, starty, endx, endy, width, height;
1042
1043       startx = node->node_x;
1044       starty = node->node_y;
1045       width = node->node_width;
1046       height = node->node_height;
1047
1048       if (node->is_dummy) {
1049         /* Use the same layout as lines for dummy nodes */
1050         canvas_put_line(pcanvas,
1051                         get_color(tileset, edge_color(node, NULL)),
1052                         LINE_GOTO,
1053                         startx, starty, width, 0);
1054       } else {
1055         const char *text = research_advance_name_translation
1056                                (research_get(client_player()), node->tech);
1057         int text_w, text_h;
1058         int icon_startx;
1059
1060         canvas_put_rectangle(pcanvas,
1061                              get_color(tileset, COLOR_REQTREE_BACKGROUND),
1062                              startx, starty, width, height);
1063
1064         /* Print color rectangle with text inside. */
1065         canvas_put_rectangle(pcanvas, get_color(tileset, node_color(node)),
1066                              startx + 1, starty + 1,
1067                              width - 2, height - 2);
1068         /* The following code is similar to the one in
1069          * node_rectangle_minimum_size(). If you change something here,
1070          * change also node_rectangle_minimum_size().
1071          */
1072
1073         get_text_size(&text_w, &text_h, FONT_REQTREE_TEXT, text);
1074
1075         canvas_put_text(pcanvas,
1076                         startx + (width - text_w) / 2,
1077                         starty + 4,
1078                         FONT_REQTREE_TEXT,
1079                         get_color(tileset, COLOR_REQTREE_TEXT),
1080                         text);
1081         icon_startx = startx + 5;
1082
1083         if (gui_options.reqtree_show_icons) {
1084           unit_type_iterate(unit) {
1085             if (advance_number(unit->require_advance) != node->tech) {
1086               continue;
1087             }
1088             sprite = get_unittype_sprite(tileset, unit, direction8_invalid());
1089             get_sprite_dimensions(sprite, &swidth, &sheight);
1090             canvas_put_sprite_full(pcanvas,
1091                                    icon_startx,
1092                                    starty + text_h + 4
1093                                    + (height - text_h - 4 - sheight) / 2,
1094                                    sprite);
1095             icon_startx += swidth + 2;
1096           } unit_type_iterate_end;
1097
1098           improvement_iterate(pimprove) {
1099             requirement_vector_iterate(&(pimprove->reqs), preq) {
1100               if (VUT_ADVANCE == preq->source.kind
1101                && advance_number(preq->source.value.advance) == node->tech) {
1102                 sprite = get_building_sprite(tileset, pimprove);
1103                 /* Improvement icons are not guaranteed to exist */
1104                 if (sprite) {
1105                   get_sprite_dimensions(sprite, &swidth, &sheight);
1106                   canvas_put_sprite_full(pcanvas,
1107                                          icon_startx,
1108                                          starty + text_h + 4
1109                                          + (height - text_h - 4 - sheight) / 2,
1110                                          sprite);
1111                   icon_startx += swidth + 2;
1112                 }
1113               }
1114             } requirement_vector_iterate_end;
1115           } improvement_iterate_end;
1116
1117           governments_iterate(gov) {
1118             requirement_vector_iterate(&(gov->reqs), preq) {
1119               if (VUT_ADVANCE == preq->source.kind
1120                && advance_number(preq->source.value.advance) == node->tech) {
1121                 sprite = get_government_sprite(tileset, gov);
1122                 get_sprite_dimensions(sprite, &swidth, &sheight);
1123                 canvas_put_sprite_full(pcanvas,
1124                                        icon_startx,
1125                                        starty + text_h + 4
1126                                        + (height - text_h - 4 - sheight) / 2,
1127                                        sprite);
1128                 icon_startx += swidth + 2;
1129               }
1130             } requirement_vector_iterate_end;
1131           } governments_iterate_end;
1132         }
1133       }
1134
1135       /* Draw all outgoing edges */
1136       startx = node->node_x + node->node_width;
1137       starty = node->node_y + node->node_height / 2;
1138       for (k = 0; k < node->nprovide; k++) {
1139         struct tree_node *dest_node = node->provide[k];
1140         color = get_color(tileset, edge_color(node, dest_node));
1141
1142         endx = dest_node->node_x;
1143         endy = dest_node->node_y + dest_node->node_height / 2;
1144
1145         if (gui_options.reqtree_curved_lines) {
1146           canvas_put_curved_line(pcanvas, color, LINE_GOTO,
1147                                  startx, starty, endx - startx,
1148                                  endy - starty);
1149         } else {
1150           canvas_put_line(pcanvas, color, LINE_GOTO,
1151                           startx, starty, endx - startx,
1152                           endy - starty);
1153         }
1154       }
1155     }
1156   }
1157 }
1158
1159 /****************************************************************************
1160   Return the tech ID at the given position of the reqtree (or A_NONE).
1161 ****************************************************************************/
1162 Tech_type_id get_tech_on_reqtree(struct reqtree *tree, int x, int y)
1163 {
1164   int i;
1165
1166   for (i = 0; i < tree->num_nodes; i++) {
1167     struct tree_node *node = tree->nodes[i];
1168
1169     if (node->is_dummy) {
1170       continue;
1171     }
1172     if (node->node_x <= x && node->node_y <= y
1173         && node->node_x + node->node_width > x
1174         && node->node_y + node->node_height > y) {
1175       return node->tech;
1176     }
1177   }
1178   return A_NONE;
1179 }
1180
1181 /****************************************************************************
1182   Return the position of the given tech on the reqtree.  Return TRUE iff
1183   it was found.
1184 ****************************************************************************/
1185 bool find_tech_on_reqtree(struct reqtree *tree, Tech_type_id tech,
1186                           int *x, int *y, int *w, int *h)
1187 {
1188   int i;
1189
1190   for (i = 0; i < tree->num_nodes; i++) {
1191     struct tree_node *node = tree->nodes[i];
1192
1193     if (!node->is_dummy && node->tech == tech) {
1194       if (x) {
1195         *x = node->node_x;
1196       }
1197       if (y) {
1198         *y = node->node_y;
1199       }
1200       if (w) {
1201         *w = node->node_width;
1202       }
1203       if (h) {
1204         *h = node->node_height;
1205       }
1206       return TRUE;
1207     }
1208   }
1209   return FALSE;
1210 }