Handles factions' safe lanes through systems. This implements the algorithm described in utils/lanes-generator (whitepaper and much clearer Python version). More...

#include "safelanes.h"
#include "array.h"
#include "conf.h"
#include "log.h"
#include "union_find.h"

Data Structures
struct	Vertex
	Reference to a spob or jump point. More...

struct	Faction
	Description of a lane-building faction. More...

Typedefs
typedef int	Edge[2]
	An edge is a pair of vertex indices.

typedef uint32_t	FactionMask
	A set of lane-building factions, represented as a bitfield.

Enumerations
enum	{ STORAGE_MODE_LOWER_TRIANGULAR_PART = -1 , STORAGE_MODE_UNSYMMETRIC = 0 , STORAGE_MODE_UPPER_TRIANGULAR_PART = +1 , SORTED = 1 , PACKED = 1 , MODE_NUMERICAL = 1 }

enum	VertexType { VERTEX_SPOB , VERTEX_JUMP }
	Object type: like SafeLaneLocType, but with Naev stack indexing in mind. More...

Functions
static int	safelanes_buildOneTurn (int iters_done)
	Run a round of optimization. Return how many builds (upper bound) have to happen next turn.

static int	safelanes_activateByGradient (cholmod_dense *Lambda_tilde, int iters_done)
	Per-system, per-faction, activates the affordable lane with best (grad phi)/L.

static void	safelanes_initStacks (void)
	Sets up the local faction/object stacks.

static void	safelanes_initStacks_edge (void)
	Sets up the local stacks with entry per edge. Faction stack must be set up.

static void	safelanes_initStacks_faction (void)
	Sets up the local stacks with entry per faction.

static void	safelanes_initStacks_vertex (void)
	Sets up the local stacks with entry per vertex (or per jump).

static void	safelanes_initStacks_anchor (void)
	Identifies anchor points: The universe graph (with in-system and 2-way-jump edges) could have many connected components. Our impedance problem needs one boundary condition for each, so we choose a representative vertex from each.

static void	safelanes_initOptimizer (void)
	Initializes resources used by lane optimization.

static void	safelanes_destroyOptimizer (void)
	Frees resources used by lane optimization.

static void	safelanes_destroyStacks (void)
	Tears down the local faction/object stacks.

static void	safelanes_destroyTmp (void)
	Tears down the local faction/object stacks.

static void	safelanes_initStiff (void)
	Sets up the stiffness matrix.

static double	safelanes_initialConductivity (int ei)
	Returns the initial conductivity value (1/length) for edge ei. The live value is stored in the stiffness matrix;.

static void	safelanes_updateConductivity (int ei_activated)
	Updates the stiffness matrix to account for the given edge being activated.

static void	safelanes_initQtQ (void)
	Sets up the (Q*)Q matrix.

static void	safelanes_initFTilde (void)
	Sets up the fluxes matrix f~.

static void	safelanes_initPPl (void)
	Sets up the PPl matrices appearing in the gradient formula.

static int	safelanes_triangleTooFlat (const vec2 m, const vec2 n, const vec2 *p, double lmn)
	Return true if this triangle is so flat that lanes from point m to point n aren't allowed.

static int	vertex_faction (int vi)
	Return the vertex's owning faction (ID, not faction_stack index), or -1 if not applicable.

static const vec2 *	vertex_pos (int vi)
	Return the vertex's coordinates within its system (by reference since our vec2's are fat).

static int	FACTION_ID_TO_INDEX (int id)
	Return the faction_stack index corresponding to a faction ID, or -1.

static FactionMask	MASK_ANY_FACTION ()
	Return a mask matching any faction.

static FactionMask	MASK_ONE_FACTION (int id)
	A mask giving this faction (NOT faction_stack index) exclusive rights to build, if it's a lane-building faction.

static FactionMask	MASK_COMPROMISE (int id1, int id2)
	A mask with appropriate lane-building rights given one faction ID owning each endpoint.

static int	cmp_key (const void p1, const void p2)
	It's a qsort comparator. Set the cmp_key_ref pointer prior to use, or else.

static void	triplet_entry (cholmod_triplet *m, int i, int j, double v)

static cholmod_dense *	safelanes_sliceByPresence (cholmod_dense m, double sysPresence)
	Construct the matrix-slice of m, selecting those rows where the corresponding presence value is positive.

static cholmod_dense *	ncholmod_ddmult (cholmod_dense A, int transA, cholmod_dense B)
	Dense times dense matrix. Return AB, or A'B if transA is true.

static double	safelanes_row_dot_row (cholmod_dense A, cholmod_dense B, int i, int j)
	Return the i,j entry of A*B', or equivalently the dot product of row i of A with row j of B.

static void	array_push_back_edge (Edge **a, int v0, int v1)
	Like array_push_back( a, Edge{v0, v1} ), but achievable in C. :-P.

void	safelanes_init (void)
	Initializes the safelanes system.

void	safelanes_destroy (void)
	Shuts down the safelanes system.

SafeLane *	safelanes_get (int faction, int standing, const StarSystem *system)
	Gets a set of safelanes for a faction and system.

void	safelanes_recalculate (void)
	Update the safe lane locations in response to the universe changing (e.g., diff applied).

int	safelanes_calculated (void)
	Whether or not the safe lanes have been calculated at least once.

Variables
static const double	ALPHA = 9.

static const double	LAMBDA = 2e10

static const double	JUMP_CONDUCTIVITY = 0.001

static const double	MIN_ANGLE = M_PI/18.

static const FactionMask	MASK_0 = 0

static const FactionMask	MASK_1 = 1

static cholmod_common	C

static Vertex *	vertex_stack

static FactionMask *	vertex_fmask

static int *	sys_to_first_vertex

static Edge *	edge_stack

static int *	sys_to_first_edge

static Faction *	faction_stack

static int *	lane_faction

static FactionMask *	lane_fmask

static double **	presence_budget

static int *	tmp_spob_indices

static Edge *	tmp_jump_edges

static double *	tmp_edge_conduct

static int *	tmp_anchor_vertices

static UnionFind	tmp_sys_uf

static cholmod_triplet *	stiff

static cholmod_sparse *	QtQ

static cholmod_dense *	ftilde

static cholmod_dense *	utilde

static cholmod_dense **	PPl

static double *	cmp_key_ref

static int	safelanes_calculated_once = 0

Detailed Description

Handles factions' safe lanes through systems. This implements the algorithm described in utils/lanes-generator (whitepaper and much clearer Python version).

Definition in file safelanes.c.

Typedef Documentation

◆ Edge

typedef int Edge[2]

An edge is a pair of vertex indices.

Definition at line 79 of file safelanes.c.

◆ FactionMask

typedef uint32_t FactionMask

A set of lane-building factions, represented as a bitfield.

Definition at line 89 of file safelanes.c.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
STORAGE_MODE_LOWER_TRIANGULAR_PART	A CHOLMOD "stype" value: matrix is interpreted as symmetric.
STORAGE_MODE_UNSYMMETRIC	A CHOLMOD "stype" value: matrix holds whatever we put in it.
STORAGE_MODE_UPPER_TRIANGULAR_PART	A CHOLMOD "stype" value: matrix is interpreted as symmetric.
SORTED	a named bool
PACKED	a named bool
MODE_NUMERICAL	yet another CHOLMOD magic number!

Definition at line 54 of file safelanes.c.

◆ VertexType

enum VertexType

Object type: like SafeLaneLocType, but with Naev stack indexing in mind.

Todo: Converge these after beefing up nlua APIs (#1862 or just jump point from internal indices).

Definition at line 69 of file safelanes.c.

Function Documentation

◆ array_push_back_edge()

static void array_push_back_edge	(	Edge **	a,
		int	v0,
		int	v1 )

inlinestatic

Like array_push_back( a, Edge{v0, v1} ), but achievable in C. :-P.

Definition at line 154 of file safelanes.c.

◆ cmp_key()

static int cmp_key	(	const void *	p1,
		const void *	p2 )

static

It's a qsort comparator. Set the cmp_key_ref pointer prior to use, or else.

Definition at line 838 of file safelanes.c.

◆ FACTION_ID_TO_INDEX()

static int FACTION_ID_TO_INDEX ( int id )

inlinestatic

Return the faction_stack index corresponding to a faction ID, or -1.

Definition at line 890 of file safelanes.c.

◆ MASK_ANY_FACTION()

static FactionMask MASK_ANY_FACTION ( )

inlinestatic

Return a mask matching any faction.

Definition at line 899 of file safelanes.c.

◆ MASK_COMPROMISE()

static FactionMask MASK_COMPROMISE	(	int	id1,
		int	id2 )

inlinestatic

A mask with appropriate lane-building rights given one faction ID owning each endpoint.

Definition at line 912 of file safelanes.c.

◆ MASK_ONE_FACTION()

static FactionMask MASK_ONE_FACTION ( int id )

inlinestatic

A mask giving this faction (NOT faction_stack index) exclusive rights to build, if it's a lane-building faction.

Definition at line 905 of file safelanes.c.

◆ ncholmod_ddmult()

static cholmod_dense * ncholmod_ddmult	(	cholmod_dense *	A,
		int	transA,
		cholmod_dense *	B )

static

Dense times dense matrix. Return A*B, or A'*B if transA is true.

Definition at line 956 of file safelanes.c.

◆ safelanes_activateByGradient()

static int safelanes_activateByGradient	(	cholmod_dense *	Lambda_tilde,
		int	iters_done )

static

Per-system, per-faction, activates the affordable lane with best (grad phi)/L.

Returns: How many builds (upper bound) have to happen next turn.

< Per faction index, the Lambda_tilde[myDofs,:] @ PPl[fi] matrices. Calloced and lazily populated.

< System si's U and Lambda rows start at sys_base; its lal rows start at lal_base.

Definition at line 696 of file safelanes.c.

◆ safelanes_buildOneTurn()

static int safelanes_buildOneTurn ( int iters_done )

static

Run a round of optimization. Return how many builds (upper bound) have to happen next turn.

Definition at line 311 of file safelanes.c.

◆ safelanes_calculated()

int safelanes_calculated ( void )

Whether or not the safe lanes have been calculated at least once.

Definition at line 276 of file safelanes.c.

◆ safelanes_destroy()

void safelanes_destroy ( void )

Shuts down the safelanes system.

Definition at line 176 of file safelanes.c.

◆ safelanes_destroyOptimizer()

static void safelanes_destroyOptimizer ( void )

static

Frees resources used by lane optimization.

Definition at line 296 of file safelanes.c.

◆ safelanes_destroyStacks()

static void safelanes_destroyStacks ( void )

static

Tears down the local faction/object stacks.

Definition at line 500 of file safelanes.c.

◆ safelanes_destroyTmp()

static void safelanes_destroyTmp ( void )

static

Tears down the local faction/object stacks.

Definition at line 528 of file safelanes.c.

◆ safelanes_get()

SafeLane * safelanes_get	(	int	faction,
		int	standing,
		const StarSystem *	system )

Gets a set of safelanes for a faction and system.

Parameters

faction	ID of the faction whose lanes we want, or a negative value signifying "all of them".
standing	Bit-mask indicating what standing to get.
system	Star system whose lanes we want.

Returns: Array (array.h) of matching SafeLane structures. Caller frees.

Definition at line 190 of file safelanes.c.

◆ safelanes_init()

void safelanes_init ( void )

Initializes the safelanes system.

Definition at line 164 of file safelanes.c.

◆ safelanes_initFTilde()

static void safelanes_initFTilde ( void )

static

Sets up the fluxes matrix f~.

Definition at line 628 of file safelanes.c.

◆ safelanes_initialConductivity()

static double safelanes_initialConductivity ( int ei )

static

Returns the initial conductivity value (1/length) for edge ei. The live value is stored in the stiffness matrix;.

See also: safelanes_initStiff above. When a lane is activated, its conductivity is updated to (1+ALPHA)/length.

Definition at line 582 of file safelanes.c.

◆ safelanes_initOptimizer()

static void safelanes_initOptimizer ( void )

static

Initializes resources used by lane optimization.

Definition at line 284 of file safelanes.c.

◆ safelanes_initPPl()

static void safelanes_initPPl ( void )

static

Sets up the PPl matrices appearing in the gradient formula.

Definition at line 641 of file safelanes.c.

◆ safelanes_initQtQ()

static void safelanes_initQtQ ( void )

static

Sets up the (Q*)Q matrix.

Definition at line 602 of file safelanes.c.

◆ safelanes_initStacks()

static void safelanes_initStacks ( void )

static

Sets up the local faction/object stacks.

Definition at line 341 of file safelanes.c.

◆ safelanes_initStacks_anchor()

static void safelanes_initStacks_anchor ( void )

static

Identifies anchor points: The universe graph (with in-system and 2-way-jump edges) could have many connected components. Our impedance problem needs one boundary condition for each, so we choose a representative vertex from each.

Definition at line 480 of file safelanes.c.

◆ safelanes_initStacks_edge()

static void safelanes_initStacks_edge ( void )

static

Sets up the local stacks with entry per edge. Faction stack must be set up.

Definition at line 405 of file safelanes.c.

◆ safelanes_initStacks_faction()

static void safelanes_initStacks_faction ( void )

static

Sets up the local stacks with entry per faction.

Definition at line 446 of file safelanes.c.

◆ safelanes_initStacks_vertex()

static void safelanes_initStacks_vertex ( void )

static

Sets up the local stacks with entry per vertex (or per jump).

Definition at line 353 of file safelanes.c.

◆ safelanes_initStiff()

static void safelanes_initStiff ( void )

static

Sets up the stiffness matrix.

Definition at line 544 of file safelanes.c.

◆ safelanes_recalculate()

void safelanes_recalculate ( void )

Update the safe lane locations in response to the universe changing (e.g., diff applied).

Definition at line 252 of file safelanes.c.

◆ safelanes_row_dot_row()

static double safelanes_row_dot_row	(	cholmod_dense *	A,
		cholmod_dense *	B,
		int	i,
		int	j )

static

Return the i,j entry of A*B', or equivalently the dot product of row i of A with row j of B.

Definition at line 974 of file safelanes.c.

◆ safelanes_sliceByPresence()

static cholmod_dense * safelanes_sliceByPresence	(	cholmod_dense *	m,
		double *	sysPresence )

static

Construct the matrix-slice of m, selecting those rows where the corresponding presence value is positive.

Definition at line 929 of file safelanes.c.

◆ safelanes_triangleTooFlat()

static int safelanes_triangleTooFlat	(	const vec2 *	m,
		const vec2 *	n,
		const vec2 *	p,
		double	lmn )

static

Return true if this triangle is so flat that lanes from point m to point n aren't allowed.

Definition at line 847 of file safelanes.c.

◆ safelanes_updateConductivity()

static void safelanes_updateConductivity ( int ei_activated )

static

Updates the stiffness matrix to account for the given edge being activated.

See also: safelanes_initStiff.

Definition at line 592 of file safelanes.c.

◆ triplet_entry()

static void triplet_entry	(	cholmod_triplet *	m,
		int	i,
		int	j,
		double	v )

inlinestatic

Definition at line 918 of file safelanes.c.

◆ vertex_faction()

static int vertex_faction ( int vi )

static

Return the vertex's owning faction (ID, not faction_stack index), or -1 if not applicable.

Definition at line 860 of file safelanes.c.

◆ vertex_pos()

static const vec2 * vertex_pos ( int vi )

static

Return the vertex's coordinates within its system (by reference since our vec2's are fat).

Definition at line 876 of file safelanes.c.

Variable Documentation

◆ ALPHA

const double ALPHA = 9.

static

Lane efficiency parameter.

Definition at line 50 of file safelanes.c.

◆ C

cholmod_common C

static

Parameter settings, statistics, and workspace used internally by CHOLMOD.

Definition at line 95 of file safelanes.c.

◆ cmp_key_ref

double* cmp_key_ref

static

To qsort() a list of indices by table value, point this at your table and use cmp_key.

Definition at line 115 of file safelanes.c.

◆ edge_stack

Edge* edge_stack

static

Array (array.h): Everything eligible to be a lane.

Definition at line 99 of file safelanes.c.

◆ faction_stack

Faction* faction_stack

static

Array (array.h): The faction IDs that can build lanes.

Definition at line 101 of file safelanes.c.

◆ ftilde

cholmod_dense* ftilde

static

Fluxes (bunch of F columns in the KU=F problem).

Definition at line 112 of file safelanes.c.

◆ JUMP_CONDUCTIVITY

const double JUMP_CONDUCTIVITY = 0.001

static

Conductivity value for inter-system jump-point connections.

Definition at line 52 of file safelanes.c.

◆ LAMBDA

const double LAMBDA = 2e10

static

Regularization term for score.

Definition at line 51 of file safelanes.c.

◆ lane_faction

int* lane_faction

static

Array (array.h): Per edge, ID of faction that built a lane there, if any, else 0.

Definition at line 102 of file safelanes.c.

◆ lane_fmask

FactionMask* lane_fmask

static

Array (array.h): Per edge, the set of factions that may build it.

Definition at line 103 of file safelanes.c.

◆ MASK_0

const FactionMask MASK_0 = 0

static

Definition at line 90 of file safelanes.c.

◆ MASK_1

const FactionMask MASK_1 = 1

static

Definition at line 90 of file safelanes.c.

◆ MIN_ANGLE

const double MIN_ANGLE = M_PI/18.

static

Path triangles can't be more acute.

Definition at line 53 of file safelanes.c.

◆ PPl

cholmod_dense** PPl

static

Array: (array.h): For each builder faction, The (P*)P in: grad_u(phi)=(Q*)Q U~ (P*)P.

Definition at line 114 of file safelanes.c.

◆ presence_budget

double** presence_budget

static

Array (array.h): Per faction, per system, the amount of presence not yet spent on lanes.

Definition at line 104 of file safelanes.c.

◆ QtQ

cholmod_sparse* QtQ

static

(Q*)Q where Q is the ExV difference matrix.

Definition at line 111 of file safelanes.c.

◆ safelanes_calculated_once

int safelanes_calculated_once = 0

static

Whether or not the safe lanes have been computed once.

Definition at line 116 of file safelanes.c.

◆ stiff

cholmod_triplet* stiff

static

K matrix, UT triplets: internal edges (E*3), implicit jump connections, anchor conditions.

Definition at line 110 of file safelanes.c.

◆ sys_to_first_edge

int* sys_to_first_edge

static

Array (array.h): For each system index, the id of its first edge, + sentinel.

Definition at line 100 of file safelanes.c.

◆ sys_to_first_vertex

int* sys_to_first_vertex

static

Array (array.h): For each system index, the id of its first vertex, + sentinel.

Definition at line 98 of file safelanes.c.

◆ tmp_anchor_vertices

int* tmp_anchor_vertices

static

Array (array.h): One vertex ID per connected component. Used to set up "stiff".

Definition at line 108 of file safelanes.c.

◆ tmp_edge_conduct

double* tmp_edge_conduct

static

Array (array.h): Conductivity (1/len) of each potential lane. Used to set up "stiff".

Definition at line 107 of file safelanes.c.

◆ tmp_jump_edges

Edge* tmp_jump_edges

static

Array (array.h): The vertex ID pairs connected by 2-way jumps. Used to set up "stiff".

Definition at line 106 of file safelanes.c.

◆ tmp_spob_indices

int* tmp_spob_indices

static

Array (array.h): The vertex IDs of spobs, to set up ftilde/PPl. Unrelated to spob IDs.

Definition at line 105 of file safelanes.c.

◆ tmp_sys_uf

UnionFind tmp_sys_uf

static

The partition of {system indices} into connected components (connected by 2-way jumps).

Definition at line 109 of file safelanes.c.

◆ utilde

cholmod_dense* utilde

static

Potentials (bunch of U columns in the KU=F problem).

Definition at line 113 of file safelanes.c.

◆ vertex_fmask

FactionMask* vertex_fmask

static

Malloced: Per vertex, the set of factions that have built on it.

Definition at line 97 of file safelanes.c.

◆ vertex_stack

Vertex* vertex_stack

static

Array (array.h): Everything eligible to be a lane endpoint.

Definition at line 96 of file safelanes.c.

Data Structures

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ Edge

◆ FactionMask

Enumeration Type Documentation

◆ anonymous enum

◆ VertexType

Function Documentation

◆ array_push_back_edge()

◆ cmp_key()

◆ FACTION_ID_TO_INDEX()

◆ MASK_ANY_FACTION()

◆ MASK_COMPROMISE()

◆ MASK_ONE_FACTION()

◆ ncholmod_ddmult()

◆ safelanes_activateByGradient()

◆ safelanes_buildOneTurn()

◆ safelanes_calculated()

◆ safelanes_destroy()

◆ safelanes_destroyOptimizer()

◆ safelanes_destroyStacks()

◆ safelanes_destroyTmp()

◆ safelanes_get()

◆ safelanes_init()

◆ safelanes_initFTilde()

◆ safelanes_initialConductivity()

◆ safelanes_initOptimizer()

◆ safelanes_initPPl()

◆ safelanes_initQtQ()

◆ safelanes_initStacks()

◆ safelanes_initStacks_anchor()

◆ safelanes_initStacks_edge()

◆ safelanes_initStacks_faction()

◆ safelanes_initStacks_vertex()

◆ safelanes_initStiff()

◆ safelanes_recalculate()

◆ safelanes_row_dot_row()

◆ safelanes_sliceByPresence()

◆ safelanes_triangleTooFlat()

◆ safelanes_updateConductivity()

◆ triplet_entry()

◆ vertex_faction()

◆ vertex_pos()

Variable Documentation

◆ ALPHA

◆ C

◆ cmp_key_ref

◆ edge_stack

◆ faction_stack

◆ ftilde

◆ JUMP_CONDUCTIVITY

◆ LAMBDA

◆ lane_faction

◆ lane_fmask

◆ MASK_0

◆ MASK_1

◆ MIN_ANGLE

◆ PPl

◆ presence_budget

◆ QtQ

◆ safelanes_calculated_once

◆ stiff

◆ sys_to_first_edge

◆ sys_to_first_vertex

◆ tmp_anchor_vertices

◆ tmp_edge_conduct

◆ tmp_jump_edges

◆ tmp_spob_indices

◆ tmp_sys_uf

◆ utilde

◆ vertex_fmask

◆ vertex_stack