Freeciv-3.2: /fast/freeciv/nightly/S3_2/client/reqtree.c Source File

Freeciv-3.2

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