A* Algorithm Optimizations

It is seems that part of the Out-of-Memory problem came from the fact that cells are re-traced more than one time for multiple possible routes. To solve this problem, an Opened Cells flag array is implemented; When a cell is calculated for possible route, the flag is set ensuring it won’t be recalculated again. And to further prevent unneccessary route trace, the A* heuristic function now take into account the current cell’s weight. Although this could result in less than optimal route, it also ensure a route is found much faster.

Implementation of Open Cells flag array result in elimination of lag spikes found in previous tests;

  • Memory usage dropped by 85% from 220 MB down to 34 MB
  • Process time dropped from 80% in spikes to an insignificant value of less than 5%

Overall, the algorithm optimization result prove to be much more successful than expected. More CPU intensive algorithm might now be added with much less worry than before.


Memory Optimizations

With a lots of Out-of-memory errors I have been getting, I decided to try optimizing the memory usage to help reduce the problem;

  • Grid coordinate (GridIndex) size is reduced from 4 to 2 bytes.
    Grid size is now limited to 128×128.
  • Weight data (RouteWeight) size is reduced from 16 to 8 bytes.

Finally, I have also remove dependancy of generic C# LinkedList class from my Tree data storage (SortedTree); By replacing SortedTreeNode.Children with internal child and sibling variables (FirstChild, LastChild, NextSibling and PreviousSibling). This last change result in approximately 50 – 100 MB reduction in memory usage.

Obstacle Avoidance Algorithm

Attempt at implementing obstacle avoidance using raycasting in a 3 steps process;

  1. Bezier algorithm guided curve movement using pure timer along pre-calculated path, regardless of obstacles.
  2. Every so often, raycasts are used to determine actual terrain obstacle in front of the unit. If an obstacle is detected, a preferred path is calculated regardless of the Bezier curve result.
  3. Using both algorithms, the unit will attempt to move along Bezier curve position, while raycasting algorithm will try force it back to a straight-line movement. With a careful alternating between both, an actual movement path is formed.

Obviously…the algorithm work fine only when there is no influent from other units in the same area. Perhaps flocking algorithm could help in that regards.