В предыдущем посте я описывал реализацию алгоритма поиска пути. Меня не устроила скорость работы этой реализации, значит придется оптимизировать.

dotTrace

Для оптимизации нужен профайлер. Я использовал dotTrace Performance Profiler. После установки в меню студии появится новая группа:

Перед запуском профайлера появится окно настроек:

Самое интересное здесь — Profiling Type. Я выбрал Line-by-line. Это самый медленный, но и самый точный вариант.
После запуска профилирования появляется окно профайлера:

После запуска программы нужно сделать те действия, которые выполняются слишком долго, а потом нажать кнопку «Get Snapshot». После этого откроется окно, в котором можно посмотреть, что же именно тормозит:

Видно, что метод поиска пути FindPath выполняется почти 2 секунды. Так же видно, что именно внутри него выполняется дольше всего.

Оптимизация

1. Свойство EstimateFullPathLength я стал заполнять при создании объекта, так как на его динамическое вычисление уходило слишком много ресурсов.
2. openSet стал списком

   var openSet = new List<PathNode>();
   

   Проверку

   while (openSet.Count > 0)
   

   переделал в

   while (openSet.Any())
   

   Получение проверяемой точки

   var currentNode = openSet.OrderBy(node => node.EstimateFullPathLength).First();
   

   Переделал так:

   openSet.Sort();
   var currentNode = openSet.First();
   

   Для это реализовал в классе PathNode интерфейс IComparable<PathNode>

   public int CompareTo(PathNode obj)
   {
     if (this.EstimateFullPathLength == obj.EstimateFullPathLength)
       return 0;
     return this.EstimateFullPathLength > obj.EstimateFullPathLength ? 1 : -1;
   }
   

3. Список просмотренных точек closedSet стал словарем

   var closedSet = new Dictionary<Point, PathNode>();
   

   а проверка того, что точка уже просмотрена, стала выглядеть так:

   if (closedSet.ContainsKey(neighbourNode.Position))
   

Результат оптимизации

В результате нахождение пути ускорилось в 3 с лишним раза.