Wolf 3D - не вовремя, но в тему

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

После того, как вы посмотрите сам эффект, можно начинать разбор технологий.


Ray casting

В основе движка всемирно известной игры Wolfenstein 3D лежит оптимизированный Ray casting.

Сейчас я поверхностно рассмотрю технологию, но знайте, что в гугле по словам "ray casting" находится целый кладезь информации.

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

Но если реализовать этот алгоритм в лоб (использую для расчёта лучей, например, алгоритм Брезенхема), то можно изобрести машину времени, превращающую новый двухъядерный компьютер в 486 DX 100.

Однако можно заметить, что достаточно проверять на пересечение со стенкой только начало ячейки (потому что дальше в этой ячейке либо ничего нет, либо стена; инфа 100%). Достаточно найти первое пересечение (и по горизонтали, и по вертикали), и их приращения по X и Y.

Тут правда есть один тонкий момент. Если вы сделаете всё в точности как написано, то, подойдя к прямой стене, вы увидите нечто, на прямую стену похожее лишь отдалённо.

Это происходит потому, что, несмотря на то, что игрок материальная точка, он всё-таки точка :), и лучи фокусируются на сфере (а экран плоский). Однако всё исправляется всего лишь одним умножением на корректирующее число (для каждого столбца своё).

Javascript & no canvas

Для реализации wolf3d на джаваскрипте и без канваса, достаточно найти метод вывода столбцов (желательно с текстурой стены).
Отобразить один одноцветный столбец, можно используя DIV:

<div style="position:absolute; top:10px; left:5px; width:1px; height:80px; background-color:red;"></div>

Для того чтобы затекстурировать его, потребуется смешать технологию CSS-sprites и тэг IMG:

<div style="position:absolute; top:0px; left:5px; width:1px; height:256px; overflow:hidden;">
 <img src="wall.png" style="position:absolute; top:10px; left:-32px; width:256px; height:80px;" alt="" />
</div>

Браузер сам будет растягивать и сжимать столбец текстуры.

Технические моменты

В целом, для человека погуглившего по поводу Ray casting-а, код будет понятен, так что пройдусь сверху-вниз по исходнику (http://nocanvas.zame-dev.org/0001/main.js), описывая общую картину и рассматривая неочевидные моменты.

var CELL_SIZE = 64;
var MAX_IMAGE_HEIGHT = 2048;

CELL_SIZE - размер одного блока на карте.
MAX_IMAGE_HEIGHT - ограничим максимальную высоту столбца, на всякий случай (чтоб какой-нибудь браузер не офигел от счастья растягивать картинку до 180263 пикселей в высоту).

function create_view(width, height, mult) ...

Создать необходимые DOM элементы для окна размером width x height. mult - ширина одного столбца.

function cast(sx, sy, x, y, dx, dy) ...
function render_column(col, x, y, a, corr) ...

Эти две функции используются для рассчёта длины луча col, направленного из точки x,y с углом a и корректирующим значением corr.

function render_it() ...

Самая Главная Функция™

function inner_loop() ...

function main_process()
{
 var old_x = hero_x; var old_y = hero_y; var old_a = hero_a;

 var time = (new Date()).valueOf();
 var loop_cnt = Math.round((time - prev_time) / MOVE_FREQ);

 if (loop_cnt > 0)
 {
  prev_time = time - ((time - prev_time) - (loop_cnt * MOVE_FREQ));

  while (loop_cnt > 0)
  {
   inner_loop();
   loop_cnt--;
  }
 }

 if (hero_x!=old_x || hero_y!=old_y || hero_a!=old_a) {
  render_it();
 }
}

Отдельно стоит рассмотреть функции main_process и inner_loop; разные браузеры обладают различным быстродействием, и то, что летает в хроме, необычайно тупит в IE8.

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

К сожалению (или к счастью :) ), исполнение куска джаваскрипта (например, функции вызванной через setTimeout или setInterval) атомарно, и тупящий рендер не даст отработать функции пересчёта координат в нужный момент времени.

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

var MOVE_FREQ = (is_ie ? 50 : 20);

...

 if (is_ie) {
  create_view(120, 90, 4);
 } else {
  create_view(160, 120, 3);
 }

Осталось только немного "пропатчить" скрипт для IE - меньшее поле обзора (но больший множитель, так что визуально оно такое же) и большее значение MOVE_FREQ.

А кроме того

Данный эффект работает в IE6+, Chrome 1+, Fx 2.6+, Safari 4+, Opera 9+.

Интересно заметить, что в IE6 он работает значительно быстрее, нежели в IE8 и IE7 (за неимением реального IE7, тестировалось в IE8 в режиме IE7).

Не менее интересно то, что FireFox значительно быстрее работает с .gif, нежели с .png (пусть даже и 8-битным).