Эффективный алгоритм наблюдения

Материал из Клуб любителей рогаликов
Перейти к: навигация, поиск

Данная статья была написана для RLNews Darren'а Hebden'а

Эта статья рассказывает об эффективности алгоритмов наблюдения, то есть, как сделать так, чтобы игрок "видел, что вокруг него". Путешествия по миру обуславливают наибольшую активность игроков, так что скорость выполнения алгоритмов имеет большое значение. Это особенно верно для 'Netrogue: The Dark Gods' по причине ограничений при выполнении, вызванных присущей java неэффективности и задержки распространения пакетов в сети. Последует справедливый вопрос "Зачем беспокойство и дискуссия, поскольку большинство разработчиков всё равно делают свои roguelike-игры, чтобы они работали локально, в режиме single-player", таким образом работая с естественными скоростями. Хорошо, прежде всего, всегда неплохо иметь быструю программу, но ещё более важно, что это оставляет большую часть времени, для того, чтобы чтобы заняться другими вещами. Например, созданием инверсной модели освещения квадрата падающим светом. Приступим.

В этом случае, "оптимальный алгоритм" в точности означает, что мы прилагаем абсолютно наименьшее количество усилий, чтобы сделать работу; наша программа будет такой ленивой, что она наотрез откажется делать больше того, что минимально требуется для выполнения её задачи. Только если и остальные задачи просты, мы получим высокую производительность.

Теперь давайте убедимся что мы согласны с тем, что мы считаем 'обзором'. Круговой обзор естественен для большинства roguelike-игр что и принимаем здесь. Представьте себе, что вы стоите в центре (очень большого) листа бумаги в форме круга. Вы можете видеть всё в его пределах, возможно за исключением областей заблокированных препятствиями, расположенными на бумаге. Затем вы делаете один шаг на юг. Сколько потребуется сделать работы, чтобы скорректировать то, что вы видите? Наверняка вы должны обратить внимание на новые вещи, попавшие в вашем поле зрения но вы также должны 'забыть' то, что больше не в пределах видимости. Ситуация выглядит похоже на это:

-------------------7
-------------------                  NW  N  NE
------.......------5                   \ | /
-----.........-----                  W - . - E
----...........----                    / | \
----...........----                  SW  S  SE
----...........----
----.....@.....----0    Игрок имеет радиус обзора 5.
----...........----        '.' - области в поле зрения.
----...........----        '-' - области вне поля зрения.
----...........----
-----.........-----
------.......------5
-------------------
-------------------7

(заметьте, что здесь игрок имеет 'идеальный' обзор; в радиусе видимости нет препятствий.)

Теперь игрок идёт на юг:

-------------------7
-------------------
------:::::::------6
-----:XXXXXXX:-----5
----:XXXXXXXXX:----
----XXXXXXXXXXX----
----XXXXXXXXXXX----
----XXXXXXXXXXX----
----XXXXX@XXXXX----0    Игрок имеет радиус обзора 5.
----XXXXXXXXXXX----        ':' - области, оказавшиеся вне поля зрения.
----XXXXXXXXXXX----        'X' - области, оставшиеся в поле зрения.
----*XXXXXXXXX*----        '*' - области, попавшие в поле зрения.   
-----*XXXXXXX*-----       
------*******------5
-------------------
-------------------7

Если при обновлении, процедура просто перерисовывает весь круг обзора, она заново вычислит 98 позиций, которые остались точно такими же, какими они были прежде. Только 11 новых координат вошли в поле зрения и 11 вышли из него. Следовательно, мы делаем 98/11 = ~8.9, почти на 900% больше работы, чем необходимо. Если радиус зрения был не 5, а 9, 244/21 = ~11.6 или почти 1200% необязательной работы. Что же до эффективности рассматриваемого алгоритма, - он не самый красивый. К счастью, есть лучший путь как это сделать.

Самое первое, что надо сделать, - распределить двухмерный массив, называемый 'матрицей обзора' ('sight matrix'), который содержит значения 'видел ли я эту позицию прежде?'. Семантически, он эквиалентен рисункам в вышеуказанном примере. Массив потом используется для того, чтобы мы никогда не перерисовывали что-то, что уже видели и что осталось таким же, затем аналогичный способ используется, чтобы 'забывать' только те вещи, которые нужно забыть. Массив должен быть достаточно большим, чтобы содержать 'круг обзора', так что если радиус зрения на максимуме может быть N, оба измерения массива должны быть (N*2)+1 (Я могу видеть на N позиций к северу меня и на N позиций к югу меня = <N*2> плюс позиция, которую я стою на = <+1> в итоге = (N*2)+1). Логично, что игрок сидит в середине круга, таким образом, центральная позиция в массиве - начало обзора.

При запуске подпрограммы рендеринга мы немедленно узнаем, установлена ли в true соответствующая позиция в матрице обзора:

  1. Мы уже видели эту позицию ранее
  2. Что к настоящему времени на экране в этой позиции обновилось (up-to-date)...

[Держать матрицу 'обновлений' ('up-to-date') тривиально в синхронной среде (однопользовательской roguelike-игре) и такие среды наиболее характерны, так что я не мешаю обсуждать, что нужно делать в асинхронной среде.]

...так, если нет причины в дальнейшей работе, координата пропускается. В противном случае если что-то увидено вновь, матрица обзора устанавивается в true в соответствующих индексах. С другой стороны, при забывании нужно рассматривать только те позиции, которые включены (поскольку мы не можем 'забыть' координаты, которые мы не могли видеть с первой позиции). Делая это, мы говорим, "Ok, вы *думаете*, что вы можете видеть то, что есть, но можете ли вы это в действительности?". Если ответ - нет, возможно применить программу 'забывания', которая должна основываться на результате, получаемом от алгоритма линии обзора. Забытая позиция затем помечается в матрице обзора как false.

Затем для завершеня этого алгоритма нам нужно просто немного больше функциональности: возможность сдвигать содержание массива, и очищать его.

Когда персонаж перемещается вперёд, матрица обзора должна сдвинуться назад:

.......
..***..
..*@*.. То, что игрок видит перед тем, как сделать шаг
..***..
.......

.......
..***..
..***.. Игрок переместился на шаг вперёд
..*@*..
.......

Смещение необходимо чтобы сохранять матрицу логически последовательный. Если игрок сделал шаг вперёд, а матрица осталась той же самой, она очевидно не отражает изменения положения. Обычно, когда определено направление перемещения, матрица смещается в *противоположном* направлении. "То, что я видел впереди, теперь _сзади_ меня."

Если случится какая-нибудь история, например, игрок переместится в новое подземелье, матрицу необходимо очистить (поскольку в новом контексте её содержимое становится бессмысленным.)

псевдокод для процедуры следующий:

      
   статичное распределение матрицы обзора размерностью [N*2+1][N*2+1],
   где N 0 максимальный радиус обзора

   Function перемещение {integer смещение_по_y, integer смещение_по_x} 
   begin
      сдвигаем матрицу обзора на -смещение_по_y и -смещение_по_x
      call наблюдение
      call забывание
   end

   Function наблюдение
   begin
     для Y выбираем наименьшее из возможных значение Y, содержащихся в 
     ограничивающем круге;      
       пока Y меньше или равен наибольшему значению L,
       содержащемся а ограничивающем круге; наращиваем Y     
         begin
            для X выбираем наименьшее из возможных значение X, 
            содержащихся в ограничивающем круге;
              пока X меньше или равен наибольшему значению M,
              содержащемся а ограничивающем круге; наращиваем X   
       begin
          если значение ячейки [Y, X] матрицы - false, 
      и соответствующее место мира можно
      видеть, посмотреть на это место и установить ячейку
      матрицы в значение true, иначе - ничего не делать.
       end
         end
   end

Реализация забывания, аналогична реализации наблюдения; внутренний цикл будет забывать позицию и устанавливать индекс матрицы в false только если матрица к настоящему времени имеет значение [Y, X] установленное в true но игрок не может видеть эту позицию (Вы могли видеть это перед ходом, и Вы думаете что вы все еще можете это видеть, но в действительности вы этого не можете.)

Есть дальнейшая оптимизация, которая может быть осуществлена, как например, определение расстояний между координатами (давая индексы матрицы, которые нужно проверить), если кого-нибудь это заинтересует, я отвечу на такие вопросы по указанному email'у .

Примечание: Этот алгоритм естественно заботится о случаях когда игрок имеет не вполне совершенное зрение; такие вещи, как например, стены и разбросанные в поле зрения предметы. Никаких модификаций делать не надо.

Надеюсь, кто-нибудь найдёт это полезным! ;)



Автор: Avier Taylor-Paul.
Источник: An Efficient Observation Algorithm.
Перевел: Дмитрий О. Бужинский [Bu], 23.05.2005.