Хочу рассказать немного об алгоритмах нахождения кратчайшего пути.

Типа вступление.

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

Алгоритм правой - левой руки.

Суть его проста до безобразия! Кто-то великий и мудрый сказал: "да я из любого лабиринта смогу выйти!". Наверно он надеялся на правело правой - левой руки. А суть его такова:

Взяться левой рукой за стенку и не отпускаясь топать, топать, при этом не забывать помечать где уже были т.е. оставлять сзади себя след. Топая, таким образом, может куда-нибудь, и придем (может даже на финишную точку нарвемся). А зачем же нам след? А это на тот случай когда у нас зацикливание и если такое случилось можно, например руку поменять.

Глюк способа: а вдруг мы будем вокруг одного столба крутиться?! Как в том анекдоте: Пьяный вокруг бочки ползает: "Вот блин! Когда этот долбанный забор кончится?!!" :)

Но на мой взгляд алгоритм оптимально подходит для движения например танчиков (все знают о чем я?) в лабиринте. (например танкам нужно двигаться от своего места рождения до твоего флага, чтоб его уничтожить!)

А теперь посерьезней способ.

Как известно самый короткий путь это прямая, поэтому прокладываем от стартовой точки до финишной прямую. И бежим по ней. Конечно проверяя, что впереди... Если наткнулись на препятствие, то начинаем его обходить по правилу рук (см. выше) до тех пор пока не вернемся на начальную прямую.

По-моему алгоритм мало подходит для сильно пересеченной местности (лабиринт в танчиках, например), но зато более эффективный в стратегиях.

Глючит когда наша прямая проходит через препятствие, напоминающее подкову, наш человечек (или танк или робот или мертвец или что там у вас?) начинает зацикливаться. Но если подумать можно и этот глюк исправить дополнив слегка алгоритм.

Ну и самое серьезное и эффективное Алгоритм А*!

А* - (А звезда) или его еще называют волновым.

По нашей карте от финишной (!) точки распространяется волна. С каждым шагом, увеличиваясь на 1. И так до тех пор, пока не достигнет стартовой (!) точки. Далее действуем от стартовой точки. Берем по убыванию значения волны, прокладывая тем самым путь к финишу. Естественно, что это все делается в вспомогательном массиве, чтобы не повредить исходную карту.

Глюков особых не замечено, путь находится всегда (если он конечно вообще существует). Проблема может только в относительной сложности реализации и работе по времени.

Ну вот, вкратце рассказал... если есть вопросы или что не понятно пишите на мыло. Или следите за обновлениями на моем сайте.

(с) Белоногов Илья, ноябрь 2002.

http://www.itsprogs.chat.ru

mailto:su27@list.ru