Алгоритм поиска пути A*

Алгоритм поиска пути A*

В интернете существует множество статей и видео по данной теме. Однако для многих поиск пути кажется сложным и не понятным. В этой статье я попытаюсь объяснить на пальцах как он работает.

Я не буду писать тут код, а лишь опишу логику алгоритма, чтобы вы могли сами подумать как это реализовать и лучше понять тему.

Итак, поиск пути, это очень распространенная задача и заключается она в поиске оптимального маршрута от точки А к точке Б. Однако алгоритм можно адаптировать под схожие задачи.

В классическом варианте, алгоритм рассчитан на карту состоящую из квадратов которые со всех сторон соединены между собой. Не смотря на это карта может быть любой формы, а связи могут быть:

  • Однонаправленными
  • Разной сложности проходимости
  • Непроходимыми
  • Могут быть связаны не только с рядом стоящими клетками ( Телепорты, порталы... )

Суть алгоритма

Для работы нам необходимо четко знать, какие клетки связаны между собой, в случае с квадратной сеткой мы можем посмотреть на рядом стоящие ячейки, но можно поступить иначе.

Каждая клетка должна знать с какими клетками она связана и на сколько тяжело проходить по ней самой.

Псевдокод клетки

Клетка{
     массив связей,
     коэффициент проходимости,
     ссылка_на_предыдущую_клетку,
     пройдено,
     Примерно_до_финиша.
}

Так же нам необходимы 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;
}
Пока нет оценок, но вы можете быть первым!

Оцените