Path FInding Optimization

Coordinator
May 23, 2013 at 10:35 PM
Edited May 23, 2013 at 10:47 PM
Although the change in HexCoords.cs (change-set # 24934) produced only a 12-15% reduction in Path Finding time, I found 4 additional places in my game engine to apply the same optimization.

This reduced the time to find the longest diagonal path on my largest game map (~450 x 750 hexes) from 2.6 sec. to 1.2 sec (about 55%).

The change was from this code:
  protected override IEnumerable<NeighbourCoords> GetNeighbours(Hexside hexsides) {
    ICoords coords = this;
    foreach (Hexside hexside in Enum.GetValues(typeof(Hexside)))
      if (hexside != Hexside.None  &&  hexsides.HasFlag(hexside)) 
        yield return new NeighbourCoords(hexside, coords.StepOut(hexside));
  }
to this:
  static readonly List<Hexside> HexsideList
               = Utils.EnumGetValues<Hexside>().Where(h=>h!=Hexside.None).ToList();

  protected override IEnumerable<NeighbourCoords> GetNeighbours(Hexside hexsides) {
    ICoords coords = this;
    foreach (var hexside in HexsideList.Where(h=>hexsides.HasFlag(h)))
      yield return new NeighbourCoords(hexside, coords.StepOut(hexside));
  }
LINQ is great for writing readable code, but you have to be careful how and when you use it in deeply nested loops.

Note also that
Utils.EnumGetValues<Hexside>().
uses one of the enclosed utility extension methods to perform a completely type-safe equivalent of
Enum.GetValues(typeof(Hexside)