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.