Войти
ПрограммированиеСтатьиИгровая логика и ИИ

C# и A* нахождение оптимального пути

Внимание! Этот документ ещё не опубликован.

Автор:

В стратегиях(и не только) вам часто надо реализовать какую-нибуть систему которая находила
бы буть из точки А в точку Б , многие начинаючие имеют с етим проблему.
В этом уроке я хочу разказать как это реализовать на C# и XNA

Для того чтобы это все можно было изпользовать в существущей игре(или программе) я буду изпользовать интерфейси
И так начнем для начала нам надо класс для того чтобы определить точку в нашем массиве мира.

public interface IGridCell
  {
      /// <summary>
      /// Координата в массиве (Х) 
      /// </summary>
      int X { get; }
   
      /// <summary>
      /// Координата в массиве(Y)
      /// </summary>
      int Y { get; }
   
      /// <summary>
      /// Вес  этой клетки. Стандартоное значение должно быть  0.
      /// Может быть больше например для тежелого ландшафта
      /// или сколько юнитов в этой клетке. Что-бы быть уверенным
      ///что эта клетка не будет частю пути,это значение должно быть довольно большим
      /// по сравнению с стандартним значением всех клеток
      /// </summary>
      int Weight { get; }
   
      /// <summary>
      /// Определает если эта точка должна считатся как часть пути
      /// 
      /// </summary>
      bool IsWalkable { get; }
   
      /// <summary>
      /// Определяет если точка p(в нашем массиве) 
                  ///равняется этой клетке   
                  /// </summary>
      /// <param name="p">Точка в массиве</param>
      /// <returns>Возвращает true если равняется</returns>
      bool Matches(Point p);
   
      /// <summary>
      /// Позиция этой клетке в "реальном" мире
      /// </summary>
      /// <remarks>Это поле НЕ используется для поиска пути, если игра 2д то 
                 ///поставте Vector2 как return ,если не используете вообще то просто удалите это поле
                 ///</remarks>
      Vector3 Position3D { get; }
  }
Теперь нам надо класс для хранения информации о нашем массиве

         public interface IGridMap
  {
      /// <summary>
      /// Возвращает позицию клетки в массиве 
      /// </summary>
      /// <param name="pos">Позиция в игровом мире</param>
      Point PosToGrid(Vector3 pos);
   
      /// <summary>
      /// Возвращает клетку которя находится на даних
      /// коорденатах
      /// p.X and p.Y.
      /// </summary>
      IGridCell GetCell(Point p);
   
      /// <summary>
      ///Воозвращает соседей клетки.
      /// Должно быть 8 клеток воокруг .Эта функция не должна
     /// воозвращать несуществующие клетки.
      /// </summary>
      /// <param name="cell">Клетка для которой надо найти</param>
      
                  ICollection<IGridCell> GetNeighbourCells(IGridCell cell);
  }

Мы уже близко, для того что-бы там не считать пути которие мы уже посчитали
там надо класс который будет хранить запрос для поиска

    public struct PathRequest
  {
                  //Точки конца и начала
                  public Point start;
      public Point end;
   
                   //Конструктор
      public PathRequest(Point start, Point end)
      {
          this.start = start;
          this.end = end;
      }
   
                   //Функция для определеня если два запроса одинаковы
      public override bool Equals(object obj)
      {
           PathRequest other = (PathRequest)obj;
          return start.Equals(other.start) && end.Equals(other.end);
      }
  }

А также нам надо класс который будет хранить сам путь

         public class Path
  {
                  /// <summary>
      /// Текущий позицию 
      /// </summary>
      PathNode current;
   
      /// <summary>
      /// Начало
      /// </summary>
      PathNode start;    
   
      /// <summary>
      /// Создать путь с такой точкой в начале
      /// </summary>
      /// <param name="start">начало</param>
      public Path(PathNode start)
      {
          current = start;
          this.start = start;
      }
   
      /// <summary>
      /// Мы в конце?
      /// </summary>
      public bool Finished { get { return current == null; } }
   
      /// <summary>
      /// Следущая точка (без удалания)
      /// </summary>
      public PathNode Next { get { return current; } }
   
      /// <summary>
      /// Возвращает следующую клетку и передвигается в перед 
      /// </summary>
      /// <returns></returns>
      public IGridCell GetNextWaypoint()
      {
          PathNode next = current;
          current = current.Predecessor;
          return next.Cell;
                }

      /// <summary>
      /// Копирует этот путь
      /// </summary>
      /// <returns></returns>
      public Path Copy()
      {
          Path copy = new Path(start);
          return copy;
      }
  }
Класс PathNode это часть самого алгоритма

        public class PathNode : IComparabl, IComparable<PathNode>, IEquatable<PathNode>
  {
      /// <summary>
      /// Родитель 
      /// </summary>
      PathNode predecessor;
 
      /// <summary>
      /// Клетка
      /// </summary>
      IGridCell cell;
   
      /// <summary>
      /// Здесь мы храним нашу цель
      /// </summary>
      Point goal;
   
      /// <summary>
      /// Цена путишествия сюда
      /// </summary>
      float g;
   
      /// <summary>
      /// Примерно сколько нам осталость до цели?
      /// </summary>
      float h;
   
      /// <summary>
      /// Общая цена движения сюда(g+h)
      /// </summary>
      float f;
   
      /// <summary>
      /// Параметр
      /// </summary>
      public float G { get { return g; } }
   
      /// <summary>
                  ///Параметр
      /// </summary>
      public float H { get { return h; } }
   
      /// <summary>
      /// Параметр
      /// </summary>
      public float F { get { return f; } }
   
      /// <summary>
      /// Параметр
      /// </summary>
      public IGridCell Cell { get { return cell; } }
   
      /// <summary>
      /// Параметр
      /// </summary>
      public PathNode Predecessor
      {
          get { return predecessor; }
          set { predecessor = value; }
      }
   
      /// <summary>
      /// Создает новую часть пути. Цена вычисляется "автоматом"
      /// </summary>
      /// <param name="predecessor">Родитель</param>
      /// <param name="cell">Клетка представлена етой частю</param>
      /// <param name="goal">Наша цель</param>
      public PathNode(PathNode predecessor, IGridCell cell, Point goal)
      {
          this.cell = cell;
          this.predecessor = predecessor;
          this.goal = goal;
   
          Update();
      }
   
      /// <summary>
      /// Пересчитует цены
      /// </summary>
      public void Update()
      {
          if (cell.Matches(goal))
          {
              // Это конец
              g = 1;
              h = 1;
              f = 1;
          }
          else
          {
              //Цена движения сюда от старта
              g = (predecessor != null ? predecessor.G : 0) + cell.Weight;                
   
              //Примерная дистанция до конца изпользуя алгоритм Manhattan'а. 10 это разтояние между клетками
              h = 10 * (Math.Abs(cell.X - goal.X) + Math.Abs(cell.Y - goal.Y));

            // Общая чена
              f = g + h;
          }
      }
 
      #region IComparable Member
   
      /// <summary>
      ///Сравним с другой частю (F).
      /// </summary>
      /// <param name="obj">Другой  PathNode</param>
      /// <returns>Возвращает -1 если дороже , 1 если дешевле или 0 если одинаково</returns>
      public int CompareTo(object obj)
      {
          PathNode node = obj as PathNode;
          if (node.F < f) return 1;
          else if (node.F > f) return -1;
          else return 0;
      }
   
      #endregion
   
      #region IEquatable<PathNode> Member
   
      /// <summary>
      /// Одинаковы ли мы?
      /// </summary>
      /// <param name="other">Другой PathNode</param>
      public bool Equals(PathNode other)
      {
          return cell == other.cell;
      }
   
      #endregion
   
      
  }


А теперь сам класс для высчитывания пути , вашы оплодисменты

       public class Pathfinder
  {
      /// <summary>
      /// Максимальное количество шагов
      /// Больше шагов=больше времени
      /// </summary>
      int stepLimit;
      
   
      /// <summary>
      /// Карта
      /// </summary>
      IGridMap map;
   
      static Pathfinder()
      {
      }
   
      /// <summary>
      /// Здесть мы храним все пути которые мы знаем
      /// </summary>
      Dictionary<PathRequest, Path> knownPaths = new Dictionary<PathRequest, Path>();
   
      /// <summary>
      /// Создает новый Pathfinder для определенной карты , с определинным количеством шагов
      /// </summary>
      /// <param name="map">карта</param>
      /// <param name="stepLimit">шаги</param>
      public Pathfinder(IGridMap map, int stepLimit)
      {
          this.map = map;
          this.stepLimit = stepLimit;
      }
   
      /// <summary>
      /// Считаем путь.
      /// Если не закончим во-время по путь вернется тот который успели зделать.
      /// Если рефреш = true то тогда этот путь (если он есть в кеше) пересчитается
      /// </summary>
      /// <param name="start">старт</param>
      /// <param name="end">конец</param>
      /// <param name="refresh">рефреш</param>
      /// <returns></returns>
      public Path CalculatePath(Vector3 start, Vector3 end, bool refresh)
      {
          return CalculatePath(map.PosToGrid(start), map.PosToGrid(end), refresh);
      }
   
      /// <summary>
      /// Считаем путь.
      /// Если не закончим во-время по путь вернется тот который успели зделать.
      /// Если рефреш = true то тогда этот путь (если он есть в кеше) пересчитается
      /// </summary>
      /// <param name="start">старт</param>
      /// <param name="end">конец</param>
      /// <param name="refresh">рефреш</param>
      /// <returns></returns>
      public Path CalculatePath(Point start, Point end, bool refresh)
      {
                  // Меняем точки местами (мы считаем путь с конца к началу)
          Point temp = end;
          end = start;
          start = temp;
   
          // Проверка если уже есть такой путь
          PathRequest request = new PathRequest(start, end);
          if (!refresh && knownPaths.ContainsKey(request))
          {
              return knownPaths[request].Copy();
          }
   
          // Это кастомный класс (смесь List и Queue)
          PriorityQueue<PathNode> open = new PriorityQueue<PathNode>();
   
          // Лист найдены клеток
          LinkedList<IGridCell> closed = new LinkedList<IGridCell>();
   
          // Клетки которие надо изследовать 
          PathNode startNode = new PathNode(null, map.GetCell(start), end);
          open.Enqueue(startNode);            
   
                     int steps = 0;
          PathNode current;
 
          do
          {
              // Стоп если достигли лимит
              if (++steps > stepLimit) return null;
   
              // Берем самую дешевую точку
              current = open.Dequeue();
   
              // Конец?
              if (current.Cell.Matches(end))
              {
                          // Сохраняем этот путь
                  Path path = new Path(current);
   
                  if (knownPaths.ContainsKey(request))
                  {
                      knownPaths[request] = path.Copy();
                  }
                  else
                  {
                      knownPaths.Add(request, path.Copy());
                  }
   
                  return path;
              }                
   
              // Смотрим воокруг этой точки
              ICollection<IGridCell> neighbours = map.GetNeighbourCells(current.Cell);
   
              foreach (IGridCell cell in neighbours)
                    {
                  // Не считать не нужное
                  if (closed.Contains(cell) || (cell.Matches(end) == false && !cell.IsWalkable))
                {
                      continue;
                  }
   
                  // Ребенок будет кто-то из сосодей 
                  PathNode successor = new PathNode(current, cell, end);
                  PathNode contained = open.Find(successor);
   
                  if (contained != null && successor.F >= contained.F)
                  {
                      // Эта точка уже в листе и к ней есть путь по дешевле
                      continue;
                  }
                  else if (contained != null && successor.F < contained.F)
                  {
                      // Точка в листе дороже чем эта
                      contained.Predecessor = current;
                      contained.Update();
                      open.Update(contained);
                  }
                  else
                  {
                      // Эта клетка еще не известна 
                      open.Enqueue(successor);
                  }
              }
   
              //Добавлем текущую клетку в лист изследованих
              closed.AddLast(current.Cell);                
   
          } while (open.Peek() != null);
   
          return null;
      }
  }

Вот это все , всем спасибо за прочтение
Исходник с  PriorityQueue автора Source


Оригинал

#ИИ, #A*, #C#, #Pathfinding, #tutorial

17 июля 2010