Explaining of civ3 slowdown - Intractable algorithms!

[Nadexander]

As anyone that has played a game on a huge map with 16 civs has noticed that it takes a _VERY_ long time for the AI to play its turns. In trying to understand why i happened on a very important observation: when you pillage a road, destroy a harbor, conquer a city or do anything else that disrupts the trade network there is a lag time of around 30 seconds (on a 900mhz cpu). The reason that this takes forever is that calculating the existance of a connection between x number of cities and through y number of squares is proportional to x! (x factorial) In other words the cost of calculating the existance of the trade network gets exponentially larger as the number of cities and the number of map squares increases. This also explains why there is a significant slow down when the AI is at war. Think of how often the AI pillages a road or takes a city? I wager that 90% of the game turn winds up being the recalculation of the trade network. I suggest that firaxis change the game mechanics so that the trade network is only calculated at the end of turn in order to make the game playable on the huge map settings.

[Peets]

Hmmm, I was wondering too why it took so long time...
good job of "maybe" finding it
Well, I hope they can do something about it...

[Ferdi]

Indeed, this problem has been reported by many other guys but without pointing the problem. I've also been faced with that and it must be DEFINITELY fixed.

[Asmodean]

If that is really so - and I suspect that you may be right there, it should be fairly easy for Firaxis to solve this - major - problem.

Maybe add a message that says (when it's your turn once again) something like: [CityX] can't build Musketeer, due to lack of supplies. Or something to that effect.

Asmodean

[Cavalier_13]

A wasted thread......

I went into detail of this in 2 prior posts in 2 different threads, and yet you say the same thing I did. Was a new thread really needed?

Cavalier

[justin_sayn]

WRONG AND WRONG!

Actually Johnson's algorithm will find the shortest past between all squares in a time that is roughly proportional to (X*X)*lgX +XE (where E is the number of links, and a link is only counted between 2 squares)

I.E.: If there are 1000 squares on the map, the time of algorithm will be proportional to:
1000*1000*Lg1000 +1000*E=

Since each square is linked to 8 other squares then there are 8*1000 = 8000 links, so we have:

1000*1000*Lg1000 +1000*8000 = 1 000 000*10 + 8 000 000

Which is equal to 18 000 000.

Since the number of squares and links on the map is constant, there is no reason for the game to take an increasingly amount of time as more cities are developed. (if they were using that alogorithm of course).

Where did you ever get the X! idea?

Eitherway, whatever algorithm they use, the number of squares is always constant on the map.

[War4ever]

laymans terms.....all i know is standard maps are about all i have the patience for

[Nadexander]

Re: WRONG AND WRONG!

Originally posted by justin_sayn
Actually Johnson's algorithm will find the shortest past between all squares in a time that is roughly proportional to (X*X)*lgX +XE (where E is the number of links, and a link is only counted between 2 squares)

I.E.: If there are 1000 squares on the map, the time of algorithm will be proportional to:
1000*1000*Lg1000 +1000*E=

Since each square is linked to 8 other squares then there are 8*1000 = 8000 links, so we have:

1000*1000*Lg1000 +1000*8000 = 1 000 000*10 + 8 000 000

Which is equal to 18 000 000.

Where did you ever get the X! idea?

Eitherway, whatever algorithm they use, the number of squares is always constant on the map.

assuming a square map of side x
number of squares is x^2
number of paths between any two squares X^4
time to find a path between two given squares: worst case
is X^2 so time to find path between all given squares is x^6
So i messed up saying that its non-polynomial. Its but its not pretty thats for sure. Doubling the map size will make it so that it takes something like 50 times as long. And you also need to consider that the bigger the map, the larger the number of units running around and pillaging things so the more often the paths need to be calculated.

[Nadexander]

Re: WRONG AND WRONG!

Originally posted by justin_sayn
Actually Johnson's algorithm will find the shortest past between all squares in a time that is roughly proportional to (X*X)*lgX +XE (where E is the number of links, and a link is only counted between 2 squares)

I.E.: If there are 1000 squares on the map, the time of algorithm will be proportional to:
1000*1000*Lg1000 +1000*E=

Since each square is linked to 8 other squares then there are 8*1000 = 8000 links, so we have:

1000*1000*Lg1000 +1000*8000 = 1 000 000*10 + 8 000 000

Which is equal to 18 000 000.

Since the number of squares and links on the map is constant, there is no reason for the game to take an increasingly amount of time as more cities are developed. (if they were using that alogorithm of course).

Where did you ever get the X! idea?

Eitherway, whatever algorithm they use, the number of squares is always constant on the map.

This is only for finding a path for any two given points (which worst case can never take more steps than the number of squares on the map. However It needs to calcualte the pairwise linking for any two cities (to see if it could be accessing a resource from that city.

[Archmage]

Uuuuh....must find tylenol.......uhhhhghhhh

[Magician]

Re: Re: WRONG AND WRONG!

Originally posted by Nadexander


This is only for finding a path for any two given points (which worst case can never take more steps than the number of squares on the map. However It needs to calcualte the pairwise linking for any two cities (to see if it could be accessing a resource from that city.

As far as I know Johnson's algorithm is capable of finding all pair shortest path. It is not limited to finding a path from two vertex alone.

Btw, I don't think this is a shotest-path problem. If you find a path (trade route) from one city to another, no matter it is the shortest or not, will be accepted. Using shortest path algo will enumerate all vertex which is a big overhead.

So playing on a large/huge map != long wait. although the chance is higher.

[Combat Ingrid]

Maybe they should include DNA computers with the patch, they are supposed to be very efficient at doing this kind of stuff