Rethinking the Trade Routes System

[Thunderbrd]

These aren't excludent of each other of course, several can be used at once. What I would like to focus now is the Merchant idea, which to me has the most potential, but still needs a lot of info to be more tangible. As T-Brd started this idea, I wish that he comes with everything he has already thought about it so to guide the discussion of this topic.

I already mentioned the idea of having the Merchant do something actively, like having a button to press both in Object City and Target City, so to simulate the trade to the player, instead of just putting the unit to patrol back and forth (BTW, I never use the Patrol command, does it make the unit go back and forth infinitely?). So how exactly the Route is established? What's the trigger? Will it give its profits every turn, or only when the Merchant comes back? And how is a Route like that interrupted? These are a few questions that come to my mind thinking on this system.

I'll comment later on how we can structure this project from here. I ll have some time tonight.

 

[nliv007]

As stated by Spirictum, combing some options would make sense. For instance (and purely for example) 7 of the 10 trade routes are done by proximity. These would not need turn to turn calculations unless a new city within the proximity is built.

The other 3 trade routes could be ones the player sets up, taking into account factors such as distance, resources produced by the city, exiting trade routes with that city, and whatever else. These routes could be made available through techs or specific buildings as the game progresses. Once set up, they can be removed by creating a new trade route (and a popup to eliminate an old one) but wouldn't need the algorithm every turn.

Add additional routes or options as the game needs, but giving some player management without creating too much micromanagement seems ideal.

 

[Spirictum]

As stated by Spirictum, combing some options would make sense. For instance (and purely for example) 7 of the 10 trade routes are done by proximity. These would not need turn to turn calculations unless a new city within the proximity is built.

That depends on more stuff then just a new city popping up. Assuming we are using a proximity algorithm to find the closest X cities, which candidates to X are viable options? Now we must come with rules for cities to establish proximity routes. Do they need to be connected by a normal route? (river, path, coast) Can they be from different Players? Can they be in different landmasses? Can they be too far away from each other? (imagine northwestern USA making routes with Alaska instead of bordering Canada for some reason)
Any of these that can change status may force a recalc of the proximity routes, like connection through normal routes, or destruction of a city.


But then your point is great, they won't need a recalc each turn. The more stable we can make this proximity web of routes, the less recalcs we will have. I believe that in many cases a full recalc can be avoided too, always aiming to accelerate game processing time.

 

[JosEPh_II]

Is this heading towards what Afforess did in AND2?

 

[Spirictum]

Is this heading towards what Afforess did in AND2?

This change is the reason I quit that mod, I can guarantee you it won't be like that. Also, Tbrd asked for the structure of the system to remain the same, so all work he has been doing will still apply. The idea isn't changing the system entirely anymore, but just use tactics to make the current system faster to process.

 

[JosEPh_II]

This change is the reason I quit that mod, I can guarantee you it won't be like that. Also, Tbrd asked for the structure of the system to remain the same, so all work he has been doing will still apply. The idea isn't changing the system entirely anymore, but just use tactics to make the current system faster to process.

Good to know. Thanks.

 

[Thunderbrd]

I will not have time to comment on this for a day or two I think.

 

[alberts8]

For non-modders:
Simply put, it takes too long when the number of routes per city gets high enough, and the number of cities as well. As an example, if we have 4 players each with 100 cities, imagine each city with the ability to make 10 Trade Routes, every player is allowed to make trade routes with each other, and every city is connected. This means that when you pass your turn, for each of the players (4) we will first organize all 100 cities so the best are first. Then for each of these cities, we will check all cities that it can establish a trade route with (400 possibilities) and organize them from best to worst, but discarding anything that goes over the number of trade routes for the city (10) after evaluating the trade value of each other city. Finally, with the best 10 cities to establish a trade route for each city, it is done. This means it'll take: 4(players)*100(cities)*400(total connected cities)*X(time to organize the best 10 trade routes to make)*MaxTradeRoutes(currently 24, I'll talk about this later in this post) = 3,840,000 instructions for the computer to process (times X, but as X is completely unpredictable, I didn't put it in the result).

If you have 4 players each with 100 cities trade routes are the last thing to worry about. Turns will take forever but that comes from all kinds of things like the city production AI or unit AI. Each Player will have at least 2000 units that alone can really slow things down.

Trade routes won't even make it into the top25 of the most time consuming things. Trust me i know because i did alot of profiling and trade routes newer came up as an issue.

I still don't know there this myth comes from, the last time it came up few months ago.

 

[Thunderbrd]

I still don't know there this myth comes from, the last time it came up few months ago

I think it's the code itself... it just screams "I'm complicated!" but since it doesn't have to run that often it never really hits so bad as it looks like it should.

 

[Spirictum]

If you have 4 players each with 100 cities trade routes are the last thing to worry about. Turns will take forever but that comes from all kinds of things like the city production AI or unit AI. Each Player will have at least 2000 units that alone can really slow things down.

Trade routes won't even make it into the top25 of the most time consuming things. Trust me i know because i did alot of profiling and trade routes newer came up as an issue.

I still don't know there this myth comes from, the last time it came up few months ago.

It's no myth, maybe it doesn't strike as hard as other stuff, but as I mentioned before it is a terrible algorithm that gets a lot worse with not so high increments in number of objects (in this case cities). 4 Players with 100 cities each may seem ok, but simply transform these 400 cities in 4000 cities and things get waaaaay worse then they were before. Also, I would like to know what this profiling you guys have been mentioning is all about. It seems a powerful tool to check what has been consuming memory.

I think it's the code itself... it just screams "I'm complicated!" but since it doesn't have to run that often it never really hits so bad as it looks like it should.

I'd like to know what is so often, so that something that, in a singleplayer, happens once for each player in the game every turn isn't considered something that happens oftenly enough.

 

[Thunderbrd]

I'd like to know what is so often, so that something that, in a singleplayer, happens once for each player in the game every turn isn't considered something that happens oftenly enough.

Sometimes a single unit figuring out what to do can be a far far more complicated procedure than determination of trade routes, to the measure of a power of 10. Often in one round, some hundreds of units are making such complex evaluations per player, sometimes well over 1k units. Gathering expected combat odds alone is likely much more complicated than the recalculation of trade routes and when a stack of 300 units considers its odds against another similarly sized stack, each unit checking each unit's combat odds to find the best unit to attack with and the best unit to defend with on the defending stack, that's when you start seeing 10 minute rounds taking place.

The trade route matter you bring up may be costing some 5 seconds per end turn, for all the cities of one player in a highly developed game.

I'll have to take some time to teach you how to profile. It IS quite interesting and a very valuable tool if you want to put your focus into speeding things up. Alberts2 may be able to explain it better. But I'll try to find some time to go find Koshling's instructions to me on the subject and share that with you. If I was going to run a profile check at this point I'd have to find those instructions again anyhow. This is why Alberts2 might be able to beat me to the explanation faster as I think he's more immediately practiced with it.

 

[Spirictum]

Now that sounds a lot better. I see now an example of something that really needs some attention. Well, I'd like to proceed with this on Trade Routes because there is indeed something to gain (although not as important as other stuff), the algorithm seems out of touch with the real mechanic it tries to simulate (only best routes for the best cities), and I've already read a lot about it in the code.

But then I'd like to check if there's something that can be done to the AI unit decision method. Next semester I'll have Algorithm Analysis if everything goes according to plan, so I hope to use what I learn there to help here. Not only that but I'm trying to start working on the Games' Lab of my university, maybe there I can find useful info as well.

Also I'm eager to see this profiling method in detail.

 

[Thunderbrd]

I'm all for these improvements to trade. If we work through the elements of a merchant AI, that can teach you the basics of unit AI matters as well and from there you'll have the keys to knowing where to follow all the rest of their algorythms. So this is actually a great development path project I think.

I'm not sure if I should be focusing any guidance on a particular portion here or not though.

 

[Spirictum]

I'll start actually doing something as soon as classes end, which will be in 2 weeks. My idea is first to do a test with a setting really overcrowded with cities and available trade routes so to see how much time it can be gained if we simply remove the calculation altogether. Then I want to try the approach I suggested of pairing cities because it's easy and quick to implement and check how much time it saves compared to the other test.

I guess this profiling technique will be useful for theses tests, so any explanation, or recommended sites to read about this method are welcome

 

[Thunderbrd]

Ok, I'll try to find time to explain it.

 

[AIAndy]

I once tried to redesign / rewrite the trade route system, but more for gameplay reasons than performance as I did not like the way it works and it did not seem to make much sense:

https://forums.civfanatics.com/threads/trade-network.490585/

The (unfinished) code is actually in C2C but only active if the global define CALCULATE_TRADE_AURAS is set to true (unless someone removed it at some point, the code is in CvTradeNetwork). The result of the calculation can then be seen as a globe layer (the auras of the different cities and the routes that connect cities with adjacent auras).

I still don't know there this myth comes from, the last time it came up few months ago.

It is old, at least this old:
https://forums.civfanatics.com/threads/trade-routes-income-performance-impact.529505/

 

[Spirictum]

I'll take a look at what you've done AIAndy, but I don't have much time now. I had stumbled upon that TRADE_AURA in the code before but didn't pay attention to it.

But then I was following the link to see how old is this topic. There Nimek is talking about it making a reference to another topic, so I followed through. Imagining I would reach somewhere with someone else talking about Trade Routes performance, but no, not really. I just saw myself starting a topic about this in RAND in 2014.

At least I found some info I had already lost, and I could see that my explanation to platyping is a mess about 2 completely different things that I wasn't so aware at the time.

And it seems who first showed me this problem was Embryodead from Sword of Islam mod of Rhye's and Fall of Civilization, but back then I had already lost where he posted this, so making my own words mine again:

I already tried to find this everywhere but I couldn't. It's not now, years after what has happened that I'll find. But I'm pretty sure Embryodead (modder of Sword of Islam RFC) said once that the algorithm to choose Trade Routes is so bad, it's one of the major issues making bigger maps with a big number of civs go slow (If I'm not mistaken, he changed it for his Sengoku mod, and despite having several civs it runs pretty fast).

So yeah, I started all this 3 years ago, while I was still playing RAND. But presumably it was embryodead who opened my eyes to this

 

[AIAndy]

I'll take a look at what you've done AIAndy, but I don't have much time now. I had stumbled upon that TRADE_AURA in the code before but didn't pay attention to it.

It was only the first step anyway, using a flood algorithm to calculate a graph of cities whose edges represent direct trade connections (with the actual plots used for the connection known as well) with small trade cities near big trade cities considered dominated by the big city so all trade of the small city flows to the big city first.
The next steps would have been to use the edges of that graph as local trade routes with effects similar to the current trade routes and then use an (unspecified) algorithm on that graph to compute far trade route effects.
So currently switching that code on has no gameplay effect and only allows you to see the local trade routes and "trade auras" that the algorithm results in (and that algorithm still needs a lot of tuning).

 

[Spirictum]

By flood algorithm you mean something like this?
https://en.wikipedia.org/wiki/Flood_fill

It's the only thing I find by searching flood algorithm

 

[Toffer90]

I'm not really sure what AIAndy means with a flood fill algorithm, but my guess is something along this line:
Think of it as a height map where many different factors defines the height of a plot, the lower they are the better they are suited for trade.
Flood fill will start filling the low lying plots by incrementing the "water level" by just a little at a time, effectively tallying up the plots in an order that follows a certain rule-set. It may be global process, or it may have a source plot where it only spreads to plots adjacent to those already filled.
When the plot of one city is "submerged" and it's connected by "water" to another city, these cities will be eligible trade partners.
Those cities that connect the earliest in the process makes for the most natural trade route pairs.

Don't take my word on this though, I'm not a programmer, AIAndy will have to confirm or correct my assumptions.