Trade Network

[Koshling]

Then the question is a good algorithm to do that.

And how often to apply it (each turn once at the start of the player turn?)

 

[Thunderbrd]

And how often to apply it (each turn once at the start of the player turn?)

Trade benefits really only get compiled at the start of a turn. And even if a network is severed, it shouldn't mean they spent the turn without whatever access they had at the start of it - thus if a Bonus access (say, Oil) coming from the trade network is somehow giving a strategic military benefit (say, a Boiling Oil Building is active at the castle walls but would be disactivated if there were no access to Oil) were severed by enemy units destroying or blocking all pathways in and out of the city, it would still continue to have that benefit until the next turn when we can presume that the severing from the network has finally allowed stores of that resource to become exhausted.

I don't know much about trade network stuff either (aside from compiling numbers and how it selects the trade cities (something that would be nice for us to eventually allow the player to micromanage if they wished)) in particular where plots and routing are concerned as all that stuff is math at a level beyond me.

From what I understand, currently the connection between one city to another is basically a boolean with no evaluation as to the quality of the connection at all. I think the quality of connection would matter quite a bit in the effectiveness of it. But that's a LOT of evaluating the board, isn't it? Wicked cool as it would be to be able to rate the connection quality from one city to another, is it even possible to do this in an efficient manner?

 

[AIAndy]

And how often to apply it (each turn once at the start of the player turn?)

At most once per game turn (it will also calculate cross border networks and sea networks afterwards).

Trade benefits really only get compiled at the start of a turn. And even if a network is severed, it shouldn't mean they spent the turn without whatever access they had at the start of it - thus if a Bonus access (say, Oil) coming from the trade network is somehow giving a strategic military benefit (say, a Boiling Oil Building is active at the castle walls but would be disactivated if there were no access to Oil) were severed by enemy units destroying or blocking all pathways in and out of the city, it would still continue to have that benefit until the next turn when we can presume that the severing from the network has finally allowed stores of that resource to become exhausted.

Bonus access from trade will remain with the plot group calculation. I have no intention to mix that up.

 

[Dancing Hoskuld]

As I mentioned before I want to start with the national land based trade network.
For each land area and each player a national trade network is generated. The cities of that player in that area are added as nodes to a graph and a trade importance is calculated. Then for each city the pathing distance to each city within a given maximum coordinate distance is calculated and added as edge to the graph.
So now we have a graph with nodes that have trade importance and edges that have a pathing distance.
The next step should eliminate edges from the graph so that cities that have a high trade importance attract connections from the lesser important ones so the direct connections between the less important cities are eliminated and the connection runs over the major trade centers (so they are at the center of star like trade connections).

One complication is that the trade path depends on terrain in different ways than moving units. For example moving along rivers is easier than across country. Perhaps rivers should be considered the equivalent of "tracks" or "mud paths" for trade purposes.

 

[Yudishtira]

One complication is that the trade path depends on terrain in different ways than moving units. For example moving along rivers is easier than across country. Perhaps rivers should be considered the equivalent of "tracks" or "mud paths" for trade purposes.

Related to that, every coast has its annoying (strategically-placed) reefs, but every river is assumed entirely free of rapids and waterfalls!

EDIT: Okay it's not really a difference, I suppose it relates more to the stuff about the quality of the route.

 

[AIAndy]

I tried around a bit but could not get the original algorithm to work to my satisfaction.
So instead I plan now to do a flooding algorithm on the plots which floods out the trade influence from the cities and whoever reaches a plot first has the trade dominance over that plot (except for the plots directly around a city which are always assigned to that city).
So you get a kind of trade aura around each city and when you neighbor to another trade aura you form a local trade connection.
I guess the trade auras could also be used for city vincinity.

That means trade aura spread can be governed by different costs than movement.

 

[ls612]

I tried around a bit but could not get the original algorithm to work to my satisfaction.
So instead I plan now to do a flooding algorithm on the plots which floods out the trade influence from the cities and whoever reaches a plot first has the trade dominance over that plot (except for the plots directly around a city which are always assigned to that city).
So you get a kind of trade aura around each city and when you neighbor to another trade aura you form a local trade connection.
I guess the trade auras could also be used for city vincinity.

That means trade aura spread can be governed by different costs than movement.

How expensive are these to calculate? The flood algorithm sounds like something that would need to be done every turn for every city, and that could be bad for turn times. Are you going to thread that?

 

[AIAndy]

How expensive are these to calculate? The flood algorithm sounds like something that would need to be done every turn for every city, and that could be bad for turn times. Are you going to thread that?

You flood from all cities at the same time so the cost is something like N log N with N being the number of plots on the map.

 

[SilentConfusion]

You flood from all cities at the same time so the cost is something like N log N with N being the number of plots on the map.

I'm ignorant in this area and completely refer to your expertise. I assume that in your opinion that is a reasonable time cost or you wouldn't have suggested it.

 

[AIAndy]

A short update on this: The code for calculating the trade dominance auras and local trade routes is written. There are some things I am not entirely happy with yet (like that the trade routes from a strong trade city go around a weak city instead of through it and fully trade dominating it) but I will probably put a first version on the SVN tomorrow or so. There is no real gameplay effect yet. It just does the calculation and can display the result but that way you can see how it looks like and bring in your own ideas.
Especially in regards to what should influence trade importance of a city and the trade cost along a plot edge.

Next step will then be to calculate far trade routes from the local trade graph and tieing the calculated values back into game mechanics like the trade routes of each city.

 

[Thunderbrd]

I'm interested to see more, yes.

 

[ls612]

A short update on this: The code for calculating the trade dominance auras and local trade routes is written. There are some things I am not entirely happy with yet (like that the trade routes from a strong trade city go around a weak city instead of through it and fully trade dominating it) but I will probably put a first version on the SVN tomorrow or so. There is no real gameplay effect yet. It just does the calculation and can display the result but that way you can see how it looks like and bring in your own ideas.
Especially in regards to what should influence trade importance of a city and the trade cost along a plot edge.

Next step will then be to calculate far trade routes from the local trade graph and tieing the calculated values back into game mechanics like the trade routes of each city.

Sounds cool to me, I look forward to seeing the next step and the ingame effects. I just have a couple questions. Is the code for this threaded or not? How much time do the routines for this use?

 

[AIAndy]

I have added the first version of the trade network code now. Trade auras and local trade routes are calculated but by default switched off with a global define in A_New_Dawn_GlobalDefines.xml.
The result can be seen in new trade globe views but has no effect yet.

Sounds cool to me, I look forward to seeing the next step and the ingame effects. I just have a couple questions. Is the code for this threaded or not? How much time do the routines for this use?

It is not threaded (as the algorithm depends on execution order and would be significantly more complex in a threaded environment).
Feel free to measure the time the calculation takes.

EDIT: I probably should also mention that there are a lot of hardcoded numbers in the model at the moment which are not refined. Nor are there a lot of things going into the trade importance calculation. Some of the trade cost calculations belong into XML but are not yet.

 

[Thunderbrd]

Can you give us a summary explanation of the dynamic in definite terms so we know what we're looking at there? Exactly what does this do? I know you did explain your intent... but I also know what we come up with in the end usually differs a bit from the plan as it was improved or refined along the way.

 

[AIAndy]

Can you give us a summary explanation of the dynamic in definite terms so we know what we're looking at there? Exactly what does this do? I know you did explain your intent... but I also know what we come up with in the end usually differs a bit from the plan as it was improved or refined along the way.

A trade importance is calculated for each city (that calculation is still very simple and needs some refinement and addition of more factors). That trade influence then floods out from the city with easier spreading along rivers and routes (and several other things). When such a trade aura meets another city's trade aura for the first time, they establish a trade connection on that plot.
The trade aura of a city is where it has trade dominance and when it is still strong enough as it hits another city's initial trade aura it can also take full trade dominance of that city. Each plot can only belong to the trade aura of one city.

And that is what you see in the new globe views. The trade dominance auras and the local trade routes connecting the cities (the colors of cities of the same player are varied slightly). Trade routes are colored for one city until the trade connection plot and then for the other.

 

[Thunderbrd]

How will this change or influence the number of trade routes and trade yields from trade routes mechanisms? What does it mean to a city to have trade dominance?

 

[Koshling]

A trade importance is calculated for each city (that calculation is still very simple and needs some refinement and addition of more factors). That trade influence then floods out from the city with easier spreading along rivers and routes (and several other things). When such a trade aura meets another city's trade aura for the first time, they establish a trade connection on that plot.
The trade aura of a city is where it has trade dominance and when it is still strong enough as it hits another city's initial trade aura it can also take full trade dominance of that city. Each plot can only belong to the trade aura of one city.

And that is what you see in the new globe views. The trade dominance auras and the local trade routes connecting the cities (the colors of cities of the same player are varied slightly). Trade routes are colored for one city until the trade connection plot and then for the other.

I wonder if you could piggy-back a better realistic culture implementation onto the flooding (essentially a second value using the same algorithm [which could be calculated in the same iteration without significant extra overhead])...

 

[Dancing Hoskuld]

I wonder if you could piggy-back a better realistic culture implementation onto the flooding (essentially a second value using the same algorithm [which could be calculated in the same iteration without significant extra overhead])...

As long as this isn't the sole basis for "Realistic Culture Spread" even in Civ V plots with resources get priority over everything else when expanding. I've stopped using "Realistic Culture Spread" because it is so frustrating not being able to get that one stone resource in the second tier because it is on a forested hill in the desert. Mind you not using "Realistic Culture Spread" is just lacking fulfillment.

 

[Koshling]

As long as this isn't the sole basis for "Realistic Culture Spread" even in Civ V plots with resources get priority over everything else when expanding. I've stopped using "Realistic Culture Spread" because it is so frustrating not being able to get that one stone resource in the second tier because it is on a forested hill in the desert. Mind you not using "Realistic Culture Spread" is just lacking fulfillment.

In his post AIAndy said:

That trade influence then floods out from the city with easier spreading along rivers and routes (and several other things).

Existence of a bonus could easily be 'another thing' and the same set of 'other things' would not necessarily have to apply to a trade-aura value as it id tot a culture-aura value. Like properties, auras can be generalized and have (potentially XML-defined) flow rules.

 

[AIAndy]

In his post AIAndy said:

That trade influence then floods out from the city with easier spreading along rivers and routes (and several other things).

Existence of a bonus could easily be 'another thing' and the same set of 'other things' would not necessarily have to apply to a trade-aura value as it id tot a culture-aura value. Like properties, auras can be generalized and have (potentially XML-defined) flow rules.

The way the algorithm works does not really allow to calculate more than one set of auras at the same time because different flow rules would cause different edges to be first in the priority queue (and it would be different where you stop).
Nonetheless we could use this algorithm in multiple runs to calculate auras for different values / flow rules, maybe even something you can stick onto static properties in cities to cause property auras on plots.

@TB: That is not yet decided (nor fully thought through). There might be buildings that require you to have a bonus in your trade aura.

The local trade routes are calculated along the trade auras and these connections form a trade graph. There will be far trade routes that can be thought as a sequence of local trade routes and you will profit (take your share) for every far trade route that goes through your city. That means that if you dominate a city, its only local trade route goes to you and you will profit from all far trade routes of that city (and probably also get a larger share).