A* проблемы с готовым компонентом - Страница 2

Nemez · 08.02.2011, 17:02

Цитата:

Сообщение от -De-

Издали не видим ничо, видим по возвращению)

Вот этот то момент и не ясен. (((
Мы возвращаемся по своим следам, но как мы спрямляем путь?

alatar · 08.02.2011, 17:06

Цитата:

Вот этот то момент и не ясен. (((

По-приходу к цели имеется куча точек с разными весами. При отработке в обратную сторону выбираются точки с наименьшим весом. В итоге имеем путь близкий к идеальному.

Rzer · 08.02.2011, 18:42

На практике на картах 200 на 200 быстрее использовать алгоритм "заливки цветом" (или волновой, кому как приятнее), работает так: есть карта, где 0x000000 - не проходимое поле, 0xFFFFFF - проходимое. Заливаем точку начала 0x000000 +1 цветом, все соседние 0x000000 + 2, если цвет численно меньше лежащего там. Доходим до точки конца, идём обратно по уменьшению значения цвета.

Преимущества:
1) не создаётся лишних экземпляров объектов (весь процесс можно свести к перемещению индекса в отклонированном ByteArray проходимости карты и стеку волны в массиве), что на практике, как ни странно гораздо быстрее (по тестам 150мс double A* против 5 мс - заливкой цветом).
2) Ищется идеальный путь.