Big update time. R17 Preview 1 is finally ready,
download it from GitHub here. What was holding it up was that I was tinkering with the code for calculating trade networks, and ended up replacing most of it from the base game. I had a feeling that the base game's implementation was way too slow, that calculating the trade network is not that complicated, and especially that it shouldn't have to blow up in the late game. My feeling was right! I was able to get my reimplementation of the trade network to run ~35x faster than the original in an extreme test case. It's enough to make maps like
Monstrosity playable all the way to the end.
My extreme test case is a late industrial era Monstrosity game with many wars going on. Previously (*) trade net calculations between turns would take 894 sec out of a total turn time of 958 sec. My custom trade net code runs in only 24.9 sec, reducing the total turn time to 93.4 sec. This is an extreme case since ~90% of the turn time is spent computing trade networks, usually it's less than that. I also measured times on an earlier save from that same game, in the early industrial era without many wars. In that more typical case, trade net calculations previously took 86 sec of an overall 153 sec turn. The custom code reduces that to just 3.85 sec, bringing the overall turn time down to 74 sec.
(*) Aside: "previously" here means with C3X R16, so including the improvement loop optimization. Out of curiosity, I turned that off and found it increased the trade net time to 943 sec and overall turn time to 1008 sec. So optimizing the improv. loops is worth about 5% in that case. That is not surprising since the Monstrosity scenario doesn't add any city improvements and the trade net calculations take so long they dwarf everything else. Optimizing the trade net makes the improv. loop optimization look better. With the trade net optimized and the improv. loops not, the trade net takes 50.0 sec of an overall 117 sec turn time, so the improv. loop optimization further reduces that by about 20%.
As for what the optimizations entail, by far the biggest improvement comes from preserving pathfinding info across jobs. Basically, when computing sea trade, the game loops over all pairs of cities with harbors that are not already connected by roads and tries to find a path between them. It processes the pairs independently, clearing the pathfinder's internal state before each search. That's extremely wasteful. For example, trying to path from city A to city B is done by crawling outward from A building up a set of reachable tiles in the direction of B (
Wikipedia has a good illustration). Either you eventually reach B, and so there is a path, or you run out of reachable tiles, and can conclude no path exists. If next you want to check for a path between cities A and C, you can get a big head start by reusing the results from the search from A to B, since those results already include many tiles reachable from A. In the extreme case where there is no path from A to B, you've already done the work of searching for a path from A to C. That's because the only way to conclude there is no path is to visit every tile reachable from A, so either you've already visited C and there is a path A->C or you haven't and there isn't.
In fact, you can do even better than that. Imagine you've searched for paths connecting A->B, A->C, A->D, etc., building up a set of reachable tiles along the way. Next you're asked if there's a path B->C. If B is in the set of tiles reachable from A, you can again reuse the pathfinder state since A and B are in the same set of reachable tiles.
Reusing the pathfinder state is not the only optimization I've done. Since I reimplemented the pathfinder logic for the trade network entirely I had the opportunity to make many improvements. Two more notable ones:
- The game's data structures make very poor use of the CPU cache. The game was written in a typical unoptimized object-oriented fashion meaning all the data that makes up a tile has been piled into a tile object and then the game map is an array of tile objects. The problem with that is when the CPU checks, for example, the terrain of a tile, it pulls into its cache many unrelated parts of the tile object which it will not use. That stuff gets pulled in simply because it's what close in memory. If soon after the CPU needs to check the terrain of the surrounding tiles, as it does while pathfinding, that data will probably not already be in the cache. It would be faster to store the terrain data separately and arrange it so that data for nearby tiles is kept nearby in memory. The replacement logic can't replace the original tile or map layout but what it can do is stash the relevant tile data in a cache-efficient structure after it's accessed once, so all later accesses to the same tile's data are done in a cache-efficient manner.
- The logic for checking sea trade accessibility at a tile level has been simplified so it only runs once per tile. The base game is inefficient here in that it checks accessibility between tiles, not per-tile, even though when you boil down the rules they only matter per-tile. For example, say you want to know if a sea route can pass between tiles T and U, and then later between tiles T and V. The base game will make four checks here, two for tiles T & U, and another for tiles T & V. However, you only need to make three checks here, one for each tile, since a sea route can pass between any two adjacent accessible tiles.
By the way, you might be wondering if that's really true, if any two adjacent, passable sea tiles can have a sea trade route passed between them. What about tiles separated by an isthmus? For example, imagine four tiles in a diamond shape, where the left and right tiles are land and the top and bottom are water. In that case, you can't pass naval units between the top and bottom tiles (unless you've activated the C3X land-sea intersections option) but you actually can pass a sea trade route between them. That's an odd little aspect of the game rules, and I'm not sure why the game is programmed that way. It may have been done for performance reasons, or maybe the devs simply never thought of it.
In terms of final performance, it's the reusing of the pathfinder's state that's responsible for almost all of the speed up. The above two improvements I mentioned only speed up trade net calculations by about 30%. I also replaced the calculation of the road network and managed to speed that up by about 2x. That sounds good but it really doesn't matter since road network computations take up 0.1% or less of the overall turn time.
To get reliable numbers for the turn times, I added the ability to measure them in-game, the option is named measure_turn_times (duh). If activated, you'll get a popup at the end of every interturn reporting how long it took, including specifically how long it took to recalculate the trade networks. Some of you might find this interesting, for example if you have a very slow save and want to know how much of the slowdown is due to the trade network.
There's a lot more in R17 Preview 1 than that. It also contains many extensions to zone of control and defensive bombard. Thanks to Vaughn for commissioning those. Here's the full list of changes:
- Optimize computation of trade networks
- For details, see the info text file in the Trade Net X folder
- Option to measure turn times
- Zone of control changes
- Allow land-to-sea and sea-to-land attacks, only using bombard stat
- May be lethal
- May be exerted by air units
- Show attack animation even when attacker is not at the top of its stack
- Defensive bombard changes
- May be lethal
- May be performed by air units
- Invisible, undetected units may be made immune
- May be performed multiple times per turn with blitz
- Naval units in a city may perform defensive bombard vs land attackers
- Allow precision strikes to target tile improvements
- Option not to end a unit's turn after it bombards a barricade
- Option to allow bombardment of other improvements on a tile with an occupied airfield
- Option to boost OCN increase from forbidden palaces in non-communal governments
- Fix graphical issues when running on Wine
- Option to allow defensive retreat on water tiles
- Overhaul implementation of shared visibility for simplicity and correctness
- Display total city count (disabled by default, appears on demographics screen)
Here's a little preview of what defensive bombard and zone of control can now do. I could have posted this version a day sooner if I hadn't taken the time to make these, so be sure to appreciate them:
Land units can exert ZoC over passing sea units & vice versa.
Air units can exert ZoC.
And they can perform defensive bombardment as well.
Defensive bombard & ZoC can be made lethal.
That's it! Please report any bugs if you find them. I'm 99% sure that my reimplementation of the trade network calculations will give exactly the same results as the original game, but it's always possible I missed something.
May you live a thousand years!!!!!! 
