makhidkarun / traveller_pyroute

Traveller trade route generator
MIT License
14 stars 5 forks source link

Speed up jump-graph generation #105

Closed CyberiaResurrection closed 7 months ago

CyberiaResurrection commented 7 months ago

Speed up trade graph generation by increasing the amount of work not done:

Memoise things that are hit repeatedly in tight loops:

  1. Whether systems are agricultural, or need an agricultural partner;
  2. Likewise for industrial systems/partners;
  3. BTN distance penalties;
  4. Maximum distance values given endpoint WTNs;

Filter distance-busts from candidate route list up front, rather than spinning through the entirety of the RouteCalculation.generate_base_routes() malarkey.

And finally, filter out more doomed route candidates: L153 of status-quo RouteCalculation quoth: max_btn = (min(star1.wtn, star2.wtn) * 2) + 1

This combines with the specified minimum route BTN to imply (letting largest doubled-WTN that can't support a trade route be W):

min_route_btn > W * 2 + 1
min_route_btn - 1 > W * 2
(min_route_btn - 1) / 2 > W
W < (min_route_btn - 1) / 2

As W must be integral, the RHS rounds down W < (min_route_btn - 1) // 2

Frinstance, with a min_route_btn setting of 11 (goes one louder), the W threshold becomes 5 - doubled Star WTN values less than 5 need to be filtered out of route generation, but not edge generation. Although such stars can't support trade routes on their own, trade routes connecting other systems can still flow through them.

Likewise, the default min_route_btn setting of 13 implies a W threshold of 6. As does a min_route_btn setting of 14.

Adding that to TradeCalculation.base_route_filter() as a bilateral filter was easier, even though it was actually a unilateral filter, than deconvolving the existing range and link filtering.

Over the 32 imperial sectors, status quo route generation: 2024-03-30 18:25:11,699 - INFO - generating jumps... 2024-03-30 18:33:46,852 - INFO - base routes: 145219 - ranges: 835401 2024-03-30 18:33:46,853 - INFO - calculating routes... 2024-03-30 18:33:47,579 - INFO - Final route count 142326

Graph generation took 8 min 36s on my box, or 516s.

With this PR: 2024-03-30 18:09:10,126 - INFO - generating jumps... 2024-03-30 18:09:10,315 - INFO - Routes with endpoints more than 599 pc apart, trimmed 2024-03-30 18:15:13,846 - INFO - base routes: 145219 - ranges: 835401 2024-03-30 18:15:13,846 - INFO - calculating routes... 2024-03-30 18:15:14,589 - INFO - Final route count 142326

Graph generation now takes 6 min 4 s on my box, or 364s.

It's a small speedup - 29% less time taken to generate the graph - off the second biggest chunk of runtime in the full-charted-space run (pathfinding dominates graph generation less with smaller input sizes). I took the chance to incorporate @tjoneslo 's feedback to resolve #104 while I was at it.