No Canvas

Pool's closed. Due to AIDS

noreply@blogger.com (Restorer) — Wed, 28 Jul 2010 21:10:00 +0000

Концерт окончен, довольные зрители расходятся по домам.

На неопрелделённый срок я закрываю проект.
Причин тому несколько, и основная — банальная нехватка времени.
Пишу игру под андроид, пишу игру для соцсетей (кстати, на js и без канвы :), работаю в конце концов.

Промежуточные итоги (надеюсь они не станут окончательными):

срок публикаций выдерживался (изменения были, но я оповещал заранее);
эффекты были интересными (для меня, по крайней мере);
обещанную игру так и не сделал (хотя демка была);
посещаемость довольно низкая (менее 50 юников в сутки), rss читают около 100 человек;
комментируемость никакая;
при публикации на хабре посещаемость возрастала до 4к юников, но быстро падала;
хабравчане демосцену особо не жалуют, комментарии не по теме, активность низкая (кстати, судя по одним и тем же лицам, комментирующим топики связанные с демосценой, прихожу к выводу, что сценеров на хабре три с половиной человека);
я поднял свой скилл написания блогозаписей (c).

Всегда ваш restorer/fct^fsb

Если вы ещё не кликнули на картинку, сделайте это. Right now!

И специально для милых двачеров - я один из тех 3.5 олдфагов, которые помнят события давних времён.

Effect X1

noreply@blogger.com (Restorer) — Wed, 16 Jun 2010 18:16:00 +0000

Я тут проходил мимо, и совершенно случайно нашел новый эффект.

Я просто оставлю его здесь, ведь можно же? Правда?

3D №2 или Illustrate! своими руками

noreply@blogger.com (Restorer) — Fri, 21 May 2010 12:58:00 +0000

Помните первую запись в этом блоге (ту, которая "Да кто угодно сможет это сделать, используя canvas!")? Сегодня я представляю вашему вниманию вариант без канвы.

Это всего-лишь тестовые наработки, но, тем не менее, они работают (да чего я тут буду расписывать, лучше посмотрите сами).

Рисовать полигоны без канвы - просто. Залитые, с градиентом и без.
Рисовать 3D без канвы - просто. Используя алгоритм художника, например.
Рисовать 3D с самопересечениями полигонов без канвы - сложно. Потому что "художник" уже не подходит, и необходим z-buffer.

На иллюстрации выше - классическая проблема алгоритма художника. В каком бы порядке не были бы отрисованы полигоны, правильной картинки всё равно не получится.

Однако, если разбить эти полигоны на несколько полигонов поменьше, то проблема исчезает.

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

Как это водится, смотреть лучше всего в Chrome. На втором месте, поднявшись на два пункта, следует Opera. Затем FireFox. В Internet Explorer ... работает (но лучше взять любой другой браузер).

К моему сожалению, библиотека Raphael (SVG/VML) не работает в мобильном Chrome (под Android).

Illustrate? Кто сказал Illustrate?

В отличие от традиционного рендера с использованием z-buffer-а, такой подход позволяет делать разные клёвые штуки, например такие:

или такие:

Кстати, если всё-таки прочитаю хоть одну книжку с описанием таких алгоритмов, обещаю переделать рендерер.

Рисовалка без канвы

noreply@blogger.com (Restorer) — Tue, 27 Apr 2010 14:24:00 +0000

Сегодняшняя запись (кстати, с недельным отставанием от графика) посвящена скорее не техническим аспектам, а человеческим взаимоотношениям.

Как обмануть человека, чтоб он остался доволен?

Предистория

Как-то так получилось, но я админю один форум, посвящённый программе для рисования графики Paint Tool SAI (кстати, офигенная штука, на самом деле). И захотелось мне под новый год сделать какой-нибудь эвент. А чём можно порадовать всякого рода художников? Конечно же, маленьким графическим редактором.

Процесс

Было решено сделать графический редактор на javascript, чтоб люди не заморачивались установкой и запуском. Флэш подошёл бы, конечно, лучше, но я на флэшэ не умею :-P

Доля IE на форуме где-то около 15%, так что игнорить его нельзя. Chome Frame использовать не хотелось, мой патентованный ®™ метод рисования кругов я ещё не придумал, а значит решение очевидно - использовать вектора в виде замечательной библиотеки raphaël.

Проблема стёрки

Код рисовалки был написан достаточно быстро, и осталось сделать стёрку. Однако, в векторах это не так просто. Если вы когда-нибудь рисовали во флэшэ, вы знаете о чём я; остальных прошу взглянуть на картинку ниже:

Скажем так... Несколько неожиданно получить скруглённые края после стёрки.
Так как в мои планы не входило написание полноценного векторного редактора с 2D полигонами и булевыми операциями над ними, я решил проблему проще.

Как-то давно, когда Riva TNT 2 была ещё неплохой видеокартой, попалась мне на глаза игра Lemmings на javascript. Так как в то время о канвасе только ходили слухи, то меня невероятно заинтересовало как это они (авторы игры) умудряются стирать части картинки на javascript.

Решение

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

На закуску

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

Код не сжат, и весьма прост (скачайте его, если есть желание).

Dangerous

noreply@blogger.com (Restorer) — Wed, 24 Mar 2010 14:19:00 +0000

Здравствуйте

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

Игра называется Dangerous (что как бы намекает). Если вы ещё не посмотрели на эффект, обязательно сделайте это (для просмотра настоятельно рекомендуется Google Chrome), ведь в этом движке нашли применение почти все no-canvas технологии, про которые я уже успел написать в блоге.

No Canvas

Stars Sky - обычные div-ы размером 1x1 px.
Planets - мой метод рисования кругов без канваса™
Polygons - http://www.uselesspickles.com/triangles/demo.html (не позволяет рисовать треугольники с освещением по гуро или текстурами, но зато генерит очень мало DOM элементов).
Cross - прицел нарисован так же, как и звёздное небо, обычными дивами.

JavaScript

Изначально я хотел использовать jQuery для доступа к DOM элементам, но решил попробовать Yet Another cSS selector (или сокращённо - yass).
В результате оказалось, что ни jQuery, ни yass мне на самом деле не нужны :), но в yass я нашёл управление зависимостями файлов искаропки, так что решил оставить.
Честно говоря сделано оно несколько странно, но чтобы не изобретать ненужный для моих целей велосипед, я решил пока оставить yass.

В очередной раз я использую кастомную функцию random, чтобы была возможность на лету генерировать целые вселенные (как в оригинальной Elite).

Так же, в этот раз я решил изменить своим принципам, и добавлять методы в объекты через прототипы (обычно я добавляю методы в конструкторе, что даёт возможность использовать "множественное наследование").

Math

Теперь о вещах, ни с канвой, ни с её отсутствием, ни даже с javascript никак не связанных.
Поговорим о математике.

Matrix

Повороты и движение выполняются с помощью привычной матрицы 4x3 (обычно используется матрица 4x4, но так как последний ряд всегда равен [0 0 0 1], его можно опустить).
Попробуем вывести объект.

1) Объект надо повернуть (матрица OBJROT)
2) Перенести в координаты где он находится (матрица OBJMOV)
3) Перенести относительно камеры (матрица CAMMOV)
4) Повернуть относительно камеры (матрица CAMROT)

Даже если шаги 2 и 3 слить и сделать без матриц, всё равно потребуется 18 умножений на точку.
Значит для 20 объектов о 6-ти вершинах каждый (а именно столько таких объектов используется в качестве "космического мусора") потребуется 20*6*18 = 2160 умножений.

Однако, можно заметить, что

(CAMROT * (CAMMOV * (OBJMOV * (OBJROT * point)))) =
(CAMROT * (CAMMOV * (OBJMOV * OBJROT))) * point =
((CAMROT * CAMMOV) * (OBJMOV * OBJROT)) * point

Итого требуется:

1) Единоразово выполнить умножение 2х матриц камеры (36 умножений)
2) Для каждого объекта выполнить умножение 3х матриц (72 умножения)
3) Для каждой точки объекта выполнить всего 9 умножений

Учитывая что на втором шаге одни из умножаемых мартиц - это матрица движения на матрицу поворота, его можно оптимизировать, выкинув ненужные умножения (в результате получим 36 умножений на 2м шаге).

Для тех же объектов потребуется выполнить всего 36 + ((36 + 9*6) * 20) = 1836 умножений, то есть на 324 умножения меньше. Причём с ростом числа объектов и числа вершин в них, разница будет расти.

Quaternion

Для управления кораблём задействуем ту же систему, что и в Elite - корабль можно вращать (roll) и поднимать/опускать (pitch).
Если пробовать его крутить по обычным осям (X/Y, X/Z, Y/Z) или даже по всем трём (что явно лишнее), через пару секунд управления становится непонятно что вообще происходит, и как нажатые кнопки влияют на ориентацию корабля в пространстве.

Чтобы избежать таких проблем, использоют кватернионы (что это?, вики). Так как мне совершенно не нравилась перспектива преобразования кватерниона в матрицу поворота самостоятельно (тем более что раньше я такого никогда не делал), на просторах интернета была найдена Oolite - open source реализация elite-подобной игры на Objective C.
Оттуда, кроме формул для матрицы поворота, я получил ещё и базисные вектора для нового пространства (или не пространства? в универе я совсем забивал на матан), которые помогут сделать движение вперёд/назад.

Hacks

Как сделать чтоб звёздное небо крутилось и двигалось вместе с планетами и объектами, но чтоб не генерить его на всю вселенную?
Сначала подвинем его относительно камеры, затем вернём вылетевшие точки внутрь блока и только потом повернём их.

Code

Несколько комментариев к коду (скачайте его прямо сейчас) в стиле javadoc:

main - загрузчик
common.* - разные полезняшки, привычные рубисту
dg - игровой менеджер. клей для остальных частей
dg.rotatematrix - матрица поворота и операции над ней
dg.quat - квартернион и операции над ним
dg.camera - по сути прокси к RotateMatrix и Quat
dg.viewport - явный представитель антипаттерна God Object - отсекает невидимые точки, расчитывает коеффициенты для проецирования, рисует точки, круги и треугольники
dg.point - точка в 3D либо вершина объекта
dg.objectslist - позволяет производить операции над списком объектов (точки, планеты либо полигональные объекты)
dg.starssky - звёздное небо
dg.planet - планеты и связанные с ними формулы
dg.planetslist - прокси к objectslist + некоторые кастомные функции
dg.object3d - полигональные объекты
dg.objects3dlist - операции над списком 3D объектов

P.S.

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

Ещё раз - удачных полётов.

Sinclair ZX80 Emulator

noreply@blogger.com (Restorer) — Wed, 10 Mar 2010 17:52:00 +0000

Здравствуйте тчк маньяк ретрофил в лице меня телеграфирует о новом эффекте тчк

Телеграмма
----------

Сегодня я хочу рассказать, как с помощью самых современных техноголий можно создать маленькую машину времени, которая отправит нас обратно в 80-е.

Ведь именно в 80х, небезызвестной фирмой Sinclair Research (в то время ещё Science of Cambridge Ltd.) был произведён компьютер Sinclair ZX80 (фотография - Daniel Ryde, Skövde 2004-08-31):

По сравнению с ZX81 или ZX-Spectrum, ZX80 не пользовался особой популярностью (что не помешало продать более 50 000 экземпляров). Столь высокие (на то время) продажи, очевидно, обусловлены низкой ценой компьютера (менее $200).

В ZX80 использовалось около 20 микросхем, 4 из корорых - ОЗУ (2 штуки), ПЗУ и процессор. В отличии от следующих моделей (ZX81 и Spectrum), не использовалось никаких ПЛМ (ULA), а только простые, доступные микросхемы.

В компьютере, по сути, не было никакого видеоконтроллера, и изображение формировалось специальной подпрограммой в ПЗУ.

Благодаря этой "особенности", изображение было не всё время, а только когда компьютер ничем не занят. Если же исполнялась программа, то изображение пропадало (да оно пропадало даже при наборе текста! Если бы у меня был реальный ZX80, меня бы это жутко бесило).

JavaScript

Javascript-а на ZX80 не было :)

Вдохновлённый эмулятором NES и ZX-Spectrum 48 на javascript, я решил сделать эмулятор Sinclair ZX80. Так как ZX80 предельно прост, то компонентов всего два - эмулятор Z80 и эмулятор компьютера.

zame-js-z80

У меня уже было ядро Z80, написанное для моего нового эмулятора ZX-Spectrum. Правда, у него был один большой недостаток - оно написано на C :) , но через несколько часов беспрерывной работы, я получил вариант на javascript.

Так как javascript гораздо медленнее, чем компилированный код на C, пришлось узнать много нового о внутреннем представлении чисел в javascript, и освежить в памяти приоритеты операторов.

Я был очень рад тому, что [ -1 & 0xFF = 0xFF ]. Это позволило упростить выражения вида [ (a - b + 0x100) & 0xFF ] до [ (a - b) & 0xFF ]

(эх, а на C всего лишь [ (uint_8)(a - b) ])

Не менее рад я был тому, что [ a + b & 0xFF = (a + b) & 0xFF ], это позволило убрать много ненужных скобочек (я не уверен, что все JS движки способны убирать лишние скобки на этапе компиляции)

Затем я прогнал код через пост-процессор, который используя всю мощь регэкспов, заменил всё что можно посчитать заранее, на готовые значения (например, 0x80 | 0x01 -> 0x81), ведь я ещё менее уверен, что все JS движки способны производить такие оптимизации.

И наконец, я более чем уверен, что JS движки не будут оптимизировать код вида:

var a = 2;

alert(a + 1);

до

alert(3)

(хотя, кажется, Google closure compiler это умеет), так что в критичных местах все переменные, которые не меняют своего значения, были заменени просто цифрами.

js-zx8x

Эмулятор самого компьютера прост как топор. Единственное, что пришлось сделать, так это чтобы нажатая кнопка оставалась нажатой некоторое время, даже если её отпустили (o_O), так как обычный жалкий кусок мяса успевает отпустить кнопку быстрее, чем код в ПЗУ ZX80 на неё отреагировать.

NoCanvas

И самое главное, как вывести изображение без канваса?

На самом деле очень просто - экран в ZX80 текстовый, так что при большом желании, можно выводить изображение хоть в textarea :) , однако, технология CSS-Sprites позволяет достить гораздо большего реализма.

P.S.

В хроме работает на отличненько, кушает от 30% до 50% процессора.

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

В файрфоксе заметно притормаживает.

В IE... работает.

Так как я никогда не видел ZX80 вживую, то не могу сказать насколько скорость эмуляции соответствует реальности. По сравнению с другими эмуляторами (теми что я смог найти под Linux), работает быстрее чем положено.

Manual

На случай если вы никогда не имели дела с ZX80, ZX81 или ZX-Spectrum, даю инструкцию по запуску единственной игры для ZX80, которую мне удалось найти (для ZX81 их гораздо больше, а уж под спектрум так совсем уйма);

1) После загрузки страницы, дождитесь появления буквы K на чёрном фоне у углу эмулятора.
2) Нажмите кнопку "Load game" (справа от эмулятора), появится листинг программы
3) Нажмите на кнопку R - должно напечататься RUN
4) Нажмите на ENTER и ожидайте инициализации игры

В самой игре: 6 - влево, 8 - вправо, 0 - стрелять.
Удачного спасения земли от космических пришельцев :)

Links

Поностальгировать - http://nocanvas.zame-dev.org/0004/
Сорсы - http://nocanvas.zame-dev.org/0004/js-zx8x-src.tar.gz

P.P.S.

Выверять текст и дописывать мелочи буду завтра.

NoCanvas Universe

noreply@blogger.com (Restorer) — Wed, 24 Feb 2010 08:37:00 +0000

Абсолютно бесполезные эффекты с выдуманными ограничениями? Это всё моё, родное :)

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

Интро

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

Решение

Использование векторов отметалось как неспортивное (несмотря на полную кроссбраузерность); border-radius очень многообещающая вещь, но, любимый всеми обозреватель интернета (любой версии), не поддерживает это свойство. Картинки с разноцветными кругами?

Решение было случайно, когда мне на глаза попалась статья о юникодных символах в википедии - можно рисовать круги символами ● (0x25CF) разных размеров (прототип эффекта).

Облом

Генерируем несколько десятков кругов, вешаем на них эффект изменения размера (радиус круга уменьшается до некоторого предела, потом увеличивается по рандому) и получаем самый настоящий облом. Даже попробовал всё это вставить в код 9elements — всё равно ерунда получается.

При небольшом изменении радиуса, круги начинают противно дрожать, убивая всю созерцательность эффекта напрочь. Я более двух дней пытался найти решение - ставил различные шрифты (желательно те, которые есть и под windows, и под linux), менял формулы, узнал о "ex" в css; ничего не помогало.

Нужно было срочно искать другой эффект или...

Решение

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

После небольшого брейнсторминга, эффект был переделан, и получилась вращающаяся вселенная.

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

Для придания большего "реализма", планеты делятся на мелкие и крупные, а в центр добавлен оранжевый круг (видимо, символизирующий солнце).

Для того, чтобы вселенная оставалась одной и той же при каждом запуске, штатный Math.random был заменен на первый попавшийся в гугле (но, зато, позволяющий выставить начальный seed).

В этом эффекте опера рвёт файрфокс (визуально), но всё равно, хром быстрее всех (IE6 в виртуалбоксе перестаёт двигаться уже при 20 планетах).

Gouraud shading без канваса

noreply@blogger.com (Restorer) — Wed, 10 Feb 2010 11:11:00 +0000

Начну я, пожалуй, с картинки для привлечения внимания.

Смотреть, конечно же, лучше всего — в хроме. Fx, IE7 и IE8 ведут себя удовлетворительно, но всё же медленнее хрома (поэтому «квадратичность» эффекта увеличена); в опере ощутимо подтормаживает; ну а про IE6 и говорить не приходится — странные артефакты в течении секунд 10-15 и тормоза.

Сначала, как обычно, немного теории.

В отличие от нулевого эффекта (тот, который с канвасом) тут я использовал честные полигоны, а не треугольники — так как интерполяция значения освещения по грани происходит без учёта перспективы, то эффект теряет немного «глянца» (такая же проблема есть и с аффинным текстурированием). С 4х-гранниками такого не происходит.

Отрисовка полигона происходит с помощью технологии scanlines: цикл проходит от самого верха до самого низа полигона, рассчитывая горизонтальные координаты отрезка и интерполируя значение освещённости на его концах. Таким методом можно рисовать только выпуклые полигоны, однако я бы посмотрел на того, кто будет использовать не выпуклые полигоны для 3D графики :)

Так как без канваса теряется возможность рисовать линии по точкам, то и возможность использовать z-buffer тоже отсутствует.

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

В этом случае, поможет алгоритм художника — достаточно рисовать полигоны с самого дальнего, а те что ближе, перекроют его в случае необходимости. В общем случае, алгоритм художника даёт весьма посредственные результаты, но для вращающегося кубика его хватает за глаза.

Javascript & no canvas

Осталось только научить браузер рисовать линии с градиентом.

Была у меня, честно говоря, крамольная мысль использовать для этого SVG и VML, но я её отверг — слишком просто. А потому я модифицировал метод применённый в Wolf 3D — картинка внутри дива.

Используются 2 картинки — одна с красным градиентом, вторая с синим. Градиент идёт сначала от чёрного к максимуму цвета, затем наоборот — это для случая, когда освещённость на левом конце отрезка выше, чем на правом.

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

Код находится в обычном для него месте: http://nocanvas.zame-dev.org/0002/main.js

Чтобы правильно выводить почти одноцветные отрезки (освещённость левого и правого края отрезка различается мало либо равна), максимальная ширина картинки увеличена до 35000 пикселей (в Wolf 3D — 2048).

Изначально для каждого кадра генерировался html код и вставлялся во вьюпорт через innerHTML, однако браузеры каждые секунд 5-10 подтормаживали — видимо происходила сборка мусора; и метод пришлось изменить.

При старте заполняются два списка элементов — с красными градиентами и с синими. В процессе отрисовки линии, элементу просто присваиваются новые стили (памятуя статью на хабре про работу браузеров с DOM деревом, обновление стилей выполняется пачкой через cssText, а не классическим способом).

В конце фрейма лишние элементы прячутся (display:none).

Жизненные моменты

Я теперь больше не пользуюсь Windows 7 дома, и окончательно превратился в красноглазика — на прошлой неделе, придя вечером домой, и желая начать писать новый пост, я включил компьютер, и пошёл делать еду; в принципе, я мог бы и не включать плиту, так как готовить я мог прямо на радиаторе чипсета :)

Ноутбук с gentoo пришёлся весьма кстати, но фотошопа не хватает (это мой open source ноут, где всё ПО open source или на худой конец freeware).

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

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

noreply@blogger.com (Restorer) — Wed, 03 Feb 2010 12:32:00 +0000

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

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

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-битным).

NoCanvas Introduction

noreply@blogger.com (Restorer) — Wed, 27 Jan 2010 07:14:00 +0000

3D с z-buffer-ом, субпиксельной точностью и освещением по Гуро на javascript? Да кто угодно сможет это сделать, используя canvas!

Можно долго и вкусно описывать преимущества канваса, но статья не про это; не менее интересно
посмотреть, чем же канвас плох.

Так чем же?

Он ни в какую не работает в Обозревателе Интернета одной большой известной корпорации: эмулируя канвас через VML мы отрезаем самые вкусные пиксельные манипуцляции, а эмуяция пиксельных вкусняшек на flash безбожно тормозит из-за того, что где-то в недрах ExternalInterface разработчики из Adobe вставили пару функций sleep :)
Только Google Chrome (aka Chromium) может обеспечить достаточную скорость исполнения джаваскрипта. Во всех остальных браузерах вкусный и сексуальный эффект рискует превратиться в слайд-шоу.
И, наконец, самое главное — это неспортивно! Я уверен, что пока есть люди пишущие сапёров на bat файлах, тетрисы на sed и боярские диалекты C++, программирование ради самого процесса программирования будет интересовать массы :)

Я ~~ненормальный псих~~ завёл блог, в котором собираюсь регулярно писать о создании различных эффектов и игр на javascript, не использующих канвас:

раз в две недели я буду писать о каком-либо новом эффекте;
раз в два месяца я буду рассказывать делать playable demo какой-нибудь игры (как водится, не использующую canvas);
и, наконец, раз в полгода я буду делать по игре (ну, по крайней мере, я буду очень стараться не сорвать сроки)

Небольшая еретическая статья на затравку — как сделать 3D + z-buffer + subpixel + gouraud shading используя канвас

Шаг 0

Для начала, необходимо позаботится о пользователях IE, предложив им поддержку тэга canvas в виде Chrome Frame: прописываем meta, подключаем гуглоскрипт, создаём блок no-canvas и правим стили для гугловского iframe (по умолчанию он появляется в центре страницы)

<head>
  <meta http-equiv="X-UA-Compatible" content="chrome=1" />
  <style type="text/css" media="screen">
.chrome-install {
  position: relative;
  margin: 0;
  padding: 0;
  top: 0;
  left: 0;
}
  </style>
  <script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/chrome-frame/1/CFInstall.min.js"></script>
</head>
<body onload="main()">
  <div id="no-canvas" style="display:none;">
    <h2>&lt;canvas&gt; support required.</h2>
    <div id="chrome-install-placeholder"></div>
  </div>
  <div id="canvas-enabled">
    <canvas id="canvas" width="384" height="384"></canvas>
  </div>
</body>

Функция main (init вызывается по таймауту, потому что иначе хром (dev версия) иногда не прорисовывает background у body до конца):

function main()
{
  canvas = document.getElementById('canvas');

  if (typeof(canvas.getContext) == 'function')
  {
    ctx = canvas.getContext('2d');
    setTimeout(init, 100);
  }
  else
  {
    document.getElementById('canvas-enabled').style.display = 'none';
    document.getElementById('no-canvas').style.display = '';

    CFInstall.check({
      node: 'chrome-install-placeholder',
      className: 'chrome-install',
      destination: window.location.href
    });
  }
}

Шаг 1

Всю отрисовку будем вести в буфере 128x128, а потом его выводить с 3-х кратным увеличением (используя putImageData).

var scr = [];
var zbuf = [];
var WDT = 128;
var HGT = 128;

function blit()
{
  var cd = ctx.createImageData(canvas.width, canvas.height);
  var data = cd.data;
  var ind = 0;

  for (var y = 0; y < HGT; y++)
  {
    var line = scr[y];

    for (var x = 0; x < WDT; x++)
    {
      data[ind++] = line[x][0]; data[ind++] = line[x][1]; data[ind++] = line[x][2]; data[ind++] = 255;
....
  }

  ctx.putImageData(cd, 0, 0);
}

Шаг 2

Представим фигуру в виде объекта и напишем читерскую функцию box, которая будет создавать кубы сразу с нормалями:

{
  points: [
    {x: point_x, y: point_y, z: point_z, n: { x: point_normal_x, y: point_normal_y, z: point_normal_z } },
    ....
  ],
  faces: [
    [point_1, point_2, point_3, { x: face_normal_x, y: face_normal_y, z: face_normal_z }],
    ....
  ],
  color: object_color,
  rot: [rot_x, rot_y, rot_z]
}

function box(size, cl, rot)
{
  var norm = 1 / Math.sqrt(3);

  return {
    points: [
      { x: -size, y: size, z: -size, n: { x: -norm, y: norm, z: -norm } },
      ....
    ],
    faces: [
      [ 0, 1, 2, { x: 0, y: 1, z: 0 } ],
      ....
    ],
    color: cl,
    rot: rot
  };
}

Шаг 3

Выполним всю чёрную работу — повернём объект (вместе с нормалями — это быстрее, чем считать нормали заново) и спроецируем его в 2D (мне было лень нормально считать уровень освещённости, по-этому я использовал метод научного тыка^tm для нахождения магической формулы и магических коеффициентов 0.7 и 3)

function project(pt, rm)
{
  var rot = {
    x: (pt.x*rm.oxx + pt.y*rm.oxy + pt.z*rm.oxz),
    y: (pt.x*rm.oyx + pt.y*rm.oyy + pt.z*rm.oyz),
    z: (pt.x*rm.ozx + pt.y*rm.ozy + pt.z*rm.ozz + ZPOS)
  };

  var l = 1 - (Math.cos(pt.n.x*rm.ozx + pt.n.y*rm.ozy + pt.n.z*rm.ozz) - 0.7) * 3;
  l = Math.max(0, Math.min(1, l));

  return {
    x: ((WDT / 2) + rot.x * (WDT / 2 - 1) / rot.z),
    y: ((HGT / 2) + rot.y * (HGT / 2 - 1) / rot.z),
    z: rot.z,
    l: l
  };
}

function draw_object(obj)
{
  var ax = (tm * obj.rot[0]);
  var ay = (tm * obj.rot[1]);
  var az = (tm * obj.rot[2]);

  var s1 = Math.sin(ax); var s2 = Math.sin(ay); var s3 = Math.sin(az);
  var c1 = Math.cos(ax); var c2 = Math.cos(ay); var c3 = Math.cos(az);

  var rm = {
    oxx: (c2 * c1),
    oxy: (c2 * s1),
    ....
  };

  var pr = [];

  for (var i = 0; i < obj.points.length; i++) {
    pr.push(project(obj.points[i], rm));
  }

  for (var i = 0; i < obj.faces.length; i++)
  {
    var face = obj.faces[i];
    var fz = (face[3].x*rm.ozx + face[3].y*rm.ozy + face[3].z*rm.ozz);

    if (fz <= 0) {
      triangle(pr[face[0]], pr[face[1]], pr[face[2]], obj.color);
    }
  }
}

Шаг 4

Напишем процедуру рисования горизонтальных линий (не самую оптимальную) и треугольников (тоже не чемпион по скорости):

function hline(y, xl, xr, cl, ll, lr, zl, zr)
{
  // Растянем линию горизонтально — так как мы используем треугольники,
  // а не честные полигоны, то при субпиксельной отрисовке без этого хака
  // иногда проявляются артефакты
  xl -= 0.5;
  xr += 0.5;
  ....
}

// **в реальном коде используется изменённая функция**
function triangle(a, b, c, cl)
{
  .... сортировка вершин ....

  var dxl = (c.x - a.x) / (c.y - a.y);
  var dxr = (b.x - a.x) / (b.y - a.y);
  ....
  var y = a.y;

  while (y < b.y)
  {
    // (y - a.y) - не обязательно целочисленное
    // за счёт этого достигается субпиксельная точность
    xl = sx + dxl * (y - a.y);
    xr = sx + dxr * (y - a.y);
    ....
    hline(y, xl, xr, cl, ll, lr, zl, zr);
    y++;
   }

   ....
}

Шаг 5

Остаётся написать функцию loop и запустить её через setInterval.

function loop()
{
  tm = ((new Date()).valueOf() - st) / 1.5;

  draw_scene();
  blit();
}

Эпилог

Полный текст скрипта доступен по адресу http://nocanvas.zame-dev.org/0000/index.html (просто загляните в исходный код страницы)