Performance

[Koshling]

Figured I might as well start a new thread for this topic since it comes up a lot.

As you may know, I'm on an ongoing crusade to improve turn times, and most weeks I spend at least one day profiling and trying to improve matters. As I mentioned a few days ago, a save game I had to fix a WFoC issue also struck me as displaying nasty performance issues, so I spent a while looking into that save game a bit more deeply. That quickly identified the problems with the great commander game option, which I've posted about elsewhere.

Anyway, I got back to the same save game again today, and delved a bit deeper. What I found was quite interesting. I already knew that a lot of the time spent on AI turn processing was in unit path evaluation, as it decides between different options (in that save game, which is pretty typical for a mature game on a large map, it was evaluating about 40,000 paths per turn). The thing I hadn't realized, until I analyzed it more carefully, was that only a few hundred of these path evaluations were dominating the total. A major cause is units deciding on a target city for a potential attack, where they check out every potential enemy city on the same landmass. On large maps that are highly connected this can amount to practically every city in the game, and, more importantly, VERY distant cities. The cost of evaluating the optimal path to a plot rises roughly with the square of the distance, so these tests of distant cities wind up contributing highly disproportionately to the total time spent.

I'm working on changes to alleviate these costs, but the interesting take out for now is that very large land masses will seriously impact the game performance. The test game in question was a giant map of earth, with the north pole providing an ice bridge, which essentially means the entire world is one land mass apart from a few 'islands' (Australia primarily). Until I manage to address this (and even then to some extent, since although I expect to be able to reduce the issue, it won't entirely go away) I recommend archipelago, or island maps, or at least those that tend to have multiple continents.

 

[velosepappe]

So does this mean that it doesnt check diplomatic relationship before deciding which cities to check?

THere are multiple ways to try to tackle this. It seems to me that breaking up landmasses like you implied would diminish the amount of potential city targets.

Maybe each civ could also have a list of cities that that are on borders of regions that you have free access to (open borders, neutral territory, same landmass), and only these cities to choose from.

Could you tell me where the code is for these path evaluations? Is it easily readable?

 

[Koshling]

So does this mean that it doesnt check diplomatic relationship before deciding which cities to check?

THere are multiple ways to try to tackle this. It seems to me that breaking up landmasses like you implied would diminish the amount of potential city targets.

Maybe each civ could also have a list of cities that that are on borders of regions that you have free access to (open borders, neutral territory, same landmass), and only these cities to choose from.

Could you tell me where the code is for these path evaluations? Is it easily readable?

It's nhat quite that simple unfortunately (the obvious stuff is mostly done already). Consider the following:

1. Yes it does winnow out the players it has good relations with first and only considers those it might gi to war with in principle
2. On borders is not a well defined concept. Consider cases where the immediate neighbors are currently friends or vassals and enemies lie beyond them
3. Close is itself I'll-defined. Railway lines for example can make something far away closer in pahing terms than something quite close
4. Crow flies distance is not closely related to path distance in most maps. Large bays, promontories of land, etc. Can mean that the land path is much longer than the direct path (as can missing open bord agreements)

I'm working on the relevant code, but if you would like to take look start with CvUnitAI::AI_pickTargetCity() (that's from memory, so might be slightly mis spelt, but it's something like that)

 

[velosepappe]

I'm working on the relevant code, but if you would like to take look start with CvUnitAI::AI_pickTargetCity() (that's from memory, so might be slightly mis spelt, but it's something like that)

I had a first look in the CvUnitAI::AI_pickTargetCity code, not easy as its currently my first look in the civ code. If I'm not mistaken each unit or stack of units looks for possible target cities each turn (isPotentialEnemy)? Then for each possible target the optimal path is chosen. Of course this is calculation intensive, I dont know how how it scales with distance but I would guess its order distance^2. Something I have thought of is using a multilevel approach. First determine regions, for example the part of land inside the border of a player civ. Then search for optimal paths between the central locations in regions for different (unit) movement types and store them (would require some storage space). This can be reused for all units inside a certain region. Possibly store the location of where this path intersects the starting (a) and destiny (b) region. Then each unit needs to only calculate the path from starting location to (a) and from (b) to destiny. If start and destiny are near enough (for example in neighbouring regions) the path could be calculated in the old way. Of course this method of pathfinding is suboptimal so you could possibly toggle between the two modes in the late game. For better performance you could even divide each regions into subregions, but you need the storage space ofcourse. And it would have to update every few turns due to infrastructure changes etc.

 

[Koshling]

I had a first look in the CvUnitAI::AI_pickTargetCity code, not easy as its currently my first look in the civ code. If I'm not mistaken each unit or stack of units looks for possible target cities each turn (isPotentialEnemy)? Then for each possible target the optimal path is chosen. Of course this is calculation intensive, I dont know how how it scales with distance but I would guess its order distance^2. Something I have thought of is using a multilevel approach. First determine regions, for example the part of land inside the border of a player civ. Then search for optimal paths between the central locations in regions for different (unit) movement types and store them (would require some storage space). This can be reused for all units inside a certain region. Possibly store the location of where this path intersects the starting (a) and destiny (b) region. Then each unit needs to only calculate the path from starting location to (a) and from (b) to destiny. If start and destiny are near enough (for example in neighbouring regions) the path could be calculated in the old way. Of course this method of pathfinding is suboptimal so you could possibly toggle between the two modes in the late game. For better performance you could even divide each regions into subregions, but you need the storage space ofcourse. And it would have to update every few turns due to infrastructure changes etc.

I tried that (well I didn't precalc reguions, but I used cached paths and proximity code for being nearish the start / end point of a cached path, but its similar). Turns out the issue is worse than I had thought (which causes this sort of appoach to fail), in that the pathing engine is actually much better at caching than I had thought, and the cost was over 95% on the FIRST (long) path to be calculated for each stack, whichmeans that even seedng th cache with a few paths (or precalculatin the region linkage equivalently) costs as much as the whole thing was before anyway.

I have another approach that I think will work though - more later after I get time to experiemnt some more.

 

[velosepappe]

I tried that (well I didn't precalc reguions, but I used cached paths and proximity code for being nearish the start / end point of a cached path, but its similar). Turns out the issue is worse than I had thought (which causes this sort of appoach to fail), in that the pathing engine is actually much better at caching than I had thought, and the cost was over 95% on the FIRST (long) path to be calculated for each stack, whichmeans that even seedng th cache with a few paths (or precalculatin the region linkage equivalently) costs as much as the whole thing was before anyway.

I have another approach that I think will work though - more later after I get time to experiemnt some more.

I dont really get it. You mean that for each stack that should be moved in unison 95% of the time was used on calculating the optimal path for the first unit? That would make sense as any unit moving seperately would take a pretty similar path. In fact its like searching for a worst case. But could you use information from previous stacks on different stacks? I read a comment in the code that this gave problems. This multilevel algorithm wouldnt use paths that other stacks have allready used but would have to store information on interregional travel in a new file. Probably it would also pose difficulties to stacks with units with different movement rules.

 

[Koshling]

I dont really get it. You mean that for each stack that should be moved in unison 95% of the time was used on calculating the optimal path for the first unit? That would make sense as any unit moving seperately would take a pretty similar path. In fact its like searching for a worst case. But could you use information from previous stacks on different stacks? I read a comment in the code that this gave problems. This multilevel algorithm wouldnt use paths that other stacks have allready used but would have to store information on interregional travel in a new file. Probably it would also pose difficulties to stacks with units with different movement rules.

No. Movement is calculated for the entire stack anyway, that's not the issue. I mean for the first PATH (that went a long way). Calculating a subsequent path that ended vaguely near (VERY vaguely) the first one is extremely cheap (due to I think caching in the pathing engine, which is not part of the DLL). What this means is that calculating just a few represenative paths (like inter-region paths) is pretty much as expensive as calculating all the paths it does now.

Edit - yeh caching stuff for use by DIFFERENT stacks is fraught with issues due to chnages hat things like promotions can make (double forest movement, abiliy to cross mountains, etc.)

 

[velosepappe]

No. Movement is calculated for the entire stack anyway, that's not the issue. I mean for the first PATH (that went a long way). Calculating a subsequent path that ended vaguely near (VERY vaguely) the first one is extremely cheap (due to I think caching in the pathing engine, which is not part of the DLL). What this means is that calculating just a few represenative paths (like inter-region paths) is pretty much as expensive as calculating all the paths it does now.

Edit - yeh caching stuff for use by DIFFERENT stacks is fraught with issues due to chnages hat things like promotions can make (double forest movement, abiliy to cross mountains, etc.)

Thanks for the reply. What do you think makes moving AI units that much more costly in the later ages if most of the paths have allready been calculated? in any case I will keep on following this, many people are praising you for the progress C2C has made, and I agree I feel C2C has made huge leaps on that aspect. I dont know if I can help you with this problem but if you would like to, please point me to other points of the code which you would like some input on (even if you didnt find it all that helpfull)

 

[Koshling]

I think I may have a solution to this, though its a bit sticking-plasterish.

Ultimately we need to stop the AI considering things that cause it to try to generate paths to things that are 'obviously too far away to be interesting', which is going to be very dependent on the calling context (so will have to be weeded out context by context).

However, for now I think I have successfully constructed a path-distance approximation method that works fairly well and is a lot less expensive (9 seconds to under 2 seconds in the game turn I'm testing with).

What it does is this:

1) Calculate a raw path length using the map distance calculator - this is a separate and much simpler use of the path generator that depends only on land/water and impassable terrain boundaries. It gets cached more or less persistently and is not unit specific. It's already used in various contexts and is very cheap. Basically it gives an idea of the 'geographic' distance involved, but has no clue about political divides, routes, stack speed etc.

2) If the raw path length is under a 'closeness' threshold just go ahead and do the real path evaluation

3) Otherwise do a real path evaluation on a short leading subpath of the raw geographic path generated. Use this to evaluate an approximation of the ratio of the raw path length to the stack-specific path length based on that ratio for the subpath. Return the total raw path length normalized by this ratio.

In principle this could exhibit pathological behaviour when the target is the far side of a region controlled by a third party with whom you do not have an open borders agreement (the raw path would go straight through, the actual would go around), but by only using the approximation for paths that are already known to be geographically long it means the distortions only occur for distant targets. Since these are almost cetainly NOT the best attack candidates anyway this is unlikely to matter in practise. I could probably improve on this by stepping along the raw path, evaluating whether it was a valid step for the actual stack and increasing the estimate heuristically by adding an extra assumed step in the approximate length for each unpathable link in the raw path (so if 10 steps of the raw path go through the territory of a third party we cannot path through add 10 to the assumed actual path length). Right now I don't think this is worthwhile, but I need to do some more testing...

Edit - after playing with this a bit, I have pushed this change to SVN. I'm not 100% happy with it due to the distortions it introduces but it does speed things up and I am fairly confident the distortion won't have any real-world effect except in extremely extremely rare cases (in which case the AI will pick a sub-optimal city in terms of the way it's intended to work, though since that's anyway sometimes way off in 'human' terms I doubt anyone would notice)

 

[strategyonly]

Just thought i would bump this any see if anyone has anymore problems lately??

 

[Thunderbrd]

I believe there are a few bugs my games have been exhibiting that sound pretty well explainable via this discourse... now that I know this thread is here I can update it with more info after I encounter them again. Been a bit since I've seen the actual problems and I keep not mentioning them because I don't know if they've been fixed on the current version or not. Anyhow... I'll eventually have more to say

 

[ls612]

Performance has been a slight issue for my OLD pc, but I'm not too concerned as I'll be upgrading to a new, much more powerful computer in a month or two. Turn times though have gone up a good bit since the new pathing engine was put in, I assume it's because of all the new assets we add.

 

[Samin]

Regarding performance, is it a known issue that in later stages of a game, the city screen becomes really slow and unresponsive, especially putting a building into the queue will take a second or two before you can do anything again (scroll the building list or queue another building)

Currently at work and can't post a save but I thought I ask first if this is a known problem or something that needs more investigation.

 

[Tipsy3000]

Thats a problem with the base game there samin, its something to do with a memory leak due to how the game engine is written or something like that. Simply restart the program and the problem goes away.

 

[Samin]

Thats a problem with the base game there samin, its something to do with a memory leak due to how the game engine is written or something like that. Simply restart the program and the problem goes away.

It certainly persists through game sessions. It is worse on larger cities, new found cities with less buildings in them still suffer some "lag" but the big ones are really bad. The game currently uses roughly 2gb ram and seems to keep more than 1 core of my cpu busy (that's idle in the background while I type this). Note though that is on a gigantic map (GEM) but with no AI players (not that that should be any problem while it's my turn and I'm in the city screen anyway) - not sure if that can factor in somehow.

 

[Koshling]

It certainly persists through game sessions. It is worse on larger cities, new found cities with less buildings in them still suffer some "lag" but the big ones are really bad. The game currently uses roughly 2gb ram and seems to keep more than 1 core of my cpu busy (that's idle in the background while I type this). Note though that is on a gigantic map (GEM) but with no AI players (not that that should be any problem while it's my turn and I'm in the city screen anyway) - not sure if that can factor in somehow.

Yeh, I think it's the new(ish) Python for sorting and filtering that just has a lot to do when there are many buildings available. It's probably addressable with some simple caching, but it's never made the priority list as yet.

 

[animalvgamer]

I have a suggestion for the AI calculations. If possible to rewrite AI decisions, I have an idea.

- Localized Unit AI. Units have independent AI, which only search for potential actions within a radius somewhat scaled with map size.

- Idle tags, in order to effectively use a localized AI that a Nation can still use to see the whole map, have an activity index. A unit which finds little to do will lower this number.

- Once this number hits a threshold, a one time calculation will make the AI search for another target. Then this cycle will continue, scans of large maps should happen far less frequently, and it should speed up AI calculations.

 

[Koshling]

I have a suggestion for the AI calculations. If possible to rewrite AI decisions, I have an idea.

- Localized Unit AI. Units have independent AI, which only search for potential actions within a radius somewhat scaled with map size.

- Idle tags, in order to effectively use a localized AI that a Nation can still use to see the whole map, have an activity index. A unit which finds little to do will lower this number.

- Once this number hits a threshold, a one time calculation will make the AI search for another target. Then this cycle will continue, scans of large maps should happen far less frequently, and it should speed up AI calculations.

Way ahead of you ;-)

1) Almost all AI searches are already localized (only searches more broadly when there is nothing to do locally, and even then only a small subset of the AI types do this)

2) For military units the ONLY non-localized search is looking for a city attack target, and that serach optimizes the order it considers things in (closest first) and has a threshold cutoff that aborts consideration when the score for a more distant city canno exceed the best score it has found so far

3) I am moving steadily to a contract brokerage system in the AI, whereby a local search in one part of the map finds something and posts a contract for any necessary unit support. Units with no priority action then consider responding to this (at a priority depreciated by distance), thus avoiding any need for them to do the search themselves.

The big time consumers in V22 and earlier were pathing calculations (i.e. - after target identification, figuring our how to get there, in the cases wheer the targets ARE distant [or worse unreachable in practise]).

In V23 this cost is no longer dominant (I wrote an entirely new pathing engine, that is considerably more performant). Right now there is no single dominant cost. City production choice is fairly significant, unit movement remains significant, but not in any one aspect any more, trade network changes can still be costly, diplomacy is now up there (AI consideration of the possibilities of that is).

There is lots more I can do, but right now, no low hanging fruit. If you have a game that is playing slowly post it and I'll do a detailed end-turn processing profile of it and se if it displays any hot-spots.

 

[animalvgamer]

Cool, then how about this:

Individual Military stacks don't search for targets independently, AI chooses a number of cities based on a percentage of the enemy targets, and weighs them. These get added to a table, and units must only choose from those cities to target. The idea is, limit the amount of choices each AI calculation has to go through.

 

[Koshling]

Cool, then how about this:

Individual Military stacks don't search for targets independently, AI chooses a number of cities based on a percentage of the enemy targets, and weighs them. These get added to a table, and units must only choose from those cities to target. The idea is, limit the amount of choices each AI calculation has to go through.

It has a cache that more or lesss serves this function, but it's probably an area that can be improved. However, until it shows up as a hot spot on a profile (generically , this applies to anything) it's not worth spending effort there. First rule of optimization - optimize the parts that are shown to be taking a long time based on real profiles. Otherwise you end up making something 100 times faster, but since it only took 1% of the total time only having a 0.01% impact on the end result.