Freeciv-3.1: /fast/freeciv/nightly/S3_1/client/reqtree.c Source File

Freeciv-3.1

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