Well its been more than a year since I last posted.  This isn't because I've stopped developing the game, its because I found I was spending too much time posting and too little time coding!

Anyway, I've made major progress since the last post.

I have started implementing my AI opponent.  Actually, I'm on my 3rd try.

The first two attempts taught me a lot but in both cases it was clear that they would not work for large scenarios.  The key realization was that the problems I was trying to solve were NP-Hard problems and any attempt to use purely deterministic methods would be pointless because of the time required.

I did extensive study of stochastic local search techniques and developed a resource allocation solver that is used both for strategic deployment and managing fronts at the tactical level.

So far I have been pretty pleased with the results.

Basically, I divide the territory into regions based on cities. So each region is a collection of cells closest to a city. This is done once at scenario creation time and is automatic. So if I change the scenario in the editor, I hit a function that recalculates these regions.

My basic turn consists of the following:

Before I do anything, I go through all my units and identify any that are 'unfit for combat' (low morale, strength, lack of ammo, supplies, etc) and reserve them to move to a supply chain and or HQ.

I also identify any units that are fatigued and rest them. Both of these are taken out of the general unit availability list for the rest of the turn.

Then I identify what I call 'regions of interest'. These are all the regions on the border between me and the enemy that are contested.

Once I've done that, I then try to allocate my forces to each region based on a scoring system that takes into account the victory points for each region (based on their city) and the relative troop strength that I would have if I moved my forces there. I use a stochastic local search solver to try to find the best allocation of units because I found that a brute force system was just taking way too long.

Once that is done, I use strategic movement (land and rail) to move my units to the regions where they have been assigned.

That completes what I call the strategic stage.

The next stage is to go through each region and assign an operational plan to the region based on who controls it, relative troop strength and some other factors like whether it is connected to my supply system. I currently have identified 12 distinct operational plans. Some are attacking, some are defending and some are administrative (consolidate, secure supply lines, etc.)

That completes the operational stage.

Finally, I go through each region and using its designated operational plan, I execute my tactical movement which consists of moving units, invading enemy cells, attacking, withdrawing, and a few other things. The movement is particularly complex as I need to identify a front and then find the best way to allocate my available units in the front. I use the same stochastic local search solver for that.

I keep looping through my tactical turns until there are no more units that can do anything useful.

After all of that, I make one more trip through all my units and do things like entrench, upgrade equipment, train, rest, etc. I'm working on a pecking order scheme based on the global situation.

As far as where I'm at:
I'm mostly done with the strategic movement although it still needs some tweaking.
I've implemented most of about 5 of the simplest operational plans.
I've completed movement, withdraw, invade and combat on the tactical level but at a very primitive stage. I have a lot of complex decisions that need to be made about where and how to attack that are still being worked out.

I also have future plans for a learning system that will evaluate games and try to use them to improve play.

Fortifications

Finished fortifications.  


Every cell in the game can have fortifications on each of its hexsides from level 1-10.  However only forts up to level 3 can be built during the game, the other levels are reserved for major fortification systems built in peace time like the Maginot Line. These can only be built in the editor.


This following enhancements were made:


1) Enemy units invading an occupied hex across a hexside that has fortifications will automatically be fired upon by the forts.  The forts increase both the hard and soft attack factors of the defending units.  Forts can be reduced by enemy engineers.


2) A new brigade type was added, engineers.  These are similar to infantry but they have some short range heavy weapons with anti-armor capability.  They also have a number of special abilities including building fortifications, reducing enemy fortifications and bridging rivers (not yet implemented).


3) A new strategic command was added, build forts.  Any time an unmoved unit that has brigades with this ability in a non-combat hex and has adequate supply and energy, it can attempt to increase the fortification level of one hexside up to a maximum of level 3.  There is a percentage chance depending on the number of brigades involved but whether it works or not it will consume a large number of supplies and energy.


4) A new operational command was added, reduce forts.  An invading unit with engineer brigades entering a fortified hexside can attempt to reduce it.  This also has a percentage chance of success and will result in some casualties.  This will also increase the recon level of the unit which will increase the likelyhood of future success.


Next up...


Victory conditions

Unit Production

Unit production is mostly complete pending a few tweaks.  Here's a summary taken from the manual:


Unit production is handled in the Unit Production Toolbar.  This can be activated by clicking the tank symbol on the main control toolbar:


The Unit Production Toolbar is divided into 3 areas:

1) Resource summary - This shows all of the available resources for building units (men, afvs, planes, etc.)

There are 4 lines:

1) Prod Rate - This shows the number of new soldiers being trained each turn and the number of key equipment types being produced.

2) Reserved - This shows the percentage of each type being reserved for new unit creation (as opposed to reinforcement).  Left clicking on the +/- buttons will increase/decrease the percentage by 1.  Right clicking will increase/decrease by 10.

3) Available - This shows the number currently available for building units.  They will be applied to units in the production queue at the beginning of next turn.

4) In Transit  - When you cancel a unit that is in production, all men and equipment are considered ‘in transit’ for a turn.  Also, when units are destroyed in combat, some soldiers will make their way to the in transit queue.  Finally, disbanded units send their men and equipment to the in transit queue.  They will be transferred to the available queue at the beginning of next turn.  

2) Available units - This shows a summary of all the available units that can be built along with details as to their commanding unit, resources needed, earliest arrival turn, etc.  Clicking on the categories above the units will toggle each type on and off.  Clicking on the page up and page down arrows will page through them.  Right clicking will go to the start / end of the list.  Clicking on a header will sort by the data in that column.

Of special note is the Avail T (available turn) column.  This column indicates the first turn that the unit will become available.  Even if all the resources required to build a unit are on hand, it still will not be deployed until this turn so it is better to wait until you are close to the available turn of a unit before moving it to the production queue.

The unit name shows the HQ in parentheses after it.  If the HQ is not currently on the map, it will also show an asterix.  To create a unit, click on its name.  The Unit Production Toolbar will temporarily close and the map will have all available deployment cities highlighted.  Clicking on one of these cities will set that as the deployment city.  The toolbar will reopen and the unit will be moved to the bottom of the ‘in production’ queue.  Clicking anywhere else on the map will cancel the build and reopen the toolbar.

3) In Production - This shows a list of all units currently in production including their progress, arrival city, earliest build turn, etc.  They are sorted in order of priority and will be filled with available resources in the order shown.  The two numbers separated by the ‘/’ symbol indicate the number assigned / number needed to complete the unit.  Units are filled at the beginning of each turn from available resources in the order they appear in this list.  The Build T column indicates the number of remaining turns until the unit is ready to be deployed.

Units can be moved up and down through the list by clicking on the arrows in the Order column.  Right clicking moves them to the beginning / end.

As with the available units, categories can be turned on and off by clicking on the category tag above the list and the page buttons will move up and down through the list.  The deployment city is shown in the City column.  Clicking on it will temporarily hide the toolbar and center the map on this city.

To cancel a unit, click on its name.  This will move the unit back into the available queue.  However, any resources assigned to the unit will be moved to the ‘in transit’ category and be unavailable for a turn.

Next up fortifications....

More optimization results

I created sort of a super scenario to test my optimizations.  I've beefed up both sides by about 5x and France now has an army of 231 corps containing 924 divisions totaling over 11 million men!  The actual French Army in WWII consisted of about 123 divisions so this mock up is approximately 7 1/2 times as large.

This is just to see if my supply system is large enough to handle a very large army.

Anyway, here's the timing logs before optimization:

 111661852|         0|Supply Points to Units
 111704450|     42598|Depots to Units
 111727008|     22558|Depots to Units
 111756022|     29014|Rail to Units
 111773117|     17095|Cities to Depots
 111775071|      1954|Depots from cell

The first column shows the clock, the second the time elapsed since the last log and the third a description of what happened.  Note, the time for an action appears on the line AFTER the description.  The total of the 4 highlighted actions is 111,265 milliseconds or about 1 minute 50 seconds.  Total time for the complete cycle is about 2 minutes.

Here's the same timing log after optimization:

  33627270|         0|Supply Points to Units
  33627866|       596|Depots to Units
  33628545|       679|Depots to Units
  33628928|       383|Rail to Units
  33637130|      8202|Cities to Depots
  33639272|      2142|Depots from cell

We are now down to a very reasonable 9860 milliseconds or about 10 seconds.  Total time for the complete cycle is now about 19 seconds.

This can be cut down even further and will probably have to be once Russia comes on board but for now its good enough to not get in the way of further development.  

So I'm on to the next stage:

Unit production....

Some new screenies

I've completely reworked Spain and built out France as a complete nation.  This was needed to support the new supply network, otherwise French troops ran out of supplies very quickly and were easily defeated by well supplied Spanish troops.


Here are some screenies:

This shows the new peak layer which was surprisingly difficult to do. After trying various overlay techniques, I found that cloning the mountain layer to another layer with a bluish white overlay and a large bluish white outer glow provided the best effect.  I also had to darken the mountains a bit to provide enough contrast.

 This shows the peaks in the Alps.

 Zoomed out view of France showing the large rail network and cities.

This is zoomed in a bit more to show the new look of the rail.  Finally was able to get a double rail look by using a 5 pixel line followed by a 2 pixel eraser.  The ties are a custom brush that had to be recreated after my hard drive disaster wiped out all of my photoshop brushes.  Finally realized to take notes on all these effects and save off custom brushes as separate files so I can recover them next time.

Some optimization results

Well the first stage of my optimization has been a resounding success.  I changed the way I check whether units are in range of their HQ at the begining of a turn.  This determines command for the entire turn which has a wide range of implications including morale, organization and the ability to execute advanced commands.


I dropped the time it took to calculate the French side (3 HQ's and 31 corps) from 7.5 seconds to 0.4 seconds.  If we assume about 600 Corps for the peak of the Soviet Army, we get about 7.7 seconds which is reasonable.  The previous method would have been an excruciating 2 minutes and 25 seconds!


How did I get such an increase in efficiency?  Well it was quite simple, I quit doing it the stupid way.


I have 2 basic functions that represent the core of the map navigation capabilities in my game:


1) GetPath - Given a unit, a target and a command (move, advance, air transport, sea transport, etc) it will return the most efficient path as a vector of cells.


2) GetCellsInRange - Given a unit, a command and a range, it will return a vector of all cells reachable with those constraints.


Interestingly enough, (2) takes approximately as long as finding a path to the furthest cell in the range.  In fact, (1) can be implemented by first executing (2) and then walking back from the target cell to the starting cell by always going to the neighbor cell with the lowest total travle cost (this is essentially Dijkstra's Algorithm).  It CAN be implemented that way, but it isn't because that would negate the efficiency of the A* algorithm which starts with Dijkstra's algorithm and adds a constraint that cuts down on the number of wasted cells that must be checked.


Before I optimized, I used the rediculously slow method of cycling through each unit and trying to plot a path back to its HQ.  I switched this around and went to each HQ and found all cells within the HQ's command range and marked them.  Then I simply cycled through each of the HQ's children and checked if that cell had been marked as in range.  For the example above, this reduced the number of path checks from 31 to 3.  But its even bigger than that because units that were far from their HQ would have been even more inneficient under the old system.  And HQ's that happen to be in low mobility territory like mountain ranges would be extremely quick to calculate.


My next step is to apply the same idea to locating supply cities.  Like before, I was cycling through each city and attempting to plot a rail path back to the capital.  I will attempt to switch it around and use (2) starting from the capital to identify all supply cities.

Supply and reinforcement done... sort of

Supply and reinforcement is functionally complete but it is extremely slow.


I like the functionality and I've built out France to be a complete nation so that the French troops will have their own supply chain while they invade Spain in my mythical test scenario.


Normally, it is considered bad form to optimize prematurely.  There are a lot of good reasons for this, the biggest being that you are likely to make changes down the road that will force you to re-optimize later.


However, I've decided to bite the bullet and tackle it now for a couple of reasons:
1) It is so slow that it will make testing everything painful.  This will cause a development inefficiency as I have to wait every time I hit the new turn button.
2) It is slow even with the relatively small countries and armies of France and Spain.  What happens when I get Russia built out with a 4 million man army???  If I can't make it fast now, I'm in big trouble when the complete game is done.  Might as well find out now if my supply chain system is just flat out too slow and needs to be scrapped and re-written.
3) Most of the optimization should be doable by simply caching the previous supply chain and then having some sort of test to determine how much of it needs to be recalculated.  This is fairly straightforward.
4) The supply chain code is fresh in my mind right now.  If I come back to optimizing it in 3 months, I will need to bring myself back up to speed.


So, taking that all into account, I'm extending this release to include an optimized supply chain procedure...