Как было реализовано пламя в Doom на Playstation

http://fabiensanglard.net/doom_fire_psx
  • Перевод

Целая глава моей книги Game Engine Black Book: DOOM посвящена консольным портам DOOM и сложностям, с которыми сталкивались их разработчики. Можно долго рассказывать о полном провале на 3DO, о сложностях на Saturn из-за аффинного наложения текстур и о потрясающем «реверс-инжиниринге с нуля», выполненном Рэнди Линденом для Super Nintendo.

Изначально двинувшись в направлении, ведущем к катастрофе[1], разработчики порта под Playstation 1 (PSX) в дальнейшем смогли сменить курс и создать порт, завоевавший успех у критиков и рынка. Final DOOM был первым истинным портом, сравнимым с PC-версией. Цветовые сектора с альфа-смешением не только усовершенствовали визуальное качество, но и улучшили геймплей благодаря индикации ключа нужного цвета. Также благодаря эффектам реверберации Audio Processing Unit консоли PSX был улучшен звук.

Команда разработчиков выполнила настолько качественную работу, что у неё осталось ещё немного свободных циклов ЦП, которые они решили использовать для генерации анимированного огня в интро и геймплее. Меня это настолько привело в благоговейный трепет, что я решил разобраться, как был реализован эффект. Когда первые поиски не дали ответа, я приготовился уже сдувать пыль с книги по MIPS для взлома исполняемого файла, но Сэмюэль Вильяреал вовремя ответил в Twitter, что он уже выполнил обратную разработку версии для Nintendo 64[2]. Мне достаточно было просто немного её подчистить, упростить и оптимизировать.

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

Базовая идея




В своей основе эффект огня использует простую карту высот. Массив размером с экран заполняется 37 значениями в интервале от 0 до 36. Каждое значение связывается с цветом от белого до чёрного, и захватывает по дороге между ними жёлтый, оранжевый и красный. Идея заключается в моделировании температуры частицы пламени, которая поднимается вверх и постепенно охлаждается.


Буфер кадра инициализируется полностью чёрным (заполненным нулями) с единственной белой строкой белых пикселей внизу (36), которая является «источником» пламени.


При каждом обновлении экрана «тепло» поднимается вверх. Для каждого пикселя в буфере кадра вычисляется новое значение. Каждый пиксель обновляется с учётом значения, расположенного непосредственно под ним. В коде нижний левый угол это нулевой индекс массива, а верхний правый угол имеет индекс FIRE_HEIGHT * FIRE_WIDTH — 1.

function doFire() {
    for(x=0 ; x < FIRE_WIDTH; x++) {
        for (y = 1; y < FIRE_HEIGHT; y++) {
            spreadFire(y * FIRE_WIDTH + x);
        }
    }
 }

 function spreadFire(src) {
    firePixels[src - FIRE_WIDTH] = firePixels[src] - 1;
 }

Заметьте, что строка 0 никогда не обновляется (итерация по y начинается не с 0, а с 1). Эта заполненная нулями строка является «генератором» огня. Простая версия с линейным охлаждением (-=1) даёт нам скучные равномерные выходные данные.


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

 function spreadFire(src) {
    var rand = Math.round(Math.random() * 3.0) & 3;
    firePixels[src - FIRE_WIDTH ] = pixel - (rand & 1);
 }


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

 function spreadFire(src) {
    var rand = Math.round(Math.random() * 3.0) & 3;
    var dst = src - rand + 1;
    firePixels[dst - FIRE_WIDTH ] = firePixels[src] - (rand & 1);
 }


[Прим. пер.: Youtube ужасно пережимает видео, лучше смотреть демо на Javascript в оригинале статьи или открыть GIF под спойлером.]

Анимация пламени в GIF (23 мегабайта)
image

Вуаля! Заметьте, что изменяя процесс распространения пламени можно также симулировать ветер. Я оставлю это в качестве упражнения для читателей, которым удалось дочитать статью.

Полный исходный код




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

Справочные материалы




[1] Источник: Полная история подробно рассказана в книге Game Engine Black Book: DOOM

[2] Источник: пост в Twitter за 25 марта 2018 года
Поделиться публикацией

Комментарии 34

    +1
    Теплые ламповые эффекты.
    Минимум памяти, минимум кода, максимум результата.
      +11
      Не то, чтобы я был старым ворчливым дедом, который считает, что раньше стоял лучше. Но про соотношение памяти к результату — как по мне сейчас ОЧЕНЬ актуальная проблема.
      Уже жду, когда появится какое-то движение, по типу гринписа, только за экономию ресурсов памяти/энергии. Потому что иногда производители ПО уже выходят за рамки разумного.
        0
        Незнаю как насчёт старым но ворчливым я стал уже давно и последнюю фразу думаю стоит писать так:
        Потому что иногда производители ПО ещё НЕ выходят за рамки разумного.
          +3

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

          +1

          Ключевое слово "иногда" в значении "только иногда", верно?

            0
            ИМХО сейчас да.
          0
          достаточно бы было движения за «открытую статистику по структуре ПО» — т.е. сколько там в процентах ресурсов (сколько музыки, картинок, видео и проч), сколько сторонних либ и фреймворков (и их названия с версиями), и сколько — собственного кода.
            0
            Применительно к самому DOOM: EXE (код) занимал 693Кб, WAD (графика, звук, карты) — 4МБ. Кода в играх всегда намного меньше, чем художественной составляющей.
            +1
            Ее (память) и сейчас также можно экономить. Только в таком режиме большой по современным меркам продукт за разумное время не напишешь. Если бороться за каждый байт, как на приставках раньше, то сколько займет написание игры типа GTA5? Плюс большинство людей забывают, что разрешение в несколько раз увеличилось, плюс битность цвета и размер текстур.
              0
              В приставочных играх и сейчас за память борются, так как там ресурсов сильно меньше чем на ПК, особенно уже ближе к концу жизненного цикла приставки. Когда она уже на порядки по производительности отстает от современных на этот момент ПК.
              Я помню как удивлялся, что игры, шустро идущие на PS3 с ее 512М памяти, адово лагали и свопились на моем ПК с 2 гигабайтами.
              Другое дело что разработчики сами никогда таким добровольно заниматься не будут, в случае с консолями их производитель приставки заставляет, просто не пропуская лагающие игры.
                0
                Уже нет. На PlayStation 4 некоторые игры тормозят вплоть до 10 FPS, сам видел. На PlayStation 4 Pro добавляют ещё больше эффектов, в результате и там игры тормозят вплоть до 10 FPS. Микрофризы и неравномерная задержка между кадрами — в порядке вещей. Ну а уж всякие квестовые баги и непроходимые задания были и в предыдущем поколении приставок. Тут ведь как всё обстоит: как только дали возможность исправить все «когда-нибудь потом» патчами, так начали забивать на тестирование и отладку, стараясь быстрее отправить игру в релиз и заработать деньги. «Когда-нибудь потом» при этом частенько не наступает вообще.
              0
              За рамки разумного они выйдут, когда наконец доделают Qt под WebAssembly. Электронщики уже ждут не дождутся возможности писать приложения под Electron на Qt…
            +3
            [Прим. пер.: Youtube ужасно пережимает видео, лучше смотреть демо на Javascript в оригинале статьи.]

            Так запостили бы гифкой:
            23MB
              +1
              Спасибо, дополнил пост.
                +2
                На здоровье! Вот вам ещё и для КДПВ гифка вместо статичного кадра:

                  +2

                  Гифки на 23 и 8 мегабайт, при том что демки целиком (вместе с логотипом DOOM-a) весят 400 килобайт.


                  Спрятал под спойлер

                    +1
                    Ух ты! Я не знал, что Хабр позволяет такое инлайнить.
                    Безусловно, ваш вариант лучше, чем гифки.
                      +3
                      Нет, не безусловно. Он жрет 15-20% цп на старичке 2600к и 80-150 метров оперативы. На мобильном устройстве откройте его.
                        0
                        Открыл сразу два демо, оба работают вообще без тормозов. При этом на странице предзагружены все гифки и видео.
                        // iphone 6s
              +15
              Статья — огонь! :)
                +1

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

                  +3
                  .webp — это, конечно, здорово, но вот огнелис его не понимает. Пока что, во всяком случае.
                    +2
                    Единственный webp в посте — это монотонный чёрный прямоугольник, так что вы мало потеряли.
                    +12
                    Нашёл на диске старую демку, в скомпилированном виде занимает 368 байт. DOS, asm x86. TASM или даже FASM должны собрать.

                    Код
                    ;; ispol'zuem 286 instruction set
                    .286

                    Code Segment
                    ;; smeshenie dlia PSP (program prefix)
                    ;; nujno dlia compilirovania v COM fail
                    org 100h

                    ;; directiva compilirovania
                    jumps

                    ;; razmer 'mas' 8000h-400 (in words) = 65536-800 (in bytes),
                    ;; vibran tak chtobi vsia programma vlezala v odin 65K segment
                    MSIZE equ 8000h-400

                    ;; Zadaet znachecnia segmentov
                    ASSUME CS:Code,DS:Code
                    Start:
                    ;; perenapravlenie DS -> na nachalo 'mas'
                    lea bx,mas ; zagruzka smeshenia 'mas'
                    shr bx,4 ; poluchaem znachenie paragrapha
                    mov ax,ds
                    add ax,bx
                    mov ds,ax ;DS ukazivaet na seg(mas) (mas doljna bit' viravnena po paragraphu)

                    ;; obnulenie 'mas'
                    mov es,ax
                    xor di,di
                    mov cx,MSIZE
                    xor ax,ax ; ax = 0
                    cld
                    rep stosw ; ax -> es:di

                    ;; perehod v GRAPH rejim (320x200)
                    mov ax,0013h
                    int 10h

                    ;; izmenenie tekushey palitri cvetov
                    mov dx,03c8h
                    xor al,al
                    out dx,al
                    inc dx

                    ;; Black -> Red, RGB[0,0,0] -> RGB[63,0,0]
                    mov cx,64
                    red: mov al,64
                    sub al,cl
                    out dx,al ; Red ( 0 -> 63 )
                    xor al,al
                    out dx,al ; Green = 0
                    out dx,al ; Blue = 0
                    loop red

                    ;; Red -> Yellow, RGB[63,0,0] -> RGB[63,63,0]
                    mov cx,64
                    yellow: mov al,63
                    out dx,al ; Red = 63
                    mov al,64
                    sub al,cl
                    out dx,al ; Green ( 0 -> 63 )
                    xor al,al
                    out dx,al ; Blue = 0
                    loop yellow

                    ;; Yellow -> White, RGB[63,63,0] -> RGB[63,63,63]
                    mov cx,64
                    white: mov al,63
                    out dx,al ; Red = 63
                    out dx,al ; Green = 63
                    mov al,64
                    sub al,cl
                    out dx,al ; Blue ( 0 -> 63 )
                    loop white

                    ;; White, RGB[63,63,63] -> RGB[63,63,63]
                    mov cx,64
                    mov al,63
                    purew: out dx,al ; Red = 63
                    out dx,al ; Green = 63
                    out dx,al ; Blue = 63
                    loop purew

                    in al,60h
                    mov byte ptr cs:[offset lab],al

                    WKey: mov ax,ds ; pomnim chto 'ds' ukazivaet na seg(mas)
                    mov es,ax
                    cld
                    mov di,0fa00h
                    ;; Zacherniaem samie nijnie strochki (до конца массиа 4.8 стpочки)
                    mov cx,768
                    xor ax,ax
                    rep stosw

                    ;; zakrashivaem 15 blokov (24x3) iz belih tochek
                    ;; visota plameni zavisit ot visoti bloka
                    ;; intensivnost' plameni ot shirini bloka
                    mov cx,15
                    spot: mov bp,cx
                    ;; vichisliaem sluchainuu koordinatu tochki
                    mov ax,320
                    call random
                    add ax,0fa00h
                    mov di,ax
                    mov cx,12 ; Shirina bloka / 2

                    mov ax,0ffffh ; Beliy cvet
                    cld
                    lines: stosw
                    mov [di+13fh],ax ;di+319
                    mov [di+27fh],ax ;di+1+639
                    loop lines
                    mov cx,bp
                    loop spot

                    mov di,960

                    ;; --- Sobstveno perechet cvetov obespechivaushiy plamia
                    flame:
                    xor ax,ax
                    xor bx,bx
                    mov bl,ds:[di-320]
                    mov al,ds:[di-640]
                    add ax,bx
                    mov bl,ds:[di-960]
                    add ax,bx
                    mov bl,ds:[di+320]
                    add ax,bx
                    mov bl,ds:[di+640]
                    add ax,bx
                    mov bl,ds:[di+960]
                    add ax,bx
                    mov bl,ds:[di+1]
                    add ax,bx
                    mov bl,ds:[di-1]
                    add ax,bx
                    shr ax,3
                    cmp al,2
                    ja subb
                    xor al,al
                    jmp output
                    subb: sub al,2
                    output: mov byte ptr ds:[di-640],al
                    mov byte ptr ds:[di-320],al
                    inc di
                    cmp di,0ff00h ;na 204 stroke vihodim
                    jne flame

                    ;; jdem okonchania vertikal'noy razvertki
                    mov dx,03dah
                    b1: in al,dx
                    test al,08h
                    jz b1

                    ;; i nachala novoi (chtobi nebilo derganey)
                    b2: in al,dx
                    test al,08h
                    jnz b2

                    ;; vivodim massiv na ecran
                    mov ax,0a000h
                    mov es,ax ; v 'es' segment nachala video ecrana
                    xor si,si
                    xor di,di
                    mov cx,79e0h ; 195 strochek
                    rep movsw

                    in al,60h
                    test al,80h
                    jnz WKey
                    cmp al,byte ptr cs:[offset lab]
                    jne WKey

                    ;; vozvrashaemsia v TEXT regim
                    mov ax,0003h
                    int 10h

                    ;; zakanchivaem programmu
                    mov ah,4ch
                    int 21h

                    ;-------------------------------------------------------------------------
                    ;; Procedura generacii RANDOM number
                    ; In: AX - Diapazon
                    ; Out: AX - [0 - AX-1]
                    ; Destroys: All ?X and ?I registers

                    RandSeed dd 0
                    Random proc
                    mov cx,ax ; save limit
                    mov ax,Word ptr cs:[RandSeed+2]
                    mov bx,Word ptr cs:[RandSeed]
                    mov si,ax
                    mov di,bx
                    mov dl,ah
                    mov ah,al
                    mov al,bh
                    mov bh,bl
                    xor bl,bl
                    rcr dl,1
                    rcr ax,1
                    rcr bx,1
                    add bx,di
                    adc ax,si
                    add bx,62e9h
                    adc ax,3619h
                    mov word ptr cs:[RandSeed],bx
                    mov word ptr cs:[RandSeed+2],ax
                    xor dx,dx
                    div cx
                    mov ax,dx ; return modulus
                    ret
                    Random EndP

                    ;; viravnivaem 'mas' po granice paragrapha
                    lab db ' RiPCoder'
                    mas dw MSIZE dup (?)

                    Code EndS
                    END Start


                    Скомпилированный com-файл в base64
                    u3ACwesEjNgDw47YjsAz/7lwfjPA/POruBMAzRC6yAMywO5CuUAAsEAqwe4ywO7u
                    4vW5QACwP+6wQCrB7jLA7uLzuUAAsD/u7rBAKsHu4vW5QACwP+7u7uL75GAuol0C
                    jNiOwPy/APq5AAMzwPOruQ8Ai+m4QAHoqQAFAPqL+LkMALj///yriYU/AYmFfwLi
                    9YvN4t2/wAMzwDPbip3A/oqFgP0Dw4qdQPwDw4qdQAEDw4qdgAIDw4qdwAMDw4pd
                    AQPDil3/A8PB6AM8AncIkJCQMsDrA5AsAoiFgP2IhcD+R4H/AP91sLraA+yoCHT7
                    7KgIdfu4AKCOwDP2M/+54HnzpeRgqIB0A+lU/y46Bl0CdQPpSv+4AwDNELRMzSEA
                    AAAAi8guoSECLoseHwKL8Iv7itSK4IrHivsy29Da0djR2wPfE8aBw+liFRk2Loke
                    HwIuoyECM9L38YvCwyAgICAgICAgICAgUmlQQ29kZXI=


                    image
                      +1
                      Если меряться, то по-полной. =)
                      Специально нашел свою школьную версию на 91 байт (есть на 97 с буферизацией), но на Досбокс сейчас, почему-то, работают с одинаковой скоростью, хотя раньше разница была налицо.

                      Код ASM
                      ;╔════════════════════─────────────
                      ;╟ CopyRight by Leushin Dmitry 2:5031/1.46@fidonet
                      ;╚══════════════════════════════════─────────────────────
                      .MODEL TINY
                      .CODE
                      .386
                      ASSUME CS:@CODE,DS:@CODE
                      ORG 100H
                      START:
                      MOV AX,13H
                      INT 10H

                      CWD
                      XOR CX,CX

                      C8: MOV AX,1010H ;3
                      INT 10H ;2
                      CMP BL,63 ;3
                      JB SHORT C9 ;2
                      INC CH ;2
                      DB 03Dh ;1
                      C9: INC DH ;2
                      INC BL ;2
                      JNZ SHORT C8 ;2 = 23

                      PUSH 0A5D0H
                      POP DS

                      C0: MOV BH,20h
                      C1: CWD
                      DEC BX
                      MOV CX,3 ; 3
                      CP: ADD DL,DS:[BX] ; 2
                      ADC DH,0 ; 2
                      INC BX ; 1
                      LOOP CP ; 2
                      ADD DL,DS:[BX+318] ;
                      ADC DH,0
                      SHR DX,2
                      JZ SHORT C5
                      DEC DX
                      C5:
                      MOV DS:[BX-322],DL
                      DEC BX
                      CMP BH,9Eh
                      JNZ SHORT C1

                      MOV CX,320
                      C2: XOR DX,DS:[BX]
                      DEC DX
                      MOV DS:[BX],DX
                      DEC BX
                      LOOP C2

                      ; MOV AH,01H
                      ; INT 16H
                      ; JZ SHORT C0
                      IN AL,60H
                      AAA
                      JB SHORT C0
                      MOV AX,03H
                      INT 10H
                      RET
                      END START

                      .COM файл в base64
                      uBMAzRCZMcm4EBDNEID7P3ID/sU9/sb+w3XtaNClH7cgmUu5AwACF4DWAEPi+AKX
                      PgGA1gDB6gJ0AUqIl77+S4D/nnXcuUABMxdKiRdL4vjkYDdyyrgDAM0Qww==

                      fire.com
                        0
                        У меня в DOSbox не работает (сразу завершается). Версия в 368 байт из поста выше работает.
                          +1
                          Работает.
                          Она перестает работать когда из порта буфера клавиатуры вычитывает код соответствующий символу с младшим нибблом менее 9 (почему именно так? я не знаю).
                          Если перетаскивать программу на ярлычек досбокса (или любым другим способом передать ему программу параметром) — то нажатия клавиши не происходит, и в буфере клавиатуры лежит 0x00, вот оно и завершается.
                          Если запустить программу из консоли досбокса — в буфере клавиатуры будет код 0x9C, те «энтер отпущен», и она будет работать.
                            0
                            Так работает, но с «глюком», который периодически выезжает вниз из середины окна, а потом уезжает обратно.
                              0
                              У меня тоже. Но это к разработчику, лень разбираться.
                                0
                                Там в цикле dx не очищается, думаю, что в этом проблема, но это не точно. Была задача написать минимальный, и она была решена, возможно, сейчас я бы еще смог уменьшить, или нет. Там несколько грязных хаков.
                                Проблема с клавишей — раньше компьютеры были помедленнее и таких проблем не было. =) Писалось в 99м году на 386 в Дос Навигаторе на школьном компьютере.
                        +3
                        Эффект прекрасен в своей простоте, но, справедливости ради, он был известен и до PS1 DOOM.
                          +2
                          Мне казалось, что алгоритм пламени известен практически всем. :) Во всяком случае, в 90-е мы его узнавали едва занявшись компьютерной графикой безо всяких интернетов друг у друга. Кстати, можно затравочную строчку менять случайным образом вместо того, чтобы добавлять случайность в каждый пиксель.
                            +2
                            Никогда не мог удовлетвориться алгоритмом пламени, и реализовал свой.

                            Вот примеры моего алгоритма:

                            Z80 3.5 MHz 168 байт кода


                            Java через Processing

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

                            Самое читаемое