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