1 /*
2 * See Licensing and Copyright notice in naev.h
3 */
4
5 /**
6 * @file economy.c
7 *
8 * @brief Handles economy stuff.
9 *
10 * Economy is handled with Nodal Analysis. Systems are modelled as nodes,
11 * jump routes are resistances and production is modelled as node intensity.
12 * This is then solved with linear algebra after each time increment.
13 */
14
15
16 #include "economy.h"
17
18 #include "naev.h"
19
20 #include <stdio.h>
21 #include "nstring.h"
22 #include <stdint.h>
23
24 #ifdef HAVE_SUITESPARSE_CS_H
25 #include <suitesparse/cs.h>
26 #else
27 #include <cs.h>
28 #endif
29
30 #include "nxml.h"
31 #include "ndata.h"
32 #include "log.h"
33 #include "spfx.h"
34 #include "pilot.h"
35 #include "rng.h"
36 #include "space.h"
37 #include "ntime.h"
38
39
40 #define XML_COMMODITY_ID "Commodities" /**< XML document identifier */
41 #define XML_COMMODITY_TAG "commodity" /**< XML commodity identifier. */
42
43
44 /*
45 * Economy Nodal Analysis parameters.
46 */
47 #define ECON_BASE_RES 30. /**< Base resistance value for any system. */
48 #define ECON_SELF_RES 3. /**< Additional resistance for the self node. */
49 #define ECON_FACTION_MOD 0.1 /**< Modifier on Base for faction standings. */
50 #define ECON_PROD_MODIFIER 500000. /**< Production modifier, divide production by this amount. */
51 #define ECON_PROD_VAR 0.01 /**< Defines the variability of production. */
52
53
54 /* commodity stack */
55 static Commodity* commodity_stack = NULL; /**< Contains all the commodities. */
56 static int commodity_nstack = 0; /**< Number of commodities in the stack. */
57
58
59 /* systems stack. */
60 extern StarSystem *systems_stack; /**< Star system stack. */
61 extern int systems_nstack; /**< Number of star systems. */
62
63
64 /*
65 * Nodal analysis simulation for dynamic economies.
66 */
67 static int econ_initialized = 0; /**< Is economy system initialized? */
68 static int econ_queued = 0; /**< Whether there are any queued updates. */
69 static int *econ_comm = NULL; /**< Commodities to calculate. */
70 static int econ_nprices = 0; /**< Number of prices to calculate. */
71 static cs *econ_G = NULL; /**< Admittance matrix. */
72
73
74 /*
75 * Prototypes.
76 */
77 /* Commodity. */
78 static void commodity_freeOne( Commodity* com );
79 static int commodity_parse( Commodity *temp, xmlNodePtr parent );
80 /* Economy. */
81 static double econ_calcJumpR( StarSystem *A, StarSystem *B );
82 static int econ_createGMatrix (void);
83 credits_t economy_getPrice( const Commodity *com,
84 const StarSystem *sys, const Planet *p ); /* externed in land.c */
85
86
87 /**
88 * @brief Converts credits to a usable string for displaying.
89 *
90 * @param[out] str Output is stored here, must have at least a length of 32
91 * char.
92 * @param credits Credits to display.
93 * @param decimals Decimals to use.
94 */
credits2str(char * str,credits_t credits,int decimals)95 void credits2str( char *str, credits_t credits, int decimals )
96 {
97 if (decimals < 0)
98 nsnprintf( str, ECON_CRED_STRLEN, "%"CREDITS_PRI, credits );
99 else if (credits >= 1000000000000000LL)
100 nsnprintf( str, ECON_CRED_STRLEN, "%.*fQ", decimals, (double)credits / 1000000000000000. );
101 else if (credits >= 1000000000000LL)
102 nsnprintf( str, ECON_CRED_STRLEN, "%.*fT", decimals, (double)credits / 1000000000000. );
103 else if (credits >= 1000000000L)
104 nsnprintf( str, ECON_CRED_STRLEN, "%.*fB", decimals, (double)credits / 1000000000. );
105 else if (credits >= 1000000)
106 nsnprintf( str, ECON_CRED_STRLEN, "%.*fM", decimals, (double)credits / 1000000. );
107 else if (credits >= 1000)
108 nsnprintf( str, ECON_CRED_STRLEN, "%.*fK", decimals, (double)credits / 1000. );
109 else
110 nsnprintf (str, ECON_CRED_STRLEN, "%"CREDITS_PRI, credits );
111 }
112
113 /**
114 * @brief Given a price and on-hand credits, outputs a colourized string.
115 *
116 * @param[out] str Output is stored here, must have at least a length of 32
117 * char.
118 * @param price Price to display.
119 * @param credits Credits available.
120 * @param decimals Decimals to use.
121 */
price2str(char * str,credits_t price,credits_t credits,int decimals)122 void price2str(char *str, credits_t price, credits_t credits, int decimals )
123 {
124 char *buf;
125
126 credits2str(str, price, decimals);
127 if (price <= credits)
128 return;
129
130 buf = strdup(str);
131 nsnprintf(str, ECON_CRED_STRLEN, "\er%s\e0", buf);
132 free(buf);
133 }
134
135 /**
136 * @brief Gets a commodity by name.
137 *
138 * @param name Name to match.
139 * @return Commodity matching name.
140 */
commodity_get(const char * name)141 Commodity* commodity_get( const char* name )
142 {
143 int i;
144 for (i=0; i<commodity_nstack; i++)
145 if (strcmp(commodity_stack[i].name,name)==0)
146 return &commodity_stack[i];
147
148 WARN("Commodity '%s' not found in stack", name);
149 return NULL;
150 }
151
152
153 /**
154 * @brief Gets a commodity by name without warning.
155 *
156 * @param name Name to match.
157 * @return Commodity matching name.
158 */
commodity_getW(const char * name)159 Commodity* commodity_getW( const char* name )
160 {
161 int i;
162 for (i=0; i<commodity_nstack; i++)
163 if (strcmp(commodity_stack[i].name,name)==0)
164 return &commodity_stack[i];
165 return NULL;
166 }
167
168
169 /**
170 * @brief Frees a commodity.
171 *
172 * @param com Commodity to free.
173 */
commodity_freeOne(Commodity * com)174 static void commodity_freeOne( Commodity* com )
175 {
176 if (com->name)
177 free(com->name);
178 if (com->description)
179 free(com->description);
180 if (com->gfx_store)
181 gl_freeTexture(com->gfx_store);
182
183 /* Clear the memory. */
184 memset(com, 0, sizeof(Commodity));
185 }
186
187
188 /**
189 * @brief Function meant for use with C89, C99 algorithm qsort().
190 *
191 * @param commodity1 First argument to compare.
192 * @param commodity2 Second argument to compare.
193 * @return -1 if first argument is inferior, +1 if it's superior, 0 if ties.
194 */
commodity_compareTech(const void * commodity1,const void * commodity2)195 int commodity_compareTech( const void *commodity1, const void *commodity2 )
196 {
197 const Commodity *c1, *c2;
198
199 /* Get commodities. */
200 c1 = * (const Commodity**) commodity1;
201 c2 = * (const Commodity**) commodity2;
202
203 /* Compare price. */
204 if (c1->price < c2->price)
205 return +1;
206 else if (c1->price > c2->price)
207 return -1;
208
209 /* It turns out they're the same. */
210 return strcmp( c1->name, c2->name );
211 }
212
213
214 /**
215 * @brief Loads a commodity.
216 *
217 * @param temp Commodity to load data into.
218 * @param parent XML node to load from.
219 * @return Commodity loaded from parent.
220 */
commodity_parse(Commodity * temp,xmlNodePtr parent)221 static int commodity_parse( Commodity *temp, xmlNodePtr parent )
222 {
223 xmlNodePtr node;
224
225 /* Clear memory. */
226 memset( temp, 0, sizeof(Commodity) );
227
228 /* Get name. */
229 xmlr_attr( parent, "name", temp->name );
230 if (temp->name == NULL)
231 WARN("Commodity from "COMMODITY_DATA_PATH" has invalid or no name");
232
233 /* Parse body. */
234 node = parent->xmlChildrenNode;
235 do {
236 xml_onlyNodes(node);
237 xmlr_strd(node, "description", temp->description);
238 xmlr_int(node, "price", temp->price);
239 if (xml_isNode(node,"gfx_store")) {
240 temp->gfx_store = xml_parseTexture( node,
241 COMMODITY_GFX_PATH"%s.png", 1, 1, OPENGL_TEX_MIPMAPS );
242 if (temp->gfx_store != NULL) {
243 } else {
244 temp->gfx_store = gl_newImage( COMMODITY_GFX_PATH"_default.png", 0 );
245 }
246 continue;
247 }
248 } while (xml_nextNode(node));
249 if ((temp->gfx_store == NULL) && (temp->price>0)) {
250 WARN("No <gfx_store> node found, using default texture for commodity \"%s\"", temp->name);
251 temp->gfx_store = gl_newImage( COMMODITY_GFX_PATH"_default.png", 0 );
252 }
253
254 #if 0 /* shouldn't be needed atm */
255 #define MELEMENT(o,s) if (o) WARN("Commodity '%s' missing '"s"' element", temp->name)
256 MELEMENT(temp->description==NULL,"description");
257 MELEMENT(temp->high==0,"high");
258 MELEMENT(temp->medium==0,"medium");
259 MELEMENT(temp->low==0,"low");
260 #undef MELEMENT
261 #endif
262
263 return 0;
264 }
265
266
267 /**
268 * @brief Throws cargo out in space graphically.
269 *
270 * @param pilot ID of the pilot throwing the stuff out
271 * @param com Commodity to throw out.
272 * @param quantity Quantity thrown out.
273 */
commodity_Jettison(int pilot,Commodity * com,int quantity)274 void commodity_Jettison( int pilot, Commodity* com, int quantity )
275 {
276 (void)com;
277 int i;
278 Pilot* p;
279 int n, effect;
280 double px,py, bvx, bvy, r,a, vx,vy;
281
282 p = pilot_get( pilot );
283
284 n = MAX( 1, RNG(quantity/10, quantity/5) );
285 px = p->solid->pos.x;
286 py = p->solid->pos.y;
287 bvx = p->solid->vel.x;
288 bvy = p->solid->vel.y;
289 for (i=0; i<n; i++) {
290 effect = spfx_get("cargo");
291
292 /* Radial distribution gives much nicer results */
293 r = RNGF()*25 - 12.5;
294 a = 2. * M_PI * RNGF();
295 vx = bvx + r*cos(a);
296 vy = bvy + r*sin(a);
297
298 /* Add the cargo effect */
299 spfx_add( effect, px, py, vx, vy, SPFX_LAYER_BACK );
300 }
301 }
302
303
304 /**
305 * @brief Loads all the commodity data.
306 *
307 * @return 0 on success.
308 */
commodity_load(void)309 int commodity_load (void)
310 {
311 uint32_t bufsize;
312 char *buf;
313 xmlNodePtr node;
314 xmlDocPtr doc;
315
316 /* Load the file. */
317 buf = ndata_read( COMMODITY_DATA_PATH, &bufsize);
318 if (buf == NULL)
319 return -1;
320
321 /* Handle the XML. */
322 doc = xmlParseMemory( buf, bufsize );
323 if (doc == NULL) {
324 WARN("'%s' is not valid XML.", COMMODITY_DATA_PATH);
325 return -1;
326 }
327
328 node = doc->xmlChildrenNode; /* Commodities node */
329 if (strcmp((char*)node->name,XML_COMMODITY_ID)) {
330 ERR("Malformed "COMMODITY_DATA_PATH" file: missing root element '"XML_COMMODITY_ID"'");
331 return -1;
332 }
333
334 node = node->xmlChildrenNode; /* first faction node */
335 if (node == NULL) {
336 ERR("Malformed "COMMODITY_DATA_PATH" file: does not contain elements");
337 return -1;
338 }
339
340 do {
341 xml_onlyNodes(node);
342 if (xml_isNode(node, XML_COMMODITY_TAG)) {
343
344 /* Make room for commodity. */
345 commodity_stack = realloc(commodity_stack,
346 sizeof(Commodity)*(++commodity_nstack));
347
348 /* Load commodity. */
349 commodity_parse(&commodity_stack[commodity_nstack-1], node);
350
351 /* See if should get added to commodity list. */
352 if (commodity_stack[commodity_nstack-1].price > 0.) {
353 econ_nprices++;
354 econ_comm = realloc(econ_comm, econ_nprices * sizeof(int));
355 econ_comm[econ_nprices-1] = commodity_nstack-1;
356 }
357 }
358 else
359 WARN("'"COMMODITY_DATA_PATH"' has unknown node '%s'.", node->name);
360 } while (xml_nextNode(node));
361
362 xmlFreeDoc(doc);
363 free(buf);
364
365 DEBUG("Loaded %d Commodit%s", commodity_nstack, (commodity_nstack==1) ? "y" : "ies" );
366
367 return 0;
368
369
370 }
371
372
373 /**
374 * @brief Frees all the loaded commodities.
375 */
commodity_free(void)376 void commodity_free (void)
377 {
378 int i;
379 for (i=0; i<commodity_nstack; i++)
380 commodity_freeOne( &commodity_stack[i] );
381 free( commodity_stack );
382 commodity_stack = NULL;
383 commodity_nstack = 0;
384
385 /* More clean up. */
386 free( econ_comm );
387 }
388
389
390 /**
391 * @brief Gets the price of a good on a planet in a system.
392 *
393 * @param com Commodity to get price of.
394 * @param sys System to get price of commodity.
395 * @param p Planet to get price of commodity.
396 * @return The price of the commodity.
397 */
economy_getPrice(const Commodity * com,const StarSystem * sys,const Planet * p)398 credits_t economy_getPrice( const Commodity *com,
399 const StarSystem *sys, const Planet *p )
400 {
401 (void) p;
402 int i, k;
403 double price;
404
405 /* Get position in stack. */
406 k = com - commodity_stack;
407
408 /* Find what commodity that is. */
409 for (i=0; i<econ_nprices; i++)
410 if (econ_comm[i] == k)
411 break;
412
413 /* Check if found. */
414 if (i >= econ_nprices) {
415 WARN("Price for commodity '%s' not known.", com->name);
416 return 0;
417 }
418
419 /* Calculate price. */
420 price = (double) com->price;
421 price *= sys->prices[i];
422 return (credits_t) price;
423 }
424
425
426 /**
427 * @brief Calculates the resistance between two star systems.
428 *
429 * @param A Star system to calculate the resistance between.
430 * @param B Star system to calculate the resistance between.
431 * @return Resistance between A and B.
432 */
econ_calcJumpR(StarSystem * A,StarSystem * B)433 static double econ_calcJumpR( StarSystem *A, StarSystem *B )
434 {
435 double R;
436
437 /* Set to base to ensure price change. */
438 R = ECON_BASE_RES;
439
440 /* Modify based on system conditions. */
441 R += (A->nebu_density + B->nebu_density) / 1000.; /* Density shouldn't affect much. */
442 R += (A->nebu_volatility + B->nebu_volatility) / 100.; /* Volatility should. */
443
444 /* Modify based on global faction. */
445 if ((A->faction != -1) && (B->faction != -1)) {
446 if (areEnemies(A->faction, B->faction))
447 R += ECON_FACTION_MOD * ECON_BASE_RES;
448 else if (areAllies(A->faction, B->faction))
449 R -= ECON_FACTION_MOD * ECON_BASE_RES;
450 }
451
452 /* @todo Modify based on fleets. */
453
454 return R;
455 }
456
457
458 /**
459 * @brief Calculates the intensity in a system node.
460 *
461 * @todo Make it time/item dependent.
462 */
econ_calcSysI(unsigned int dt,StarSystem * sys,int price)463 static double econ_calcSysI( unsigned int dt, StarSystem *sys, int price )
464 {
465 (void) dt;
466 (void) sys;
467 (void) price;
468 return 0.;
469 #if 0
470 int i;
471 double I;
472 double prodfactor, p;
473 double ddt;
474 Planet *planet;
475
476 ddt = (double)(dt / NTIME_UNIT_LENGTH);
477
478 /* Calculate production level. */
479 p = 0.;
480 for (i=0; i<sys->nplanets; i++) {
481 planet = sys->planets[i];
482 if (planet_hasService(planet, PLANET_SERVICE_INHABITED)) {
483 /*
484 * Calculate production.
485 */
486 /* We base off the current production. */
487 prodfactor = planet->cur_prodfactor;
488 /* Add a variability factor based on the Gaussian distribution. */
489 prodfactor += ECON_PROD_VAR * RNG_2SIGMA() * ddt;
490 /* Add a tendency to return to the planet's base production. */
491 prodfactor -= ECON_PROD_VAR *
492 (planet->cur_prodfactor - prodfactor)*ddt;
493 /* Save for next iteration. */
494 planet->cur_prodfactor = prodfactor;
495 /* We base off the sqrt of the population otherwise it changes too fast. */
496 p += prodfactor * sqrt(planet->population);
497 }
498 }
499
500 /* The intensity is basically the modified production. */
501 I = p / ECON_PROD_MODIFIER;
502
503 return I;
504 #endif
505 }
506
507
508 /**
509 * @brief Creates the admittance matrix.
510 *
511 * @return 0 on success.
512 */
econ_createGMatrix(void)513 static int econ_createGMatrix (void)
514 {
515 int ret;
516 int i, j;
517 double R, Rsum;
518 cs *M;
519 StarSystem *sys;
520
521 /* Create the matrix. */
522 M = cs_spalloc( systems_nstack, systems_nstack, 1, 1, 1 );
523 if (M == NULL)
524 ERR("Unable to create CSparse Matrix.");
525
526 /* Fill the matrix. */
527 for (i=0; i < systems_nstack; i++) {
528 sys = &systems_stack[i];
529 Rsum = 0.;
530
531 /* Set some values. */
532 for (j=0; j < sys->njumps; j++) {
533
534 /* Get the resistances. */
535 R = econ_calcJumpR( sys, sys->jumps[j].target );
536 R = 1./R; /* Must be inverted. */
537 Rsum += R;
538
539 /* Matrix is symmetrical and non-diagonal is negative. */
540 ret = cs_entry( M, i, sys->jumps[j].target->id, -R );
541 if (ret != 1)
542 WARN("Unable to enter CSparse Matrix Cell.");
543 ret = cs_entry( M, sys->jumps[j].target->id, i, -R );
544 if (ret != 1)
545 WARN("Unable to enter CSparse Matrix Cell.");
546 }
547
548 /* Set the diagonal. */
549 Rsum += 1./ECON_SELF_RES; /* We add a resistance for dampening. */
550 cs_entry( M, i, i, Rsum );
551 }
552
553 /* Compress M matrix and put into G. */
554 if (econ_G != NULL)
555 cs_spfree( econ_G );
556 econ_G = cs_compress( M );
557 if (econ_G == NULL)
558 ERR("Unable to create economy G Matrix.");
559
560 /* Clean up. */
561 cs_spfree(M);
562
563 return 0;
564 }
565
566
567 /**
568 * @brief Initializes the economy.
569 *
570 * @return 0 on success.
571 */
economy_init(void)572 int economy_init (void)
573 {
574 int i;
575
576 /* Must not be initialized. */
577 if (econ_initialized)
578 return 0;
579
580 /* Allocate price space. */
581 for (i=0; i<systems_nstack; i++) {
582 if (systems_stack[i].prices != NULL)
583 free(systems_stack[i].prices);
584 systems_stack[i].prices = calloc(econ_nprices, sizeof(double));
585 }
586
587 /* Mark economy as initialized. */
588 econ_initialized = 1;
589
590 /* Refresh economy. */
591 economy_refresh();
592
593 return 0;
594 }
595
596
597 /**
598 * @brief Increments the queued update counter.
599 *
600 * @sa economy_execQueued
601 */
economy_addQueuedUpdate(void)602 void economy_addQueuedUpdate (void)
603 {
604 econ_queued++;
605 }
606
607
608 /**
609 * @brief Calls economy_refresh if an economy update is queued.
610 */
economy_execQueued(void)611 int economy_execQueued (void)
612 {
613 if (econ_queued)
614 return economy_refresh();
615
616 return 0;
617 }
618
619
620 /**
621 * @brief Regenerates the economy matrix. Should be used if the universe
622 * changes in any permanent way.
623 */
economy_refresh(void)624 int economy_refresh (void)
625 {
626 /* Economy must be initialized. */
627 if (econ_initialized == 0)
628 return 0;
629
630 /* Create the resistance matrix. */
631 if (econ_createGMatrix())
632 return -1;
633
634 /* Initialize the prices. */
635 economy_update( 0 );
636
637 return 0;
638 }
639
640
641 /**
642 * @brief Updates the economy.
643 *
644 * @param dt Deltatick in NTIME.
645 */
economy_update(unsigned int dt)646 int economy_update( unsigned int dt )
647 {
648 int ret;
649 int i, j;
650 double *X;
651 double scale, offset;
652 /*double min, max;*/
653
654 /* Economy must be initialized. */
655 if (econ_initialized == 0)
656 return 0;
657
658 /* Create the vector to solve the system. */
659 X = malloc(sizeof(double)*systems_nstack);
660 if (X == NULL) {
661 WARN("Out of Memory!");
662 return -1;
663 }
664
665 /* Calculate the results for each price set. */
666 for (j=0; j<econ_nprices; j++) {
667
668 /* First we must load the vector with intensities. */
669 for (i=0; i<systems_nstack; i++)
670 X[i] = econ_calcSysI( dt, &systems_stack[i], j );
671
672 /* Solve the system. */
673 /** @TODO This should be improved to try to use better factorizations (LU/Cholesky)
674 * if possible or just outright try to use some other library that does fancy stuff
675 * like UMFPACK. Would be also interesting to see if it could be optimized so we
676 * store the factorization or update that instead of handling it individually. Another
677 * point of interest would be to split loops out to make the solving faster, however,
678 * this may be trickier to do (although it would surely let us use cholesky always if we
679 * enforce that condition). */
680 ret = cs_qrsol( 3, econ_G, X );
681 if (ret != 1)
682 WARN("Failed to solve the Economy System.");
683
684 /*
685 * Get the minimum and maximum to scale.
686 */
687 /*
688 min = +HUGE_VALF;
689 max = -HUGE_VALF;
690 for (i=0; i<systems_nstack; i++) {
691 if (X[i] < min)
692 min = X[i];
693 if (X[i] > max)
694 max = X[i];
695 }
696 scale = 1. / (max - min);
697 offset = 0.5 - min * scale;
698 */
699
700 /*
701 * I'm not sure I like the filtering of the results, but it would take
702 * much more work to get a sane system working without the need of post
703 * filtering.
704 */
705 scale = 1.;
706 offset = 1.;
707 for (i=0; i<systems_nstack; i++)
708 systems_stack[i].prices[j] = X[i] * scale + offset;
709 }
710
711 /* Clean up. */
712 free(X);
713
714 econ_queued = 0;
715 return 0;
716 }
717
718
719 /**
720 * @brief Destroys the economy.
721 */
economy_destroy(void)722 void economy_destroy (void)
723 {
724 int i;
725
726 /* Must be initialized. */
727 if (!econ_initialized)
728 return;
729
730 /* Clean up the prices in the systems stack. */
731 for (i=0; i<systems_nstack; i++) {
732 if (systems_stack[i].prices != NULL) {
733 free(systems_stack[i].prices);
734 systems_stack[i].prices = NULL;
735 }
736 }
737
738 /* Destroy the economy matrix. */
739 if (econ_G != NULL) {
740 cs_spfree( econ_G );
741 econ_G = NULL;
742 }
743
744 /* Economy is now deinitialized. */
745 econ_initialized = 0;
746 }
747