Programmers: Help me CUT TURN TIMES IN HALF OR MORE!

I have discovered a major bottleneck in turn times while working on the event engine. I did some painstaking turn time analysis because I thought my new events engine was causing some problems but I realized it was not the main source of the bottleneck.

So what was it? It was three triremes stuck behind my lines that could not move anywhere... so they always triggered the AI_explore() routine. By "moving" these ships back into their own territory I cut down turn times from almost 30 seconds to 10 seconds! This is a MAJOR PROBLEM! Later in the game another 20 seconds were being added to 20 second turn times causing me to wait almost a minute between turns!

The AI_explore() routine takes a minimum of 5 seconds every time it is called by a single unit (on a huge map)! Why? Because it tries every square on the board for a "best plot" and when it does this, it tries generating a path to each plot. THAT IS A LOT OF TIME.... path generation is very time consuming (relatively speaking).

So I want to come up with a way to fix this problem and it won't be easy. I have already come up with a partial solution that divides the board into exploration "areas" in a grid system that keeps track of how much of the area is explored. I have some good ideas on where to go as I have spent some time coming up with them.

My basic algorithm is headed towards direction finding rather than plot finding. Something like this:

Instead of scanning the board for individual plots, it will evaluate each plot it can move to in a single turn and use my "exploration grid" as a means to evaluate how much unexplored territory lies in the general direction of each of those possible moves.

By doing this, we may be able to redo the whole "exploration" algorithm. Currently exploration is done using two seperate algorithms. We may be able to combine them into one that takes quite possibly 1/200th or less of the time!

I'm not sure that I get your idea fully, but this sounds like a great goal.

I have what I think is a separate idea:

Divide the world up into a large grid of squares (with a square being a plot of tiles, say 10x10 tiles, or larger), and ordinally number the squares.

The squares have a true/false for whether they've been explored or not; Only unexplored, unassigned squares will be explored.

Each AI unit on explore orders is assigned one square as a target; The decision can be purely random---assignment by randomizer.

AI then beelines to the center of it's square, and then maps the square's tiles as a 2D linear array (no decision-making); To randomize the mapping, the first time the AI unit starts mapping, a random roll decides the orientation that the array is mapped. E.g. Work left to right, top to bottom, or some other permutation (e.g. bottom to top, left to right).

Once the explorer is done, the square is counted as explored. The next square targeted should be in the vicinity for efficiency.

Not very pretty, but if it's relatively simple with few decisions and no weighted analysis, then it should execute fast. If the squares are pretty small, the effect on the AI's game play should be pretty minimal (i.e. no disadvantage).


Another idea is to actually let the AI cheat a little (*boo* Hisss!! right?). Make tiles with resources its first target, and then have it move cardinally, ordinally, spirally out from the tile. Maybe make the AI target iron tiles (feed it the info as an invisible cheat) as bases of exploration. Or maybe even feed it very late game resources as bases, e.g. uranium, coal and oil, since those won't impact the game until very late if at all. To keep the AI from duplication during exploration, the targets will have to be numbered ordinally and assigned to units.

primem0ver said:

My basic algorithm is headed towards direction finding rather than plot finding. Something like this:

Instead of scanning the board for individual plots, it will evaluate each plot it can move to in a single turn and use my "exploration grid" as a means to evaluate how much unexplored territory lies in the general direction of each of those possible moves.

By doing this, we may be able to redo the whole "exploration" algorithm. Currently exploration is done using two seperate algorithms. We may be able to combine them into one that takes quite possibly 1/200th or less of the time!

Click to expand...

GoodGame said:

Divide the world up into a large grid of squares (with a square being a plot of tiles, say 10x10 tiles, or larger), and ordinally number the squares...The decision can be purely random---assignment by randomizer

Click to expand...

This is very close to my original idea except that 1-it is not simply true and false and 2-it is not randomly assigned.

My original idea involves a basic grid where each cell of the grid is 4 x 4 plots. This is VERY convenient because the way world size is determined and even defined in the xml is by numbers which are then multiplied by 4 to get the actual map size. It also coincides with being just slightly smaller than the vision range of a sea unit with "optics."

However, another grid system is used and superimposed over the one mentioned above: the board is then divided into 4 quadrants, and then each quadrant is subdivided into quadrants and so on until we have quadrants where one side has a minimum width of 2 and max of 3 cells. Depending on the size of the map there are anywhere from 3-6 layers or grids.

The cells and quadrants (grids) are all linked to the ones they overlay (macro => micro) and keep track of how many plots are in each and so it is very easy to manipulate the number of cells explored. So instead of having a boolean value, each cell/quadrant has an accessor that returns an int value representing the percent explored. These percents are used in weighing which area to explore first.

The above idea has a built in problem: where in the quadrant/cell should the ship move to (you suggested the center)? This problem arises from the fact that the "central" plot may not be valid for a particular unit. But that does not necessarily mean the unit cannot get to the grid area (for example, the one right next to the central plot may be fine!). So choosing a specific plot as a destination is nearly pointless.

The programming for my original (above) idea is already done because I thought I could get around this problem by creating a path regardless if the path was valid or not and then just make sure the first turn segment was valid. As long as it was, I could move to the first turn segment and then plan the rest of the journey later. This effectively moves the ship towards its destination and if it gets sidetracked by better opportunities, so what? It still solves the problem.

HOWEVER... I ran into a bug because the Civ4 executlable (which contains the path finding code) does not save path information if path generation fails like it does when it succeeds (I was very annoyed by this fact... why not save it until another path is attempted?).

So now I am trying the new approach I mentioned: focusing on testing nearby plots (within one turn of current position) instead of the whole board to get a general direction rather than a specific plot. My grid system should still help if I link it upwards (micro => macro which I did last night) because it contains information which will help the AI pick the best direction to access unexplored territory.

I would like to continue hearing ideas though because as I mentioned, this is not an easy problem to tackle.

This may be completely irrelevant, but it seems to me that the area searched should probably be limited to the maximum movement of the unit, no? Although I guess this would be bad for land units where tile improvements and differing terrain movement costs would cause real problems.

Dom Pedro II said:

This may be completely irrelevant, but it seems to me that the area searched should probably be limited to the maximum movement of the unit, no? Although I guess this would be bad for land units where tile improvements and differing terrain movement costs would cause real problems.

Click to expand...

LOL... yes... thats the whole point of what I am doing, although with the search grid I mentioned, it can still tell which parts of the map (beyond its range of movement) have the most unexplored territory.

I finished programming my first version and tested it. It seems to work ok, but there are some gliches that suggest I need to change the algorithm a bit. But let me just say this: I have removed (just for testing) the other explore routine and am ONLY using my own for sea units (it does not even do AI_exploreRange(int)).

As far as time...it works SO MUCH better. Only a small fraction of a second instead of 5 seconds!

Well, good... as someone who wants to pack his mod full of stuff, any reduction in processing time is music to my ears.

Keep in mind though that the AI_explore() routine is not called about 80% of the time. Only when units get stuck (such as triremes or other units with limited mobility) and later in the game when about 1/3 or 1/2 of the board is explored do you start to see a serious lag due to this issue. This is why turns in the late renaissance start to take a while and really start to climb in the industrial era.

When you get to modern times I think the main reason turns take a while is because there are so many units.

you could try changing the code in AI_Explore:


with something like:

which only looks at the 10x10 tiles centered at the unit.
But if I understood this code the AI kind of cheats looking at the whole map and chooses to explore in the direction tile with goodies and other good stuff, and you will be limiting it.

My guess is that generatePath() is the expensive part, which is used to know that the unit can actually get there and to calculate iValue. If two plots in the same area means you can get from one to the other you could replace generatePath() with a much less expensive, less accurate estimate.

But take all this with a big rock of salt cause Ive just started playing with the sdk.

As you get to learn the SDK you will find that Firaxis did a pretty good job with most things. A routine already exists called AI_exploreRange(some int) that does exactly what you suggest where "some int" is the radius. The problem arises when this range does not give any decent results (such as the entire surroundings are already explored and the unit must backtrack and find a new place to explore).

But thanks for the help.

Actually, this is a fairly common way of doing things in the SDK unfortunately. For example:
In other words, rather than have the areas keep track of what plots they contain, the plots keep track; whenever an area has any operation that involves its plots, it cycles through the entire plot list, top to bottom, asking "Hey, are you a part of me?".
It's probably not a huge ineffeciency in the big scheme of things, but it's a completely unnecessary one. Cobined with it being used for almost every operation involving areas (and who knows what other classes have similar problems), I'm guessing it adds up to quite a bit of unnecessary overhead.

I have noticed this victarus. You must also keep in mind though that while it may be faster in the short run, too much memory also slows things down even worse. There has to be a balance. As long as what you are suggestiong involves only a bit of memory, we are ok. But the more you keep track of, the more memory that is used. They probably could have removed some of this (which is why I am writing a whole new class to help with what you suggest) but there is a balance that must be kept between performance and memory usage. Finding that balance for any large project can be a challenge.

Of course there are also ridiculous shortcuts as well like AI_explore()!

Well I'm not talking about doubling where it's listed necessarily, but putting it where it would result in the least amount of overhead - in this case, listing the plots in the areas instead of vice versa (or, if it's used enough by both, put a pointer in both to eachother or something similar - the memory used for a pointer is minimal after all, less than saving an integer index to identify the area, albeit a little more risky).
The main question is which is used more: the getArea() call outside the area functions, or within the area functions? If the latter than the answer to should the data be moved is obvious. If the former, it's still a toss up depending on how much: after all, to find the plot's area would involve searching every area until that plot is found (which can till be faster if it's the last area if done properly), while doing an area-to-plot search involves searching every plot, even if all of the area's plots have been found.


Of course, this is just an example. Really though, there's probably a fair amount of room for optimization throughout the entire program, especially if it's more heavily modded.

memory use is, I dont know grid size for a huge map but suppose its 128x100 * sizeof(pointer) = 50KB, that would be 0.0002% of the ~300MB civilization4.exe is using as reported by the taskmanager.

and another idea:
if unit can't find usable plot for explore, there is very small probability, taht tis can be doable in next few turns too
so maybe unit will have a counter, which is set after unsuccessfull explore attempt (randomly from ie. 2 to 10 turns) and during this period this unit will skip AI_explore routine?

Mexico said:

and another idea:
if unit can't find usable plot for explore, there is very small probability, taht tis can be doable in next few turns too
so maybe unit will have a counter, which is set after unsuccessfull explore attempt (randomly from ie. 2 to 10 turns) and during this period this unit will skip AI_explore routine?

Click to expand...

That's not a bad idea... I haven't looked at the code, but it seems to me that the type of obstruction preventing a valid plot should determine the number of turns to wait... I mean, if it's a border issue, then it should be a long time before the unit tries to move again. However, if it's something that might change soon, the counter should be less.

Again, I'm just throwing that out there without having examined the conditions for the code.

the memory used for a pointer is minimal after all, less than saving an integer index to identify the area, albeit a little more risky

Click to expand...

True... and if that is all you are talking about, then fine. But it is not all I am talking about. I created a seperate class for the grid information I am saving to help speed things up. Keeping track of useful information simply be linking information together with a pointer. But if more than that is necessary (which from what you were describing seemed like the case), depending on the situation and how much you want to keep track of, it can get a bit taxing on memory usage.

But that is neither here nor there. We are hopefully making small additions to memory usage.

That isn't a bad idea Mexico if we can't do anything else... but I am going to try my grid system first and see if that helps solve the problem. Actually so far it is doing a good job. There is only one issue I have yet to get around. Sometimes units get stuck going back and forth because they see a good part of the board and move towards it. Then they realize they can't get to it and move back to the other good part of the board... and move back to the old position. But from there the cycle starts again.