┌────────────────────────────┐
│ ░▒▓█▓██ Поиск пути ██▓█▓▒░ │
└────────────────────────────┘
(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 будем по координатам ( или
адресу ). Можно идти на сле-
дующую клетку или нет, будем оп-
ределять по самой карте.
Вообще говоря, вариантов тут
очень много и все зависит от ва-
шей фантазии и способностей, так
что, дерзайте.
