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                   advance_name_for_player(client.conn.playing, node->tech));
 173     *width += 2;
 174     *height += 8;
 175
 176     max_icon_height = 0;
 177     icons_width_sum = 5;
 178
 179     if (reqtree_show_icons) {
 180       /* units */
 181       unit_type_iterate(unit) {
 182         if (advance_number(unit->require_advance) != node->tech) {
 183           continue;
 184         }
 185         sprite = get_unittype_sprite(tileset, unit, direction8_invalid(),
 186                                      TRUE);
 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 reachable)
 391 {
 392   struct reqtree *tree = fc_malloc(sizeof(*tree));
 393   int j;
 394   struct tree_node *nodes[advance_count()];
 395
 396   nodes[A_NONE] = NULL;
 397   advance_index_iterate(A_FIRST, tech) {
 398     if (!valid_advance_by_number(tech)) {
 399       nodes[tech] = NULL;
 400       continue;
 401     }
 402     if (pplayer && reachable && !player_invention_reachable(pplayer, tech, TRUE)) {
 403       /* Reqtree requested for particular player and this tech is
 404        * unreachable to him/her. */
 405       nodes[tech] = NULL;
 406       continue;
 407     }
 408     nodes[tech] = new_tree_node();
 409     nodes[tech]->is_dummy = FALSE;
 410     nodes[tech]->tech = tech;
 411   } advance_index_iterate_end;
 412
 413   advance_index_iterate(A_FIRST, tech) {
 414     struct advance *padvance = valid_advance_by_number(tech);
 415     Tech_type_id tech_one, tech_two;
 416
 417     if (!padvance) {
 418       continue;
 419     }
 420     if (nodes[tech] == NULL) {
 421       continue;
 422     }
 423
 424     tech_one = advance_required(tech, AR_ONE);
 425     tech_two = advance_required(tech, AR_TWO);
 426
 427     if (reachable && A_NONE != tech_one
 428         && A_LAST != tech_two && A_NONE != tech_two
 429         && (nodes[tech_one] == NULL || nodes[tech_two] == NULL)) {
 430       /* Print only reachable techs. */
 431       continue;
 432     }
 433
 434     /* Formerly, we used to remove the redundant requirement nodes (the
 435      * technologies already included in the requirements of the other
 436      * requirement).  However, it doesn't look like a good idea, because
 437      * a player can steal any technology independently of the technology
 438      * tree. */
 439     if (A_NONE != tech_one && A_LAST != tech_two) {
 440       add_requirement(nodes[tech], nodes[tech_one]);
 441       if (A_NONE != tech_two) {
 442         add_requirement(nodes[tech], nodes[tech_two]);
 443       }
 444     }
 445   } advance_index_iterate_end;
 446
 447   /* Copy nodes from local array to dynamically allocated one.
 448    * Skip non-existing entries */
 449   tree->nodes = fc_calloc(advance_count(), sizeof(*tree->nodes));
 450   j = 0;
 451   advance_index_iterate(A_FIRST, tech) {
 452     if (nodes[tech]) {
 453       fc_assert_action(valid_advance_by_number(nodes[tech]->tech), continue);
 454       tree->nodes[j++] = nodes[tech];
 455     }
 456   } advance_index_iterate_end;
 457   tree->num_nodes = j;
 458   tree->layers = NULL;
 459
 460   return tree;
 461 }
 462
 463 /*************************************************************************
 464   Free all memory used by tech_tree struct
 465 *************************************************************************/
 466 void destroy_reqtree(struct reqtree *tree)
 467 {
 468   int i;
 469
 470   for (i = 0; i < tree->num_nodes; i++) {
 471     free(tree->nodes[i]->require);
 472     free(tree->nodes[i]->provide);
 473     free(tree->nodes[i]);
 474   }
 475   free(tree->nodes);
 476   if (tree->layers) {
 477     for (i = 0; i < tree->num_layers; i++) {
 478       free(tree->layers[i]);
 479     }
 480     if (tree->layer_size) {
 481       free(tree->layer_size);
 482     }
 483   }
 484   free(tree);
 485 }
 486
 487 /*************************************************************************
 488   Compute the longest path from this tree_node to the node with
 489   no requirements. Store the result in node->layer.
 490 *************************************************************************/
 491 static int longest_path(struct tree_node *node)
 492 {
 493   int max, i;
 494
 495   if (node->layer != -1) {
 496     return node->layer;
 497   }
 498   max = -1;
 499   for (i = 0; i < node->nrequire; i++) {
 500     max = MAX(max, longest_path(node->require[i]));
 501   }
 502   node->layer = max + 1;
 503   return node->layer;
 504 }
 505
 506 /*************************************************************************
 507   Compute longest_path for all nodes, thus prepare longest path layering
 508 *************************************************************************/
 509 static void longest_path_layering(struct reqtree *tree)
 510 {
 511   int i;
 512
 513   for (i = 0; i < tree->num_nodes; i++) {
 514     if (tree->nodes[i]) {
 515       longest_path(tree->nodes[i]);
 516     }
 517   }
 518 }
 519
 520 /*************************************************************************
 521   Find the largest value of layer amongst children of the given node
 522 *************************************************************************/
 523 static int max_provide_layer(struct tree_node *node)
 524 {
 525   int i;
 526   int max = node->layer;
 527
 528   for (i = 0; i < node->nprovide; i++) {
 529     if (node->provide[i]->layer > max) {
 530       max = node->provide[i]->layer;
 531     }
 532   }
 533   return max;
 534 }
 535
 536 /*************************************************************************
 537   Create new tree which has dummy nodes added. The source tree is
 538   completely copied, you can freely deallocate it.
 539 *************************************************************************/
 540 static struct reqtree *add_dummy_nodes(struct reqtree *tree)
 541 {
 542   struct reqtree *new_tree;
 543   int num_dummy_nodes = 0;
 544   int k, i, j;
 545
 546   /* Count dummy nodes to be added */
 547   for (i = 0; i < tree->num_nodes; i++) {
 548     int mpl;
 549
 550     if (tree->nodes[i] == NULL) {
 551       continue;
 552     }
 553     mpl = max_provide_layer(tree->nodes[i]);
 554     if (mpl > tree->nodes[i]->layer + 1) {
 555       num_dummy_nodes += mpl - tree->nodes[i]->layer - 1;
 556     }
 557   }
 558
 559   /* create new tree */
 560   new_tree = fc_malloc(sizeof(*new_tree));
 561   new_tree->nodes =
 562       fc_malloc(sizeof(new_tree->nodes) *
 563                 (tree->num_nodes + num_dummy_nodes));
 564   new_tree->num_nodes = tree->num_nodes + num_dummy_nodes;
 565
 566   /* copy normal nodes */
 567   for (i = 0; i < tree->num_nodes; i++) {
 568     new_tree->nodes[i] = new_tree_node();
 569     new_tree->nodes[i]->is_dummy = FALSE;
 570     new_tree->nodes[i]->tech = tree->nodes[i]->tech;
 571     new_tree->nodes[i]->layer = tree->nodes[i]->layer;
 572     tree->nodes[i]->number = i;
 573   }
 574
 575   /* allocate dummy nodes */
 576   for (i = 0; i < num_dummy_nodes; i++) {
 577     new_tree->nodes[i + tree->num_nodes] = new_tree_node();
 578     new_tree->nodes[i + tree->num_nodes]->is_dummy = TRUE;
 579   }
 580   /* k points to the first unused dummy node */
 581   k = tree->num_nodes;
 582
 583   for (i = 0; i < tree->num_nodes; i++) {
 584     struct tree_node *node = tree->nodes[i];
 585     int mpl;
 586
 587     fc_assert_action(!node->is_dummy, continue);
 588
 589     mpl = max_provide_layer(node);
 590
 591     /* if this node will have dummy as ancestors, connect them in a chain */
 592     if (mpl > node->layer + 1) {
 593       add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
 594       for (j = node->layer + 2; j < mpl; j++) {
 595         add_requirement(new_tree->nodes[k + j - node->layer - 1],
 596                         new_tree->nodes[k + j - node->layer - 2]);
 597       }
 598       for (j = node->layer + 1; j < mpl; j++) {
 599         new_tree->nodes[k + j - node->layer - 1]->layer = j;
 600       }
 601     }
 602
 603     /* copy all edges and create edges with dummy nodes */
 604     for (j = 0; j < node->nprovide; j++) {
 605       int provide_y = node->provide[j]->layer;
 606
 607       if (provide_y == node->layer + 1) {
 608         /* direct connection */
 609         add_requirement(new_tree->nodes[node->provide[j]->number],
 610                         new_tree->nodes[i]);
 611       } else {
 612         /* connection through dummy node */
 613         add_requirement(new_tree->nodes[node->provide[j]->number],
 614                         new_tree->nodes[k + provide_y - node->layer - 2]);
 615       }
 616     }
 617
 618     if (mpl > node->layer + 1) {
 619       k += mpl - node->layer - 1;
 620       fc_assert(k <= new_tree->num_nodes);
 621     }
 622   }
 623   new_tree->layers = NULL;
 624
 625   return new_tree;
 626 }
 627
 628 /*************************************************************************
 629   Calculate layers[] and layer_size[] fields of tree.
 630   There should be layer value calculated for each node.
 631   Nodes will be put into layers in no particular order.
 632 *************************************************************************/
 633 static void set_layers(struct reqtree *tree)
 634 {
 635   int i;
 636   int num_layers = 0;
 637
 638   /* count total number of layers */
 639   for (i = 0; i < tree->num_nodes; i++) {
 640     num_layers = MAX(num_layers, tree->nodes[i]->layer);
 641   }
 642   num_layers++;
 643   tree->num_layers = num_layers;
 644
 645   {
 646     /* Counters for order - order number for the next node in the layer */
 647     int T[num_layers];
 648
 649     tree->layers = fc_malloc(sizeof(*tree->layers) * num_layers);
 650     tree->layer_size = fc_malloc(sizeof(*tree->layer_size) * num_layers);
 651     for (i = 0; i < num_layers; i++) {
 652       T[i] = 0;
 653       tree->layer_size[i] = 0;
 654     }
 655     for (i = 0; i < tree->num_nodes; i++) {
 656       tree->layer_size[tree->nodes[i]->layer]++;
 657     }
 658
 659     for (i = 0; i < num_layers; i++) {
 660       tree->layers[i] =
 661           fc_malloc(sizeof(*tree->layers[i]) * tree->layer_size[i]);
 662     }
 663     for (i = 0; i < tree->num_nodes; i++) {
 664       struct tree_node *node = tree->nodes[i];
 665
 666       tree->layers[node->layer][T[node->layer]] = node;
 667       node->order = T[node->layer];
 668       T[node->layer]++;
 669     }
 670   }
 671 }
 672
 673 struct node_and_float {
 674   struct tree_node *node;
 675   float value;
 676 };
 677
 678 /*************************************************************************
 679   Comparison function used by barycentric_sort.
 680 *************************************************************************/
 681 static int cmp_func(const void *_a, const void *_b)
 682 {
 683   const struct node_and_float *a = _a, *b = _b;
 684
 685   if (a->value > b->value) {
 686     return 1;
 687   }
 688   if (a->value < b->value) {
 689     return -1;
 690   }
 691   return 0;
 692 }
 693
 694 /*************************************************************************
 695   Simple heuristic: Sort nodes on the given layer by the average x-value
 696   of its' parents.
 697 *************************************************************************/
 698 static void barycentric_sort(struct reqtree *tree, int layer)
 699 {
 700   struct node_and_float T[tree->layer_size[layer]];
 701   int i, j;
 702   float v;
 703
 704   for (i = 0; i < tree->layer_size[layer]; i++) {
 705     struct tree_node *node = tree->layers[layer][i];
 706
 707     T[i].node = node;
 708     v = 0.0;
 709     for (j = 0; j < node->nrequire; j++) {
 710       v += node->require[j]->order;
 711     }
 712     if (node->nrequire > 0) {
 713       v /= (float) node->nrequire;
 714     }
 715     T[i].value = v;
 716   }
 717   qsort(T, tree->layer_size[layer], sizeof(*T),
 718         cmp_func);
 719
 720   for (i = 0; i < tree->layer_size[layer]; i++) {
 721     tree->layers[layer][i] = T[i].node;
 722     T[i].node->order = i;
 723   }
 724 }
 725
 726 /*************************************************************************
 727   Calculate number of edge crossings beetwen layer and layer+1
 728 *************************************************************************/
 729 static int count_crossings(struct reqtree *tree, int layer)
 730 {
 731   int layer1_size = tree->layer_size[layer];
 732   int layer2_size = tree->layer_size[layer + 1];
 733   int X[layer2_size];
 734   int i, j, k;
 735   int sum = 0;
 736
 737   for (i = 0; i < layer2_size; i++) {
 738     X[i] = 0;
 739   }
 740
 741   for (i = 0; i < layer1_size; i++) {
 742     struct tree_node *node = tree->layers[layer][i];
 743
 744     for (j = 0; j < node->nprovide; j++) {
 745       sum += X[node->provide[j]->order];
 746     }
 747     for (j = 0; j < node->nprovide; j++) {
 748       for (k = 0; k < node->provide[j]->order; k++) {
 749         X[k]++;
 750       }
 751     }
 752   }
 753
 754   return sum;
 755 }
 756
 757 /*************************************************************************
 758   Swap positions of two nodes on the same layer
 759 *************************************************************************/
 760 static void swap(struct reqtree *tree, int layer, int order1, int order2)
 761 {
 762   struct tree_node *node1 = tree->layers[layer][order1];
 763   struct tree_node *node2 = tree->layers[layer][order2];
 764
 765   tree->layers[layer][order1] = node2;
 766   tree->layers[layer][order2] = node1;
 767   node1->order = order2;
 768   node2->order = order1;
 769 }
 770
 771 /*************************************************************************
 772   Try to reduce the number of crossings by swapping two nodes and checking
 773   if it improves the situation.
 774 *************************************************************************/
 775 static void improve(struct reqtree *tree)
 776 {
 777   int crossings[tree->num_layers - 1];
 778   int i, x1, x2, layer;
 779
 780   for (i = 0; i < tree->num_layers - 1; i++) {
 781     crossings[i] = count_crossings(tree, i);
 782   }
 783
 784   for (layer = 0; layer < tree->num_layers; layer++) {
 785     int layer_size = tree->layer_size[layer];
 786     int layer_sum = 0;
 787
 788     if (layer > 0) {
 789       layer_sum += crossings[layer - 1];
 790     }
 791     if (layer < tree->num_layers - 1) {
 792       layer_sum += crossings[layer];
 793     }
 794
 795     for (x1 = 0; x1 < layer_size; x1++) {
 796       for (x2 = x1 + 1; x2 < layer_size; x2++) {
 797         int new_crossings = 0;
 798         int new_crossings_before = 0;
 799
 800         swap(tree, layer, x1, x2);
 801         if (layer > 0) {
 802           new_crossings_before += count_crossings(tree, layer - 1);
 803         }
 804         if (layer < tree->num_layers - 1) {
 805           new_crossings += count_crossings(tree, layer);
 806         }
 807         if (new_crossings + new_crossings_before > layer_sum) {
 808           swap(tree, layer, x1, x2);
 809         } else {
 810           layer_sum = new_crossings + new_crossings_before;
 811           if (layer > 0) {
 812             crossings[layer - 1] = new_crossings_before;
 813           }
 814           if (layer < tree->num_layers - 1) {
 815             crossings[layer] = new_crossings;
 816           }
 817         }
 818       }
 819     }
 820   }
 821 }
 822
 823 /*************************************************************************
 824   Generate optimized tech_tree from current ruleset.
 825   You should free it by destroy_reqtree.
 826
 827   If pplayer is not NULL, techs unreachable to that player are not shown.
 828 *************************************************************************/
 829 struct reqtree *create_reqtree(struct player *pplayer, bool reachable)
 830 {
 831   struct reqtree *tree1, *tree2;
 832   int i, j;
 833
 834   tree1 = create_dummy_reqtree(pplayer, reachable);
 835   longest_path_layering(tree1);
 836   tree2 = add_dummy_nodes(tree1);
 837   destroy_reqtree(tree1);
 838   set_layers(tree2);
 839
 840   /* It's good heuristics for beginning */
 841   for (j = 0; j < 20; j++) {
 842     for (i = 0; i < tree2->num_layers; i++) {
 843       barycentric_sort(tree2, i);
 844     }
 845   }
 846
 847   /* Now burn some CPU */
 848   for (j = 0; j < 20; j++) {
 849     improve(tree2);
 850   }
 851
 852   calculate_diagram_layout(tree2);
 853
 854   return tree2;
 855 }
 856
 857 /****************************************************************************
 858   Give the dimensions of the reqtree.
 859 ****************************************************************************/
 860 void get_reqtree_dimensions(struct reqtree *reqtree,
 861                             int *width, int *height)
 862 {
 863   if (width) {
 864     *width = reqtree->diagram_width;
 865   }
 866   if (height){
 867     *height = reqtree->diagram_height;
 868   }
 869 }
 870
 871 /****************************************************************************
 872   Return a background color of node's rectangle
 873 ****************************************************************************/
 874 static enum color_std node_color(struct tree_node *node)
 875 {
 876   if (!node->is_dummy) {
 877     struct player_research* research = player_research_get(client.conn.playing);
 878
 879     if (!research) {
 880       return COLOR_REQTREE_KNOWN;
 881     }
 882
 883     if (!player_invention_reachable(client.conn.playing, node->tech, TRUE)) {
 884       return COLOR_REQTREE_UNREACHABLE;
 885     }
 886
 887     if (!player_invention_reachable(client.conn.playing, node->tech, FALSE)) {
 888       if (is_tech_a_req_for_goal(client.conn.playing, node->tech,
 889                                  research->tech_goal)
 890           || node->tech == research->tech_goal) {
 891         return COLOR_REQTREE_GOAL_NOT_GETTABLE;
 892       } else {
 893         return COLOR_REQTREE_NOT_GETTABLE;
 894       }
 895     }
 896
 897     if (research->researching == node->tech) {
 898       return COLOR_REQTREE_RESEARCHING;
 899     }
 900
 901     if (TECH_KNOWN == player_invention_state(client.conn.playing, node->tech)) {
 902       return COLOR_REQTREE_KNOWN;
 903     }
 904
 905     if (is_tech_a_req_for_goal(client.conn.playing, node->tech,
 906                                research->tech_goal)
 907         || node->tech == research->tech_goal) {
 908       if (TECH_PREREQS_KNOWN ==
 909             player_invention_state(client.conn.playing, 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 ==
 917           player_invention_state(client.conn.playing, 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 player_research *research = player_research_get(client.conn.playing);
 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 (is_tech_a_req_for_goal(client.conn.playing, dest_node->tech,
 984                              research->tech_goal)
 985       || dest_node->tech == research->tech_goal) {
 986     return REQTREE_GOAL_EDGE;
 987   }
 988
 989   if (TECH_KNOWN == player_invention_state(client.conn.playing, node->tech)) {
 990     if (TECH_KNOWN == player_invention_state(client.conn.playing, 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 = advance_name_for_player(client.conn.playing, 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 (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, DIR8_SOUTH, TRUE);
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 (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 }