В интернете существует множество статей и видео по данной теме. Однако для многих поиск пути кажется сложным и не понятным. В этой статье я попытаюсь объяснить на пальцах как он работает.
Код во всех случаях будет отличаться, поэтому самое главное понять логику.
Итак. Поиск пути - это очень распространенная задача. Заключается она в поиске оптимального маршрута от точки А к точке Б. Однако алгоритм можно адаптировать под схожие задачи.
В классическом варианте, алгоритм рассчитан на карту состоящую из квадратов которые со всех сторон соединены между собой. Не смотря на это карта может быть любой формы, а связи могут быть:
- Однонаправленными
- Разной сложности проходимости
- Непроходимыми
- Могут быть связаны не только с рядом стоящими клетками ( Телепорты, порталы... )
Суть алгоритма поиска пути
Для работы нам необходимо четко знать, какие клетки связаны между собой. В случае с квадратной сеткой мы можем посмотреть на рядом стоящие ячейки. Но можно поступить иначе.
Каждая клетка должна знать:
- С какими клетками она связана
- На сколько тяжело проходить по ней самой.
Псевдокод клетки
Клетка{
массив связей,
коэффициент проходимости,
ссылка_на_предыдущую_клетку,
пройдено,
Примерно_до_финиша.
}Так же нам необходимы 2 массива. В одном мы будем хранить клетки, которые в данный момент нужно посмотреть. В другом клетки, которые уже посмотрены и больше не учувствуют в расчётах.
Считаем на сколько все связанные клетки далеко от нашей текущей позиции, а так-же на сколько далеко эти клетки от конечной точки.
Выбираем клетку у которой сумма меньше всего. Записываем в нее из какой клетки мы пришли и смотрим на клетки связанные уже с ней.
Проводим те же расчёты дальше, пока не дойдем до финиша.
Звучит очень просто, на деле все так-же, но немного сложнее в плане написания кода. Главное тут, это понять логику как оно вообще работает, после этого написание кода не должно вызывать проблем.
Ниже я приведу псевдокод алгоритма. Он более полный, но возможно не всем будет понятен, а также приложу несколько видео на эту тему.
массив В_ОБРАБОТКЕ
массив ОБРАБОТАННЫЕ
В_ОБРАБОТКЕ.Добавить( НАЧАЛЬНАЯ_КЛЕТКА )
цикл ( пока не нашли финиш ){
цикл ( Пока В_ОБРАБОТКЕ не пуст ){
КЛЕТКА = В_ОБРАБОТКЕ.клетка с наименьшей суммой ( пройдено + Примерно_до_финиша )
цикл ( КЛЕТКА.связи ){
если (СВЯЗЬ находиться в массиве ОБРАБОТАННЫЕ) Пропускаем СВЯЗЬ и смотрим слудующую
СВЯЗЬ.ссылка_на_предыдущую_клетку = КЛЕТКА
СВЯЗЬ.пройдено = КЛЕТКА.пройдено + расстояние_между_клетками
СВЯЗЬ.Примерно_до_финиша = расстояние_напрямую (от СВЯЗЬ до КОНЕЧНАЯ_КЛЕТКА)
если ( СВЯЗЬ = КОНЕЧНАЯ_КЛЕТКА ) {
ВРЕМЕННАЯ_КЛЕТКА = СВЯЗЬ
массив ПУТЬ = пуст
цикл( пока ВРЕМЕННАЯ_КЛЕТКА не равна НАЧАЛЬНАЯ_КЛЕТКА){
ПУТЬ.Добавить( ВРЕМЕННАЯ_КЛЕТКА )
ВРЕМЕННАЯ_КЛЕТКА = ВРЕМЕННАЯ_КЛЕТКА.ссылка_на_предыдущую_клетку
}
Заканчиваем алгоритм и выдает ПУТЬ
}иначе{
В_ОБРАБОТКЕ.Добавить( СВЯЗЬ )
В_ОБРАБОТКЕ.Удалить( КЛЕТКА )
ОБРАБОТАННЫЕ.Добавить( КЛЕТКА )
}
}
}
}
Ну и конечно же сам код, написанный для моей игры. Вероятно для кого-то он будет бесполезен, с другой стороны, думаю что оставить его здесь лишним не будет:
// переменные для расчёта пути
private List<TileStats> check = new List<TileStats>(); // тайлы которые мы проверяем
private List<TileStats> is_check = new List<TileStats>(); // тайлы которые мы проверили
public List<TileStats> result = new List<TileStats>(); // тропинка
public bool theEndCheck = false;
public List<TileStats> CheckTileTo(TileStats to, TileStats _activeTile)
{
for (int i = 0; i < tiles.Count; i++)
{ // для безопасности очищаем информацию хранящуюся на тайлах
tiles[i].GetComponent<TileStats>().prevTile = null; // очищаем предыдущий объект с которого мы пришли
tiles[i].GetComponent<TileStats>().distance = 0; // очищаем дистанцию пройденную
tiles[i].GetComponent<TileStats>().distanceEnd = 0; // очищаем дистанцию до поиского объекта
}
// функция поиска пути
theEndCheck = false; // обнуляем переменную конца
check.Clear(); // очищаем список проверяемых тайлов
is_check.Clear(); // очищаем список проверенных тайлов
result.Clear(); // очищаем список результата
check.Add(_activeTile); // добавляем в проверку ячейку на которой стоим
_activeTile.prevTile = _activeTile; // добавляем ячейе саму себя
if (to == _activeTile)
return null;
int i_step = 10; // переменная для незацикливания цикла
while (!theEndCheck)
{
int j_step = 10; // переменная для незакикливания цикла
while (check.Count > 0)
{
TileStats item = SelectMinTile(); // ищем элемент с минимальной дистанцией
int step_tile = item.Tiles.Count;
for (int i = 0; i < item.Tiles.Count; i++) // перебираем соседние тайлы
{
bool noSelect = false; // переменная которая исключает проверку соседнего тайла
float distantion = item.distance + Vector2.Distance(item.transform.position, item.Tiles[i].transform.position); // считаем пройденную дистанцию от тайла котоый проверем, до соседнего тайла
float distanceEnd = Vector2.Distance(to.transform.position, item.Tiles[i].transform.position); // считаем дистанцию до конечной точки
if (SelectCheck(item.Tiles[i], is_check)) // провереряем есть ли у нас элемент в списке проверенных
{
if (distantion + distanceEnd > item.Tiles[i].distance + item.Tiles[i].distanceEnd) // проверяем этот элемент на изменение наименьшей дистанции
noSelect = true; // запрещаем проверку
}
if (item.Tiles[i].Hardcore > selectedWarriror.GetComponent<PlayerStats>().type) noSelect = true; // проверяем на тип перемещения
if (!noSelect) // если у нас проверка разрешена
{
if (SelectCheck(item.Tiles[i], check)) // проверяем существует ли у нас объект в списке провяемых
{
if (distantion + distanceEnd < item.Tiles[i].distance + item.Tiles[i].distanceEnd) // проверяем дистанция меньше чем была до этого
{
item.Tiles[i].prevTile = item; // меняем предыдущий тайл
item.Tiles[i].distance = distantion; // меняем пройденную дистанцию
item.Tiles[i].distanceEnd = distanceEnd; // меняем конечную дистанцию
}
}
else
{
item.Tiles[i].prevTile = item; // задаём предыдущий тайл
item.Tiles[i].distance = distantion; // записываем пройденную дистанцию
item.Tiles[i].distanceEnd = distanceEnd; // записываем конечную дистанцию
}
if (item.Tiles[i] == to) // проверяем если наш соседний тайл конец
{
TileStats timeTile = item.Tiles[i]; // временный тайл
while (timeTile != _activeTile) // запускаем цикл, пока наш временный тайл не является началом
{
result.Add(timeTile); // добавляем временный тайл в результат
timeTile = timeTile.prevTile; // временный тайл становится предыдущим тайлом
}
theEndCheck = true; // говорим что нашли конец
return result; // выходим из функции
}
if (item.prevTile != item.Tiles[i] && !SelectCheck(item.Tiles[i], check)) // проверяем что тайл который мы проверяем не является предыдущим и проверяем что наш проверяем тайл уже не находится в массиве проверяемых
check.Add(item.Tiles[i]); // мы добавляем тайл в проверяемые
check.Remove(item); // исключаем свой тайл и проверки
if (!SelectCheck(item, is_check)) is_check.Add(item); // если проверяемого тайла нет в списке проверенных, то добавляем проверяемый тайл в список проверенных
}
else
{
step_tile--;
}
}
// првоверить что у соседних тайлов нет выходов и удалить проверяемы тайл из списка проверки
if (step_tile == 0)
{
check.Remove(item); // убираем из списка проверяемых
if (!SelectCheck(item, is_check)) is_check.Add(item); // проверяем есть ли она в списке проверенных если нет то добавляем
}
j_step--;
}
i_step--;
if (check.Count == 0) theEndCheck = true;
}
return result;
}
public bool SelectCheck(TileStats selectTile, List<TileStats> list)
{
bool select = false; // переменная проверки
for (int i = 0; i < list.Count; i++) // цикл по всему списку
{
if (list[i].Equals(selectTile)) // проверяем есть ли у нас элемент в списке
{
select = true; // говорим что есть
break; // останавливаем цикл
}
}
return select; // возвращаем результат
}
public TileStats SelectMinTile()
{
TileStats ret = null;
float min = float.PositiveInfinity;
for (int i = 0; i < check.Count; i++)
{
if (check[i].distance + check[i].distanceEnd < min)
{
min = check[i].distance + check[i].distanceEnd;
ret = check[i];
}
}
return ret;
}