Freeciv-3.3: /fast/freeciv/nightly/main/client/reqtree.c Source File

Freeciv-3.3

Loading...
Searching...
No Matches
reqtree.c
Go to the documentation of this file.
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 This structure describes a node in a technology tree diagram.
64 A node can by dummy or real. Real node describes a technology.
65****************************************************************************/
66struct tree_node {
67 bool is_dummy;
68 Tech_type_id tech;
69
70 /* Incoming edges */
71 int nrequire;
72 struct tree_node **require;
73
74 /* Outgoing edges */
75 int nprovide;
76 struct tree_node **provide;
77
78 /* Logical position on the diagram */
79 int order, layer;
80
81 /* Coordinates of the rectangle on the diagram in pixels */
82 int node_x, node_y, node_width, node_height;
83
84 /* For general purpose */
85 int number;
86};
87
88/****************************************************************************
89 Structure which describes abstract technology diagram.
90 Nodes are ordered inside layers[] table.
91****************************************************************************/
92struct reqtree {
93 int num_nodes;
94 struct tree_node **nodes;
95
96 int num_layers;
97 /* Size of each layer */
98 int *layer_size;
99 struct tree_node ***layers;
100
101 /* In pixels */
102 int diagram_width, diagram_height;
103};
104
105
106/****************************************************************************
107 Edge types for coloring the edges by type in the tree
108****************************************************************************/
109 enum reqtree_edge_type {
110 REQTREE_EDGE = 0, /* Normal, "unvisited" */
111 REQTREE_READY_EDGE,
112 REQTREE_KNOWN_EDGE, /* Both nodes known, "visited" */
113 REQTREE_ACTIVE_EDGE,
114 REQTREE_GOAL_EDGE /* Dest node is part of goal "future visited" */
115};
116
117/*********************************************************************/
120 static void add_requirement(struct tree_node *node, struct tree_node *req)
121{
122 fc_assert_ret(node != NULL);
123 fc_assert_ret(req != NULL);
124
125 node->require =
126 fc_realloc(node->require,
127 sizeof(*node->require) * (node->nrequire + 1));
128 node->require[node->nrequire] = req;
129 node->nrequire++;
130
131 req->provide =
132 fc_realloc(req->provide,
133 sizeof(*req->provide) * (req->nprovide + 1));
134 req->provide[req->nprovide] = node;
135 req->nprovide++;
136}
137
138/*********************************************************************/
141 static struct tree_node *new_tree_node(void)
142{
143 struct tree_node *node = fc_malloc(sizeof(*node));
144
145 node->nrequire = 0;
146 node->nprovide = 0;
147 node->require = NULL;
148 node->provide = NULL;
149 node->order = -1;
150 node->layer = -1;
151
152 return node;
153}
154
155/*********************************************************************/
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(utype) {
183
184 if (!is_tech_req_for_utype(utype, advance_by_number(node->tech))) {
185 continue;
186 }
187
188 sprite = get_unittype_sprite(tileset, utype,
189 ACTIVITY_LAST, direction8_invalid());
190 get_sprite_dimensions(sprite, &swidth, &sheight);
191 max_icon_height = MAX(max_icon_height, sheight);
192 icons_width_sum += swidth + 2;
193 } unit_type_iterate_end;
194
195 /* Buildings */
196 improvement_iterate(pimprove) {
197 if (valid_improvement(pimprove)) {
198 requirement_vector_iterate(&(pimprove->reqs), preq) {
199 if (VUT_ADVANCE == preq->source.kind
200 && advance_number(preq->source.value.advance) == node->tech) {
201 sprite = get_building_sprite(tileset, pimprove);
202 /* Improvement icons are not guaranteed to exist */
203 if (sprite) {
204 get_sprite_dimensions(sprite, &swidth, &sheight);
205 max_icon_height = MAX(max_icon_height, sheight);
206 icons_width_sum += swidth + 2;
207 }
208 }
209 } requirement_vector_iterate_end;
210 }
211 } improvement_iterate_end;
212
213 /* Governments */
214 governments_iterate(gov) {
215 requirement_vector_iterate(&(gov->reqs), preq) {
216 if (VUT_ADVANCE == preq->source.kind
217 && advance_number(preq->source.value.advance) == node->tech) {
218 sprite = get_government_sprite(tileset, gov);
219 get_sprite_dimensions(sprite, &swidth, &sheight);
220 max_icon_height = MAX(max_icon_height, sheight);
221 icons_width_sum += swidth + 2;
222 }
223 } requirement_vector_iterate_end;
224 } governments_iterate_end;
225 }
226
227 *height += max_icon_height;
228 if (*width < icons_width_sum) {
229 *width = icons_width_sum;
230 }
231 }
232}
233
234/*********************************************************************/
238 static void symmetrize(struct reqtree* tree)
239{
240 int layer;
241 int i, j;
242
243 for (layer = 0; layer < tree->num_layers; layer++) {
244 for (i = 0; i < tree->layer_size[layer]; i++) {
245 struct tree_node *node = tree->layers[layer][i];
246 int v, node_y, node_height;
247
248 if (node->nrequire == 0) {
249 continue;
250 }
251 v = 0;
252 for (j = 0; j < node->nrequire; j++) {
253 struct tree_node *node_require = node->require[j];
254
255 v += node_require->node_y + node_require->node_height / 2;
256 }
257 v /= node->nrequire;
258 node_y = node->node_y;
259 node_height = node->node_height;
260
261 if (v < node_y + node_height / 2) {
262 if (node_y <= 0) {
263 continue;
264 }
265
266 if (i > 0) {
267 struct tree_node *node_above = tree->layers[layer][i - 1];
268
269 if (node_above->node_y
270 + node_above->node_height >= node_y - 11) {
271 continue;
272 }
273 }
274 node_y--;
275 } else if (v > node_y + node_height / 2) {
276 if (node_y + node_height >= tree->diagram_height - 1) {
277 continue;
278 }
279 if (i < tree->layer_size[layer] - 1) {
280 struct tree_node* node_below = tree->layers[layer][i + 1];
281
282 if (node_y + node_height >= node_below->node_y - 11) {
283 continue;
284 }
285 }
286 node_y++;
287 }
288 node->node_y = node_y;
289 }
290 }
291}
292
293/*********************************************************************/
297 static void calculate_diagram_layout(struct reqtree *tree)
298{
299 int i, layer, layer_offs;
300
301 /* Calculate minimum size of rectangle for each node */
302 for (i = 0; i < tree->num_nodes; i++) {
303 struct tree_node *node = tree->nodes[i];
304
305 node_rectangle_minimum_size(tree->nodes[i],
306 &node->node_width, &node->node_height);
307 node->number = i;
308 }
309
310 /* Calculate height of the diagram. There should be at least 10 pixels
311 * between any two nodes */
312 tree->diagram_height = 0;
313 for (layer = 0; layer < tree->num_layers; layer++) {
314 int h_sum = 0;
315
316 for (i = 0; i < tree->layer_size[layer]; i++) {
317 struct tree_node *node = tree->layers[layer][i];
318
319 h_sum += node->node_height;
320
321 if (i < tree->layer_size[layer] - 1) {
322 h_sum += 10;
323 }
324 }
325 tree->diagram_height = MAX(tree->diagram_height, h_sum);
326 }
327
328 /* Calculate maximum width of node for each layer and enlarge other nodes
329 * to match maximum width.
330 * Calculate x offsets
331 */
332 layer_offs = 0;
333 for (layer = 0; layer < tree->num_layers; layer++) {
334 int max_width = 0;
335
336 for (i = 0; i < tree->layer_size[layer]; i++) {
337 struct tree_node *node = tree->layers[layer][i];
338
339 max_width = MAX(max_width, node->node_width);
340 }
341
342 for (i = 0; i < tree->layer_size[layer]; i++) {
343 struct tree_node *node = tree->layers[layer][i];
344
345 node->node_width = max_width;
346 node->node_x = layer_offs;
347 }
348
349 /* Space between layers should be proportional to their size */
350 if (layer != tree->num_layers - 1) {
351 layer_offs += max_width * 5 / 4 + 80;
352 } else {
353 layer_offs += max_width + 10;
354 }
355 }
356 tree->diagram_width = layer_offs;
357
358 /* Once we have x positions calculated we can
359 * calculate y-position of nodes on the diagram
360 * Distribute nodes steadily.
361 */
362 for (layer = 0; layer < tree->num_layers; layer++) {
363 int y = 0;
364 int h_sum = 0;
365
366 for (i = 0; i < tree->layer_size[layer]; i++) {
367 struct tree_node *node = tree->layers[layer][i];
368
369 h_sum += node->node_height;
370 }
371
372 for (i = 0; i < tree->layer_size[layer]; i++) {
373 struct tree_node *node = tree->layers[layer][i];
374
375 node->node_y = y;
376 y += node->node_height;
377 if (tree->layer_size[layer] > 1) {
378 y += (tree->diagram_height - h_sum)
379 / (tree->layer_size[layer] - 1) - 1;
380 }
381 }
382 }
383
384 /* The symetrize() function moves node by one pixel per call */
385 for (i = 0; i < tree->diagram_height; i++) {
386 symmetrize(tree);
387 }
388}
389
390/*********************************************************************/
397 static struct reqtree *create_dummy_reqtree(struct player *pplayer,
398 bool show_all)
399{
400 const struct research *presearch = research_get(pplayer);
401 struct reqtree *tree = fc_malloc(sizeof(*tree));
402 int j;
403 Tech_type_id ac = advance_count();
404 struct tree_node *nodes[ac];
405
406 nodes[A_NONE] = NULL;
407 advance_index_iterate_max(A_FIRST, tech, ac) {
408 if (!valid_advance_by_number(tech)) {
409 nodes[tech] = NULL;
410 continue;
411 }
412
413 if (pplayer && !show_all
414 && !research_invention_reachable(presearch, tech)) {
415 /* Reqtree requested for particular player and this tech is
416 * unreachable to them. */
417 nodes[tech] = NULL;
418 continue;
419 }
420 nodes[tech] = new_tree_node();
421 nodes[tech]->is_dummy = FALSE;
422 nodes[tech]->tech = tech;
423 } advance_index_iterate_max_end;
424
425 advance_index_iterate_max(A_FIRST, tech, ac) {
426 struct advance *padvance = valid_advance_by_number(tech);
427 Tech_type_id tech_one, tech_two;
428
429 if (!padvance) {
430 continue;
431 }
432 if (nodes[tech] == NULL) {
433 continue;
434 }
435
436 tech_one = advance_required(tech, AR_ONE);
437 tech_two = advance_required(tech, AR_TWO);
438
439 if (!show_all && A_NONE != tech_one
440 && A_LAST != tech_two && A_NONE != tech_two
441 && (nodes[tech_one] == NULL || nodes[tech_two] == NULL)) {
442 /* Print only reachable techs. */
443 continue;
444 }
445
446 /* Formerly, we used to remove the redundant requirement nodes
447 * (the technologies already included in the requirements of the other
448 * requirement). However, it doesn't look like a good idea, because
449 * a player can steal any technology independently of the technology
450 * tree. */
451 if (A_NONE != tech_one && A_LAST != tech_two) {
452 add_requirement(nodes[tech], nodes[tech_one]);
453 if (A_NONE != tech_two) {
454 add_requirement(nodes[tech], nodes[tech_two]);
455 }
456 }
457 } advance_index_iterate_max_end;
458
459 /* Copy nodes from local array to dynamically allocated one.
460 * Skip non-existing entries */
461 tree->nodes = fc_calloc(ac, sizeof(*tree->nodes));
462 j = 0;
463 advance_index_iterate_max(A_FIRST, tech, ac) {
464 if (nodes[tech]) {
465 fc_assert_action(valid_advance_by_number(nodes[tech]->tech), continue);
466 tree->nodes[j++] = nodes[tech];
467 }
468 } advance_index_iterate_max_end;
469 tree->num_nodes = j;
470 tree->layers = NULL;
471
472 return tree;
473}
474
475/*********************************************************************/
478 void destroy_reqtree(struct reqtree *tree)
479{
480 int i;
481
482 for (i = 0; i < tree->num_nodes; i++) {
483 free(tree->nodes[i]->require);
484 free(tree->nodes[i]->provide);
485 free(tree->nodes[i]);
486 }
487 free(tree->nodes);
488 if (tree->layers) {
489 for (i = 0; i < tree->num_layers; i++) {
490 free(tree->layers[i]);
491 }
492 if (tree->layer_size) {
493 free(tree->layer_size);
494 }
495 }
496 free(tree);
497}
498
499/*********************************************************************/
503 static int longest_path(struct tree_node *node)
504{
505 int max, i;
506
507 if (node->layer != -1) {
508 return node->layer;
509 }
510 max = -1;
511 for (i = 0; i < node->nrequire; i++) {
512 max = MAX(max, longest_path(node->require[i]));
513 }
514 node->layer = max + 1;
515 return node->layer;
516}
517
518/*********************************************************************/
521 static void longest_path_layering(struct reqtree *tree)
522{
523 int i;
524
525 for (i = 0; i < tree->num_nodes; i++) {
526 if (tree->nodes[i]) {
527 longest_path(tree->nodes[i]);
528 }
529 }
530}
531
532/*********************************************************************/
535 static int max_provide_layer(struct tree_node *node)
536{
537 int i;
538 int max = node->layer;
539
540 for (i = 0; i < node->nprovide; i++) {
541 if (node->provide[i]->layer > max) {
542 max = node->provide[i]->layer;
543 }
544 }
545
546 return max;
547}
548
549/*********************************************************************/
553 static struct reqtree *add_dummy_nodes(struct reqtree *tree)
554{
555 struct reqtree *new_tree;
556 int num_dummy_nodes = 0;
557 int k, i, j;
558
559 /* Count dummy nodes to be added */
560 for (i = 0; i < tree->num_nodes; i++) {
561 int mpl;
562
563 if (tree->nodes[i] == NULL) {
564 continue;
565 }
566 mpl = max_provide_layer(tree->nodes[i]);
567 if (mpl > tree->nodes[i]->layer + 1) {
568 num_dummy_nodes += mpl - tree->nodes[i]->layer - 1;
569 }
570 }
571
572 /* Create new tree */
573 new_tree = fc_malloc(sizeof(*new_tree));
574 new_tree->nodes =
575 fc_malloc(sizeof(new_tree->nodes) *
576 (tree->num_nodes + num_dummy_nodes));
577 new_tree->num_nodes = tree->num_nodes + num_dummy_nodes;
578
579 /* Copy normal nodes */
580 for (i = 0; i < tree->num_nodes; i++) {
581 new_tree->nodes[i] = new_tree_node();
582 new_tree->nodes[i]->is_dummy = FALSE;
583 new_tree->nodes[i]->tech = tree->nodes[i]->tech;
584 new_tree->nodes[i]->layer = tree->nodes[i]->layer;
585 tree->nodes[i]->number = i;
586 }
587
588 /* Allocate dummy nodes */
589 for (i = 0; i < num_dummy_nodes; i++) {
590 new_tree->nodes[i + tree->num_nodes] = new_tree_node();
591 new_tree->nodes[i + tree->num_nodes]->is_dummy = TRUE;
592 }
593 /* k points to the first unused dummy node */
594 k = tree->num_nodes;
595
596 for (i = 0; i < tree->num_nodes; i++) {
597 struct tree_node *node = tree->nodes[i];
598 int mpl;
599
600 fc_assert_action(!node->is_dummy, continue);
601
602 mpl = max_provide_layer(node);
603
604 /* If this node will have dummy as ancestors, connect them in a chain */
605 if (mpl > node->layer + 1) {
606 add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
607 for (j = node->layer + 2; j < mpl; j++) {
608 add_requirement(new_tree->nodes[k + j - node->layer - 1],
609 new_tree->nodes[k + j - node->layer - 2]);
610 }
611 for (j = node->layer + 1; j < mpl; j++) {
612 new_tree->nodes[k + j - node->layer - 1]->layer = j;
613 }
614 }
615
616 /* Copy all edges and create edges with dummy nodes */
617 for (j = 0; j < node->nprovide; j++) {
618 int provide_y = node->provide[j]->layer;
619
620 if (provide_y == node->layer + 1) {
621 /* Direct connection */
622 add_requirement(new_tree->nodes[node->provide[j]->number],
623 new_tree->nodes[i]);
624 } else {
625 /* Connection through dummy node */
626 add_requirement(new_tree->nodes[node->provide[j]->number],
627 new_tree->nodes[k + provide_y - node->layer - 2]);
628 }
629 }
630
631 if (mpl > node->layer + 1) {
632 k += mpl - node->layer - 1;
633 fc_assert(k <= new_tree->num_nodes);
634 }
635 }
636 new_tree->layers = NULL;
637
638 return new_tree;
639}
640
641/*********************************************************************/
646 static void set_layers(struct reqtree *tree)
647{
648 int i;
649 int num_layers = 0;
650
651 /* Count total number of layers */
652 for (i = 0; i < tree->num_nodes; i++) {
653 num_layers = MAX(num_layers, tree->nodes[i]->layer);
654 }
655 num_layers++;
656 tree->num_layers = num_layers;
657
658 {
659 /* Counters for order - order number for the next node in the layer */
660 int T[num_layers];
661
662 tree->layers = fc_malloc(sizeof(*tree->layers) * num_layers);
663 tree->layer_size = fc_malloc(sizeof(*tree->layer_size) * num_layers);
664 for (i = 0; i < num_layers; i++) {
665 T[i] = 0;
666 tree->layer_size[i] = 0;
667 }
668 for (i = 0; i < tree->num_nodes; i++) {
669 tree->layer_size[tree->nodes[i]->layer]++;
670 }
671
672 for (i = 0; i < num_layers; i++) {
673 tree->layers[i] =
674 fc_malloc(sizeof(*tree->layers[i]) * tree->layer_size[i]);
675 }
676 for (i = 0; i < tree->num_nodes; i++) {
677 struct tree_node *node = tree->nodes[i];
678
679 tree->layers[node->layer][T[node->layer]] = node;
680 node->order = T[node->layer];
681 T[node->layer]++;
682 }
683 }
684}
685
686 struct node_and_float {
687 struct tree_node *node;
688 float value;
689};
690
691/*********************************************************************/
694 static int cmp_func(const void *_a, const void *_b)
695{
696 const struct node_and_float *a = _a, *b = _b;
697
698 if (a->value > b->value) {
699 return 1;
700 }
701 if (a->value < b->value) {
702 return -1;
703 }
704
705 return 0;
706}
707
708/*********************************************************************/
712 static void barycentric_sort(struct reqtree *tree, int layer)
713{
714 if (tree->layer_size[layer] > 0) {
715 struct node_and_float T[tree->layer_size[layer]];
716 int i, j;
717 float v;
718
719 for (i = 0; i < tree->layer_size[layer]; i++) {
720 struct tree_node *node = tree->layers[layer][i];
721
722 T[i].node = node;
723 v = 0.0;
724 for (j = 0; j < node->nrequire; j++) {
725 v += node->require[j]->order;
726 }
727 if (node->nrequire > 0) {
728 v /= (float) node->nrequire;
729 }
730 T[i].value = v;
731 }
732 qsort(T, tree->layer_size[layer], sizeof(*T),
733 cmp_func);
734
735 for (i = 0; i < tree->layer_size[layer]; i++) {
736 tree->layers[layer][i] = T[i].node;
737 T[i].node->order = i;
738 }
739 }
740}
741
742/*********************************************************************/
745 static int count_crossings(struct reqtree *tree, int layer)
746{
747 int layer1_size = tree->layer_size[layer];
748 int layer2_size = tree->layer_size[layer + 1];
749 int X[layer2_size];
750 int i, j, k;
751 int sum = 0;
752
753 for (i = 0; i < layer2_size; i++) {
754 X[i] = 0;
755 }
756
757 for (i = 0; i < layer1_size; i++) {
758 struct tree_node *node = tree->layers[layer][i];
759
760 for (j = 0; j < node->nprovide; j++) {
761 sum += X[node->provide[j]->order];
762 }
763 for (j = 0; j < node->nprovide; j++) {
764 for (k = 0; k < node->provide[j]->order; k++) {
765 X[k]++;
766 }
767 }
768 }
769
770 return sum;
771}
772
773/*********************************************************************/
776 static void swap(struct reqtree *tree, int layer, int order1, int order2)
777{
778 struct tree_node *node1 = tree->layers[layer][order1];
779 struct tree_node *node2 = tree->layers[layer][order2];
780
781 tree->layers[layer][order1] = node2;
782 tree->layers[layer][order2] = node1;
783 node1->order = order2;
784 node2->order = order1;
785}
786
787/*********************************************************************/
791 static void improve(struct reqtree *tree)
792{
793 int layers = tree->num_layers;
794 int crossings[layers - 1];
795 int i, x1, x2, layer;
796
797 for (i = 0; i < layers - 1; i++) {
798 crossings[i] = count_crossings(tree, i);
799 }
800
801 for (layer = 0; layer < layers; layer++) {
802 int layer_size = tree->layer_size[layer];
803 int layer_sum = 0;
804
805 if (layer > 0) {
806 layer_sum += crossings[layer - 1];
807 }
808 if (layer < layers - 1) {
809 layer_sum += crossings[layer];
810 }
811
812 for (x1 = 0; x1 < layer_size; x1++) {
813 for (x2 = x1 + 1; x2 < layer_size; x2++) {
814 int new_crossings = 0;
815 int new_crossings_before = 0;
816
817 swap(tree, layer, x1, x2);
818
819 if (layer > 0) {
820 new_crossings_before += count_crossings(tree, layer - 1);
821 }
822 if (layer < layers - 1) {
823 new_crossings += count_crossings(tree, layer);
824 }
825 if (new_crossings + new_crossings_before > layer_sum) {
826 swap(tree, layer, x1, x2);
827 } else {
828 layer_sum = new_crossings + new_crossings_before;
829 if (layer > 0) {
830 crossings[layer - 1] = new_crossings_before;
831 }
832 if (layer < layers - 1) {
833 crossings[layer] = new_crossings;
834 }
835 }
836 }
837 }
838 }
839}
840
841/*********************************************************************/
847 struct reqtree *create_reqtree(struct player *pplayer, bool show_all)
848{
849 struct reqtree *tree1, *tree2;
850 int i, j;
851
852 tree1 = create_dummy_reqtree(pplayer, show_all);
853 longest_path_layering(tree1);
854 tree2 = add_dummy_nodes(tree1);
855 destroy_reqtree(tree1);
856 set_layers(tree2);
857
858 /* It's good heuristics for beginning */
859 for (j = 0; j < 20; j++) {
860 for (i = 0; i < tree2->num_layers; i++) {
861 barycentric_sort(tree2, i);
862 }
863 }
864
865 /* Now burn some CPU */
866 for (j = 0; j < 20; j++) {
867 improve(tree2);
868 }
869
870 calculate_diagram_layout(tree2);
871
872 return tree2;
873}
874
875/*********************************************************************/
878 void get_reqtree_dimensions(struct reqtree *reqtree,
879 int *width, int *height)
880{
881 if (width) {
882 *width = reqtree->diagram_width;
883 }
884 if (height) {
885 *height = reqtree->diagram_height;
886 }
887}
888
889/*********************************************************************/
892 static enum color_std node_color(struct tree_node *node)
893{
894 if (!node->is_dummy) {
895 struct research *research = research_get(client_player());
896
897 if (!research) {
898 return COLOR_REQTREE_KNOWN;
899 }
900
901 if (!research_invention_reachable(research, node->tech)) {
902 return COLOR_REQTREE_UNREACHABLE;
903 }
904
905 if (!research_invention_gettable(research, node->tech, TRUE)) {
906 if (research_goal_tech_req(research, research->tech_goal, node->tech)
907 || node->tech == research->tech_goal) {
908 return COLOR_REQTREE_GOAL_NOT_GETTABLE;
909 } else {
910 return COLOR_REQTREE_NOT_GETTABLE;
911 }
912 }
913
914 if (research->researching == node->tech) {
915 return COLOR_REQTREE_RESEARCHING;
916 }
917
918 if (TECH_KNOWN == research_invention_state(research, node->tech)) {
919 return COLOR_REQTREE_KNOWN;
920 }
921
922 if (research_goal_tech_req(research, research->tech_goal, node->tech)
923 || node->tech == research->tech_goal) {
924 if (TECH_PREREQS_KNOWN == research_invention_state(research,
925 node->tech)) {
926 return COLOR_REQTREE_GOAL_PREREQS_KNOWN;
927 } else {
928 return COLOR_REQTREE_GOAL_UNKNOWN;
929 }
930 }
931
932 if (TECH_PREREQS_KNOWN == research_invention_state(research,
933 node->tech)) {
934 return COLOR_REQTREE_PREREQS_KNOWN;
935 }
936
937 return COLOR_REQTREE_UNKNOWN;
938 } else {
939 return COLOR_REQTREE_BACKGROUND;
940 }
941}
942
943/*********************************************************************/
947 static enum reqtree_edge_type get_edge_type(struct tree_node *node,
948 struct tree_node *dest_node)
949{
950 struct research *research = research_get(client_player());
951
952 if (dest_node == NULL) {
953 /* Assume node is a dummy */
954 dest_node = node;
955 }
956
957 /* Find the required tech */
958 while (node->is_dummy) {
959 fc_assert(node->nrequire == 1);
960 node = node->require[0];
961 }
962
963 /* Find destination advance by recursing in dest_node->provide[]
964 * watch out: recursion */
965 if (dest_node->is_dummy) {
966 enum reqtree_edge_type sum_type = REQTREE_EDGE;
967 int i;
968
969 fc_assert(dest_node->nprovide > 0);
970 for (i = 0; i < dest_node->nprovide; ++i) {
971 enum reqtree_edge_type type = get_edge_type(node, dest_node->provide[i]);
972
973 switch (type) {
974 case REQTREE_ACTIVE_EDGE:
975 case REQTREE_GOAL_EDGE:
976 return type;
977 case REQTREE_KNOWN_EDGE:
978 case REQTREE_READY_EDGE:
979 sum_type = type;
980 break;
981 default:
982 /* No change */
983 break;
984 }
985 }
986
987 return sum_type;
988 }
989
990 if (!research) {
991 /* Global observer case */
992 return REQTREE_KNOWN_EDGE;
993 }
994
995 if (research->researching == dest_node->tech) {
996 return REQTREE_ACTIVE_EDGE;
997 }
998
999 if (research_goal_tech_req(research, research->tech_goal, dest_node->tech)
1000 || dest_node->tech == research->tech_goal) {
1001 return REQTREE_GOAL_EDGE;
1002 }
1003
1004 if (TECH_KNOWN == research_invention_state(research, node->tech)) {
1005 if (TECH_KNOWN == research_invention_state(research, dest_node->tech)) {
1006 return REQTREE_KNOWN_EDGE;
1007 } else {
1008 return REQTREE_READY_EDGE;
1009 }
1010 }
1011
1012 return REQTREE_EDGE;
1013}
1014
1015/*********************************************************************/
1019 static enum color_std edge_color(struct tree_node *node,
1020 struct tree_node *dest_node)
1021{
1022 enum reqtree_edge_type type = get_edge_type(node, dest_node);
1023
1024 switch (type) {
1025 case REQTREE_ACTIVE_EDGE:
1026 return COLOR_REQTREE_RESEARCHING;
1027 case REQTREE_GOAL_EDGE:
1028 return COLOR_REQTREE_GOAL_UNKNOWN;
1029 case REQTREE_KNOWN_EDGE:
1030 /* Using "text" black instead of "known" white/ground/green */
1031 return COLOR_REQTREE_TEXT;
1032 case REQTREE_READY_EDGE:
1033 return COLOR_REQTREE_PREREQS_KNOWN;
1034 default:
1035 return COLOR_REQTREE_EDGE;
1036 }
1037}
1038
1039/*********************************************************************/
1045 void draw_reqtree(struct reqtree *tree, struct canvas *pcanvas,
1046 int canvas_x, int canvas_y,
1047 int tt_x, int tt_y, int w, int h)
1048{
1049 int i, j, k;
1050 int swidth, sheight;
1051 struct sprite* sprite;
1052 struct color *color;
1053
1054 /* Draw the diagram */
1055 for (i = 0; i < tree->num_layers; i++) {
1056 for (j = 0; j < tree->layer_size[i]; j++) {
1057 struct tree_node *node = tree->layers[i][j];
1058 int startx, starty, endx, endy, width, height;
1059
1060 startx = node->node_x;
1061 starty = node->node_y;
1062 width = node->node_width;
1063 height = node->node_height;
1064
1065 if (node->is_dummy) {
1066 /* Use the same layout as lines for dummy nodes */
1067 canvas_put_line(pcanvas,
1068 get_color(tileset, edge_color(node, NULL)),
1069 LINE_GOTO,
1070 startx, starty, width, 0);
1071 } else {
1072 const char *text = research_advance_name_translation
1073 (research_get(client_player()), node->tech);
1074 int text_w, text_h;
1075 int icon_startx;
1076
1077 canvas_put_rectangle(pcanvas,
1078 get_color(tileset, COLOR_REQTREE_BACKGROUND),
1079 startx, starty, width, height);
1080
1081 /* Print color rectangle with text inside. */
1082 canvas_put_rectangle(pcanvas, get_color(tileset, node_color(node)),
1083 startx + 1, starty + 1,
1084 width - 2, height - 2);
1085 /* The following code is similar to the one in
1086 * node_rectangle_minimum_size(). If you change something here,
1087 * change also node_rectangle_minimum_size().
1088 */
1089
1090 get_text_size(&text_w, &text_h, FONT_REQTREE_TEXT, text);
1091
1092 canvas_put_text(pcanvas,
1093 startx + (width - text_w) / 2,
1094 starty + 4,
1095 FONT_REQTREE_TEXT,
1096 get_color(tileset, COLOR_REQTREE_TEXT),
1097 text);
1098 icon_startx = startx + 5;
1099
1100 if (gui_options.reqtree_show_icons) {
1101 unit_type_iterate(utype) {
1102
1103 if (!is_tech_req_for_utype(utype, advance_by_number(node->tech))) {
1104 continue;
1105 }
1106
1107 sprite = get_unittype_sprite(tileset, utype,
1108 ACTIVITY_LAST, direction8_invalid());
1109 get_sprite_dimensions(sprite, &swidth, &sheight);
1110 canvas_put_sprite_full(pcanvas,
1111 icon_startx,
1112 starty + text_h + 4
1113 + (height - text_h - 4 - sheight) / 2,
1114 sprite);
1115 icon_startx += swidth + 2;
1116 } unit_type_iterate_end;
1117
1118 improvement_iterate(pimprove) {
1119 if (valid_improvement(pimprove)) {
1120 requirement_vector_iterate(&(pimprove->reqs), preq) {
1121 if (VUT_ADVANCE == preq->source.kind
1122 && advance_number(preq->source.value.advance) == node->tech) {
1123 sprite = get_building_sprite(tileset, pimprove);
1124 /* Improvement icons are not guaranteed to exist */
1125 if (sprite) {
1126 get_sprite_dimensions(sprite, &swidth, &sheight);
1127 canvas_put_sprite_full(pcanvas,
1128 icon_startx,
1129 starty + text_h + 4
1130 + (height - text_h - 4 - sheight) / 2,
1131 sprite);
1132 icon_startx += swidth + 2;
1133 }
1134 }
1135 } requirement_vector_iterate_end;
1136 }
1137 } improvement_iterate_end;
1138
1139 governments_iterate(gov) {
1140 requirement_vector_iterate(&(gov->reqs), preq) {
1141 if (VUT_ADVANCE == preq->source.kind
1142 && advance_number(preq->source.value.advance) == node->tech) {
1143 sprite = get_government_sprite(tileset, gov);
1144 get_sprite_dimensions(sprite, &swidth, &sheight);
1145 canvas_put_sprite_full(pcanvas,
1146 icon_startx,
1147 starty + text_h + 4
1148 + (height - text_h - 4 - sheight) / 2,
1149 sprite);
1150 icon_startx += swidth + 2;
1151 }
1152 } requirement_vector_iterate_end;
1153 } governments_iterate_end;
1154 }
1155 }
1156
1157 /* Draw all outgoing edges */
1158 startx = node->node_x + node->node_width;
1159 starty = node->node_y + node->node_height / 2;
1160 for (k = 0; k < node->nprovide; k++) {
1161 struct tree_node *dest_node = node->provide[k];
1162
1163 color = get_color(tileset, edge_color(node, dest_node));
1164
1165 endx = dest_node->node_x;
1166 endy = dest_node->node_y + dest_node->node_height / 2;
1167
1168 if (gui_options.reqtree_curved_lines) {
1169 canvas_put_curved_line(pcanvas, color, LINE_GOTO,
1170 startx, starty, endx - startx,
1171 endy - starty);
1172 } else {
1173 canvas_put_line(pcanvas, color, LINE_GOTO,
1174 startx, starty, endx - startx,
1175 endy - starty);
1176 }
1177 }
1178 }
1179 }
1180}
1181
1182/*********************************************************************/
1185 Tech_type_id get_tech_on_reqtree(struct reqtree *tree, int x, int y)
1186{
1187 int i;
1188
1189 for (i = 0; i < tree->num_nodes; i++) {
1190 struct tree_node *node = tree->nodes[i];
1191
1192 if (node->is_dummy) {
1193 continue;
1194 }
1195 if (node->node_x <= x && node->node_y <= y
1196 && node->node_x + node->node_width > x
1197 && node->node_y + node->node_height > y) {
1198 return node->tech;
1199 }
1200 }
1201
1202 return A_NONE;
1203}
1204
1205/*********************************************************************/
1209 bool find_tech_on_reqtree(struct reqtree *tree, Tech_type_id tech,
1210 int *x, int *y, int *w, int *h)
1211{
1212 int i;
1213
1214 for (i = 0; i < tree->num_nodes; i++) {
1215 struct tree_node *node = tree->nodes[i];
1216
1217 if (!node->is_dummy && node->tech == tech) {
1218 if (x) {
1219 *x = node->node_x;
1220 }
1221 if (y) {
1222 *y = node->node_y;
1223 }
1224 if (w) {
1225 *w = node->node_width;
1226 }
1227 if (h) {
1228 *h = node->node_height;
1229 }
1230 return TRUE;
1231 }
1232 }
1233
1234 return FALSE;
1235}
height
struct canvas int int struct sprite int int int int height
Definition canvas_g.h:44
canvas_put_rectangle
struct canvas int int int int struct sprite *sprite canvas_put_rectangle
Definition canvas_g.h:55
canvas_y
struct canvas int int canvas_y
Definition canvas_g.h:43
canvas_x
struct canvas int canvas_x
Definition canvas_g.h:43
canvas_put_line
struct canvas int int int int struct sprite *sprite struct canvas struct color int int int int height canvas_put_line
Definition canvas_g.h:62
pcanvas
struct canvas * pcanvas
Definition canvas_g.h:42
canvas_put_text
canvas_put_text
Definition canvas_g.h:80
width
struct canvas int int struct sprite int int int width
Definition canvas_g.h:44
LINE_GOTO
@ LINE_GOTO
Definition canvas_g.h:26
client_main.h
client_player
#define client_player()
Definition client_main.h:106
T
#define T(x)
get_color
struct color * get_color(const struct tileset *t, enum color_std stdcolor)
Definition colors_common.c:100
colors_g.h
incite_cost
char * incite_cost
Definition comments.c:74
Tech_type_id
int Tech_type_id
Definition fc_types.h:381
government.h
governments_iterate
#define governments_iterate(NAME_pgov)
Definition government.h:122
governments_iterate_end
#define governments_iterate_end
Definition government.h:125
canvas_put_sprite_full
void canvas_put_sprite_full(struct canvas *pcanvas, int canvas_x, int canvas_y, struct sprite *sprite)
Definition canvas.c:144
get_text_size
void get_text_size(int *width, int *height, enum client_font font, const char *text)
Definition canvas.c:341
canvas_put_curved_line
void canvas_put_curved_line(struct canvas *pcanvas, struct color *pcolor, enum line_type ltype, int start_x, int start_y, int dx, int dy)
Definition canvas.c:276
type
GType type
Definition repodlgs.c:1313
valid_improvement
const struct impr_type * valid_improvement(const struct impr_type *pimprove)
Definition improvement.c:211
improvement.h
improvement_iterate_end
#define improvement_iterate_end
Definition improvement.h:205
improvement_iterate
#define improvement_iterate(_p)
Definition improvement.h:199
log.h
fc_assert_ret
#define fc_assert_ret(condition)
Definition log.h:191
fc_assert
#define fc_assert(condition)
Definition log.h:176
fc_assert_action
#define fc_assert_action(condition, action)
Definition log.h:187
fc_calloc
#define fc_calloc(n, esz)
Definition mem.h:38
fc_realloc
#define fc_realloc(ptr, sz)
Definition mem.h:36
fc_malloc
#define fc_malloc(sz)
Definition mem.h:34
gui_options
struct client_options gui_options
Definition options.c:71
options.h
max_provide_layer
static int max_provide_layer(struct tree_node *node)
Definition reqtree.c:535
longest_path
static int longest_path(struct tree_node *node)
Definition reqtree.c:503
barycentric_sort
static void barycentric_sort(struct reqtree *tree, int layer)
Definition reqtree.c:712
cmp_func
static int cmp_func(const void *_a, const void *_b)
Definition reqtree.c:694
draw_reqtree
void draw_reqtree(struct reqtree *tree, struct canvas *pcanvas, int canvas_x, int canvas_y, int tt_x, int tt_y, int w, int h)
Definition reqtree.c:1045
get_reqtree_dimensions
void get_reqtree_dimensions(struct reqtree *reqtree, int *width, int *height)
Definition reqtree.c:878
node_rectangle_minimum_size
static void node_rectangle_minimum_size(struct tree_node *node, int *width, int *height)
Definition reqtree.c:159
add_requirement
static void add_requirement(struct tree_node *node, struct tree_node *req)
Definition reqtree.c:120
node_color
static enum color_std node_color(struct tree_node *node)
Definition reqtree.c:892
count_crossings
static int count_crossings(struct reqtree *tree, int layer)
Definition reqtree.c:745
improve
static void improve(struct reqtree *tree)
Definition reqtree.c:791
symmetrize
static void symmetrize(struct reqtree *tree)
Definition reqtree.c:238
add_dummy_nodes
static struct reqtree * add_dummy_nodes(struct reqtree *tree)
Definition reqtree.c:553
set_layers
static void set_layers(struct reqtree *tree)
Definition reqtree.c:646
longest_path_layering
static void longest_path_layering(struct reqtree *tree)
Definition reqtree.c:521
calculate_diagram_layout
static void calculate_diagram_layout(struct reqtree *tree)
Definition reqtree.c:297
get_tech_on_reqtree
Tech_type_id get_tech_on_reqtree(struct reqtree *tree, int x, int y)
Definition reqtree.c:1185
find_tech_on_reqtree
bool find_tech_on_reqtree(struct reqtree *tree, Tech_type_id tech, int *x, int *y, int *w, int *h)
Definition reqtree.c:1209
swap
static void swap(struct reqtree *tree, int layer, int order1, int order2)
Definition reqtree.c:776
get_edge_type
static enum reqtree_edge_type get_edge_type(struct tree_node *node, struct tree_node *dest_node)
Definition reqtree.c:947
edge_color
static enum color_std edge_color(struct tree_node *node, struct tree_node *dest_node)
Definition reqtree.c:1019
new_tree_node
static struct tree_node * new_tree_node(void)
Definition reqtree.c:141
destroy_reqtree
void destroy_reqtree(struct reqtree *tree)
Definition reqtree.c:478
create_reqtree
struct reqtree * create_reqtree(struct player *pplayer, bool show_all)
Definition reqtree.c:847
create_dummy_reqtree
static struct reqtree * create_dummy_reqtree(struct player *pplayer, bool show_all)
Definition reqtree.c:397
reqtree_edge_type
reqtree_edge_type
Definition reqtree.c:109
REQTREE_READY_EDGE
@ REQTREE_READY_EDGE
Definition reqtree.c:111
REQTREE_ACTIVE_EDGE
@ REQTREE_ACTIVE_EDGE
Definition reqtree.c:113
REQTREE_EDGE
@ REQTREE_EDGE
Definition reqtree.c:110
REQTREE_KNOWN_EDGE
@ REQTREE_KNOWN_EDGE
Definition reqtree.c:112
REQTREE_GOAL_EDGE
@ REQTREE_GOAL_EDGE
Definition reqtree.c:114
reqtree.h
requirement_vector_iterate_end
#define requirement_vector_iterate_end
Definition requirements.h:94
requirement_vector_iterate
#define requirement_vector_iterate(req_vec, preq)
Definition requirements.h:92
research_invention_reachable
bool research_invention_reachable(const struct research *presearch, const Tech_type_id tech)
Definition research.c:668
research_goal_tech_req
bool research_goal_tech_req(const struct research *presearch, Tech_type_id goal, Tech_type_id tech)
Definition research.c:807
research_advance_name_translation
const char * research_advance_name_translation(const struct research *presearch, Tech_type_id tech)
Definition research.c:273
research_get
struct research * research_get(const struct player *pplayer)
Definition research.c:128
research_invention_state
enum tech_state research_invention_state(const struct research *presearch, Tech_type_id tech)
Definition research.c:619
research_invention_gettable
bool research_invention_gettable(const struct research *presearch, const Tech_type_id tech, bool allow_holes)
Definition research.c:693
research.h
MAX
#define MAX(x, y)
Definition shared.h:54
sprite_g.h
y
struct sprite int int y
Definition sprite_g.h:31
x
struct sprite int x
Definition sprite_g.h:31
get_sprite_dimensions
struct sprite int int int int struct sprite int int float bool smooth get_sprite_dimensions
Definition sprite_g.h:36
advance
Definition tech.h:124
canvas
Definition canvas.h:22
client_options::reqtree_show_icons
bool reqtree_show_icons
Definition options.h:222
client_options::reqtree_curved_lines
bool reqtree_curved_lines
Definition options.h:223
color
Definition colors.h:21
color::color
GdkRGBA color
Definition colors.h:22
node_and_float
Definition reqtree.c:686
node_and_float::node
struct tree_node * node
Definition reqtree.c:687
node_and_float::value
float value
Definition reqtree.c:688
player
Definition player.h:249
reqtree
Definition repodlgs.cpp:85
reqtree::num_nodes
int num_nodes
Definition repodlgs.cpp:86
reqtree::nodes
struct tree_node ** nodes
Definition repodlgs.cpp:87
reqtree::layer_size
int * layer_size
Definition repodlgs.cpp:89
reqtree::diagram_height
int diagram_height
Definition repodlgs.cpp:91
reqtree::diagram_width
int diagram_width
Definition repodlgs.cpp:91
reqtree::layers
struct tree_node *** layers
Definition repodlgs.cpp:90
reqtree::num_layers
int num_layers
Definition repodlgs.cpp:88
research
Definition research.h:39
research::researching
Tech_type_id researching
Definition research.h:52
research::tech_goal
Tech_type_id tech_goal
Definition research.h:83
sprite
Definition sprite.h:22
tileset
Definition tilespec.c:482
tree_node
Definition repodlgs.cpp:70
tree_node::tech
Tech_type_id tech
Definition repodlgs.cpp:72
tree_node::nprovide
int nprovide
Definition repodlgs.cpp:75
tree_node::number
int number
Definition repodlgs.cpp:79
tree_node::provide
struct tree_node ** provide
Definition repodlgs.cpp:76
tree_node::node_width
int node_width
Definition repodlgs.cpp:78
tree_node::node_y
int node_y
Definition repodlgs.cpp:78
tree_node::layer
int layer
Definition repodlgs.cpp:77
tree_node::node_x
int node_x
Definition repodlgs.cpp:78
tree_node::order
int order
Definition repodlgs.cpp:77
tree_node::is_dummy
bool is_dummy
Definition repodlgs.cpp:71
tree_node::node_height
int node_height
Definition repodlgs.cpp:78
tree_node::nrequire
int nrequire
Definition repodlgs.cpp:73
tree_node::require
struct tree_node ** require
Definition repodlgs.cpp:74
TRUE
#define TRUE
Definition support.h:46
FALSE
#define FALSE
Definition support.h:47
advance_by_number
struct advance * advance_by_number(const Tech_type_id atype)
Definition tech.c:107
valid_advance_by_number
struct advance * valid_advance_by_number(const Tech_type_id id)
Definition tech.c:176
advance_required
Tech_type_id advance_required(const Tech_type_id tech, enum tech_req require)
Definition tech.c:121
advance_number
Tech_type_id advance_number(const struct advance *padvance)
Definition tech.c:98
tech.h
advance_index_iterate_max
#define advance_index_iterate_max(_start, _index, _max)
Definition tech.h:253
AR_TWO
@ AR_TWO
Definition tech.h:112
AR_ONE
@ AR_ONE
Definition tech.h:111
advance_index_iterate_max_end
#define advance_index_iterate_max_end
Definition tech.h:259
advance_count
static Tech_type_id advance_count(void)
Definition tech.h:170
A_FIRST
#define A_FIRST
Definition tech.h:44
A_NONE
#define A_NONE
Definition tech.h:43
A_LAST
#define A_LAST
Definition tech.h:45
get_government_sprite
struct sprite * get_government_sprite(const struct tileset *t, const struct government *gov)
Definition tilespec.c:6832
get_building_sprite
struct sprite * get_building_sprite(const struct tileset *t, const struct impr_type *pimprove)
Definition tilespec.c:6822
get_unittype_sprite
struct sprite * get_unittype_sprite(const struct tileset *t, const struct unit_type *punittype, enum unit_activity activity, enum direction8 facing)
Definition tilespec.c:6844
tilespec.h
is_tech_req_for_utype
bool is_tech_req_for_utype(const struct unit_type *ptype, struct advance *padv)
Definition unittype.c:2710
unit_type_iterate
#define unit_type_iterate(_p)
Definition unittype.h:859
unit_type_iterate_end
#define unit_type_iterate_end
Definition unittype.h:866