1. We have added a Gift Upgrades feature that allows you to gift an account upgrade to another member, just in time for the holiday season. You can see the gift option when going to the Account Upgrades screen, or on any user profile screen.
    Dismiss Notice

Genetic AI Development

Discussion in 'Civ4 - Community Enchancement Project' started by The Great Apple, Aug 30, 2006.

  1. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    I have been poking around the AI code myself, just trying to get a handle on what it does.

    I found something in AI_foundValue (in CVPlayerAI.cpp), which I think could stand a change. This routine is used to evaluate locations to found a new city.

    line 1527 (near the end):

    Code:
    iValue /= (max(0, (iBadTile - (NUM_CITY_PLOTS / getAIVar(90)))) + getAIVar(91)); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    this will always ignore at least one bad tile, and, I think, tend to skew quite quickly away from the firaxis default. Might I suggest the following change?

    First, this is the same code, but more readable:
    Code:
    iTempValue = iBadTile - (NUM_CITY_PLOTS / getAIVar(90));
    iTempValue = max(0, iTempValue);
    iTempValue += getAIVar(91)
    iValue /= iTempValue; 
    
    Now, here is the agorithm change:
    Code:
    iTempValue = (getAIVar(n) * iBadTile) - (getAIVar(n+1) * (NUM_CITY_PLOTS / 4));
    iTempValue /= max(1, getAIVar(n+2)); // can remove max if AI var cannot be zero
    iTempValue = max(0, iTempValue);
    iTempValue += getAIVar(91)
    iValue /= iTempValue; 
    
    it also potentially has a divide by zero, unless none of your AI variables can be zero? If they cannot be zero, you 'could' change getAIVar(n) to (getAIVar(n)-1) and do the same for getAIVar(n+1), but that might have strange implications in your mutations, as a 0 or 1 value would be quite special.

    Which brings me to a more fundamental point. There are many cases where two variables are quite interlinked. For example:

    Code:
    iValue *= getAIVar(86); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    iValue /= getAIVar(87); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    This is really just one variable, but a fractional one.

    Have you considered making a more fundamental change and using floating point (or fractional) numbers for your AI variables? You could do this with near zero processing cost if you wanted, by integrating math functions into the lookup, creating fuctions like:

    Code:
    int addAIVar(int value, int aiVarIndex)
    int multiplyByAIVar(int value, int aiVarIndex)
    int divideByAIVar(int value, int aiVarIndex)
    int divideAIVarBy(int value, int aiVarIndex)
    
    so the above would become:

    Code:
    value = multiplyByAIVar(value, 8687);
    where 8687 is the old 86 value divided by the old 87 value in a floating point (or fixed) number.

    The function call overhead is going to be more than the math, so you will lose no time over just doing a lookup. In fact, it may be faster, becase it is one call, instead of two.

    You might want to add a flag or two to pass, to invert one or the other parameters, and to specify the order.

    Anyway, it is a thought, it would allow each variable to be truely unique. Currently, I would hazard to guess that upwards of 20% of your variables are related in this way, meaning that the ratio of the two is what is important, so values of 30 and 60 for the pair is the same as 300 and 600 for the pair. This could end up wasting a lot of generations and testing.

    Actually, now that I think about this, I have another solution. Replace all the divisors by some fixed number that works well with the range of AI values. So, if your AI values can range from 1 to 1000, a good divisor might be in the 50-100 range. (The higher your max AI value, the safer it is to pick a divisor).

    If the divisor is constant, then only one value is changing, and you do not have to make the floating point change. In effect, you are almost using fixed point numbers. In theory, you could even use different divisors in different places, but you probably want to at least have them be multiplied by some constant (I would suggest a constant in C, rather than reading a number from XML or some other variable, just for speed). Like so:

    Code:
    #define TGA_DIVISOR  100
    
    Going this way, the inital code changes to:

    Code:
    iValue *= getAIVar(86); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    iValue /= TGA_DIVISOR; // TGA | AutoGenFunction | v0.02 | 24 August 2006
    -Iustus
     
  2. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Continuing the same idea, the same function, lines 1529-1532:

    Code:
    if (pPlot->getBonusType() != NO_BONUS)
    {
    	iValue /= getAIVar(92); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    }
    Note the original firaxis value is 4. I cannot see how very high numbers are going to do anything but wildly skew this out of all meaningfulness. You can use the same constant to normalize this value and make values meaningful.

    Code:
    if (pPlot->getBonusType() != NO_BONUS)
    {
    	iValue *= TGA_DIVISOR; 
    	iValue /= getAIVar(92); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    }
    Of course, if you do this, all old values for AIVar(92) should be multiplied by TGA_DIVISOR. But this would allow for much more range of values.

    Without the change, it is likely that useful values are going to be in the range of 1-9 or so, with the change, they will be values from 100-900, much more variability. Without the change, assuming the value is allowed to mutate from 1 to 1000, then 99% of the mutations will be useless, or actually worse, 99% of the mutations will cause the AI in this case to ignore whether it is founding a city on a bonus, which means that in all likelyhood, all successful AIs will do this.

    I suspect there are many cases where the range of mutation is similar, causing most of the values to be wildly out of the 'useful' range. By adding some math like this, you can force them to be more in the correct range.

    In fact, each specific algorithm can be tuned to only vary a specific amount by doing some math on that constant.

    I would suggest that the smart way to do it is to just have a constant which is this:

    Code:
    #define  MAX_TGA_AI_VALUE     1000
    Then the above changes to:

    Code:
    if (pPlot->getBonusType() != NO_BONUS)
    {
    	iValue *= (MAX_TGA_AI_VALUE/10); 
    	iValue /= getAIVar(92); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    }
    The compiler will still create a constant in this case. You could create a default value still, but I would do it like so:

    Code:
    #define TGA_DIVISOR  (MAX_TGA_AI_VALUE/10)
    This is assuming that the goal is a number which is a percentage, which ranges from 1% to 1000% (ie from 0.01 to 10.0 times)

    -Iustus
     
  3. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    The same function, lintes 1534-1549 (the end):

    Code:
    if (bStartingLoc)
    {
    	iDifferentAreaTile = 0;
    
    	for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    	{
    		pLoopPlot = plotCity(iX, iY, iI);
    
    		if ((pLoopPlot == NULL) || (pLoopPlot->area() != pArea))
    		{
    			iDifferentAreaTile++;
    		}
    	}
    
    	iValue /= (max(0, (iDifferentAreaTile - ((NUM_CITY_PLOTS * getAIVar(93)) / getAIVar(94)))) + getAIVar(95)); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    }
    Here this is just an agorithm error in the Firaxis agorithm. This bug causes the AI to not like to start civs on the coast (yes there is a fudge factor for that above), but even so.

    The fix is to make sure that we only count land plots on a different area, like so:

    Code:
    if (bStartingLoc)
    {
    	iDifferentAreaTile = 0;
    
    	for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    	{
    		pLoopPlot = plotCity(iX, iY, iI);
    
    		if ((pLoopPlot == NULL) || (!pLoopPlot->isWater() && (pLoopPlot->area() != pArea)))
    		{
    			iDifferentAreaTile++;
    		}
    	}
    
    	iValue /= (max(0, (iDifferentAreaTile - ((NUM_CITY_PLOTS * getAIVar(93)) / getAIVar(94)))) + getAIVar(95)); // TGA | AutoGenFunction | v0.02 | 24 August 2006
    }
    -Iustus
     
  4. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Mutation is +/- 0-20% +/- 0-2. The percentage will work on the large numbers, while the integer should tweak small numbers. Currently the values have a lower threshold of 1, so we can't get any divide by 0 errors. This means that the bonus value you highlighted, for example, could only change between 2 and 6 in one mutation with approximate chances as follows:

    2 ~ 4%
    3 ~ 10%
    4 ~ 70% (remains default)
    5 ~ 10%
    6 ~ 4%

    EDIT: Actually this is incorrect. There is a very small chance of 7 (~1%) as I round the sum.

    As you can see, the chances of a massive skew for each individual variable are quite low. Over the whole set there are likely to be quite a few which skew a relatively large amount either upwardly or downwardly, but this is want we want.

    I do, however, like the idea of a constant divisor. It would allow the removal of the slightly dodgy integer mutation which I've never really liked, and put it all in the hands of percentages. It also means we can get more precise values for values nearer to 1 there are sevaral values which default to 1. I'm not sure what the magnetude should be - I would imagine 100 would be large enough to prevent any problems (max default value is 100000, which can mutate upward...)

    If you want to make changes to the AI code be my guest. For the sake of keeping things tidy I would suggest you implement your code as I have, with only the boolean check to see if it should be active in the source, and a new class for your functions with inheritance similar to the ones I've set up. If you add any new variables you'll have to enter default values in genAIData.py - it's pretty self explanitary in there, just make sure you add anything new at the end.

    Also, if you see anything in the genetic code that you feel could do with a tweak (if, for example, one value should never be larger then another and it could possible be) feel free to tweak away.

    I'm in the process of setting up a project on sourceforge which should allow us to do source control a bit better. Currently the best way of sorting it is probably for people to post their updated files on the forum and I'll merge them together.


    -----
    FYI: The way I assigned the genetic variables was a bit haphazard and perhaps could have been done more effectively had I taken more time over it, however, to be honest, browsing through tens of thousands of lines of code changing the odd value here and there would take for ever (I did about 50 variables this way and it took several hours)... so I did it automatically (took about 2 hours for ~ 1200 variables). This is why there are some jumps in variable number occasionally, and why some are missing (I checked each one based on some context, but I may not have got it right ;)).
     
  5. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Another random thought about player value randomization. At the moment there are random factors thrown in by Firaxis, but, unfortunetly randomness is probably bad in AI vs AI confilcts, and so we're probably going to get value inflation to cancel out the random factor.

    Would it be a good idea to make the random value to be a percentage fluctuation of the value? This should get rid of value inflation, hence keeping things a bit random. This might not be neccessary as the whole genetic AI process is going to make the AI pretty unpredicatable anyway.
     
  6. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Ahh, that makes a lot of sense. That solves 'most' of the out of range problem.

    To my mind, bigger is better. I would suggest using 1024, as the math would be much faster. (You could use 128, but I like 1024, that gives room for more variation, without really getting close to MAX_INT)

    As far as adding a constant divisor, I think that is the kind of thing you should do. In order to do it properly, and not invalidate old data, you need to have a method for multiplying the old values by the divisor. Perhaps a table listing the multiplyer for each old value to each new value, or at least a list of booleans for each AIvalue that says whether it needs to be increased.

    Ideally, this would be something that could change over time, although that makes the data file more complex. That way over time, you could covert more and more variables to using a constant divisor, rather than doing them all in one pass.

    Once you have the general framework done, if there is an easy way to update individual variables to switch to using a divisor, and to depricate old no longer used variables, I would be happy to help on this.

    Where is this code, I am not seeing it in the files I downloaded.

    Great. I will probably wait until this is done before trying to make any large changes. For the most part, right now, I have been walking through the Warlords SDK version (and comparing with the 161 SK version), trying to learn how the AI code works. In the places where I was interested, I then compared specific routines to your changed versions, and commented above.

    ----------

    By the way, what version of visual studio are you using? I am using Visual Studio.net Pro 2003.

    I do not thing the project file that was included with the source files I downloaded is the one you use, as it does not include any of the TGA_ files which create new subclasses. The files are there, but they are not part of the project. I suspect you have a modified VC++ Project file which was not part of the sources you are distributing. That or you are using a totally different IDE.

    Or perhaps I am just missing something in Visual Studio. I am not that familiar with it.

    I can build the 161 and warlords SDK, but I cannot build your version as of yet, although I have not put much effort into it.

    Any suggestions on how best to set up my directories to work with multiple versions of the SDK, and with cvs, would be appreciated. I have just installed TortoiseCVS, but I am completely unfamiliar with it (although I am familiar with cvs in general).

    -Iustus
     
  7. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Can you be more specific about what you mean here? What sort of change are you suggesting?

    There are a lot of different kinds of randomization. For example:

    1. random variables generated each turn which are used in many calculations all over the AI
      • the random optimistic bonus that an AI will give to all of its combat evaluations. This is modified by the leaderhead, which is why someone like Napoleon will consistantly overestimate his chances in every battle, and attack with poor odds
    2. the random extra weight given an item when calculating 'worth' of something
      • 0-2000 given to each tech when deciding which tech to research next
      • extra weight given when deciding which promotion to pick
    3. the random choice whether or not to do a particular action, typically this is generated by rolling 0-n, and if the roll is 0, then we preform the action
      • Deciding when to start a war (preparations)
      • Deciding when to demand tribute

    Do you mean just changing some of these or all of them? Do you mean to change the function that generates random numbers or change some of the locations that make the calls to generate random numbers?

    This could be as big (or bigger) an undertaking than adding all the variables used by the genetic AI in the first place.

    -Iustus
     
  8. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    I was planning on - I meant more generic alternative algorithms for the AI toggable by booleans.

    Sorry - not clear enough. I meant if you see when browsing through the code areas where, say, variable 345 must be larger then variable 346 unless weird things happen feel free to change it. I'm pretty sure there some logic breaking down to do with assigning unitAIs but I can't seem to find it.

    VS 2005 Express to compile, though I use codeblocks as an IDE. I forgot to update the VS files to include the files I added. Sorry!
    My folder structure is as follows:

    My Documents/My Games/SMC4/MODS/Genetic AI DEV/Assets (python files go here)
    My Documents/My Games/SMC4/MODS/Genetic AI DEV/CvGameCoreDLL Genetics (SDK)

    Upon completing a compile the .dll file in the assets directory is automatically replaced with the compiled one. You'll need the boost libraries in the SDK folder (they are not included in the .zip).

    I must admit to being not very familier with CVS in general - I plan to work it out as I go along... it usually works!
     
  9. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Sorry, again me not being clear. Number 2. As this random value is probably not helpful in AI vs AI games it'll probably slowly get removed by inflation of all the other numbers. Changing them to multiply the end value by a random number instead of adding a random number would cause randomness without the risk of this inflation (although it would randomize larger values more, which may or may not be bad).

    Number 3 should probably fall under the realm of the genetics as well. I think I missed most, if not all of them on my first sweep.
     
  10. Craterus22

    Craterus22 Chieftain

    Joined:
    Oct 7, 2001
    Messages:
    689
    Way to go!



    Not sure what you mean exactly, (EDIT - had to re-read that - now i understand) but I would suggest assigning genai randomly for one of the two leader attributes. Each genai's highest attribute could be used as the indicator for the first assignment.

    As each civ leader comes up for assignment, do a 50/50 roll to select which attribute to pick.

    Then from the small pool you created select the highest rated genai for that attribute.
     
  11. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    http://sourceforge.net/projects/civ4geneticai/

    If you PM me your SourceForge account names I can add people as Devs, which should allow you to tinker with the CVS. Current source and assets on there should be up to date and working.


    I've also implemented matching of leaderhead flavours to AIs. Unfortunetly the way this has done tends to cause the best AIs to be picked first (as they are better at everything). This means that it's likely that player 0 (the one the human views) will win more often then others. This doesn't actually make any difference at all, but it looks a bit funny.
     
  12. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Might have a rather big potential improvement here:

    http://forums.civfanatics.com/showthread.php?t=185926

    Basically, I believe the vanilla AI odds calculator is quite a way off. It doesn't return the right values, completely messing up the AI combat. Definately something that can be improved IMO.
     
  13. se7en

    se7en Chieftain

    Joined:
    Apr 17, 2003
    Messages:
    96
    i'm protocol7 on sourceforge

    here's the dna lab tool (although i haven't uploaded it yet, haha.) i'll add you as a dev in case i fall off the planet or whatever.

    https://sourceforge.net/projects/dnalab
     
  14. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Could somebody who knows more about C++ then me take a look at this for me?

    This function finds the best allocation of plot improvements for a city and determines the yield from this allocation. I'm worried it's leaking memory.

    The bit I'm worried about is aaaiPlotYieldImprovement. I've inialized it as a pointer to a two dimensional array, and then used the new command to allocate a third dimension of size determined at runtime (from XML). Look for the bits in bold.

    Now it works, but I've a strange feeling that the way I've done it is causing the array not to be deleted after completion of the function. Is this so? If so, how would I remedy it? Would cycling through all the entries in the original 2D array which I initialized the third dimesion off and deleting them work? (as in delete [] aaaiPlotYieldImprovement[iI][iJ]; (see bold bit at bottom of code))

    Thanks for any help! I'm kinda learning as I go along. It's a pretty big number crunching algorithm which is why I decided to store all the possible results in an array rather then working each one out from scratch each time. BTW - does anybody happen to know any way of timing this individaul function? I tried profiling, but couldn't find where the results were logged to. It runs a bit more often then I would like, and I'm conecerned about it's speed.

    Code:
    int TGA_CvCityAI::TGA_calculateOptimalCityYield(YieldTypes eYield, int iPopDrop, bool bSetImprovements)
    {
    	CvPlot* pPlot;
    	int iPlotYield;
    	int iBestPlotYield;
    	int iCityYield;
    	int iCityFood;
    	int iPlot;
    	ImprovementTypes eImprovement;
    	ImprovementTypes eTempImprovement;
    	ImprovementTypes eFinalImprovement;
    	ImprovementTypes eBestImprovement;
    	BuildTypes eBuild;
    	BuildTypes eBestBuild;
    	bool bBonus;
    	int iI, iJ, iK;
    
    	bool abUsedPlots[NUM_CITY_PLOTS];
    	ImprovementTypes aeImprovementsForPlot[NUM_CITY_PLOTS];
    
    	// char szDbgMsg[256];
    
    	// Store all the possible improvement combinations on each plot for each yield type in an array.
    	// As each calculation needs to be done 100s (or 1000s) of times this should make things zoom in comparison.
    [B]	int* aaaiPlotYieldImprovement[NUM_CITY_PLOTS][NUM_YIELD_TYPES];[/B]
    
    	for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    	{
    		if (iI != CITY_HOME_PLOT)
    		{
    			pPlot = getCityIndexPlot(iI);
    
    			for (iJ = 0; iJ < NUM_YIELD_TYPES; iJ++)
    			{
    [B]				aaaiPlotYieldImprovement[iI][iJ] = new int[GC.getNumImprovementInfos()];[/B]
    
    				for (iK = 0; iK < GC.getNumImprovementInfos(); iK++)
    				{
    					aaaiPlotYieldImprovement[iI][iJ][iK] = 0;
    				}
    
    				for (iK = 0; iK < GC.getNumBuildInfos(); iK++)
    				{
    					eImprovement = (ImprovementTypes)GC.getBuildInfo((BuildTypes)iK).getImprovement();
    					eBuild = (BuildTypes)iJ;
    
    					if (pPlot->canHaveImprovement(eImprovement, getTeam(), true))
    					{
    						eFinalImprovement = finalImprovementUpgrade(eImprovement);
    
    						if (eFinalImprovement == NO_IMPROVEMENT)
    						{
    							eFinalImprovement = eImprovement;
    						}
    
    						if (GET_PLAYER(getOwnerINLINE()).canBuild(pPlot, eBuild, false, false))
    						{
    							aaaiPlotYieldImprovement[iI][iJ][eImprovement] += TGA_calculatePlotYield(pPlot, eImprovement, (YieldTypes)iJ, false);
    						}
    						aaaiPlotYieldImprovement[iI][iJ][eImprovement] += TGA_calculatePlotYield(pPlot, eFinalImprovement, (YieldTypes)iJ, true);
    					}
    				}
    			}
    		}
    	}
    [spoiler=Unimportant actual work-doing code]
    	iPopDrop = -1;
    	iCityFood = 0;
    	iI = NUM_CITY_PLOTS;
    
    	while (GC.getFOOD_CONSUMPTION_PER_POPULATION() * iI > iCityFood)
    	{
    		iCityFood = getCityIndexPlot(CITY_HOME_PLOT)->getYield((YieldTypes)YIELD_FOOD);
    		iCityYield = getCityIndexPlot(CITY_HOME_PLOT)->getYield(eYield);
    		iPopDrop += 1;
    
    		for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    		{
    			abUsedPlots[iI] = false;
    			aeImprovementsForPlot[iI] = NO_IMPROVEMENT;
    		}
    
    		for (iI = 0; iI < (NUM_CITY_PLOTS - iPopDrop); iI++)
    		{
    			if (iI != CITY_HOME_PLOT)
    			{
    				eBestImprovement = NO_IMPROVEMENT;
    				eBestBuild = NO_BUILD;
    				iBestPlotYield = 0;
    				bBonus = false;
    
    				for (iJ = 0; iJ < NUM_CITY_PLOTS; iJ++)
    				{
    				    if (iJ != CITY_HOME_PLOT)
    				    {
    						if (!abUsedPlots[iJ])
    						{
    							pPlot = getCityIndexPlot(iJ);
    
    							if (canWork(pPlot), true)
    							{
    								for (iK = 0; iK < GC.getNumBuildInfos(); iK++)
    								{
    									eImprovement = (ImprovementTypes)GC.getBuildInfo((BuildTypes)iK).getImprovement();
    									eBuild = (BuildTypes)iK;
    
    									if (pPlot->canHaveImprovement(eImprovement, getTeam(), true))
    									{
    										eFinalImprovement = finalImprovementUpgrade(eImprovement);
    
    										if (eFinalImprovement == NO_IMPROVEMENT)
    										{
    											eFinalImprovement = eImprovement;
    										}
    
    										// Always use the bonuses
    										if (pPlot->getBonusType(getTeam()) != NO_BONUS)
    										{
    											if (GC.getImprovementInfo(eFinalImprovement).isImprovementBonusTrade(pPlot->getBonusType(getTeam())))
    											{
    												eBestImprovement = eImprovement;
    												eBestBuild = eBuild;
    												bBonus = true;
    												iPlot = iJ;
    
    												break;
    											}
    										}
    
    										if (GC.getFOOD_CONSUMPTION_PER_POPULATION() * iI >= iCityFood)
    										{
    											iPlotYield = aaaiPlotYieldImprovement[iJ][YIELD_FOOD][eImprovement];
    
    											if (iPlotYield > iBestPlotYield)
    											{
    												iBestPlotYield = iPlotYield;
    												eBestImprovement = eImprovement;
    												eBestBuild = eBuild;
    												iPlot = iJ;
    											}
    											// In a tie we want to find the best one for our yield
    											else if (iPlotYield == iBestPlotYield)
    											{
    												if (eBestImprovement != NO_IMPROVEMENT)
    												{
    													eTempImprovement = finalImprovementUpgrade(eBestImprovement);
    
    													if (eTempImprovement == NO_IMPROVEMENT)
    													{
    														eTempImprovement = eBestImprovement;
    													}
    												}
    												else
    												{
    													eTempImprovement = NO_IMPROVEMENT;
    												}
    												if (aaaiPlotYieldImprovement[iJ][YIELD_FOOD][eFinalImprovement] > aaaiPlotYieldImprovement[iJ][YIELD_FOOD][eTempImprovement])
    												{
    													eBestImprovement = eImprovement;
    													eBestBuild = eBuild;
    													iPlot = iJ;
    												}
    											}
    										}
    										else
    										{
    											iPlotYield = aaaiPlotYieldImprovement[iJ][eYield][eImprovement];
    											if (iPlotYield > iBestPlotYield)
    											{
    												iBestPlotYield = iPlotYield;
    												eBestImprovement = eImprovement;
    												eBestBuild = eBuild;
    												iPlot = iJ;
    											}
    										}
    									}
    								}
    								if (eBestBuild == NO_BUILD)
    								{
    									iPlotYield = TGA_calculatePlotYield(pPlot, NO_IMPROVEMENT, eYield, true);
    									if (iPlotYield > iBestPlotYield)
    									{
    										iBestPlotYield = iPlotYield;
    										iPlot = iJ;
    									}
    								}
    							}
    							else
    							{
    								abUsedPlots[iJ] = true;
    							}
    						}
    				    }
    				}
    
    				//sprintf(szDbgMsg, "eBestImprovement: %d, iBestPlotYield: %d", eBestImprovement, iBestPlotYield);
    				//logMsg(szDbgMsg);
    
    				if (iBestPlotYield != 0 || bBonus)
    				{
    					// These can't be arrayed - the array takes into account if we can build it or not. This doesn't.
    					iCityFood += TGA_calculatePlotYield(getCityIndexPlot(iPlot), eBestImprovement, YIELD_FOOD, true);
    					iCityYield += TGA_calculatePlotYield(getCityIndexPlot(iPlot), eBestImprovement, eYield, true);
    
    					abUsedPlots[iPlot] = true;
    					aeImprovementsForPlot[iPlot] = eBestImprovement;
    				}
    				else
    				// We've run out of plots that can be worked
    				{
    					break;
    				}
    			}
    		}
    	}[/spoiler]	[B]// POTENTIAL FIX?
    	for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    	{
    		if (iI != CITY_HOME_PLOT)
    		{
    			for (iJ = 0; iJ < NUM_YIELD_TYPES; iJ++)
    			{
    				delete [] aaaiPlotYieldImprovement[iI][iJ];
    			}
    		}
    	}[/B]
    
    	if (bSetImprovements)
    	{
    	    for (iI = 0; iI < NUM_CITY_PLOTS; iI++)
    	    {
    			if (iI != CITY_HOME_PLOT)
    			{
    	            m_aeRecommendedImprovements[iI] = aeImprovementsForPlot[iI];
    			}
    	    }
    	}
    	
    	return iCityYield;
    }
     
  15. suspendinlight

    suspendinlight Chieftain

    Joined:
    Oct 23, 2005
    Messages:
    446
    Location:
    Urbana, IL
    Just to preface, I'm definately not a C++ expert and I don't know much about how to interface with Civ 4 or what libraries are available, but here's some comments:

    For the timing issue, include time.h and then do the following:
    Code:
    clock_t time = clock();
    ...
    ...
    ...
    time = clock()-time;
    printf("Function time is: %fs.\n", time/(float)CLK_TCK); // if you want seconds, which you probably don't
    About the memory leak, yes that is a memory leak if you are never deleting anything. Rather than using new & delete, I would prefer to use an array of std::vector<> which is dynamic but also doesn't require you to delete the contents manually as with new. If you want to do it with new/delete you are going to have to do the delete operation.

    If you want to do vectors you might just say (I assume but don't know that this will work with 2D arrays):
    Code:
    std::vector<int> aaaiPlotYieldImprovement[NUM_CITY_PLOTS][NUM_YIELD_TYPES]
    ...
    ...
    ...
    aaaiPlotYieldImprovement[iI][iJ].resize(GC.getNumImprovementInfos(), 0);
    ...
    ...
    ...
    // aaaiPlotYieldImprovement[iI][iJ][iK] = 0;
    // get rid of this altogether with the resize command
    ...etc
    
     
  16. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    yes, you are leaking memory.

    You could look at
    SAFE_DELETE_ARRAY()

    which is what is used all over the place, but that does not really solve the problem.

    I would suggest a different solution.

    What about adding these to the classes themselves.

    You could have each plot know what the best improvement is for that plot (it defaults to UNKNOWN)

    Then once each turn, calculate the best improvement for every plot that belongs to every city of that player, prior to using them.

    Then that routine is just a lookup.

    Yes, there are some issues with some data being out of date, but it will only be at most 1 turn out of date, and usually not even that, if you place the recalculate in the right spot.

    This does slightly violate the style of Civ to constantly recalculate everything, but honestly, isnt that a good thing?

    You could add a slight sanity check when deciding worker actions to make sure that nothing drastic has changed, if you feel it necessary.

    You might want to force a recalc every time you learn a new tech, this would catch almost all of the issues with timing.

    The plot could also store the best yield info if you want to cache that as well.

    the 'get' function you will be using off the plot class should be smart enough to do the recalc if the value is UNKNOWN of course. But you want to force it to be redone every turn, even if it is known.

    You also probably want to set the value to UNKNOWN on a plot when the owner of a plot changes, to force an immediate recalc.

    An alternative is to store it in the city class, but that is going to end up being a rather large array that way. Additionally, the info will not move when you change a plot from one city to another, like it should.

    You definitely should avoid calling new (and delete) that frequently. Worst case, you could put your entire array, unaltered in the city class, create the array if it does not exist, otherwise just use the existing array, recalculating numbers every time. This would at least avoid the new/delete thrashing.

    If you wanted to be even more efficient, you could only do a recalc per plot when that plot is changed (ie forest grows, etc), changes hands, or a new tech is learned. This would be a bit tricker, and more prone to bugs (ie, missing a case where something changed), which is why I suggested doing a forced recalc every turn.

    -Iustus
     
  17. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Currently there are two steps going on:

    1) For each improvement for each plot that the city can work, or may be able to work in the future, get the yield of the plot with that improvment. Assign to aaaiPlotYieldImprovement.

    2) Using those improvements work out the theoretical maximum yield of the city, and which improvements these require. This can change if any of the plots change in the city, and influences what the workers will build. Previously this would calculate the improvement yield again every time, which was quite time consuming, so I decided to do it only once.

    Now I'm pretty sure step 2 is fine memorywise - it's step 1 that I don't much like. I think I might take you're advice and have it updating each time in CvPlot::doTurn() - it's really where it belongs and will avoid all this temperary big array business, making it much more perminent. It should also run a bit smoother.

    Thanks for the help!
     
  18. Iustus

    Iustus Chieftain

    Joined:
    Jul 18, 2006
    Messages:
    609
    Location:
    Sunnyvale, CA
    Welcome.

    I would recommend only doing the calculations for plots that are contained within a city's fat grid. (You need to know the owner player of a plot to calculate improvements he can build anyway)

    -Iustus
     
  19. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Updated the CVS to version 0.34.

    *Added constant divisor of 1024 to all values.
    *Fiddled around with some of my alternative algorithms.
     
  20. The Great Apple

    The Great Apple Big Cheese

    Joined:
    Mar 24, 2002
    Messages:
    3,361
    Location:
    Oxford, England
    Bad news. I'm going to be away from a computer with Civ for the next 8-10 weeks (for verious unexpected reasons), which means I won't be able to work much on this.

    As v0.34 has several huge glitches I think we will have to revert to 0.33 for this time, unless somebody else has some tweaks that they would like to make in the mean time. If this is the case feel free to compile and PM/email me a version (with a changelog) and I'll update it.

    I'll have about 5000 AIs on me so I'll be able to update the main thread.
     

Share This Page