[Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
<URL: http://bugs.freeciv.org/Ticket/Display.html?id=12719 >
For reasons that may become apparent in the fullness of time, I think it
should be called a reqtree not a techtree.
This patch changes that and also cleans up style and adds some comments.
Mateusz, I think it's ready for committing. Anything else you want to
do with it?
Side note: the longest path is 18 nodes. There is only one such path.
Changing just 2 techs lowers the longest path to 16 nodes. This makes
the tree narrower and prettier. The effect on gameplay is probably small.
-jason
Index: data/default/techs.ruleset
===================================================================
RCS file: /home/freeciv/CVS/freeciv/data/default/techs.ruleset,v
retrieving revision 1.25
diff -u -r1.25 techs.ruleset
--- data/default/techs.ruleset 17 Dec 2004 00:14:16 -0000 1.25
+++ data/default/techs.ruleset 12 Apr 2005 21:49:30 -0000
@@ -380,7 +380,7 @@
[advance_laser]
name = _("Laser")
req1 = "Mass Production"
-req2 = "Nuclear Power"
+req2 = "Nuclear Fission"
flags = ""
graphic = "a.laser"
graphic_alt = "-"
@@ -435,7 +435,7 @@
[advance_mass_production]
name = _("Mass Production")
-req1 = "Automobile"
+req1 = "Combustion"
req2 = "The Corporation"
flags = "Population_Pollution_Inc"
graphic = "a.mass_production"
Index: client/Makefile.am
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/Makefile.am,v
retrieving revision 1.63
diff -u -r1.63 Makefile.am
--- client/Makefile.am 31 Mar 2005 17:28:02 -0000 1.63
+++ client/Makefile.am 12 Apr 2005 21:49:23 -0000
@@ -182,6 +182,8 @@
options.h \
repodlgs_common.c \
repodlgs_common.h \
+ reqtree.c \
+ reqtree.h \
text.c \
text.h \
tilespec.c \
Index: client/reqtree.c
===================================================================
RCS file: client/reqtree.c
diff -N client/reqtree.c
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ client/reqtree.c 12 Apr 2005 21:49:23 -0000
@@ -0,0 +1,875 @@
+/**********************************************************************
+ Copyright (C) 2005 The Freeciv Project
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+***********************************************************************/
+
+#ifdef HAVE_CONFIG_H
+#include <config.h>
+#endif
+
+#include <assert.h>
+#include <log.h>
+#include <stdarg.h>
+#include <string.h>
+
+#include "game.h"
+#include "tech.h"
+
+#include "colors_g.h"
+
+#include "reqtree.h"
+
+/****************************************************************************
+ This structure desribes a node in a technology tree diagram.
+ A node can by dummy or real. Real node describes a technology.
+****************************************************************************/
+struct tree_node {
+ bool is_dummy;
+ Tech_Type_id tech;
+
+ int nrequire;
+ struct tree_node **require;
+
+ int nprovide;
+ struct tree_node **provide;
+
+ /* Note that y means a layer and x ordering in that layer */
+ int layer, order;
+
+ /* Coordinates of the rectangle on the diagram */
+ int node_x, node_y, node_width, node_height;
+
+ /* for general purpose */
+ int number;
+};
+
+/****************************************************************************
+ Structure which describes abstract technology diagram.
+ Nodes are ordered inside layers[] table.
+****************************************************************************/
+struct reqtree {
+ int num_nodes;
+ struct tree_node **nodes;
+
+ int num_layers;
+ int *layer_size;
+ struct tree_node ***layers;
+
+ int diagram_width, diagram_height;
+};
+
+
+/*************************************************************************
+ Add requirement edge to node and provide edge to req
+*************************************************************************/
+static void add_requirement(struct tree_node *node, struct tree_node *req)
+{
+ node->require =
+ fc_realloc(node->require,
+ sizeof(*node->require) * (node->nrequire + 1));
+ node->require[node->nrequire] = req;
+ node->nrequire++;
+
+ req->provide =
+ fc_realloc(req->provide,
+ sizeof(*req->provide) * (req->nprovide + 1));
+ req->provide[req->nprovide] = node;
+ req->nprovide++;
+}
+
+/*************************************************************************
+ Allocate and init new tree node
+*************************************************************************/
+static struct tree_node *new_tree_node(void)
+{
+ struct tree_node *node = fc_malloc(sizeof(*node));
+
+ node->nrequire = 0;
+ node->nprovide = 0;
+ node->require = NULL;
+ node->provide = NULL;
+ node->layer = -1;
+ node->order = -1;
+ return node;
+}
+
+/****************************************************************************
+ Return minimum size of the rectangle on the diagram which
+ corresponds to the given node
+****************************************************************************/
+static void node_rectangle_minimum_size(struct tree_node *node,
+ int *width, int *height)
+{
+ if (node->is_dummy) {
+ *width = *height = 1;
+ } else {
+ get_text_size(width, height, FONT_REQTREE_TEXT,
+ get_tech_name(game.player_ptr, node->tech));
+ *width += 2;
+ *height += 8;
+ }
+}
+
+/****************************************************************************
+ Move nodes up and down without changing order but making it more
+ symetrical. Gravitate towards parents average position
+****************************************************************************/
+static void symmetrize(struct reqtree* tree)
+{
+ int layer;
+ int i, j;
+
+ for (layer = 0; layer < tree->num_layers; layer++) {
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+ int v, node_y, node_height;
+
+ if (node->nrequire == 0) {
+ continue;
+ }
+ v = 0;
+ for (j = 0; j < node->nrequire; j++) {
+ struct tree_node *node_require = node->require[j];
+
+ v += node_require->node_y + node_require->node_height / 2;
+ }
+ v /= node->nrequire;
+ node_y = node->node_y;
+ node_height = node->node_height;
+ if (v < node_y + node_height / 2) {
+ if (node_y <= 0) {
+ continue;
+ }
+ if (i > 0) {
+ struct tree_node *node_above = tree->layers[layer][i - 1];
+
+ if (node_above->node_y
+ + node_above->node_height >= node_y - 11) {
+ continue;
+ }
+ }
+ node_y--;
+ } else if (v > node_y + node_height / 2) {
+ if (node_y + node_height >= tree->diagram_height - 1) {
+ continue;
+ }
+ if (i < tree->layer_size[layer] - 1) {
+ struct tree_node* node_below = tree->layers[layer][i + 1];
+
+ if (node_y + node_height >= node_below->node_y - 11) {
+ continue;
+ }
+ }
+ node_y++;
+ }
+ node->node_y = node_y;
+ }
+ }
+}
+
+/****************************************************************************
+ Calculate rectangles position and size from current tech_tree
+****************************************************************************/
+static void calculate_diagram_layout(struct reqtree *tree)
+{
+ int i, layer, layer_offs;
+
+ /* calculate minimum size of rectangle for each node */
+ for (i = 0; i < tree->num_nodes; i++) {
+ struct tree_node *node = tree->nodes[i];
+
+ node_rectangle_minimum_size(tree->nodes[i],
+ &node->node_width, &node->node_height);
+ node->number = i;
+ }
+
+ /* calculate height of the diagram. There should be at least 10 pixels
+ * beetween any two nodes */
+ tree->diagram_height = 0;
+ for (layer = 0; layer < tree->num_layers; layer++) {
+ int h_sum = 0;
+
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ h_sum += node->node_height;
+ if (i < tree->layer_size[layer] - 1) {
+ h_sum += 10;
+ }
+ }
+ tree->diagram_height = MAX(tree->diagram_height, h_sum);
+ }
+
+ /* calculate maximum width of node for each layer and enlarge other nodes
+ * calculate x offsets
+ */
+ layer_offs = 0;
+ for (layer = 0; layer < tree->num_layers; layer++) {
+ int max_width = 0;
+
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ max_width = MAX(max_width, node->node_width);
+ }
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ node->node_width = max_width;
+ node->node_x = layer_offs;
+ }
+ if (layer != tree->num_layers - 1) {
+ layer_offs += max_width * 5 / 4 + 80;
+ } else {
+ layer_offs += max_width + 10;
+ }
+ }
+ tree->diagram_width = layer_offs;
+
+ /* Calculate y-position of nodes on the diagram
+ * Distribute nodes steadily
+ */
+ for (layer = 0; layer < tree->num_layers; layer++) {
+ int y = 0;
+ int h_sum = 0;
+
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ h_sum += node->node_height;
+ }
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ node->node_y = y;
+ y += node->node_height;
+ if (tree->layer_size[layer] > 1) {
+ y += (tree->diagram_height - h_sum)
+ / (tree->layer_size[layer] - 1) - 1;
+ }
+ }
+ }
+
+ for (i = 0; i < tree->diagram_height; i++) {
+ symmetrize(tree);
+ }
+}
+
+/*************************************************************************
+ Create a "dummy" tech tree from current ruleset. This tree is then
+ fleshed out further (see create_reqtree).
+*************************************************************************/
+static struct reqtree *create_dummy_reqtree(void)
+{
+ /* Doesn't include dummy edges (?) */
+ struct reqtree *tree = fc_malloc(sizeof(*tree));
+ struct advance *advance;
+ int j;
+ struct tree_node *nodes[game.num_tech_types];
+
+ tech_type_iterate(tech) {
+ if (!tech_exists(tech) || tech == A_NONE) {
+ nodes[tech] = NULL;
+ continue;
+ }
+ nodes[tech] = new_tree_node();
+ nodes[tech]->is_dummy = FALSE;
+ nodes[tech]->tech = tech;
+ } tech_type_iterate_end;
+
+ tech_type_iterate(tech) {
+ if (!tech_exists(tech)) {
+ continue;
+ }
+ advance = &advances[tech];
+ if (advance->req[0] != A_NONE && advance->req[1] != A_LAST) {
+ if ((advance->req[1] != A_NONE
+ && !is_tech_a_req_for_goal(game.player_ptr, advance->req[0],
+ advance->req[1]))
+ || advance->req[1] == A_NONE) {
+ add_requirement(nodes[tech], nodes[advance->req[0]]);
+ }
+
+ if (advance->req[1] != A_NONE) {
+ if (!is_tech_a_req_for_goal(game.player_ptr, advance->req[1],
+ advance->req[0])) {
+ add_requirement(nodes[tech], nodes[advance->req[1]]);
+ }
+ }
+ }
+ } tech_type_iterate_end;
+
+ tree->nodes = fc_malloc(game.num_tech_types * sizeof(*tree->nodes));
+ j = 0;
+ tech_type_iterate(tech) {
+ if (nodes[tech]) {
+ tree->nodes[j] = nodes[tech];
+ assert(tech_exists(tree->nodes[j]->tech));
+ j++;
+ }
+ }
+ tech_type_iterate_end;
+ tree->num_nodes = j;
+ tree->layers = NULL;
+
+ return tree;
+}
+
+/*************************************************************************
+ Free all memory used by tech_tree struct
+*************************************************************************/
+void destroy_reqtree(struct reqtree *tree)
+{
+ int i;
+
+ for (i = 0; i < tree->num_nodes; i++) {
+ free(tree->nodes[i]->require);
+ free(tree->nodes[i]->provide);
+ free(tree->nodes[i]);
+ }
+ free(tree->nodes);
+ if (tree->layers) {
+ for (i = 0; i < tree->num_layers; i++) {
+ free(tree->layers[i]);
+ }
+ if (tree->layer_size) {
+ free(tree->layer_size);
+ }
+ }
+ free(tree);
+}
+
+/*************************************************************************
+ Compute the longest path from this tree_node to the node with
+ no requirements. Store the result int node->order
+*************************************************************************/
+static int longest_path(struct tree_node *node)
+{
+ int max, i;
+
+ if (node->order != -1) {
+ return node->order;
+ }
+ max = -1;
+ for (i = 0; i < node->nrequire; i++) {
+ max = MAX(max, longest_path(node->require[i]));
+ }
+ node->order = max + 1;
+ return node->order;
+}
+
+/*************************************************************************
+ Compute longest_path for all nodes, thus prepare longest path layering
+*************************************************************************/
+static void longest_path_layering(struct reqtree *tree)
+{
+ int i;
+
+ for (i = 0; i < tree->num_nodes; i++) {
+ if (tree->nodes[i]) {
+ longest_path(tree->nodes[i]);
+ }
+ }
+}
+
+/*************************************************************************
+ Find the largest value of y amongst children of the given node
+*************************************************************************/
+static int max_provide_layer(struct tree_node *node)
+{
+ int i;
+ int max = node->order;
+
+ for (i = 0; i < node->nprovide; i++) {
+ if (node->provide[i]->order > max) {
+ max = node->provide[i]->order;
+ }
+ }
+ return max;
+}
+
+/*************************************************************************
+ Create new tree which has dummy nodes added. The source tree is
+ completely copied, you can freely deallocate it.
+*************************************************************************/
+static struct reqtree *add_dummy_nodes(struct reqtree *tree)
+{
+ struct reqtree *new_tree;
+ int num_dummy_nodes = 0;
+ int k, i, j;
+
+ /* Count dummy nodes to be added */
+ for (i = 0; i < tree->num_nodes; i++) {
+ int mpl;
+
+ if (tree->nodes[i] == NULL) {
+ continue;
+ }
+ mpl = max_provide_layer(tree->nodes[i]);
+ if (mpl > tree->nodes[i]->order + 1) {
+ num_dummy_nodes += mpl - tree->nodes[i]->order - 1;
+ }
+ }
+
+ /* create new tree */
+ new_tree = fc_malloc(sizeof(*new_tree));
+ new_tree->nodes =
+ fc_malloc(sizeof(new_tree->nodes) *
+ (tree->num_nodes + num_dummy_nodes));
+ new_tree->num_nodes = tree->num_nodes + num_dummy_nodes;
+
+ /* copy normal nodes */
+ for (i = 0; i < tree->num_nodes; i++) {
+ new_tree->nodes[i] = new_tree_node();
+ new_tree->nodes[i]->is_dummy = FALSE;
+ new_tree->nodes[i]->tech = tree->nodes[i]->tech;
+ new_tree->nodes[i]->order = tree->nodes[i]->order;
+ tree->nodes[i]->number = i;
+ }
+
+ /* allocate dummy nodes */
+ for (i = 0; i < num_dummy_nodes; i++) {
+ new_tree->nodes[i + tree->num_nodes] = new_tree_node();
+ new_tree->nodes[i + tree->num_nodes]->is_dummy = TRUE;
+ }
+ /* k points to the first unused dummy node */
+ k = tree->num_nodes;
+
+ for (i = 0; i < tree->num_nodes; i++) {
+ struct tree_node *node = tree->nodes[i];
+ int mpl;
+
+ assert(!node->is_dummy);
+
+ mpl = max_provide_layer(node);
+
+ /* if this node will have dummy as ancestors, connect them in a chain */
+ if (mpl > node->order + 1) {
+ add_requirement(new_tree->nodes[k], new_tree->nodes[i]);
+ for (j = node->order + 2; j < mpl; j++) {
+ add_requirement(new_tree->nodes[k + j - node->order - 1],
+ new_tree->nodes[k + j - node->order - 2]);
+ }
+ for (j = node->order + 1; j < mpl; j++) {
+ new_tree->nodes[k + j - node->order - 1]->order = j;
+ }
+ }
+
+ /* copy all edges and create edges with dummy nodes */
+ for (j = 0; j < node->nprovide; j++) {
+ int provide_y = node->provide[j]->order;
+
+ if (provide_y == node->order + 1) {
+ /* direct connection */
+ add_requirement(new_tree->nodes[node->provide[j]->number],
+ new_tree->nodes[i]);
+ } else {
+ /* connection through dummy node */
+ add_requirement(new_tree->nodes[node->provide[j]->number],
+ new_tree->nodes[k + provide_y - node->order - 2]);
+ }
+ }
+
+ if (mpl > node->order + 1) {
+ k += mpl - node->order - 1;
+ assert(k <= new_tree->num_nodes);
+ }
+ }
+ new_tree->layers = NULL;
+
+ return new_tree;
+}
+
+/*************************************************************************
+ Calculate layers[] and layer_size[] fields of tree.
+ There should be y value calculated for each node.
+ Nodes will be put into layers in no particular order.
+*************************************************************************/
+static void set_layers(struct reqtree *tree)
+{
+ int i;
+ int num_layers = 0;
+
+ /* count total number of layers */
+ for (i = 0; i < tree->num_nodes; i++) {
+ num_layers = MAX(num_layers, tree->nodes[i]->order);
+ }
+ num_layers++;
+ tree->num_layers = num_layers;
+
+ {
+ /* counters for x */
+ int T[num_layers];
+
+ tree->layers = fc_malloc(sizeof(*tree->layers) * num_layers);
+ tree->layer_size = fc_malloc(sizeof(*tree->layer_size) * num_layers);
+ for (i = 0; i < num_layers; i++) {
+ T[i] = 0;
+ tree->layer_size[i] = 0;
+ }
+ for (i = 0; i < tree->num_nodes; i++) {
+ tree->layer_size[tree->nodes[i]->order]++;
+ }
+
+ for (i = 0; i < num_layers; i++) {
+ tree->layers[i] =
+ fc_malloc(sizeof(*tree->layers[i]) * tree->layer_size[i]);
+ }
+ for (i = 0; i < tree->num_nodes; i++) {
+ struct tree_node *node = tree->nodes[i];
+
+ tree->layers[node->order][T[node->order]] = node;
+ node->layer = T[node->order];
+ T[node->order]++;
+ }
+ }
+}
+
+struct node_and_float {
+ struct tree_node *node;
+ float value;
+};
+
+/*************************************************************************
+ Comparison function used by barycentric_sort.
+*************************************************************************/
+static int cmp_func(const void *_a, const void *_b)
+{
+ const struct node_and_float *a = _a, *b = _b;
+
+ if (a->value > b->value) {
+ return 1;
+ }
+ if (a->value < b->value) {
+ return -1;
+ }
+ return 0;
+}
+
+/*************************************************************************
+ Simple heuristic: Sort nodes on the given layer by the average x-value
+ of its' parents.
+*************************************************************************/
+static void barycentric_sort(struct reqtree *tree, int layer)
+{
+ struct node_and_float T[tree->layer_size[layer]];
+ int i, j;
+ float v;
+
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ T[i].node = node;
+ v = 0.0;
+ for (j = 0; j < node->nrequire; j++) {
+ v += node->require[j]->layer;
+ }
+ if (node->nrequire > 0) {
+ v /= (float) node->nrequire;
+ }
+ T[i].value = v;
+ }
+ qsort(T, tree->layer_size[layer], sizeof(*T),
+ cmp_func);
+
+ for (i = 0; i < tree->layer_size[layer]; i++) {
+ tree->layers[layer][i] = T[i].node;
+ T[i].node->layer = i;
+ }
+}
+
+/*************************************************************************
+ Calculate number of edge crossings beetwen layer and layer+1
+*************************************************************************/
+static int count_crossings(struct reqtree *tree, int layer)
+{
+ int layer1_size = tree->layer_size[layer];
+ int layer2_size = tree->layer_size[layer + 1];
+ int X[layer2_size];
+ int i, j, k;
+ int sum = 0;
+
+ for (i = 0; i < layer2_size; i++) {
+ X[i] = 0;
+ }
+
+ for (i = 0; i < layer1_size; i++) {
+ struct tree_node *node = tree->layers[layer][i];
+
+ for (j = 0; j < node->nprovide; j++) {
+ sum += X[node->provide[j]->layer];
+ }
+ for (j = 0; j < node->nprovide; j++) {
+ for (k = 0; k < node->provide[j]->layer; k++) {
+ X[k]++;
+ }
+ }
+ }
+
+ return sum;
+}
+
+/*************************************************************************
+ Swap positions of two nodes on the same layer
+*************************************************************************/
+static void swap(struct reqtree *tree, int layer, int layer1, int layer2)
+{
+ struct tree_node *node1 = tree->layers[layer][layer1];
+ struct tree_node *node2 = tree->layers[layer][layer2];
+
+ tree->layers[layer][layer1] = node2;
+ tree->layers[layer][layer2] = node1;
+ node1->layer = layer2;
+ node2->layer = layer1;
+}
+
+/*************************************************************************
+ Try to reduce the number of crossings by swapping two nodes and checking
+ if it improves the situation.
+*************************************************************************/
+static void improve(struct reqtree *tree)
+{
+ int crossings[tree->num_layers - 1];
+ int i, x1, x2, layer;
+
+ for (i = 0; i < tree->num_layers - 1; i++) {
+ crossings[i] = count_crossings(tree, i);
+ }
+
+ for (layer = 0; layer < tree->num_layers; layer++) {
+ int layer_size = tree->layer_size[layer];
+ int layer_sum = 0;
+
+ if (layer > 0) {
+ layer_sum += crossings[layer - 1];
+ }
+ if (layer < tree->num_layers - 1) {
+ layer_sum += crossings[layer];
+ }
+
+ for (x1 = 0; x1 < layer_size; x1++) {
+ for (x2 = x1 + 1; x2 < layer_size; x2++) {
+ int new_crossings = 0;
+ int new_crossings_before = 0;
+
+ swap(tree, layer, x1, x2);
+ if (layer > 0) {
+ new_crossings_before += count_crossings(tree, layer - 1);
+ }
+ if (layer < tree->num_layers - 1) {
+ new_crossings += count_crossings(tree, layer);
+ }
+ if (new_crossings + new_crossings_before > layer_sum) {
+ swap(tree, layer, x1, x2);
+ } else {
+ layer_sum = new_crossings + new_crossings_before;
+ if (layer > 0) {
+ crossings[layer - 1] = new_crossings_before;
+ }
+ if (layer < tree->num_layers - 1) {
+ crossings[layer] = new_crossings;
+ }
+ }
+ }
+ }
+ }
+}
+
+/*************************************************************************
+ Generate optimized tech_tree from current ruleset
+*************************************************************************/
+struct reqtree *create_reqtree(void)
+{
+ struct reqtree *tree1, *tree2;
+ int i, j;
+
+ tree1 = create_dummy_reqtree();
+ longest_path_layering(tree1);
+ tree2 = add_dummy_nodes(tree1);
+ destroy_reqtree(tree1);
+ set_layers(tree2);
+
+ /* It's good heuristics for beginning */
+ for (j = 0; j < 20; j++) {
+ for (i = 0; i < tree2->num_layers; i++) {
+ barycentric_sort(tree2, i);
+ }
+ }
+
+ /* Now burn some CPU */
+ for (j = 0; j < 20; j++) {
+ improve(tree2);
+ }
+
+ calculate_diagram_layout(tree2);
+
+ return tree2;
+}
+
+/****************************************************************************
+ Give the dimensions of the reqtree.
+****************************************************************************/
+void get_reqtree_dimensions(struct reqtree *reqtree,
+ int *width, int *height)
+{
+ if (width) {
+ *width = reqtree->diagram_width;
+ }
+ if (height){
+ *height = reqtree->diagram_height;
+ }
+}
+
+/****************************************************************************
+ Return a background color of node's rectangle
+****************************************************************************/
+static enum color_std node_color(struct tree_node *node)
+{
+ if (!node->is_dummy) {
+ if (game.player_ptr->research->researching == node->tech) {
+ return COLOR_STD_CYAN;
+ }
+
+ if (get_invention(game.player_ptr, node->tech) == TECH_KNOWN) {
+ return COLOR_STD_GROUND;
+ }
+
+ if (is_tech_a_req_for_goal(game.player_ptr, node->tech,
+ game.player_ptr->ai.tech_goal)
+ || node->tech == game.player_ptr->ai.tech_goal) {
+ if (get_invention(game.player_ptr, node->tech) == TECH_REACHABLE) {
+ return COLOR_STD_RACE8;
+ } else {
+ return COLOR_STD_RACE3;
+ }
+ }
+
+ if (get_invention(game.player_ptr, node->tech) == TECH_REACHABLE) {
+ return COLOR_STD_YELLOW;
+ }
+
+ return COLOR_STD_RED;
+ } else {
+ return COLOR_STD_BLACK;
+ }
+
+}
+
+/****************************************************************************
+ Draw the reqtree diagram!
+
+ This draws the given portion of the reqtree diagram (given by
+ (tt_x,tt_y) and (w,h) onto the canvas at position (canvas_x, canvas_y).
+****************************************************************************/
+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)
+{
+ int i, j, k;
+
+ /* draw the diagram */
+ for (i = 0; i < tree->num_layers; i++) {
+ for (j = 0; j < tree->layer_size[i]; j++) {
+ struct tree_node *node = tree->layers[i][j];
+ int startx, starty, endx, endy, width, height;
+
+ startx = node->node_x;
+ starty = node->node_y;
+ width = node->node_width;
+ height = node->node_height;
+
+ canvas_put_rectangle(pcanvas, COLOR_STD_BLACK,
+ startx, starty, width, height);
+
+ if (!node->is_dummy) {
+ const char *text = get_tech_name(game.player_ptr, node->tech);
+ int text_w, text_h;
+
+ /* Print color rectangle with text inside. */
+ canvas_put_rectangle(pcanvas, node_color(node),
+ startx + 1, starty + 1,
+ width - 2, height - 2);
+ get_text_size(&text_w, &text_h, FONT_REQTREE_TEXT, text);
+
+ canvas_put_text(pcanvas,
+ startx + (width - text_w) / 2,
+ starty + (height - text_h) / 2,
+ FONT_REQTREE_TEXT, COLOR_STD_BLACK, text);
+ }
+
+ /* Draw all outgoing edges */
+ startx = node->node_x + node->node_width;
+ starty = node->node_y + node->node_height / 2;
+ for (k = 0; k < node->nprovide; k++) {
+ struct tree_node *dest_node = node->provide[k];
+
+ endx = dest_node->node_x;
+ endy = dest_node->node_y + dest_node->node_height / 2;
+
+ canvas_put_line(pcanvas, COLOR_STD_BLACK, LINE_NORMAL,
+ startx, starty, endx - startx, endy - starty);
+ }
+ }
+ }
+}
+
+/****************************************************************************
+ Return the tech ID at the given position of the reqtree (or A_NONE).
+****************************************************************************/
+Tech_Type_id get_tech_on_reqtree(struct reqtree *tree, int x, int y)
+{
+ int i;
+
+ for (i = 0; i < tree->num_nodes; i++) {
+ struct tree_node *node = tree->nodes[i];
+
+ if (node->is_dummy) {
+ continue;
+ }
+ if (node->node_x <= x && node->node_y <= y
+ && node->node_x + node->node_width > x
+ && node->node_y + node->node_height > y) {
+ return node->tech;
+ }
+ }
+ return A_NONE;
+}
+
+/****************************************************************************
+ Return the position of the given tech on the reqtree. Return TRUE iff
+ it was found.
+****************************************************************************/
+bool find_tech_on_reqtree(struct reqtree *tree, Tech_Type_id tech,
+ int *x, int *y, int *w, int *h)
+{
+ int i;
+
+ for (i = 0; i < tree->num_nodes; i++) {
+ struct tree_node *node = tree->nodes[i];
+
+ if (!node->is_dummy && node->tech == tech) {
+ if (x) {
+ *x = node->node_x;
+ }
+ if (y) {
+ *y = node->node_y;
+ }
+ if (w) {
+ *w = node->node_width;
+ }
+ if (h) {
+ *h = node->node_height;
+ }
+ return TRUE;
+ }
+ }
+ return FALSE;
+}
Index: client/reqtree.h
===================================================================
RCS file: client/reqtree.h
diff -N client/reqtree.h
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ client/reqtree.h 12 Apr 2005 21:49:23 -0000
@@ -0,0 +1,50 @@
+/**********************************************************************
+ Copyright (C) 2005 The Freeciv Project
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+***********************************************************************/
+
+#ifndef FC__REQTREE_H
+#define FC__REQTREE_H
+
+#include "canvas_g.h"
+
+/* Requirements Tree
+ *
+ * This file provides functions for drawing a tree-like graph of
+ * requirements. This can be used for creating an interactive diagram
+ * showing the dependencies of various sources.
+ *
+ * A tree must first be created with create_reqtree; this will do all of the
+ * calculations needed for the tree and is a fairly expensive operation.
+ * After creating the tree, the other functions may be used to access or
+ * draw it.
+ *
+ * Currently only techs are supported (as sources and requirements).
+ */
+
+struct reqtree;
+
+struct reqtree *create_reqtree(void);
+void destroy_reqtree(struct reqtree *tree);
+
+void get_reqtree_dimensions(struct reqtree *tree,
+ int *width, int *height);
+
+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);
+
+Tech_Type_id get_tech_on_reqtree(struct reqtree *tree, int x, int y);
+bool find_tech_on_reqtree(struct reqtree *tree, Tech_Type_id tech,
+ int *x, int *y, int *w, int *h);
+
+#endif
Index: client/gui-gtk-2.0/canvas.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/gui-gtk-2.0/canvas.c,v
retrieving revision 1.2
diff -u -r1.2 canvas.c
--- client/gui-gtk-2.0/canvas.c 28 Mar 2005 16:59:14 -0000 1.2
+++ client/gui-gtk-2.0/canvas.c 12 Apr 2005 21:49:23 -0000
@@ -263,8 +263,14 @@
}
static PangoLayout *layout;
-static PangoFontDescription **fonts[FONT_COUNT] = {&main_font,
- &city_productions_font};
+static struct {
+ PangoFontDescription **font;
+ bool shadowed;
+} fonts[FONT_COUNT] = {
+ {&main_font, TRUE},
+ {&city_productions_font, TRUE},
+ {&city_productions_font, FALSE} /* FIXME: should use separate font */
+};
/****************************************************************************
Return the size of the given text in the given font. This size should
@@ -280,7 +286,7 @@
layout = pango_layout_new(gdk_pango_context_get());
}
- pango_layout_set_font_description(layout, *fonts[font]);
+ pango_layout_set_font_description(layout, *fonts[font].font);
pango_layout_set_text(layout, text, -1);
pango_layout_get_pixel_extents(layout, &rect, NULL);
@@ -311,12 +317,18 @@
}
gdk_gc_set_foreground(civ_gc, colors_standard[color]);
- pango_layout_set_font_description(layout, *fonts[font]);
+ pango_layout_set_font_description(layout, *fonts[font].font);
pango_layout_set_text(layout, text, -1);
pango_layout_get_pixel_extents(layout, &rect, NULL);
- gtk_draw_shadowed_string(pcanvas->v.pixmap,
- toplevel->style->black_gc, civ_gc,
- canvas_x,
- canvas_y + PANGO_ASCENT(rect), layout);
+ if (fonts[font].shadowed) {
+ gtk_draw_shadowed_string(pcanvas->v.pixmap,
+ toplevel->style->black_gc, civ_gc,
+ canvas_x,
+ canvas_y + PANGO_ASCENT(rect), layout);
+ } else {
+ gdk_draw_layout(pcanvas->v.pixmap, civ_gc,
+ canvas_x, canvas_y + PANGO_ASCENT(rect),
+ layout);
+ }
}
Index: client/gui-gtk-2.0/repodlgs.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/gui-gtk-2.0/repodlgs.c,v
retrieving revision 1.82
diff -u -r1.82 repodlgs.c
--- client/gui-gtk-2.0/repodlgs.c 6 Apr 2005 17:36:15 -0000 1.82
+++ client/gui-gtk-2.0/repodlgs.c 12 Apr 2005 21:49:23 -0000
@@ -45,28 +45,25 @@
#include "options.h"
#include "packhand_gen.h"
#include "control.h"
+#include "reqtree.h"
#include "text.h"
+#include "canvas.h"
#include "repodlgs_common.h"
#include "repodlgs.h"
/******************************************************************/
static void create_science_dialog(bool make_modal);
-static void science_help_callback(GtkTreeView *view,
- GtkTreePath *arg1,
- GtkTreeViewColumn *arg2,
- gpointer data);
static void science_change_callback(GtkWidget * widget, gpointer data);
static void science_goal_callback(GtkWidget * widget, gpointer data);
-
/******************************************************************/
static struct gui_dialog *science_dialog_shell = NULL;
static GtkWidget *science_label;
static GtkWidget *science_current_label, *science_goal_label;
static GtkWidget *science_change_menu_button, *science_goal_menu_button;
static GtkWidget *science_help_toggle;
-static GtkListStore *science_model[3];
+static GtkWidget *science_drawing_area;
static int science_dialog_shell_is_modal;
static GtkWidget *popupmenu, *goalmenu;
@@ -163,7 +160,99 @@
gui_dialog_destroy(science_dialog_shell);
}
}
-
+
+/****************************************************************************
+ Change tech goal, research or open help dialog
+****************************************************************************/
+static void button_release_event_callback(GtkWidget *widget,
+ GdkEventButton *event,
+ gpointer *data)
+{
+ struct reqtree *tree = g_object_get_data(G_OBJECT(widget), "reqtree");
+ int x = event->x, y = event->y;
+ Tech_Type_id tech = get_tech_on_reqtree(tree, x, y);
+
+ if (tech == A_NONE) {
+ return;
+ }
+ if (event->button == 1) {
+ /* LMB: set research or research goal */
+ switch (get_invention(game.player_ptr, tech)) {
+ case TECH_REACHABLE:
+ dsend_packet_player_research(&aconnection, tech);
+ break;
+ case TECH_UNKNOWN:
+ dsend_packet_player_tech_goal(&aconnection, tech);
+ break;
+ case TECH_KNOWN:
+ break;
+ }
+ } else if (event->button == 3) {
+ /* RMB: get help */
+ /* FIXME: this should work for ctrl+LMB or shift+LMB (?) too */
+ popup_help_dialog_typed(get_tech_name(game.player_ptr, tech), HELP_TECH);
+ }
+}
+
+/****************************************************************************
+ Draw the invalidated portion of the reqtree.
+****************************************************************************/
+static void update_science_drawing_area(GtkWidget *widget, gpointer data)
+{
+ /* FIXME: this currently redraws everything! */
+ struct canvas canvas = {.type = CANVAS_PIXMAP,
+ .v.pixmap = GTK_LAYOUT(widget)->bin_window};
+ struct reqtree *reqtree = g_object_get_data(G_OBJECT(widget), "reqtree");
+ int width, height;
+
+ get_reqtree_dimensions(reqtree, &width, &height);
+ draw_reqtree(reqtree, &canvas, 0, 0, 0, 0, width, height);
+}
+
+/****************************************************************************
+ Return main widget of new technology diagram.
+ This is currently GtkScrolledWindow
+****************************************************************************/
+static GtkWidget *create_reqtree_diagram(void)
+{
+ GtkWidget *sw;
+ struct reqtree *reqtree = create_reqtree();
+ GtkAdjustment* adjustment;
+ int width, height;
+ int x;
+
+ get_reqtree_dimensions(reqtree, &width, &height);
+
+ sw = gtk_scrolled_window_new(NULL, NULL);
+ science_drawing_area = gtk_layout_new(NULL, NULL);
+ g_object_set_data_full(G_OBJECT(science_drawing_area), "reqtree", reqtree,
+ (GDestroyNotify)destroy_reqtree);
+ g_signal_connect(G_OBJECT(science_drawing_area), "expose_event",
+ G_CALLBACK(update_science_drawing_area), NULL);
+ g_signal_connect(G_OBJECT(science_drawing_area), "button-release-event",
+ G_CALLBACK(button_release_event_callback), NULL);
+ gtk_widget_add_events(science_drawing_area,
+ GDK_BUTTON_RELEASE_MASK | GDK_BUTTON2_MOTION_MASK |
+ GDK_BUTTON3_MOTION_MASK);
+
+ gtk_layout_set_size(GTK_LAYOUT(science_drawing_area), width, height);
+
+ gtk_container_add(GTK_CONTAINER(sw), science_drawing_area);
+ gtk_scrolled_window_set_policy(GTK_SCROLLED_WINDOW(sw),
+ GTK_POLICY_AUTOMATIC,
+ GTK_POLICY_AUTOMATIC);
+
+ adjustment = gtk_scrolled_window_get_hadjustment(GTK_SCROLLED_WINDOW(sw));
+
+ /* Center on currently researched node */
+ if (find_tech_on_reqtree(reqtree, game.player_ptr->research->researching,
+ &x, NULL, NULL, NULL)) {
+ /* FIXME: this is just an approximation */
+ gtk_adjustment_set_value(adjustment, x - 100);
+ }
+
+ return sw;
+}
/****************************************************************
...
@@ -171,7 +260,7 @@
void create_science_dialog(bool make_modal)
{
GtkWidget *frame, *hbox, *w;
- int i;
+ GtkWidget *science_diagram;
gui_dialog_new(&science_dialog_shell, GTK_NOTEBOOK(top_notebook));
gui_dialog_set_title(science_dialog_shell, _("Science"));
@@ -227,39 +316,9 @@
w = gtk_label_new("");
gtk_box_pack_start(GTK_BOX(hbox), w, TRUE, FALSE, 0);
-
- sw = gtk_scrolled_window_new(NULL, NULL);
- gtk_scrolled_window_set_policy(GTK_SCROLLED_WINDOW(sw),
- GTK_POLICY_AUTOMATIC, GTK_POLICY_ALWAYS);
- gtk_box_pack_start(GTK_BOX(science_dialog_shell->vbox), sw, TRUE, TRUE, 5);
-
- hbox = gtk_hbox_new(TRUE, 0);
- gtk_scrolled_window_add_with_viewport(GTK_SCROLLED_WINDOW(sw), hbox);
-
-
- for (i=0; i<ARRAY_SIZE(science_model); i++) {
- GtkWidget *view;
- GtkTreeSelection *selection;
- GtkCellRenderer *renderer;
- GtkTreeViewColumn *column;
-
- science_model[i] = gtk_list_store_new(1, G_TYPE_STRING);
- view = gtk_tree_view_new_with_model(GTK_TREE_MODEL(science_model[i]));
- gtk_box_pack_start(GTK_BOX(hbox), view, TRUE, TRUE, 0);
- gtk_widget_set_name(view, "small font");
- selection = gtk_tree_view_get_selection(GTK_TREE_VIEW(view));
- g_object_unref(science_model[i]);
- gtk_tree_view_columns_autosize(GTK_TREE_VIEW(view));
- gtk_tree_view_set_headers_visible(GTK_TREE_VIEW(view), FALSE);
-
- renderer = gtk_cell_renderer_text_new();
- column = gtk_tree_view_column_new_with_attributes(NULL, renderer,
- "text", 0, NULL);
- gtk_tree_view_append_column(GTK_TREE_VIEW(view), column);
-
- g_signal_connect(view, "row_activated",
- G_CALLBACK(science_help_callback), NULL);
- }
+
+ science_diagram = create_reqtree_diagram();
+ gtk_box_pack_start(GTK_BOX(science_dialog_shell->vbox), science_diagram,
TRUE, TRUE, 0);
gui_dialog_show_all(science_dialog_shell);
@@ -329,30 +388,6 @@
/****************************************************************
...
*****************************************************************/
-static void science_help_callback(GtkTreeView *view,
- GtkTreePath *arg1,
- GtkTreeViewColumn *arg2,
- gpointer data)
-{
- GtkTreeModel *model = gtk_tree_view_get_model(view);
-
- if (GTK_TOGGLE_BUTTON(science_help_toggle)->active) {
- GtkTreeIter it;
- char *s;
-
- gtk_tree_model_get_iter(model, &it, arg1);
- gtk_tree_model_get(model, &it, 0, &s, -1);
- if (*s != '\0') {
- popup_help_dialog_typed(s, HELP_TECH);
- } else {
- popup_help_dialog_string(HELP_TECHS_ITEM);
- }
- }
-}
-
-/****************************************************************
-...
-*****************************************************************/
static gint cmp_func(gconstpointer a_p, gconstpointer b_p)
{
const gchar *a_str, *b_str;
@@ -386,7 +421,7 @@
void science_dialog_update(void)
{
if(science_dialog_shell) {
- int i, j, hist;
+ int i, hist;
char text[512];
GtkWidget *item;
GList *sorting_list = NULL, *it;
@@ -398,12 +433,10 @@
return;
}
- gtk_label_set_text(GTK_LABEL(science_label), science_dialog_text());
-
- for (i=0; i<ARRAY_SIZE(science_model); i++) {
- gtk_list_store_clear(science_model[i]);
- }
+ gtk_widget_queue_draw(science_drawing_area);
+ gtk_label_set_text(GTK_LABEL(science_label), science_dialog_text());
+
/* collect all researched techs in sorting_list */
for(i=A_FIRST; i<game.num_tech_types; i++) {
if ((get_invention(game.player_ptr, i)==TECH_KNOWN)) {
@@ -413,19 +446,6 @@
/* sort them, and install them in the list */
sorting_list = g_list_sort(sorting_list, cmp_func);
- for(i=0; i<g_list_length(sorting_list); i++) {
- GtkTreeIter it;
- GValue value = { 0, };
-
- j = GPOINTER_TO_INT(g_list_nth_data(sorting_list, i));
- gtk_list_store_append(science_model[i%ARRAY_SIZE(science_model)], &it);
-
- g_value_init(&value, G_TYPE_STRING);
- g_value_set_static_string(&value, get_tech_name(game.player_ptr, j));
- gtk_list_store_set_value(science_model[i%ARRAY_SIZE(science_model)], &it,
- 0, &value);
- g_value_unset(&value);
- }
g_list_free(sorting_list);
sorting_list = NULL;
@@ -578,6 +598,7 @@
g_list_index(sorting_list, GINT_TO_POINTER(hist)));
g_list_free(sorting_list);
sorting_list = NULL;
+
}
}
Index: client/include/canvas_g.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/client/include/canvas_g.h,v
retrieving revision 1.3
diff -u -r1.3 canvas_g.h
--- client/include/canvas_g.h 28 Mar 2005 16:59:15 -0000 1.3
+++ client/include/canvas_g.h 12 Apr 2005 21:49:24 -0000
@@ -54,6 +54,7 @@
enum client_font {
FONT_CITY_NAME,
FONT_CITY_PROD,
+ FONT_REQTREE_TEXT,
FONT_COUNT
};
void get_text_size(int *width, int *height,
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, (continued)
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, Mateusz Stefek, 2005/04/05
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, Mateusz Stefek, 2005/04/05
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Benoit Hudson, 2005/04/05
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Vasco Alexandre da Silva Costa, 2005/04/05
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Jason Short, 2005/04/06
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, Jason Short, 2005/04/08
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Jason Short, 2005/04/08
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, Mateusz Stefek, 2005/04/09
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram, Mateusz Stefek, 2005/04/09
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Jason Short, 2005/04/09
- [Freeciv-Dev] (PR#12719) Automaticaly generated techtree diagram,
Jason Short <=
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Benoit Hudson, 2005/04/12
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Jason Short, 2005/04/12
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Christian Knoke, 2005/04/13
- [Freeciv-Dev] Re: (PR#12719) Automaticaly generated techtree diagram, Peter Schaefer, 2005/04/13
|
|
