В стратегиях(и не только) вам часто надо реализовать какую-нибуть систему которая находила
бы буть из точки А в точку Б , многие начинаючие имеют с етим проблему.
В этом уроке я хочу разказать как это реализовать на 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