Virtual Worlds #01 31 декабря 1999

Программирование

Ассемблер - Поиск пути. Решение задачи "статического" поиска наикратчайшего маршрута между двумя точками.

 ┌────────────────────────────┐
 │ ░▒▓█▓██ Поиск пути ██▓█▓▒░ │
 └────────────────────────────┘

           (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 будем по координатам ( или
адресу  ).  Можно  идти  на сле-
дующую клетку или нет, будем оп-
ределять по самой карте.

  Вообще  говоря,  вариантов тут
очень много и все зависит от ва-
шей фантазии и способностей, так
что, дерзайте.