Freeciv-3.3
Loading...
Searching...
No Matches
Data Structures | Enumerations | Functions
reqtree.c File Reference
#include <stdarg.h>
#include <string.h>
#include "log.h"
#include "government.h"
#include "improvement.h"
#include "research.h"
#include "tech.h"
#include "client_main.h"
#include "options.h"
#include "tilespec.h"
#include "reqtree.h"
#include "colors_g.h"
#include "sprite_g.h"

Go to the source code of this file.

Data Structures

struct  tree_node
 
struct  reqtree
 
struct  node_and_float
 

Enumerations

enum  reqtree_edge_type {
  REQTREE_EDGE = 0 , REQTREE_READY_EDGE , REQTREE_KNOWN_EDGE , REQTREE_ACTIVE_EDGE ,
  REQTREE_GOAL_EDGE
}
 

Functions

static void add_requirement (struct tree_node *node, struct tree_node *req)
 
static struct tree_nodenew_tree_node (void)
 
static void node_rectangle_minimum_size (struct tree_node *node, int *width, int *height)
 
static void symmetrize (struct reqtree *tree)
 
static void calculate_diagram_layout (struct reqtree *tree)
 
static struct reqtreecreate_dummy_reqtree (struct player *pplayer, bool show_all)
 
void destroy_reqtree (struct reqtree *tree)
 
static int longest_path (struct tree_node *node)
 
static void longest_path_layering (struct reqtree *tree)
 
static int max_provide_layer (struct tree_node *node)
 
static struct reqtreeadd_dummy_nodes (struct reqtree *tree)
 
static void set_layers (struct reqtree *tree)
 
static int cmp_func (const void *_a, const void *_b)
 
static void barycentric_sort (struct reqtree *tree, int layer)
 
static int count_crossings (struct reqtree *tree, int layer)
 
static void swap (struct reqtree *tree, int layer, int order1, int order2)
 
static void improve (struct reqtree *tree)
 
struct reqtreecreate_reqtree (struct player *pplayer, bool show_all)
 
void get_reqtree_dimensions (struct reqtree *reqtree, int *width, int *height)
 
static enum color_std node_color (struct tree_node *node)
 
static enum reqtree_edge_type get_edge_type (struct tree_node *node, struct tree_node *dest_node)
 
static enum color_std edge_color (struct tree_node *node, struct tree_node *dest_node)
 
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)
 

Enumeration Type Documentation

◆ reqtree_edge_type

Enumerator
REQTREE_EDGE 
REQTREE_READY_EDGE 
REQTREE_KNOWN_EDGE 
REQTREE_ACTIVE_EDGE 
REQTREE_GOAL_EDGE 

Definition at line 109 of file reqtree.c.

Function Documentation

◆ add_dummy_nodes()

static struct reqtree * add_dummy_nodes ( struct reqtree tree)
static

Create new tree which has dummy nodes added. The source tree is completely copied, you can freely deallocate it.

Definition at line 553 of file reqtree.c.

Referenced by create_reqtree().

◆ add_requirement()

static void add_requirement ( struct tree_node node,
struct tree_node req 
)
static

Add requirement edge to node and provide edge to req

Definition at line 120 of file reqtree.c.

Referenced by add_dummy_nodes(), and create_dummy_reqtree().

◆ barycentric_sort()

static void barycentric_sort ( struct reqtree tree,
int  layer 
)
static

Simple heuristic: Sort nodes on the given layer by the average x-value of its parents.

Definition at line 712 of file reqtree.c.

Referenced by create_reqtree().

◆ calculate_diagram_layout()

static void calculate_diagram_layout ( struct reqtree tree)
static

Calculate rectangles position and size from the tree. Logical order should already be calculated.

Definition at line 297 of file reqtree.c.

Referenced by create_reqtree().

◆ cmp_func()

static int cmp_func ( const void _a,
const void _b 
)
static

Comparison function used by barycentric_sort().

Definition at line 694 of file reqtree.c.

Referenced by barycentric_sort().

◆ count_crossings()

static int count_crossings ( struct reqtree tree,
int  layer 
)
static

Calculate number of edge crossings between layer and layer + 1

Definition at line 745 of file reqtree.c.

Referenced by improve().

◆ create_dummy_reqtree()

static struct reqtree * create_dummy_reqtree ( struct player pplayer,
bool  show_all 
)
static

Create a "dummy" tech tree from current ruleset. This tree is then fleshed out further (see create_reqtree() ). This tree doesn't include dummy edges. Layering and ordering isn't done also.

If pplayer is given, add only techs reachable by that player to tree.

Definition at line 397 of file reqtree.c.

Referenced by create_reqtree().

◆ create_reqtree()

struct reqtree * create_reqtree ( struct player pplayer,
bool  show_all 
)

Generate optimized tech_tree from current ruleset. You should free it by destroy_reqtree().

If pplayer is not NULL, techs unreachable to that player are not shown.

Definition at line 847 of file reqtree.c.

Referenced by research_diagram::reset(), and science_diagram_data().

◆ destroy_reqtree()

void destroy_reqtree ( struct reqtree tree)

Free all memory used by tech_tree struct

Definition at line 478 of file reqtree.c.

Referenced by create_reqtree(), research_diagram::reset(), science_diagram_data(), and research_diagram::~research_diagram().

◆ 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 
)

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).

Definition at line 1045 of file reqtree.c.

Referenced by science_diagram_update(), science_diagram_update(), and research_diagram::update_reqtree().

◆ edge_color()

static enum color_std edge_color ( struct tree_node node,
struct tree_node dest_node 
)
static

Return a stroke color for an edge between two nodes. If node is a dummy, dest_node can be NULL

Definition at line 1019 of file reqtree.c.

Referenced by draw_reqtree().

◆ find_tech_on_reqtree()

bool find_tech_on_reqtree ( struct reqtree tree,
Tech_type_id  tech,
int x,
int y,
int w,
int h 
)

Return the position of the given tech on the reqtree. Return TRUE iff it was found.

Definition at line 1209 of file reqtree.c.

Referenced by science_diagram_center().

◆ get_edge_type()

static enum reqtree_edge_type get_edge_type ( struct tree_node node,
struct tree_node dest_node 
)
static

Return the type for an edge between two nodes. If node is a dummy, dest_node can be NULL

Definition at line 947 of file reqtree.c.

Referenced by edge_color(), and get_edge_type().

◆ get_reqtree_dimensions()

void get_reqtree_dimensions ( struct reqtree reqtree,
int width,
int height 
)

Give the dimensions of the reqtree.

Definition at line 878 of file reqtree.c.

Referenced by research_diagram::reset(), science_diagram_center(), science_diagram_data(), science_diagram_update(), and science_diagram_update().

◆ get_tech_on_reqtree()

Tech_type_id get_tech_on_reqtree ( struct reqtree tree,
int  x,
int  y 
)

Return the tech ID at the given position of the reqtree (or A_NONE).

Definition at line 1185 of file reqtree.c.

Referenced by research_diagram::mousePressEvent(), science_diagram_button_release_callback(), science_diagram_left_button_up(), and science_diagram_right_button_up().

◆ improve()

static void improve ( struct reqtree tree)
static

Try to reduce the number of crossings by swapping two nodes and checking if it improves the situation.

Definition at line 791 of file reqtree.c.

Referenced by create_reqtree().

◆ longest_path()

static int longest_path ( struct tree_node node)
static

Compute the longest path from this tree_node to the node with no requirements. Store the result in node->layer.

Definition at line 503 of file reqtree.c.

Referenced by longest_path(), and longest_path_layering().

◆ longest_path_layering()

static void longest_path_layering ( struct reqtree tree)
static

Compute longest_path for all nodes, thus prepare longest path layering

Definition at line 521 of file reqtree.c.

Referenced by create_reqtree().

◆ max_provide_layer()

static int max_provide_layer ( struct tree_node node)
static

Find the largest value of layer amongst children of the given node

Definition at line 535 of file reqtree.c.

Referenced by add_dummy_nodes().

◆ new_tree_node()

static struct tree_node * new_tree_node ( void  )
static

Allocate and initialize new tree node

Definition at line 141 of file reqtree.c.

Referenced by add_dummy_nodes(), and create_dummy_reqtree().

◆ node_color()

static enum color_std node_color ( struct tree_node node)
static

Return a background color of node's rectangle

Definition at line 892 of file reqtree.c.

Referenced by draw_reqtree().

◆ node_rectangle_minimum_size()

static void node_rectangle_minimum_size ( struct tree_node node,
int width,
int height 
)
static

Return minimum size of the rectangle in pixels on the diagram which corresponds to the given node

Definition at line 159 of file reqtree.c.

Referenced by calculate_diagram_layout().

◆ set_layers()

static void set_layers ( struct reqtree tree)
static

Calculate layers[] and layer_size[] fields of tree. There should be layer value calculated for each node. Nodes will be put into layers in no particular order.

Definition at line 646 of file reqtree.c.

Referenced by create_reqtree().

◆ swap()

static void swap ( struct reqtree tree,
int  layer,
int  order1,
int  order2 
)
static

Swap positions of two nodes on the same layer

Definition at line 776 of file reqtree.c.

Referenced by improve().

◆ symmetrize()

static void symmetrize ( struct reqtree tree)
static

Move nodes up and down without changing order but making it more symmetrical. Gravitate towards parents average position.

Definition at line 238 of file reqtree.c.

Referenced by calculate_diagram_layout().