Advanced Economy & Trade Routes

Afforess said:

I don't think fixing the performance costs is possible.

Click to expand...

If we keep the concept always best TRs possible.

But if we change the concept maybe it can significantly enhance the performance, don't you think?

This is why my first idea was to check a random approach to see the performance gain. AND with max 16 routes probably dragged the performance to a worst stage, but in LoR (with 8 max TRs) performance was only significantly affected in Huge Modern Era (at least on my 64-bit OS, 2.4 GHz, 6 GB RAM pc under minimum graphics, a mediocre processing power by my guess, I don't know much on this subject too). Passing of turns that took like half a minute. Size in total cities: something around 300, and average 5 routes/city.

Reducing the total number of TRs and/or trying a beter approach at calculating the TRs may do a substantial gain on performance, at the cost of not having the best results (which is what makes it ubearable to performance now), and keeping most of the other game features intact.

Spirictum said:

If we keep the concept always best TRs possible.

But if we change the concept maybe it can significantly enhance the performance, don't you think?

This is why my first idea was to check a random approach to see the performance gain. AND with max 16 routes probably dragged the performance to a worst stage, but in LoR (with 8 max TRs) performance was only significantly affected in Huge Modern Era (at least on my 64-bit OS, 2.4 GHz, 6 GB RAM pc under minimum graphics, a mediocre processing power by my guess, I don't know much on this subject too). Passing of turns that took like half a minute. Size in total cities: something around 300, and average 5 routes/city.

Reducing the total number of TRs and/or trying a beter approach at calculating the TRs may do a substantial gain on performance, at the cost of not having the best results (which is what makes it ubearable to performance now), and keeping most of the other game features intact.

Click to expand...

That would make TR's performance worse. I don't think you understand the real cost of performance for trade routes. Here is the issue, trade route calculations cause an O(n^4) calculation per player, or N^5 for the entire game.

(See: http://en.wikipedia.org/wiki/Big_O_notation )

To calculate trade routes for the entire game:

Loop over each player,
- Then Loop over each city "X" a player owns
- - - Then loop over each player,
- - - - - Then loop over each city each player owns,
- - - - - - - Check if the city is connected to city X (above) and save it as a potential trade route
- - - - - - - Loop over the number of trade routes possible for our city and find the best

The deepest most nesting of loops (iterations) is 5, hence N^5. That means with 10 players and 10 cities per player, in 1 turn, the game must calculate 10 ^ 5 (100000) statements just for trade routes.

In a game with 50 players and an average of 25 cities per player on a gigantic map, this becomes 50 * 25 * 50 * 25 * 12 (18750000). That is a lot. Per turn.

To reduce the amount of performance impact trade routes cause, you must reduce the number of nested iterations. Tweaking the logic will not produce any gains. The exponent factor with nested iterations creates huge results even with small numbers.

Well, I think it could be cut pretty significantly in a number of ways. Most importantly, Monte Carlo style: toss a (virtual) coin on every step of the way to check whether or not we loop over particular entity this turn. While the exponent stays the same, we get only 1/32 the actual number of calculations to perform. Or we can put a counter (although there I'm not sure from a programming standpoint whether the overhead would be worth it) on each city that it had it's TRs recalculated, sort it from oldest to newest, and calculate from there only up to an X calculations per turn (say, 100 000), and stop (to keep turns from being longer than Y seconds). Bigger game would mean that the recalculations happen less often, but real time issues would be more bearable. We could add full loop for the players who change war/open borders state in any given turn, though.

That said, the new building modifiers seem better than trying to patch trade routes. It's just that practical computational complexity is somewhat of interest to me (theoretical too, but less so).

When I started college some years ago, I opted for engineering but one called production engineering (former industrial engineering) because I was young and naive. When I started working on a big company here in Brazil called Vale (former Vale do Rio Doce) I realized most of the subjects I studied were completely useless in my job, and this wouldn't change. Maybe if I got really big, but to that it was a lot more important to be polite, nice and talk much with people to gain their trust and things I honestly don't feel inclined to do with so many people around me. It wasn't for me for 2 reasons now.

Then I thought: I liked so much videogames and computer games (CIV being my favorite since I was 11 yo) and some friends were doing Computer Engineering, already showing me that in their jobs they used a lot of what they learn in college all the time. The more you understand the topics, the better a programmer you become.

So I changed last year to Computer Engineering, and now here in the forum you bring me the subject of last year's Advanced Data Structures (which was pretty hard BTW). It's at these times that I truly realize I did the right choice. Thank you Afforess.


So I'm still thinking what we can do with that nest of doom there, I'm pretty sure if we change the concept of 'always need to do best routes' we may reach ways of reducing that mess by not having to do all those things. You're right about my random approach, it seems it would only affect the last loop, changing to a random number, which indeed wouldn't do much difference. But if we start thinking in not so dynamic TRs it could make a big difference.

Filling with random probabilities would make faster and slower turns at random, I guess, like random % of turns to trigger updateTradeRoutes(), or random % of cities, or even random % of TRs.

If they could be actually stored, instead of re-visited every time routes must update, I think we could enhance this as well, but maybe there is a reson they didn't do that? Would this be bad for the game in some way?

But random seems to be one of the devils of OOS, at least as far as I've read, so maybe this approach will be terrible for MP? Correct me if I'm wrong please.

But going deeper in that not dynamic TRs, it could be something a lil more under our control. This would require a totally new concept, so I'm not sure if it's a good way. But it would remove that feel you have of TRs not being under our control.

What do you think? This way most other game features remain intact (or with small changes) and we make TR calc something less a burden to the game

BlindKitty said:

Well, I think it could be cut pretty significantly in a number of ways. Most importantly, Monte Carlo style: toss a (virtual) coin on every step of the way to check whether or not we loop over particular entity this turn. While the exponent stays the same, we get only 1/32 the actual number of calculations to perform. Or we can put a counter (although there I'm not sure from a programming standpoint whether the overhead would be worth it) on each city that it had it's TRs recalculated, sort it from oldest to newest, and calculate from there only up to an X calculations per turn (say, 100 000), and stop (to keep turns from being longer than Y seconds). Bigger game would mean that the recalculations happen less often, but real time issues would be more bearable. We could add full loop for the players who change war/open borders state in any given turn, though.

That said, the new building modifiers seem better than trying to patch trade routes. It's just that practical computational complexity is somewhat of interest to me (theoretical too, but less so).

Click to expand...

Yes, that would make trade routes faster, but it would make it increasingly random. One could take your argument to it's (absurd) logical conclusion, just gift every player a random amount of commerce each turn. After all, thats what trade routes would become, and that's much faster!

Spirictum said:

When I started college some years ago, I opted for engineering but one called production engineering (former industrial engineering) because I was young and naive. When I started working on a big company here in Brazil called Vale (former Vale do Rio Doce) I realized most of the subjects I studied were completely useless in my job, and this wouldn't change. Maybe if I got really big, but to that it was a lot more important to be polite, nice and talk much with people to gain their trust and things I honestly don't feel inclined to do with so many people around me. It wasn't for me for 2 reasons now.

Then I thought: I liked so much videogames and computer games (CIV being my favorite since I was 11 yo) and some friends were doing Computer Engineering, already showing me that in their jobs they used a lot of what they learn in college all the time. The more you understand the topics, the better a programmer you become.

So I changed last year to Computer Engineering, and now here in the forum you bring me the subject of last year's Advanced Data Structures (which was pretty hard BTW). It's at these times that I truly realize I did the right choice. Thank you Afforess.

Click to expand...

Yay! I actually switched to focus on Computer Science & Mathematics due to Civ4 modding in the early days too.

Spirictum said:

So I'm still thinking what we can do with that nest of doom there, I'm pretty sure if we change the concept of 'always need to do best routes' we may reach ways of reducing that mess by not having to do all those things. You're right about my random approach, it seems it would only affect the last loop, changing to a random number, which indeed wouldn't do much difference. But if we start thinking in not so dynamic TRs it could make a big difference.

Filling with random probabilities would make faster and slower turns at random, I guess, like random % of turns to trigger updateTradeRoutes(), or random % of cities, or even random % of TRs.

Click to expand...

See my above response to BlindKitty.

Spirictum said:

If they could be actually stored, instead of re-visited every time routes must update, I think we could enhance this as well, but maybe there is a reson they didn't do that? Would this be bad for the game in some way?

Click to expand...

Well, cache invalidation of trade routes is hard. You'd have to invalidate any time a road is created or destroyed. (Or a war starts, or a player changes civics...you get the picture. It's *hard*).

Spirictum said:

But random seems to be one of the devils of OOS, at least as far as I've read, so maybe this approach will be terrible for MP? Correct me if I'm wrong please.

Click to expand...

Randoms are not the devil. Randoms in Civ4 are deterministic. That means, starting with the same "seed" (initial value), it will roll the same exact random number out every time. This does not cause an OOS. Where issues come in is if something that is part of the interface calls a RNG. Say I open a menu and that causes the RNG to roll out a number, and updates the seed, but the other player does not. Then our RNG's are out of sync!

The great misunderstanding of determinism and RNG's has lead many modders to fear it. RNG's are not scary, they are very predictable, when used correctly.

---

So after all the discussion of patching TR's, I am even more for my ideas to replace it with connectedness modifiers than before. It makes it much easier to understand the bonuses and makes the strategy of gameplay more coherent. All the suggested TR fixes just make the bad system even worse, from a gameplay standpoint. How much does +1 trade routes benefit a city? Impossible to know before, really. How much does 1% per connected city benefit a city? That is easy to understand.

Afforess said:

Yes, that would make trade routes faster, but it would make it increasingly random. One could take your argument to it's (absurd) logical conclusion, just gift every player a random amount of commerce each turn. After all, thats what trade routes would become, and that's much faster!

Click to expand...

One could argue, that finding optimal trade routes in increasingly complicated world takes longer time for merchants. But yeah, that's kind of hyperbole that came to my mind too.

Afforess said:

So after all the discussion of patching TR's, I am even more for my ideas to replace it with connectedness modifiers than before. It makes it much easier to understand the bonuses and makes the strategy of gameplay more coherent. All the suggested TR fixes just make the bad system even worse, from a gameplay standpoint. How much does +1 trade routes benefit a city? Impossible to know before, really. How much does 1% per connected city benefit a city? That is easy to understand.

Click to expand...

I'm with you here. Seems like a better idea to me. Actually it gives me one other idea that is probably not worth a fuss - what if we divide road improvement into two kinds of improvement - one would be 'major road' and other 'local roads network'. The first one would be connecting resources/cities, and the other one would benefit the other improvements the way currently roads are. Some of those (especially early ones) could work as both, and from railroads you would have to build two types. Just a little idea, due to overall importance of roads.

So after all the discussion of patching TR's, I am even more for my ideas to replace it with connectedness modifiers than before. It makes it much easier to understand the bonuses and makes the strategy of gameplay more coherent. All the suggested TR fixes just make the bad system even worse, from a gameplay standpoint. How much does +1 trade routes benefit a city? Impossible to know before, really. How much does 1% per connected city benefit a city? That is easy to understand.

Click to expand...

+1

Do it. We can adapt or die!

JosEPh

+ Several. I've never understood the point of trade routes myself.

I hope we can reach a new way of giving by connectedness that truly substitutes TRs.

And I went back to LoR to test a game without TRs on an incredibly big mapsize (that's why I didn't test in AND, because I don't know how to override Perfect Mongoose or Perfect World), and the difference is impressive: With TRs the game was horrendously slow before AD, now it's becoming like this past 1000 AD. The dll still can only handle 50 civs, and LoR doesn't have even 40 different civs, so there is much to happen yet.

Any ideas already about the new concept?

BTW, about that OOS stuff, is the reason you gave the only reason for OOSs or there is more? What has been significantly reducing my gametesting on AND is the OOSs because I like to play with a friend, so our MPs are when I can devote more time to gametesting, but having 4-5 OOS per 3-4 hours of game is unbearable

Spirictum said:

BTW, about that OOS stuff, is the reason you gave the only reason for OOSs or there is more? What has been significantly reducing my gametesting on AND is the OOSs because I like to play with a friend, so our MPs are when I can devote more time to gametesting, but having 4-5 OOS per 3-4 hours of game is unbearable

Click to expand...

Any action that causes the state of the game to differ between machines causes an out of sync, not just randoms.

Well, you've got me convinced
Sounds very good to me. Looking forward to see your changes in a new rev.

Just one idea: Will your modifiers be displayed in a way as TRs before? Just to give the feeling that "we still have TRs".

Sogroon said:

Well, you've got me convinced
Sounds very good to me. Looking forward to see your changes in a new rev.

Just one idea: Will your modifiers be displayed in a way as TRs before? Just to give the feeling that "we still have TRs".

Click to expand...

They will be listed on the building description and included in the "actual effects" hover. What else are you looking for?

(Also, we can reclaim the trade routes part of the city screen for more building real estate.)

Afforess said:

They will be listed on the building description and included in the "actual effects" hover. What else are you looking for?

(Also, we can reclaim the trade routes part of the city screen for more building real estate.)

Click to expand...

yeah take the empty space that TRs will leave behind and use it to display this info

Actually, there's no "empty space" left by taking off TR. And that's because in the very same space other info are showed if you click the right button (food, hammers and commerce). By the way, what about UN Resolutions giving Trade Routes with everyone and +1 Trade Route (Single Currency)?
It's looking very hard to me to remove TR without causing troubles. Still, I know Afforess skill so it's up to him.

One more thing, beside the obvious advantage in reducing calculation time, I think this whole thread started (correct me if I'm wrong) because somehow "players first in the player order have an advantage". I don't know if this is true for single player or multiplayer games or both. But I've learned something unexpected when studying MP and OOS problems, and this is that order of players is not the same IIRC when you use simultaneous turns (I'm not sure what happens in single player games): i.e. players are "shuffled" so that the order is (more or less) random. Obviously this is necessary because otherwise order of players would influence the game (just think about more players finishing a wonder at the same time). Are we sure this isn't the case for trade routes too? I mean, is it tested that order of players is affecting trade routes?

45°38'N-13°47'E;13322681 said:

One more thing, beside the obvious advantage in reducing calculation time, I think this whole thread started (correct me if I'm wrong) because somehow "players first in the player order have an advantage". I don't know if this is true for single player or multiplayer games or both. But I've learned something unexpected when studying MP and OOS problems, and this is that order of players is not the same IIRC when you use simultaneous turns (I'm not sure what happens in single player games): i.e. players are "shuffled" so that the order is (more or less) random. Obviously this is necessary because otherwise order of players would influence the game (just think about more players finishing a wonder at the same time). Are we sure this isn't the case for trade routes too? I mean, is it tested that order of players is affecting trade routes?

Click to expand...

Simultaneous turns does not affect the internal game ordering.

45°38'N-13°47'E;13322669 said:

Actually, there's no "empty space" left by taking off TR. And that's because in the very same space other info are showed if you click the right button (food, hammers and commerce). By the way, what about UN Resolutions giving Trade Routes with everyone and +1 Trade Route (Single Currency)?
It's looking very hard to me to remove TR without causing troubles. Still, I know Afforess skill so it's up to him.

Click to expand...

In the short term, I'd just turn off that resolution. Long term, it could give something else.

I started it for 3 reasons:

Advanced Economy options,

TR benefitting players first in player order,

TR calcs

The benefit is in player order but it only happens once in a while when specific conditions are met. And I think even if MP Simultaneous games change the order of the players, it doesn't change the order of assignment (Player 0 will remain Player 0 throughout the game, even though he may not be the first to start every time) At least logs never changed me from Player 0 on my games, so I assume this.

The idea is that if you may do a TR with yourself or with a foreign city on your landmass, it's better to let the foreign TR be used by other city then by this, because maybe it can be assigned to a city you own later on your own cities' list that is overseas toward the target foreign city.

For this to happen, besides the same land mass thing above, you must have domestic TRs being used and cities on other landmasses (or isles). Isn't a big problem, but the solution seems quite simple

If I may chime in since Joe asked those of us on C2C to take a look at the thread here and comment...

Ok, so ultimately 4 core points have been made so far as I can see:

1) The automated selection of trade route cities is a wretchedly time-expensive processing waste.

2) Player choice is next to non-existent in the trade route structure. There's some few variables players manipulate but to keep from there being far too much micro-management, there's a horrendous streamlining that makes the whole structure akin to a set of 'random' bonuses.

3)The concept of trade producing valuable yields/commerces from nowhere is rather flawed (though maybe not quite so bad for the Commerce Yield itself as it may be the only thing truly justified to be 'generated' this way.)

4) It would be faster and potentially more meaningful still if we were to establish new tags to adjust trade route manipulations on buildings, civis, etc... to manipulate Commerce per connected cities instead.

Ok.

So I'll respond directly to those main points and then offer some additional points for consideration and then offer a solution I've not seen suggested here that I feel would ADD to gameplay rather than simply streamline and shed what I feel are SOME very valuable game mechanic features attached to the concept of trade routes to begin with.

So responses:
1) I can't argue here. Surely this is a horrendous processing effort. Koshling may have cached the results significantly but yes, it goes a long ways towards making the later game take a lot longer turns and overall the design is indeed terrible.

2 & 3) I've always wished that aside from Commerce generation, it would be nice if Yields and Commerces could actually BE traded between cities based on player choices. Would be far preferable if percentages of the resources (not to be misconstrued as BONUSES) of a given city could actually be given to another city via thereafter automated 'routes'. If cities could make agreements directly with one another to trade say, some food from one city FOR a certain amount of gold FROM the other. ALLOW the establishments of trades (and not just bonuses between civs at a player level) to be a PART of the game.

For example: You know you want more food for your arctic city because it has a tough time doing so for itself so you establish a trade between that city and another where it will give some of its gold income for some of the other city's food income.

Another Example: You want more production in this particular city because you're training up an army or you're trying to get it built up from an infancy status so you make a trade with another city for some of its production.

Added Commerce Yield 'from thin air' would be a positive side effect for both cities because it's the learning from each other and witnessing of the other's tricks and clever concepts in action (research), small time wheeling and dealing and thus added taxation from commerce taking place between the populations of both cities(gold), the sharing of attitudes, artwork and cultural ideas(culture) and the opportunities to learn secrets and valuable strategic information from the other locations(espionage) that is what the Commerce Yield represents and just establishing inter-city trades would generate this - in fact would be one of the most powerful ways TO generate Commerce Yield!

Sounds like something that would get more complex still and thus be a processing nightmare of an even worse magnitude right?

I think it can be done and make it done much cheaper in terms of processing.


4) I object somewhat. I liked the idea the first time I read it here but I've been thinking on the concept and it really does leave a LOT of game features out of the picture. Cultural sharing, espionage (as has been pointed out), tech diffusion issues, (for C2C we HAD trade route interactions for Properties and I still think we just need to restructure it so it can be re-established - and the advanced disease etc... structure I was working on would heavily use trade routes in a more controlled manner), Religion Sharing - You'd be wiping out automatic religious spreads here, Corporation interactions I think use trade routes. Then you've got Internal Only trade vs International Trade, trade agreements in diplomacy, events, resolutions... a TON of building and other tags that are devoted to interacting with the trade route mechanism that would need to be entirely rethought... There's a LOT of considerations that would make this seemingly simple adjustment highly complex and would leave the game lacking some useful interactions.

You'd be adding more tags that would need to be implemented through a tremendously laborious effort that includes the removal of all the previous implementations for trade route tags. I realize that AND probably doesn't use as many as C2C since we have bridges and road 'buildings' I don't think AND uses but still... that's a lot to consider. You have Civics and Traits and Techs to reconsider how to rework... As noted, this is a horrendously HUGE restructuring to go through for either mod.


However...


I have a solution to propose and it's probably what I would do for C2C at some point soon. (I've got a little work to do there yet to pave the way for this further in the way I'd implement it but it could be done in AND differently.)

So the solution I would propose:

Don't know about AND but in C2C we have Merchant units. I've got a few issues with them too. They ALSO generate production and food in a much greater volume than it takes to train them (in the case of the Food Merchants to an almost ridiculously imbalancing extent that makes it so that if you want to grow a city you'll build these until you're happy with your population no matter how high that population may become.) They seem to be a good idea in theory but are incredibly imbalancing.

If you want to use them to generate gold or commerce which is a paltry use for them (unless they're naval trader units and have thus no other use) they're laborious to utilize and problematic for the AI who currently sees them as primarily great scouting units since they can explore enemy territory as they can't be kept out by closed borders etc...


I would suggest
1) Disable all automatic determinations for trade route establishment. This immediately fixes the processing hell and 'lack of choices' problems. Give them back to the player!

2) Do so through trade units. Give the units an ability to Broker a trade route. Track the unit's 'home city' and make it necessary to send them, successfully, to the city you wish to establish a trade route with.

3) The route itself that's brokered could be of a number of different route yield types. Commerce generation would be a natural side effect for both cities but one city would give a yield in a volume determined by the upgrade phase of the trade unit for gold from the other city in a volume determined by the upgrade phase of the trade unit.

4) Otherwise disable yield/commerces generation by default.

5) Keep the max # of trade routes limits and trade route commerce yield modifiers all current buildings, civic, etc already give. Wherever possible allow trade routes to continue to work as they currently do and maintain the majority of the UI it already utilizes in the city screen, except that we are no longer talking about an automatic system of assignment. For maximum routes, your city's trade units would not be able to broker more deals than the city is limited to.

6) Obviously the somewhat heavier processing would swap over to unit generation for this purpose and the ai for those units. But I'm thinking this could be done with much less processing weight.

7) Deals must be accepted or rejected and must remain able to be cancelled. So there would be some new popups and AI considerations there but may not need to be toooo complex, particularly if the AI is programmed to be fair and generally open to trading without good strategic reason not to be.

8) Deals must be registered as an act of international trading for diplomacy's sake.

9) Some deals could be setup to be humanitarian, like food aid sent to another city where nothing is asked in return.

10) Each deal still counts as one trade route. And perhaps more than one deal could be struck with the same city even.


This way you'd make trade a lot more strategic and even adventurous as you'd need to get your merchants to their targets without those merchants being destroyed before brokering the deals you're wanting to setup. That would certainly serve C2C as it could lead to a lot more Criminal interactions and such as well.

Anyhow, take this as you will - just a suggestion from another modding mind.

Hi ThunderBrd. Its great to have other devs around.

I agree with your points about player control in points 2&3, in redirecting trade routes, but it seems it would massively increase the micromanagement and complexity. I really want to replace TR's with something simpler, not more complex.

About #4... Yes there are some things that will need to be worked out. The UN treaty for trade routes. The espionage modifiers. RAND tech diffusion doesn't depend on trade routes anymore, so that's ok. I'm not sure what "Culture Sharing" refers to, I am unaware of any mechanics where trade routes influence culture spread.

Corporate and Religion spread use connectedness checks, not trade routes. There are a ton of building tags, but I think it's not unmanagable.

I'm still really in favor of replacing trade routes with connectedness yield & commerce modifiers. It is just simpler to understand and see from a player's perspective. Everything else requires more micromanagement, not less.

Afforess said:

Hi ThunderBrd. Its great to have other devs around.

I agree with your points about player control in points 2&3, in redirecting trade routes, but it seems it would massively increase the micromanagement and complexity. I really want to replace TR's with something simpler, not more complex.

About #4... Yes there are some things that will need to be worked out. The UN treaty for trade routes. The espionage modifiers. RAND tech diffusion doesn't depend on trade routes anymore, so that's ok. I'm not sure what "Culture Sharing" refers to, I am unaware of any mechanics where trade routes influence culture spread.

Corporate and Religion spread use connectedness checks, not trade routes. There are a ton of building tags, but I think it's not unmanagable.

I'm still really in favor of replacing trade routes with connectedness yield & commerce modifiers. It is just simpler to understand and see from a player's perspective. Everything else requires more micromanagement, not less.

Click to expand...

For the scope of AND's focus vs C2C's focus as sister mods yet differing I can fully understand your position on that. I think C2C could get away with adding another game element because that would be a good thing for the C2C target player whereas for AND's target player you're probably right.