Shared AND/C2C Debug codes

Thunderbrd

Thunderbrd

C2C War Dog
Joined
Jan 2, 2010
Messages
29,813
Location
Las Vegas
Since Afforess is back and working on the dll in AND and we've had some good discussions we determined the need for a thread to share any significant debug codes with one another. We've been intermittently sharing these across AND and C2C through 45* for a while now but not reliably and I sometimes wonder how greatly both sides may suffer for this.

So from now on, I'll be posting any code adjustments I need to make to fix issues here with some brief explanation as to why and where it was (if a small snippet.) I believe Afforess is equally committed to sharing what they've found and debugged with us all the same.

Here's to a new spirit of cooperation between both great mods founded on common structures!
 
To start:
I found the caching here is truly problematic. I added notes that explain:
Code: 
bool CvPlot::isInUnitZoneOfControl(PlayerTypes ePlayer) const
{
	//Check adjacent tiles
	//TB fix - this cannot be reasonably cached or we'll need to include the players that are creating ZoCs into the caching data - otherwise this can affect your own units!
	//if this removal of caching slows things down tooo much we'll need to go ahead and upgrade m_iPromotionZoneOfControl to a boolean array that considers the player creating the zone -
	//but even that can be wrong in simultaneous turns when units can move and the ZOC should move with them.  So caching works for cities ok when a check is added to make sure that the owner
	//of the city creating the ZOC is one at war with the group that wants to move through the ZOC but not so well for units in any situation.
	//if (m_iPromotionZoneOfControl > -1)
	//{
	//	return m_iPromotionZoneOfControl;
	//}

And here:
Code: 
bool CvPlot::isInCityZoneOfControl(PlayerTypes ePlayer) const
{
	if (m_iCityZoneOfControl > -1)
	{
		if (GET_TEAM(GET_PLAYER(ePlayer).getTeam()).isAtWar(GET_PLAYER(getOwner()).getTeam()))
		{
			return true;
		}
		return (m_iCityZoneOfControl > -1);
	}
If you reference your side of the code you'll likely see that the caching is not checking to make sure that it's STILL a ZoC generated by an enemy, thus your own ZoC CAN end up counting against your own units! These code bits should repair this problem.

I'll be updating these to C2C soon as well - they are not yet committed to the SVN and may not be for a day or two as another adjustment in the code still needs some testing (not a debug.)
 
Hm, I noticed those caches too, and I was worried they were too simplistic as well. (I didn't implement the caching, I don't know who actually did) My concern is that adding a boolean array for all players adds significant memory overhead, considering the number of CvPlot objects created in a map.

The way Zone of Control is calculated also makes caching problematic. To determine if there is a zone of control, the game has to:

check the units on the current plot
check the units on all adjacent plots
examine the unit for the zone of control attribute
check if the teams are at war

Considering ZoC is checked frequently for pathfinding, this is a serious performance issue.

One idea I had for caching in a different way would be to use a (hash) map stored in CvPlayer that contains iX, iY indices to tiles that under zone of control. Typically there are only a few tiles (usually fewer than 100, rarely above 1000) under any zone of control. The map would store these tiles, and it would be recomputed at the end of each players turn.

Then the check for zone of control would be:

loop all players
check each player we are at war with
check to see if this tile x,y is in the player's zoc hashmap
 
The White Wizard said:
Hm, I noticed those caches too, and I was worried they were too simplistic as well. (I didn't implement the caching, I don't know who actually did) My concern is that adding a boolean array for all players adds significant memory overhead, considering the number of CvPlot objects created in a map.
Click to expand...
That's exactly why I didn't feel it was going to be better to try to implement a caching there at all and figured it would be best to just leave it uncaching (this means some slowdown unfortunately which has become a BIG issue for some of late but it's better to work properly and not overload the system as a whole than it is to have more speed imo.)

check the units on the current plot
check the units on all adjacent plots
examine the unit for the zone of control attribute
check if the teams are at war

Considering ZoC is checked frequently for pathfinding, this is a serious performance issue.
Click to expand...
That's right though. And caching it at all such that it will only adjust at the end of a turn means that mid-turn moves will create problems during simultaneous play turns.

One idea I had for caching in a different way would be to use a (hash) map stored in CvPlayer that contains iX, iY indices to tiles that under zone of control. Typically there are only a few tiles (usually fewer than 100, rarely above 1000) under any zone of control. The map would store these tiles, and it would be recomputed at the end of each players turn.

Then the check for zone of control would be:

loop all players
check each player we are at war with
check to see if this tile x,y is in the player's zoc hashmap
Click to expand...
I'm not too comfy working with hash maps yet but if you build that out I'd be interested to evaluate it. Can this overcome the simultaneous turns problem though? I suppose such caching could be turned off entirely if simultaneous turns are on to fix that.

Afforess said:
I also made a few fixes and changes to some of my previous features that may be relevant:

Updated Tech Diffusion

Zone of Control Changes

Advanced Diplomacy: Trading Water Units

Ruthless AI: Backstabs

Ruthless AI: Buying War Allies
Click to expand...
It'll take a while to go through those... but I appreciate them being shared.


Along those lines, you'll want to take note of the Ranged Bombard Rework that's recently taken place here. I realize you'll probably want to address the problems very differently (and maybe earn some fans in so doing since some of my opinions on this seem to be controversial) particularly since you aren't using multiple combat classes in AND but I'm sharing it with you because its a reaction to some very real problems in the ranged bombard mission's effective programming. We had a TON of units here that were supposed to be able to Ranged Bombard and could do so but without any effect and I believe we adopted that in from AND so could still be an issue for y'all as well.
 
Thunderbrd said:
That's exactly why I didn't feel it was going to be better to try to implement a caching there at all and figured it would be best to just leave it uncaching (this means some slowdown unfortunately which has become a BIG issue for some of late but it's better to work properly and not overload the system as a whole than it is to have more speed imo.)
Click to expand...

Another, even simpler option is to just keep track if any units that cause zone of control have been constructed. If this is stored globally, you can skip the entire logic until such a unit is built. That is the simplest caching mechanism, but is ineffective once such units exist.

Thunderbrd said:
I'm not too comfy working with hash maps yet but if you build that out I'd be interested to evaluate it. Can this overcome the simultaneous turns problem though? I suppose such caching could be turned off entirely if simultaneous turns are on to fix that.
Click to expand...

Hash maps are a pretty simple data structure, and are included in the C++ std library. I've used them a lot in other languages.
 
Afforess said:
I also made a few fixes and changes to some of my previous features that may be relevant:

Updated Tech Diffusion

Zone of Control Changes

Advanced Diplomacy: Trading Water Units

Ruthless AI: Backstabs

Ruthless AI: Buying War Allies
Click to expand...

Hi

I found alot errors and smaller coding errors in the last months it's hard to post all of them here but in the future i will.

Examples from CvTeam, GET_PLAYER((PlayerTypes)iI).getID() is wrong here must be getTeam().
Code: 
void CvTeam::changeTradeModifier(int iChange)
{
	if (iChange != 0)
	{
		m_iTradeModifier += iChange;
		for (int iI = 0; iI < MAX_PLAYERS; iI++)
		{
			if (GET_PLAYER((PlayerTypes)iI).[B][COLOR="Red"]getID() [/COLOR][/B]== getID() && GET_PLAYER((PlayerTypes)iI).isAlive())
			{
				GET_PLAYER((PlayerTypes)iI).updateTradeRoutes();
			}
		}
	}
}

int CvTeam::getForeignTradeModifier() const
{
	return m_iForeignTradeModifier;
}
void CvTeam::changeForeignTradeModifier(int iChange)
{
	if (iChange != 0)
	{
		m_iForeignTradeModifier += iChange;
		for (int iI = 0; iI < MAX_PLAYERS; iI++)
		{
			if (GET_PLAYER((PlayerTypes)iI).[B][COLOR="Red"]getID()[/COLOR][/B] == getID() && GET_PLAYER((PlayerTypes)iI).isAlive())
			{
				GET_PLAYER((PlayerTypes)iI).updateTradeRoutes();
			}
		}
	}
}


I noticed in the AND forum posts about CTD's because of missing ArtInfos take a look at the changes from rev6841.
This adds displaying a error message in case of a missing ArtInfo
then using a release dll and a not perfect fix for a possible CTD.
 
Thanks for those alberts2,

I would love it if someone familiar with the AI path generator could take a look at this stackoverflow in the CvPathGenerator I found in a players save.

You can use the latest RAND SVN and the save here: http://forums.civfanatics.com/showpost.php?p=13207256&postcount=1845

What happens is the recursion in DeleteChildTree in CvPathGenerator leads to a StackOverflow. I don't really understand what should be going on for me to adequately debug. The stack wasn't that big (only 40-50 function calls on the stack queued up).

I also caught a nasty missing return in CvGameCoreUtils, in rare cases the function would not return anything, likely corrupting the game.


There were also some other general fixes and improvements of AI logic.
 
Afforess said:
Thanks for those alberts2,

I would love it if someone familiar with the AI path generator could take a look at this stackoverflow in the CvPathGenerator I found in a players save.

You can use the latest RAND SVN and the save here: http://forums.civfanatics.com/showpost.php?p=13207256&postcount=1845

What happens is the recursion in DeleteChildTree in CvPathGenerator leads to a StackOverflow. I don't really understand what should be going on for me to adequately debug. The stack wasn't that big (only 40-50 function calls on the stack queued up).

I also caught a nasty missing return in CvGameCoreUtils, in rare cases the function would not return anything, likely corrupting the game.


There were also some other general fixes and improvements of AI logic.
Click to expand...

The recursion can legitimately be as deep as the longest path, typically up to a few hundred. The statement that the stack was only 40-50 deep AND it was a stack overflow don't seem entirely consistent! Does that method have a large stack frame? If so it may be that it is that which needs to be tackled.
 
Afforess said:
Another, even simpler option is to just keep track if any units that cause zone of control have been constructed. If this is stored globally, you can skip the entire logic until such a unit is built. That is the simplest caching mechanism, but is ineffective once such units exist.



Hash maps are a pretty simple data structure, and are included in the C++ std library. I've used them a lot in other languages.
Click to expand...

A few (possibly useful, but no guarantees!) observations:

1) You probably cannot live entirely without this ZoC caching without crippling performance
2) I agree that the current code appears to be over-simplistic, at least viewed in isolation.
3) To tackle this effectively you need to know more about the usage patterns. In particular, during player A's turn processing, is the routine called with ePlayer always, or very predominantly equal to A? If so the current simplistic system can easily be amended by adding an eCachedForPlayer, which records what player the cached value corresponds to, and only returns from cache on a match, else does the full calculation (or uses a slower second level hash cache). Cache invalidation policy then becomes the main issue to worry about - do you replace the cache-for-player with the Player of the last request? Is it better to set it up in advance to be the player whose turn it is, and not allow that to change during the turn? Maybe you allow changes based on monitored hit-rate? There are many possibilities.
4) Whatever caching scheme you use you will almost certainly need cache invalidation calls that can be made on critical events such as:
4.1) Start of a new player's turn slice - this may or may not be strictly necessary, bu it shouldn't cost much and it errs on the safe side
4.2) Movement of any GG with a ZOC promotion (only needs to invalidate for plots in a certain range)
4.3) Construction of any building or improvement that has Zoc capabilities (again with limited range)
4.4) Death of any GG with a ZOC promotion
 
Koshling said:
A few (possibly useful, but no guarantees!) observations:

1) You probably cannot live entirely without this ZoC caching without crippling performance
Click to expand...

Removing that ZoC cache had a big impact but that was because the code for the CityZoneOfControl evaluation was really slow.
I made a few simple optimizations in rev7392 now it's alot faster.
 
Afforess said:
Thanks for those alberts2,

I would love it if someone familiar with the AI path generator could take a look at this stackoverflow in the CvPathGenerator I found in a players save.

You can use the latest RAND SVN and the save here: http://forums.civfanatics.com/showpost.php?p=13207256&postcount=1845

What happens is the recursion in DeleteChildTree in CvPathGenerator leads to a StackOverflow. I don't really understand what should be going on for me to adequately debug. The stack wasn't that big (only 40-50 function calls on the stack queued up).

I also caught a nasty missing return in CvGameCoreUtils, in rare cases the function would not return anything, likely corrupting the game.


There were also some other general fixes and improvements of AI logic.
Click to expand...

In C2C that nasty missing return in CvGameCoreUtils is already correct but i will take a look at the AI logic fixes. I have to take a look at the save to see if i'am able to fix that possible bug in the CvPathGenerator. I never saw something like that happening before.
 
alberts2 said:
Removing that ZoC cache had a big impact but that was because the code for the CityZoneOfControl evaluation was really slow.
I made a few simple optimizations in rev7392 now it's alot faster.
Click to expand...

Looks like we STILL could optimize significantly there with some caching, particularly for the unit side of the effect. We could end up with it being faster than it was by doing both what you've done AND what Koshling suggested. Been considering taking some of those steps myself actually.

Only thing is, Koshling, what you suggest still overlooks the possibility that multiple ZoCs from multiple players may exist on the same plot I think. This leaves me still pondering the best approach, which may well be something along the lines Afforess suggested. But you certainly brought up a nice list of cache invalidation points!

Also... I just did some interesting caching on the improvement upgrade stuff and I'd like you to give it a quick look over if you can find a moment to do so at some point... just to make sure I've done everything in the most optimal way. This is my first attempt with some of these caching mechanisms and I'm hoping I really hit where the processing was slowest but you might see some other ways or other positioning for some of those elements to improve on things that I don't.
 
Thunderbrd said:
Looks like we STILL could optimize significantly there with some caching, particularly for the unit side of the effect. We could end up with it being faster than it was by doing both what you've done AND what Koshling suggested. Been considering taking some of those steps myself actually.
Click to expand...


Not really because the gain is to low for the amount of needed changes and possible bugs.
With the save strategyonly posted in the bugs thread 5 turns take 233 seconds CvPlot::isInUnitZoneOfControl takes only 2. This is after a small change i made before it was 2.4 seconds.
 
Ok... cool :D You rock man! You tend to find very simple approaches that work true wonders and that's pretty cool and good for me to learn from.
 
Thunderbrd said:
Looks like we STILL could optimize significantly there with some caching, particularly for the unit side of the effect. We could end up with it being faster than it was by doing both what you've done AND what Koshling suggested. Been considering taking some of those steps myself actually.

Only thing is, Koshling, what you suggest still overlooks the possibility that multiple ZoCs from multiple players may exist on the same plot I think. This leaves me still pondering the best approach, which may well be something along the lines Afforess suggested. But you certainly brought up a nice list of cache invalidation points!

Also... I just did some interesting caching on the improvement upgrade stuff and I'd like you to give it a quick look over if you can find a moment to do so at some point... just to make sure I've done everything in the most optimal way. This is my first attempt with some of these caching mechanisms and I'm hoping I really hit where the processing was slowest but you might see some other ways or other positioning for some of those elements to improve on things that I don't.
Click to expand...

The golden rule of optimization is:

Measure what takes time and fix that. never fix things that are not consuming a lot of time even if you can see obviously better/faster ways to do them.

For this reason I totally agree with what Alberts says (don't bother). However, just for reference on this sort of problem should it arise in another context:

The issue you point out is a non-issue because it's a rare case. In this instance you would cache all the (common) one-player cases, and just cache a special value meaning 'invalid cache' for the (rare) two+ player cases. When the special value is encountered on a read it is just interpreted as a cache miss, and you fall back on the expensive full calculation. Since the cache still covers the common cases (overlapping ZOCs as a percentage of total tiles is a TINY percentage) you get almost all results coming from cache and still gain most of the savings (like 99.99%)
 
Koshling said:
The golden rule of optimization is:

Measure what takes time and fix that. never fix things that are not consuming a lot of time even if you can see obviously better/faster ways to do them.

For this reason I totally agree with what Alberts says (don't bother). However, just for reference on this sort of problem should it arise in another context:

The issue you point out is a non-issue because it's a rare case. In this instance you would cache all the (common) one-player cases, and just cache a special value meaning 'invalid cache' for the (rare) two+ player cases. When the special value is encountered on a read it is just interpreted as a cache miss, and you fall back on the expensive full calculation. Since the cache still covers the common cases (overlapping ZOCs as a percentage of total tiles is a TINY percentage) you get almost all results coming from cache and still gain most of the savings (like 99.99%)
Click to expand...

Ok, that's clever. I take it the 'even if you can see obviously better/faster ways to do them' bit is mostly due to any added memory it might require to do so?
 
I recently cut out all of the code related to the election & dark age features. It cuts down on the save and memory footprint lightly - at least its a very minor step towards a smaller footprint. Low hanging fruit.

Changes/Diff View.
 
You must log in or register to reply here.

Similar threads

PDX Firefly
Developer Diary | After the Demo
Replies
5
Views
975
Sephi
S
Recursive
  • Locked
New Version - 3.0.4 (November 29, 2022)
15 16 17
Replies
327
Views
42K
Recursive
Recursive
Blake00
  • Sticky
Vote for Sid Meier's Civilization I and II (MGE & Test of Time) to be added to GoG
2
Replies
25
Views
9K
Blake00
Blake00
TerrisH
Out of the Portals, a Never Ending Story.
2 3 4
Replies
61
Views
8K
Aiken_Drumn
Aiken_Drumn
Recursive
  • Locked
New Beta Patch - 1/9
4 5 6
Replies
119
Views
20K
Kim Dong Un
Kim Dong Un
Top Bottom