Из журнала Virtual Worlds #1 Дзержинск, 2000 +----------------------------+ | ------- Поиск пути ------- | +----------------------------+ (C) TimeKeeper/MHCG Поиск кратчайшего пути - очень интересная алгоритмическая зада- ча. Область ее применения весьма обширна: стратегические и логи- ческие игры ( пошаговые и в реальном времени ), системные программы ( трассировщик печат- ных плат ), и т. п. Для нас, в данный момент, интереснее всего алгоритмы, которые можно приме- нить в играх. Я склонен все по- добные алгоритмы разделять на две категории: статические и ди- намические. Динамические алгоритмы поиска пути должны работать очень быстро и корректировать путь в зависимости от динамических из- менений ландшафта ( передвижения других обьектов, появление новых препятствий, исчезновение ста- рых... ). Такие алгоритмы ис- пользуются для стратегических игр, в которых действия происхо- дят в реальном времени. Один из подобных алгоритмов успешно был реализован В. Медноноговым в "Черном Вороне". Статические алгоритмы исполь- зуются для пошаговых стратегий, программ разводки печатных плат и в других областях, где нужна точность и не обязательна быстрота выполнения ( примером может служить UFO-II ). Динамические алгоритмы выпол- няются гораздо быстрее статичес- ких, но обладают низкой точ- ностью, в то время как статичес- кие уступают в быстроте, но зато имеют 100% точность. Недавно передо мной встала за- дача создания статического алго- ритма поиска кратчайшего пути для игровой карты размером 128*128 полей. Тогда мне был из- вестен лишь один алгоритм. Точ- ного названия я уже не помню, но действовал он приблизительно так: Предположим, у нас есть двумерный массив KARTA (x,y) - карта размерами X * Y, на кото- рой будем строить путь. Заведем два дополнительных одномерных массива размером x*y: INDEX (x*y) и PATH (x*y). Суть алгоритма заключается в том, что на каждом шаге мы будем смотреть куда можно пойти из клеток, в которые мы могли по- пасть на предыдущем шаге и, если эти клетки отсутствуют в массиве INDEX, то мы добавляем их туда, а в массив PATH записываем соот- ветственно путь - номер ( или координаты, это кому как будет удобнее ) клетки, из которой мы попали в ту, которую записали в массив INDEX. Алгоритм заканчивает свою ра- боту в одном из двух случаев: Либо мы дошли до искомой клетки, либо нам больше некуда идти, т. е. мы записали в массив INDEX все клетки, в которые можно по- пасть из начальной и среди них не оказалось искомой. Понятно, что во втором случае путь мы не нашли вообще. Докажем теперь, что если мы нашли путь, то он и есть самый кратчайший и более короткого пу- ти не существует. Вообще говоря, это следует из нашего алгоритма. На каждом шаге мы смотрели, на какие клетки можно пойти из тех, в которые мы могли придти на предыдущем шаге и добавляли их в массив INDEX, если их там еще не было. Значит, в результате мы получили наикратчайший путь, т. к. если бы существовал путь бо- лее короткий, это означало бы, что до клетки-цели можно дойти за меньшее число шагов и значит, она уже содержалась бы в массиве INDEX, что противоречит нашему алгоритму. Довольно неплохой и понятный алгоритм, но посмотрим, как мы сможем реализовать его на прак- тике: Для работы нам понадобяться два рабочих массива размерами X*Y, а это, ни много ни мало, а 3*X*Y байт ОЗУ, плюс еще буфер для хранения найденного пути. Если карта имеет малые размероы, то это еще более-менее приемле- мо, но, как было упомянуто выше, статические алгоритмы исполь- зуются в основном для пошаговых стратегий или разводки печатных плат. Если взять карту размером 128*128, то для игры что еще ку- да ни шло ( хотя это, вообще го- воря, мало ), но для печатных плат это совершенно неприемлемо - максимум пять корпусов микрос- хем в длину при классе разводки не выше третьего. Но ведь и 128*128 - это уже 16384 байт для карты + 3*128*128=49152 байт для массивов поиска пути, да еще бу- фер для хранения пути. Вообще говоря, размеры рабочих массивов можно уменьшить и взять их число равным количеству кле- ток на карте, на которые можно ходить, но это врядли решит проблему. Алгоритм 2. По сути дела, это тот же самый алгоритм, оптимизированный мной по критерию минимизации исполь- зуемой под буфера памяти (хотя на скорости это отобразится не лучшим образом). У нас в памяти хранится массив с размерами равными размерам карты. Каждый байт этого массива отвечает за одну клетку на карте и имеет следующую побитовую раскладку: Bits: 7 6 5 4 3 2 1 0 | | | | +-+ +-+-- INDEX | | | | +------ PATH не ис- | | +---------- MASKSTEP пользу- | +------------ TARGET ется +-------------- INPUT INDEX - Аналог массива из преды- дущего алгоритма и принимает следующие значения: = 0, если клетка не была добав- лена в массив. = 3, если клетка уже занесена в массив. = 2, для клеток заносимых в мас- сив на текущем шаге. = 1, для занесенных на предыду- щем шаге. PATH - два бита направления. Со- держат в себе код, указывающий из какой клетки мы попали в эту: 0 - справа 1 - сверху 2 - слева 3 - снизу MASKSTEP - бит содержащий 0, ес- ли на эту клетку можно ходить ( т. е. если она проходима ), и 1 - в противном случае. TARGET - содержит 1, если это клетка-цель. INPUT - содержит 1, если это клетка-источник. При таком подходе, для карты 128*128 понадобится массив раз- мером 16384 байт, что как раз равно объему одной странички па- мяти. Сам алгоритм: 0. Создаем рабочий массив раз- мерами XLEN * YLEN. 1. Ищем в массиве клетки с INDEX = 1. Если такие отсут- ствуют, то переходим к пункту 6. 2. Для каждой найденной клетки проверяем, куда можно идти, т. е. проверяем клетки слева, свер- ху, справа, снизу и, если в них INDEX=0, и MASKSTEP=0, то запи- сываем туда INDEX=2, и PATH: 2 - для клетки слева 3 - -//- сверху 0 - -//- справа 1 - -//- снизу 3. Если среди клеток, прове- ренных в пункте 2, найдем кле- тку цель, т.е. ту, у которой TARGET=1, то переходим к пункту 7. 4. Теперь смотрим весь массив и заменяем INDEX=1 на INDEX=3, INDEX=2 на INDEX=1. 5. Переходим к пункту 1. 6. Путь не существует, останов. 7. Итак мы нашли клетку-цель, создадим теперь буфер пути: а) Ставим указатель на клетку- цель. б) Добавляем в буфер пути чис- ло, содержащееся в клетке, на которой стоит указатель в поле PATH. в) Смещаем указатель на клетку из которой мы попали в ту, на которой сейчас стоит указатель. Все это повторяем до тех пор, пока не достигнем клетки- источника, т. е. той, у которой INPUT=1. Как вы наверное заметили, в данном алгоритме ходить можно только по четырем направлениям по горизонтали и вертикали, вы спросите:"Почему?". Просто, ког- да я разрабатывал этот алгоритм, передо мной стояла именно такая задача, но никто не мешает от- вести вам под направление три бита ( в нашем варианте не ис- пользуется седьмой бит ) и сде- лать возможность перемещения в восьми направлениях. Далее, ал- горитм еще можно оптимизировать, если выкинуть пункт 4. Делается это очень просто. Как было ска- зано выше, INDEX принимает одно из четырех значений: 0 - клетка еще не была проверена 3 - уже проверена 1 и 2 - используются для опреде- ления того, в какие клетки мы могли попасть на предыдущем шаге (1) и в какие можем попасть на текущем (2). Далее, во всех клетках INDEX=1 заменяется на INDEX=3, а INDEX=2 на INDEX=1. Тем самым мы подготавливаем рабочую карту к следующему шагу. Делаем так: вводим две новые переменные VAR0, VAR1 ( Изначально VAR0=1, VAR1=2 ). В 1-ом пункте будем искать клетки с INDEX=VAR0 и сразу присваивать им INDEX=3. Теперь в четвертом пункте, вмес- то того чтобы изменять индексы на карте, просто меняем местами значения переменных VAR0 и VAR1, что гораздо быстрее. Итак: 0. Создаем рабочий массив разме- рами XLEN * YLEN. и присваиваем VAR0=1, VAR1=2. 1. Ищем в массиве клетки с INDEX = VAR0. Если такие отсутствуют, то переходим к пункту 6. 2. Для каждой найденной клетки: а) присваиваем INDEX=3. б) проверяем куда можно идти, т. е. проверяем клетки слева, сверху, справа и снизу и, если в них INDEX = 0 и MASKSTEP = 0, то записываем туда INDEX = VAR1, и PATH: 2 - для клетки слева 3 - -//- сверху 0 - -//- справа 1 - -//- снизу 3. Если среди клеток, проверен- ных в пункте 2, найдем клетку- цель, т. е. ту, у которой TARGET = 1, то переходим к пункту 7. 4. Меняем значения переменных VAR0 и VAR1 местами: TEMP:=VAR0, VAR0:=VAR1, VAR1:=TEMP. 5. Переходим к пункту 1. 6. Путь не существует, останов. 7. Итак, мы нашли клетку-цель и надо создать буфер пути ( см. выше ). Пункты 1 и 2 лучше связать, т. е., если нашли клетку, то сразу проделываем для нее все из пункта 2. Также лучше сразу про- верять клетку на наличие TARGET=1, чтобы не делать лишних циклов. Еще, для данного примера, мож- но уменьшить буфер, используемый программой под динамическую кар- ту в два раза, что в принципе, повлечет за собой уменьшение скорости обработки. Для этого будем использовать только четыре бита: 2 бита - INDEX, 2 бита - PATH. А определять TARGET и INPUT будем по координатам ( или адресу ). Можно идти на сле- дующую клетку или нет, будем оп- ределять по самой карте. Вообще говоря, вариантов тут очень много и все зависит от ва- шей фантазии и способностей, так что, дерзайте.