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

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

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

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

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

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

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

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

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

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

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

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

Так же нам необходимы 2 массива. В одном мы будем хранить клетки, которые в данный момент нужно посмотреть, а в другом клетки, которые уже посмотрены и больше не учувствуют в расчётах.

Считаем на сколько все связанные клетки далеко от нашей текущей позиции, а так-же на сколько далеко эти клетки от конечной точки.

Выбираем клетку у которой сумма меньше всего. Записываем в нее из какой клетки мы пришли и смотрим на клетки связанные уже с ней.

Проводим те же расчёты дальше, пока не дойдем до финиша.

Звучит очень просто, на деле все так-же, но немного сложнее в плане написания кода. Главное тут, это понять логику как оно вообще работает, после этого написание кода не должно вызывать проблем.

Ниже я приведу псевдокод алгоритма. Он более полный, но возможно не всем будет понятен, а также приложу несколько видео на эту тему.

массив В_ОБРАБОТКЕ
массив ОБРАБОТАННЫЕ

В_ОБРАБОТКЕ.Добавить( НАЧАЛЬНАЯ_КЛЕТКА )

цикл ( пока не нашли финиш ){
	цикл ( Пока В_ОБРАБОТКЕ не пуст ){
		КЛЕТКА = В_ОБРАБОТКЕ.клетка с наименьшей суммой ( пройдено + Примерно_до_финиша )

		цикл ( КЛЕТКА.связи ){

			если (СВЯЗЬ находиться в массиве ОБРАБОТАННЫЕ) Пропускаем СВЯЗЬ и смотрим слудующую

			СВЯЗЬ.ссылка_на_предыдущую_клетку = КЛЕТКА
			СВЯЗЬ.пройдено = КЛЕТКА.пройдено + расстояние_между_клетками
			СВЯЗЬ.Примерно_до_финиша = расстояние_напрямую (от СВЯЗЬ до КОНЕЧНАЯ_КЛЕТКА)

			если ( СВЯЗЬ = КОНЕЧНАЯ_КЛЕТКА ) {

				ВРЕМЕННАЯ_КЛЕТКА = СВЯЗЬ
				массив ПУТЬ = пуст

				цикл( пока ВРЕМЕННАЯ_КЛЕТКА не равна НАЧАЛЬНАЯ_КЛЕТКА){
					ПУТЬ.Добавить( ВРЕМЕННАЯ_КЛЕТКА )
					ВРЕМЕННАЯ_КЛЕТКА = ВРЕМЕННАЯ_КЛЕТКА.ссылка_на_предыдущую_клетку
				}

				Заканчиваем алгоритм и выдает ПУТЬ

			}иначе{
				В_ОБРАБОТКЕ.Добавить( СВЯЗЬ )
				В_ОБРАБОТКЕ.Удалить( КЛЕТКА )
				ОБРАБОТАННЫЕ.Добавить( КЛЕТКА )
			}
		}
	}
}
Пока нет оценок, но вы можете быть первым!

Оцените