[Из песочницы] «Камень я не дам» или как устроены ресурсы игры «Проклятые Земли»29.12.2018 18:34

rynka_dqz5ny9nqgs7gawsw4zxy.jpeg

Много ли вы вспомните российских игр? Качественных? Запоминающихся? Да, такие были. Если вам больше 35 или вы фанат российского игропрома, то с «Проклятыми Землями» вы наверняка знакомы.

История начиналась весьма прозаично: лето, жара. Делать особо нечего, а при ленивом просмотре содержимого жёсткого диска ноутбука взгляд зацепился за папку со знакомой иконкой-дракончиком, лежащую без дела уже пару лет.

Какому фанату игры не будет интересно узнать, что же там внутри?


Информация об игре

Проклятые Земли — или, как они назывались за пределами СНГ, Evil Islands: Curse of the Lost Soul, stealth-RPG игра, вышедшая в 2000 году. Разработкой игры занималась студия Nival Interactive, на тот момент уже зарекомендовавшая себя серией игр Аллоды (Rage of Mages за рубежом). Работали в ней, в основном, выпускники МГУ — им было вполне по силам реализовать одну из первых игр с полностью трёхмерным миром.
В 2010 году права на название перешли Mail.Ru (информация), однако игра продаётся в магазине GOG всё ещё от лица Nival.

Относительно недавно игре исполнилось 18 лет — днём рождения считается 26 октября, дата выхода в СНГ. Несмотря на возраст, официальный мастер-сервер ещё в строю: периодически кто-то решает поползать по лесам Гипата да стукнуть десяток-другой скелетов с отрядом товарищей.


Коротко о статье

Изначально, моей целью было лишь написать односторонний конвертер «для себя» на Python 3, причём с использованием исключительно стандартных библиотек. Однако в процессе плавно началось написание документации по форматам, попытки как-то стандартизировать вывод. Для части форматов была описана структура с помощью Kaitai Struct. В результате всё вылилось в написание данной статьи и wiki по форматам.

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


… и о том, как её читать

Для всех форматов приведены схемы (.ksy файлы), которые можно в два клика сконвертировать в код на нескольких самых популярных языках.

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

Игра представляет собой портативное приложение, содержащее движок с библиотеками, лаунчер и, собственно, упакованные ресурсы.


Это интересно: настройки игры практически целиком хранятся в реестре. Баг камеры в GOG версии связан с тем, что установщик не прописывает корректные значения по-умолчанию.

При первом взгляде на содержимое папки game, мы сразу заметим пару новых расширений файлов: ASI и REG.
Первый — динамическая библиотека, которую рассматривать мы не будем (этим занимаются специалисты по реверс-инжинирингу), а вот второе — первый собственный формат файлов игры.


REG

Файлы этого типа — бинарная сериализация общеизвестных текстовых INI файлов.
Содержимое разбивается на секции, хранящие ключи и их значения. REG файл сохраняет эту иерархию, однако ускоряет чтение и разбор данных — в 2000 году это, видимо, было критично.

В общем виде, можно описать структуру данной диаграммой:
yhsefo2h5nxp0ghwse2zla8cmv0.png


Описание структуры 
meta:
  id: reg
  title: Evil Islands, REG file (packed INI)
  application: Evil Islands
  file-extension: reg
  license: MIT
  endian: le
doc: Packed INI file
seq:
  - id: magic
    contents: [0xFB, 0x3E, 0xAB, 0x45]
    doc: Magic bytes
  - id: sections_count
    type: u2
    doc: Number of sections
  - id: sections_offsets
    type: section_offset
    doc: Sections offset table
    repeat: expr
    repeat-expr: sections_count
types:
  section_offset:
    doc: Section position in file
    seq:
      - id: order
        type: s2
        doc: Section order number
      - id: offset
        type: u4
        doc: Global offset of section in file
    instances:
      section:
        pos: offset
        type: section
    types:
      section:
        doc: Section representation
        seq:
          - id: keys_count
            type: u2
            doc: Number of keys in section
          - id: name_len
            type: u2
            doc: Section name lenght
          - id: name
            type: str
            encoding: cp1251
            size: name_len
            doc: Section name
          - id: keys
            type: key
            doc: Section's keys
            repeat: expr
            repeat-expr: keys_count
        types:
          key:
            doc: Named key
            seq:
              - id: order
                type: s2
                doc: Key order in section
              - id: offset
                type: u4
                doc: Key offset in section
            instances:
              key_record:
                pos: _parent._parent.offset + offset
                type: key_data
          key_data:
            seq:
              - id: packed_type
                type: u1
                doc: Key value info
              - id: name_len
                type: u2
                doc: Key name lenght
              - id: name
                type: str
                encoding: cp1251
                size: name_len
                doc: Key name
              - id: value
                type: value
                doc: Key value
            instances:
              is_array:
                value: packed_type > 127
                doc: Is this key contain array
              value_type:
                value: packed_type & 0x7F
                doc: Key value type
            types:
              value:
                doc: Key value
                seq:
                  - id: array_size
                    type: u2
                    if: _parent.is_array
                    doc: Value array size
                  - id: data
                    type:
                      switch-on: _parent.value_type
                      cases:
                        0: s4
                        1: f4
                        2: string
                    repeat: expr
                    repeat-expr: '_parent.is_array ? array_size : 1'
                    doc: Key value data
              string:
                doc: Sized string
                seq:
                  - id: len
                    type: u2
                    doc: String lenght
                  - id: value
                    type: str
                    encoding: cp1251
                    size: len
                    doc: String


Это интересно: в 2002 году Nival поделился некоторыми инструментами с коммьюнити игры (снапшот сайта) — одним из них был сериализатор INI в REG. Как можно догадаться, почти сразу появился и десериализатор, пусть и не официальный.

Со стартовой папкой разобрались, перейдём к подкаталогам.
Первым взгляд падает на папку Cameras, содержащую CAM файлы.


CAM

Очень простой формат — просто упаковки положений камер во времени. Камера описывается позицией и вращением. Два остальных поля — предположительно, время и шаг в последовательности перемещений.

cu8ubjrcz2pode-v3lydliwrvsq.png


Описание структуры 
meta:
  id: cam
  title: Evil Islands, CAM file (cameras)
  application: Evil Islands
  file-extension: cam
  license: MIT
  endian: le
doc: Camera representation
seq:
  - id: cams
    type: camera
    repeat: eos
types:
  vec3:
    doc: 3d vector
    seq:
      - id: x
        type: f4
        doc: x axis
      - id: y
        type: f4
        doc: y axis
      - id: z
        type: f4
        doc: z axis
  quat:
    doc: quaternion
    seq:
      - id: w
        type: f4
        doc: w component
      - id: x
        type: f4
        doc: x component
      - id: y
        type: f4
        doc: y component
      - id: z
        type: f4
        doc: z component
  camera:
    doc: Camera parameters
    seq:
      - id: unkn0
        type: u4
        doc: unknown
      - id: unkn1
        type: u4
        doc: unknown
      - id: position
        type: vec3
        doc: camera's position
      - id: rotation
        type: quat
        doc: camera's rotation

В соседней папке — Res, хранятся (неожиданно!) RES файлы, являющиеся архивами.


RES

Этот формат иногда прячется под другими расширениями, но оригинальное всё же именно RES.
Структура данных весьма типична для архива с произвольным доступом к файлам: есть таблицы для хранения информации о файлах внутри, таблица имён, само содержимое файлов.
Структура каталогов содержится прямо в именах.

Стоит отметить два крайне интересных факта:


  1. Архив оптимизирован под загрузку информации о файлах в связный список с закрытым хэшированием.
  2. Можно хранить содержимое файла один раз, но ссылаться на него под разными именами. Насколько мне известно, этот факт использовался в фанатском репаке, где за счёт этого был сильно уменьшен размер игры. В оригинальном дистрибутиве оптимизация архивов не использовалась.

_9ie8_m0lc_b1n0ddnagkue514g.png


Описание структуры 
meta:
  id: res
  title: Evil Islands, RES file (resources archive)
  application: Evil Islands
  file-extension: res
  license: MIT
  endian: le
doc: Resources archive
seq:
  - id: magic
    contents: [0x3C, 0xE2, 0x9C, 0x01]
    doc: Magic bytes
  - id: files_count
    type: u4
    doc: Number of files in archive
  - id: filetable_offset
    type: u4
    doc: Filetable offset
  - id: nametable_size
    type: u4
    doc: Size of filenames
instances:
  nametable_offset:
    value: filetable_offset + 22 * files_count
    doc: Offset of filenames table
  filetable:
    pos: filetable_offset
    type: file_record
    repeat: expr
    repeat-expr: files_count
    doc: Files metadata table
types:
  file_record:
    doc: File metadata
    seq:
      - id: next_index
        type: s4
        doc: Next file index
      - id: file_size
        type: u4
        doc: Size of file in bytes
      - id: file_offset
        type: u4
        doc: File data offset
      - id: last_change
        type: u4
        doc: Unix timestamp of last change time
      - id: name_len
        type: u2
        doc: Lenght of filename
      - id: name_offset
        type: u4
        doc: Filename offset in name array
    instances:
      name:
        io: _root._io
        pos: name_offset + _parent.nametable_offset
        type: str
        encoding: cp1251
        size: name_len
        doc: File name
      data:
        io: _root._io
        pos: file_offset
        size: file_size
        doc: Content of file


Это интересно: в русской версии игры, архив Speech.res содержит два подкаталога s и t с полностью идентичным содержанием, из-за чего размер архива в два раза больше — именно поэтому игра не помещается на один CD.

Теперь можно распаковать все архивы (могут быть вложенными):


  • RES — просто архив,
  • MPR — ландшафт игровых уровней,
  • MQ — информация о заданиях мультиплеера,
  • ANM — набор анимаций,
  • MOD — 3d модель,
  • BON — расположение костей модели.

Если файлы внутри архива не имеют расширения, будем ставить расширение родителя — касается BON и ANM архивов.

Также можно разбить все полученные файлы на четыре группы:


  1. Текстуры;
  2. Базы данных;
  3. Модели;
  4. Файлы уровня.

Начнём с простого — с текстур.


MMP

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

a71s-rtar5cg6ipi53n86bbsxps.png


Описание структуры 
meta:
  id: mmp
  title: Evil Islands, MMP file (texture)
  application: Evil Islands
  file-extension: mmp
  license: MIT
  endian: le
doc: MIP-mapping texture
seq:
  - id: magic
    contents: [0x4D, 0x4D, 0x50, 0x00]
    doc: Magic bytes
  - id: width
    type: u4
    doc: Texture width
  - id: height
    type: u4
    doc: Texture height
  - id: mip_levels_count
    type: u4
    doc: Number of MIP-mapping stored levels
  - id: fourcc
    type: u4
    enum: pixel_formats
    doc: FourCC label of pixel format
  - id: bits_per_pixel
    type: u4
    doc: Number of bits per pixel
  - id: alpha_format
    type: channel_format
    doc: Description of alpha bits
  - id: red_format
    type: channel_format
    doc: Description of red bits
  - id: green_format
    type: channel_format
    doc: Description of green bits
  - id: blue_format
    type: channel_format
    doc: Description of blue bits
  - id: unused
    size: 4
    doc: Empty space
  - id: base_texture
    type:
      switch-on: fourcc
      cases:
        'pixel_formats::argb4': block_custom
        'pixel_formats::dxt1': block_dxt1
        'pixel_formats::dxt3': block_dxt3
        'pixel_formats::pnt3': block_pnt3
        'pixel_formats::r5g6b5': block_custom
        'pixel_formats::a1r5g5b5': block_custom
        'pixel_formats::argb8': block_custom
        _: block_custom
types:
  block_pnt3:
    seq:
      - id: raw
        size: _root.bits_per_pixel
  block_dxt1:
    seq:
      - id: raw
        size: _root.width * _root.height >> 1
  block_dxt3:
    seq:
      - id: raw
        size: _root.width * _root.height
  block_custom:
    seq:
      - id: lines
        type: line_custom
        repeat: expr
        repeat-expr: _root.height
    types:
      line_custom:
        seq:
          - id: pixels
            type: pixel_custom
            repeat: expr
            repeat-expr: _root.width
        types:
          pixel_custom:
            seq:
              - id: raw
                type:
                  switch-on: _root.bits_per_pixel
                  cases:
                    8: u1
                    16: u2
                    32: u4
            instances:
              alpha:
                value: '_root.alpha_format.count == 0 ? 255 : 255 * ((raw & _root.alpha_format.mask) >> _root.alpha_format.shift) / (_root.alpha_format.mask >> _root.alpha_format.shift)'
              red:
                value: '255 * ((raw & _root.red_format.mask) >> _root.red_format.shift) / (_root.red_format.mask >> _root.red_format.shift)'
              green:
                value: '255 * ((raw & _root.green_format.mask) >> _root.green_format.shift) / (_root.green_format.mask >> _root.green_format.shift)'
              blue:
                value: '255 * ((raw & _root.blue_format.mask) >> _root.blue_format.shift) / (_root.blue_format.mask >> _root.blue_format.shift)'
  channel_format:
    doc: Description of bits for color channel
    seq:
      - id: mask
        type: u4
        doc: Binary mask for channel bits
      - id: shift
        type: u4
        doc: Binary shift for channel bits
      - id: count
        type: u4
        doc: Count of channel bits
enums:
  pixel_formats:
    0x00004444: argb4
    0x31545844: dxt1
    0x33545844: dxt3
    0x33544E50: pnt3
    0x00005650: r5g6b5
    0x00005551: a1r5g5b5
    0x00008888: argb8

Возможные форматы упаковки пикселей:


fourcc Описание
44 44 00 00 ARGB4
44 58 54 31 DXT1
44 58 54 33 DXT3
50 4E 54 33 PNT3 — RLE сжатый ARGB8
50 56 00 00 R5G5B5
51 55 00 00 A1R5G5B5
88 88 00 00 ARGB8


О PNT3

Если формат изображения PNT3, то структура пикселей после распаковки — ARGB8; bits_per_pixel — размер сжатого изображения в байтах.


Распаковка PNT3

n = 0
destination = b""

while src < size:
    v = int.from_bytes(source[src:src + 4], byteorder='little')
    src += 4

    if v > 1000000 or v == 0:
        n += 1
    else:
        destination += source[src - (1 + n) * 4:src - 4]
        destination += b"\x00" * v
        n = 0


Это интересно: часть текстур отражена по вертикали (или некоторые не отражены?).
А ещё игра весьма ревностно относится к прозрачности — если изображение с альфа каналом, цвет прозрачных пикселов должен быть точно чёрным. Или белым — тут как повезёт.

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


Базы данных (*DB и иже с ними)

Этот формат крайне неудобно описывать — по существу, это сериализованное дерево нод (или таблиц записей). Файл состоит из нескольких таблиц с заданными типами полей. Общая структура: таблицы вложены в общую «корневую» ноду, записи — ноды внутри таблицы.

В каждой ноде задаётся её тип и размер: 

unsigned char type_index;
unsigned char raw_size; // не используется вне этого блока
unsigned length; // не читается из файла

read(raw_size);

if (raw_size & 1)
{
    length = raw_size >> 1;
    for (int i = 0; i < 3; i++)
        length <<= 8;
        read(raw_size);
        length += raw_size;
}
else
    length = raw_size >> 1;

Тип поля таблицы берётся по индексу из форматной строки для таблицы, по полученному значению определяется реальный тип.


Типы полей
обозначение описание
S string
I 4b int
U 4b unsigned
F 4b float
X bits byte
f float array
i int array
B bool
b bool array
H unknown hex bytes
T time
0 not stated
1 0FII
2 SUFF
3 FFFF
4 0SISS
5 0SISS00000U


Описание баз

Предметы (.idb)


таблица структура
Материалы SSSIFFFIFIFfIX
Оружие SSISIIIFFFFIFIXB00000IHFFFfHHFF
Броня SSISIIIFFFFIFIXB00000ffBiHH
Быстрые предметы SSISIIIFFFFIFIXB00000IIFFSbH
Квестовые предметы SSISIIIFFFFIFIXB00000Is
Продаваемые предметы SSISIIIFFFFIFIXB00000IHI

Переключатели (.ldb)


таблица структура
Прототип переключателя SfIFTSSS

Умения и навыки (.pdb)


таблица структура
Умения SSI0000000s
Навыки SSI0000000SSIIIFFFIIIIBI

Следы (prints.db)


таблица структура
Следы крови 0S11
Следы пламени 0S110000001
Следы ног 0S11

Заклинания (.sdb)


таблица структура
Прототипы SSSFIFIFFFFIIIIUSSIIbIXFFFFF
Модификаторы SSFIFFISX
Шаблоны 0SssSX
Шаблоны для брони 0SssSX
Шаблоны для оружия 0SssSX

Существа (.udb)


таблица структура
Повреждаемые части SffUU
Расы SUFFUUFfFUUf222222000000000000SssFSsfUUfUUIUSBFUUUU
Прототипы монстров SSIUIFFFSFFFFFFFFFUFFFFFFff33sfssSFFFFFUFUSF
NPC SUFFFFbbssssFUB

Выкрики (acks.db)


таблица структура
Ответы 0S0000000044444444444444444444445444444444444
Крики 0S0000000044444
Прочее 0S0000000044

Задания (.qdb)


таблица структура
Задания SFIISIIs
Брифинги SFFsSsssssI


Это интересно: 16.01.2002 Nival выложил исходные базы для мультиплеера в csv формате, а также утилиту-конвертер в игровой формат (снапшот сайта). Естественно, обратный конвертер не замедлил появиться. Также есть минимум два документа с описанием полей и их типов от модмейкеров, но читать их весьма тяжело.


ADB

База данных анимации для конкретного типа юнитов. В отличии от упомянутых выше *DB, достаточно «человечна» — это одноуровневая таблица со статичными размерами полей.

vmf4jr_3jtmqytycobxvurk7v2c.png


Описание структуры 
meta:
  id: adb
  title: Evil Islands, ADB file (animations database)
  application: Evil Islands
  file-extension: adb
  license: MIT
  endian: le
doc: Animations database
seq:
  - id: magic
    contents: [0x41, 0x44, 0x42, 0x00]
    doc: Magic bytes
  - id: animations_count
    type: u4
    doc: Number of animations in base
  - id: unit_name
    type: str
    encoding: cp1251
    size: 24
    doc: Name of unit
  - id: min_height
    type: f4
    doc: Minimal height of unit
  - id: mid_height
    type: f4
    doc: Middle height of unit
  - id: max_height
    type: f4
    doc: Maximal height of unit
  - id: animations
    type: animation
    doc: Array of animations
    repeat: expr
    repeat-expr: animations_count
types:
  animation:
    doc: Animation's parameters
    seq:
      - id: name
        type: str
        encoding: cp1251
        size: 16
        doc: Animation's name
      - id: number
        type: u4
        doc: Index in animations array
      - id: additionals
        type: additional
        doc: Packed structure with animation parameters
      - id: action_probability
        type: u4
        doc: Percents of action probability
      - id: animation_length
        type: u4
        doc: Lenght of animation in game ticks
      - id: movement_speed
        type: f4
        doc: Movement speed
      - id: start_show_hide1
        type: u4
      - id: start_show_hide2
        type: u4
      - id: start_step_sound1
        type: u4
      - id: start_step_sound2
        type: u4
      - id: start_step_sound3
        type: u4
      - id: start_step_sound4
        type: u4
      - id: start_hit_frame
        type: u4
      - id: start_special_sound
        type: u4
      - id: spec_sound_id1
        type: u4
      - id: spec_sound_id2
        type: u4
      - id: spec_sound_id3
        type: u4
      - id: spec_sound_id4
        type: u4
    types:
      additional:
        seq:
          - id: packed
            type: u8
        instances:
          weapons:
            value: 'packed & 127'
          allowed_states:
            value: '(packed >> 15) & 7'
          action_type:
            value: '(packed >> 18) & 15'
          action_modifyer:
            value: '(packed >> 22) & 255'
          animation_stage:
            value: '(packed >> 30) & 3'
          action_forms:
            value: '(packed >> 36) & 63'


Это интересно: для нескольких юнитов используется частично урезанный формат базы, практически не исследованный.

Разобравшись с базами данных, объявляем рекламную паузу. Но рекламировать ничего не будем — не наш метод. Лучше обозначим то, что пригодится дальше — как именуются файлы существ.


Формат имён моделей

Имя собирается из групп по два символа — сокращений логического «уровня».
Например, персонаж-женщина будет unhufe — Unit > Human > Female, а initwesp — Inventory > Item > Weapon > Spear, то есть, копьё в инвентаре (не спине, и то хорошо).


Полное дерево элементов имени: 
un: # unit
  an: # animal
    wi: # wild
      ti # tiger
      ba # bat
      bo # boar
      hy # hyen
      de # deer
      gi # rat
      ra # rat
      cr # crawler
      wo # wolf
    ho: # home
      co # cow
      pi # pig
      do # dog
      ho # horse
      ha # hare
  or: # orc
    fe # female
    ma # male
  mo: # monster
    co # column (menu)
    un # unicorn
    cu # Curse
    be # beholder
    tr # troll
    el # elemental
    su # succub (harpie)
    ba # banshee
    dr # driad
    sh # shadow
    li # lizard
    sk # skeleton
    sp # spider
    go # golem, goblin
    ri # Rick
    og # ogre
    zo # zombie
    bi # Rik's dragon
    cy # cyclope
    dg # dragon
    wi # willwisp
    mi # octopus
    to # toad
  hu: # human
    fe # female
    ma # male
in: # inventory
  it: # item
    qu # quest
    qi # interactive
    ar: # armor
      pl # plate
      gl # gloves
      lg # leggins
      bt # boots
      sh # shirt
      hl # helm
      pt # pants
    li: # loot
      mt # material
      tr # trade
    we: # weapon
      hm # hammer
      dg # dagger
      sp # spear
      cb # crossbow
      sw # sword
      ax # axe
      bw # bow
  gm # game menu
  fa: # faces
    un: # unit
      an: # animal
        wi: # wild
          ti: # tiger
            face # face
          ba: # bat
            face # face
          bo: # boar
            face # face
          de: # deer
            face # face
          ra: # rat
            face # face
          cr: # crawler
            face # face
          wo: # wolf
            face # face
        ho: # home
          co: # cow
            face # face
          pi: # pig
            face # face
          do: # dog
            face # face
          ho: # horse
            face # face
          ha: # hare
            face # face
      hu: # human
        fe: # female
          fa # 
          me # 
          th # 
        ma: # male
          fa # 
          me # 
          th # 
      mo: # monster
        to: # toad
          face # face
        tr: # troll
          face # face
        or: # orc
          face # face
        sp: # spider
          face # face
        li: # lizard
          face # face
na: # nature
  fl: # flora
    bu # bush
    te # termitary
    tr # tree
    li # waterplant
  wa # waterfall
  sk # sky
  st # stone
ef: # effects
  cu # 
  ar # 
co # components
st: # static
  si # switch
  bu: # building
    to # tower
    ho # house
  tr # trap
  br # bridge
  ga # gate
  we # well (waterhole)
  wa: # wall
    me # medium
    li # light
  to # torch
  st # static


Это интересно: по данной классификации, грибы — деревья, големы с гоблинами — братья, а Тка-Рик — монстр. Также тут можно заметить «рабочие» имена монстров, подозрительно похожие на таковые из D&D — beholder (злобоглаз), succub (гарпия), ogre (людоед), driad (лесовики).

Морально отдохнув, окунёмся с головой в модели. Они представлены несколькими форматами, которые компонуются между собой.


LNK

Логически — основа модели. Описывает иерархию частей модели, в терминах современного 3d моделирования — иерархию костей.

wevaa186p5bq4fvw8-4vtxbfiju.png


Описание структуры 
meta:
  id: lnk
  title: Evil Islands, LNK file (bones hierarchy)
  application: Evil Islands
  file-extension: lnk
  license: MIT
  endian: le
doc: Bones hierarchy
seq:
  - id: bones_count
    type: u4
    doc: Number of bones
  - id: bones_array
    type: bone
    repeat: expr
    repeat-expr: bones_count
    doc: Array of bones
types:
  bone:
    doc: Bone node
    seq:
      - id: bone_name_len
        type: u4
        doc: Length of bone's name
      - id: bone_name
        type: str
        encoding: cp1251
        size: bone_name_len
        doc: Bone's name
      - id: parent_name_len
        type: u4
        doc: Length of bone's parent name
      - id: parent_name
        type: str
        encoding: cp1251
        size: parent_name_len
        doc: Bone's parent name

Имя родителя основной кости — пустая строка (длины 0).

Кости есть, однако недостаточно назвать их и сложить кучкой — нужно собрать их в скелет.


BON

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

rqf0ntdd5sxadr0us5gfq5cfq2g.png


Описание структуры 
meta:
  id: bon
  title: Evil Islands, BON file (bone position)
  application: Evil Islands
  file-extension: bon
  license: MIT
  endian: le
doc: Bone position
seq:
  - id: position
    type: vec3
    doc: Bone translation
    repeat: eos
types:
  vec3:
    doc: 3d vector
    seq:
      - id: x
        type: f4
        doc: x axis
      - id: y
        type: f4
        doc: y axis
      - id: z
        type: f4
        doc: z axis

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

Как это работает: у модели есть три параметра интерполяции — условно, сила, ловкость, рост. Также есть 8 крайних состояний модели. Используя параметры, можем получить итоговую модель трилинейной интерполяцией.


Непосредственно, алгоритм 
def trilinear(val, coefs=[0, 0, 0]):
    # Linear interpolation by str
    t1 = val[0] + (val[1] - val[0]) * coefs[1]
    t2 = val[2] + (val[3] - val[2]) * coefs[1]
    # Bilinear interpolation by dex
    v1 = t1 + (t2 - t1) * coefs[0]

    # Linear interpolation by str
    t1 = val[4] + (val[5] - val[4]) * coefs[1]
    t2 = val[6] + (val[7] - val[6]) * coefs[1]
    # Bilinear interpolation by dex
    v2 = t1 + (t2 - t1) * coefs[0]

    # Trilinear interpolation by height
    return v1 + (v2 - v1) * coefs[2]


Это интересно: трилинейная интерполяция модели используется для анимации некоторых объектов, например, открытия каменной двери и сундуков.

Теперь самое время посмотреть на сами части модели.


FIG

Пожалуй, этот формат понять слёту невозможно. В сети можно найти его описание и плагин для блендера, но даже с ними осознание приходит не сразу. Взгляните:

c_yxbuglpgn1h0j2g48gc1lk1dw.png


Описание структуры 
meta:
  id: fig
  title: Evil Islands, FIG file (figure)
  application: Evil Islands
  file-extension: fig
  license: MIT
  endian: le
doc: 3d mesh
seq:
  - id: magic
    contents: [0x46, 0x49, 0x47, 0x38]
    doc: Magic bytes
  - id: vertex_count
    type: u4
    doc: Number of vertices blocks
  - id: normal_count
    type: u4
    doc: Number of normals blocks
  - id: texcoord_count
    type: u4
    doc: Number of UV pairs
  - id: index_count
    type: u4
    doc: Number of indeces
  - id: vertex_components_count
    type: u4
    doc: Number of vertex components
  - id: morph_components_count
    type: u4
    doc: Number of morphing components
  - id: unknown
    contents: [0, 0, 0, 0]
    doc: Unknown (aligment)
  - id: group
    type: u4
    doc: Render group
  - id: texture_index
    type: u4
    doc: Texture offset
  - id: center
    type: vec3
    doc: Center of mesh
    repeat: expr
    repeat-expr: 8
  - id: aabb_min
    type: vec3
    doc: AABB point of mesh
    repeat: expr
    repeat-expr: 8
  - id: aabb_max
    type: vec3
    doc: AABB point of mesh
    repeat: expr
    repeat-expr: 8
  - id: radius
    type: f4
    doc: Radius of boundings
    repeat: expr
    repeat-expr: 8
  - id: vertex_array
    type: vertex_block
    doc: Blocks of raw vertex data
    repeat: expr
    repeat-expr: 8
  - id: normal_array
    type: vec4x4
    doc: Packed normal data
    repeat: expr
    repeat-expr: normal_count
  - id: texcoord_array
    type: vec2
    doc: Texture coordinates data
    repeat: expr
    repeat-expr: texcoord_count
  - id: index_array
    type: u2
    doc: Triangles indeces
    repeat: expr
    repeat-expr: index_count
  - id: vertex_components_array
    type: vertex_component
    doc: Vertex components array
    repeat: expr
    repeat-expr: vertex_components_count
  - id: morph_components_array
    type: morph_component
    doc: Morphing components array
    repeat: expr
    repeat-expr: morph_components_count
types:
  morph_component:
    doc: Morphing components indeces
    seq:
      - id: morph_index
        type: u2
        doc: Index of morphing data
      - id: vertex_index
        type: u2
        doc: Index of vertex
  vertex_component:
    doc: Vertex components indeces
    seq:
      - id: position_index
        type: u2
        doc: Index of position data
      - id: normal_index
        type: u2
        doc: Index of normal data
      - id: texture_index
        type: u2
        doc: Index of texcoord data
  vec2:
    doc: 2d vector
    seq:
      - id: u
        type: f4
        doc: u axis
      - id: v
        type: f4
        doc: v axis
  vec3:
    doc: 3d vector
    seq:
      - id: x
        type: f4
        doc: x axis
      - id: y
        type: f4
        doc: y axis
      - id: z
        type: f4
        doc: z axis
  vec3x4:
    doc: 3d vector with 4 values per axis
    seq:
      - id: x
        type: f4
        doc: x axis
        repeat: expr
        repeat-expr: 4
      - id: y
        type: f4
        doc: y axis
        repeat: expr
        repeat-expr: 4
      - id: z
        type: f4
        doc: z axis
        repeat: expr
        repeat-expr: 4
  vertex_block:
    doc: Vertex raw block
    seq:
      - id: block
        type: vec3x4
        doc: Vertex data
        repeat: expr
        repeat-expr: _root.vertex_count
  vec4x4:
    doc: 4d vector with 4 values per axis
    seq:
      - id: x
        type: f4
        doc: x axis
        repeat: expr
        repeat-expr: 4
      - id: y
        type: f4
        doc: y axis
        repeat: expr
        repeat-expr: 4
      - id: z
        type: f4
        doc: z axis
        repeat: expr
        repeat-expr: 4
      - id: w
        type: f4
        doc: w axis
        repeat: expr
        repeat-expr: 4

В чём сложность? Так ведь данные нормалей и вершин хранятся в блоках по 4, а вершины ещё и скомпонованы в 8 блоков для интерполяции.


Это интересно: предположительно, такая группировка сделана для ускорения обработки с помощью SSE инструкций, появившихся в процессорах Intel с 1999.

Что ж, модель мы прочли и составили, однако чего-то не хватает. Точно — анимации!


ANM

Анимация хранится в виде ключевых состояний покомпонентно. Интересен тот факт, что реализована поддержка не только скелетной анимации, но и повершинного морфинга.

i_yblr5zy2irqqer1jqi6tm8v_c.png


Описание структуры 
meta:
  id: anm
  title: Evil Islands, ANM file (bone animation)
  application: Evil Islands
  file-extension: anm
  license: MIT
  endian: le
doc: Bone animation
seq:
  - id: rotation_frames_count
    type: u4
    doc: Number of rotation frames
  - id: rotation_frames
    type: quat
    repeat: expr
    repeat-expr: rotation_frames_count
    doc: Bone rotations
  - id: translation_frames_count
    type: u4
    doc: Number of translation frames
  - id: translation_frames
    type: vec3
    repeat: expr
    repeat-expr: translation_frames_count
    doc: Bone translation
  - id: morphing_frames_count
    type: u4
    doc: Number of morphing frames
  - id: morphing_vertex_count
    type: u4
    doc: Number of vertices with morphing
  - id: morphing_frames
    type: morphing_frame
    repeat: expr
    repeat-expr: morphing_frames_count
    doc: Array of morphing frames
types:
  vec3:
    doc: 3d vector
    seq:
      - id: x
        type: f4
        doc: x axis
      - id: y
        type: f4
        doc: y axis
      - id: z
        type: f4
        doc: z axis
  quat:
    doc: quaternion
    seq:
      - id: w
        type: f4
        doc: w component
      - id: x
        type: f4
        doc: x component
      - id: y
        type: f4
        doc: y component
      - id: z
        type: f4
        doc: z component
  morphing_frame:
    doc: Array of verteces morphing
    seq:
      - id: vertex_shift
        type: vec3
        repeat: expr
        repeat-expr: _parent.morphing_vertex_count
        doc: Morphing shift per vertex

Всё — теперь у нас есть полноценная модель, можно полюбоваться на свежеотрендеренного ящера-отшельника:

butksmbjbom_kgib93drtz9xvj8.jpeg


Момент ностальгии

Узнать, что нужно Ящеру

Разговор с ящером в его жилище

Ящер-Отшельник: Ты пришел, человек. Это хорошо.

Зак: Это все, что ты хотел мне сказать?

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

Ящер-Отшельник: Люди любят золото. Ящерам золото неинтересно. Ты выполнишь мое задание, и я дам тебе золото, которое есть у меня. Этого золота много.

Зак (задумчиво и без особой заинтересованности): Хм… Золото… Оно, конечно, не помешает…

Зак: Было бы лучше, если бы ты помог мне узнать, где живет старый маг, которого я так долго ищу. Ведь ящеры — древний народ, и вы можете это знать!

Ящер-Отшельник: Ты прав. Ящеры — древний народ. Я могу собрать все, что нам известно про старика. Ты согласен выполнить мое задание?

Зак: О чем разговор! Считай, что все уже сделано.

Ящер-Отшельник (серьезно): Уже сделано? Ты хочешь меня обмануть?

Зак: Вообще-то я хотел пошутить, а то ты уж больно серьезен.

Ящер-Отшельник: Понимаю. Это шутка. Наверное, я тоже смогу пошутить. Потом. А сейчас мне надо, чтобы ты вернул воду в Канал. Воду украли у нас орки.

Ящер-Отшельник: Иди на юг вдоль воды. Увидишь плотину и Канал. Плотину надо поднять. Рычагом. Я его дам. Канал нужно завалить. Камнем. Камень я не дам. Он уже лежит на краю Канала. Вверх по течению от плотины. Камень тяжелый. Когда орки копали, они его поднимали долго. Если ты его толкнешь, обратно он будет падать быстро.

Ящер-Отшельник: После этого возвращайся. Я расскажу тебе все, что узнаю про старого Мага.

Зак: По рукам! Но, кстати, если ты добавишь к рассказу немножко монет, я вовсе не обижусь.

Ящер-Отшельник: За монетами отправляйся к моим сородичам, которые живут на отмелях дальше, на юге. Пройди на самый дальний песчаный остров, третий по счету. Сокровища будут твоими!

Ящер-Отшельник (сам себе): Странно. Этот человек любит юмор. Я пошутил. Человек не засмеялся. Очень странно.

Теперь — самое интересное: как хранится карта.


MP

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

Сначала нужно дать общую характеристику ландшафту:


  • число «чанков» — кусков карты 32×32 метра;
  • максимальную высоту (так как высота вершин хранится в целочисленной шкале);
  • число тайловых атласов.

Дополнительно идёт описание материалов карты, а также анимированных тайлов — например, воды или лавы.

rq5azvlnywx7dynoartwivfelea.png


Описание структуры 
meta:
  id: mp
  title: Evil Islands, MP file (map header)
  application: Evil Islands
  file-extension: mp
  license: MIT
  endian: le
doc: Map header
seq:
  - id: magic
    contents: [0x72, 0xF6, 0x4A, 0xCE]
    doc: Magic bytes
  - id: max_altitude
    type: f4
    doc: Maximal height of terrain
  - id: x_chunks_count
    type: u4
    doc: Number of sectors by x
  - id: y_chunks_count
    type: u4
    doc: Number of sectors by y
  - id: textures_count
    type: u4
    doc: Number of texture files
  - id: texture_size
    type: u4
    doc: Size of texture in pixels by side
  - id: tiles_count
    type: u4
    doc: Number of tiles
  - id: tile_size
    type: u4
    doc: Size of tile in pixels by side
  - id: materials_count
    type: u2
    doc: Number of materials
  - id: animated_tiles_count
    type: u4
    doc: Number of animated tiles
  - id: materials
    type: material
    doc: Map materials
    repeat: expr
    repeat-expr: materials_count
  - id: id_array
    type: u4
    doc: Tile type
    repeat: expr
    repeat-expr: tiles_count
    enum: tile_type
  - id: animated_tiles
    type: animated_tile
    doc: Animated tiles
    repeat: expr
    repeat-expr: animated_tiles_count
types:
  material:
    doc: Material parameters
    seq:
      - id: type
        type: u4
        doc: Material type by
        enum: terrain_type
      - id: color
        type: rgba
        doc: RGBA diffuse color
      - id: self_illumination
        type: f4
        doc: Self illumination
      - id: wave_multiplier
        type: f4
        doc: Wave speed multiplier
      - id: warp_speed
        type: f4
        doc: Warp speed multiplier
      - id: unknown
        size: 12
    types:
      rgba:
        doc: RGBA color
        seq:
          - id: r
            type: f4
            doc: Red channel
          - id: g
            type: f4
            doc: Green channel
          - id: b
            type: f4
            doc: Blue channel
          - id: a
            type: f4
            doc: Alpha channel
    enums:
      terrain_type:
        0: base
        1: water_notexture
        2: grass
        3: water
  animated_tile:
    doc: Animated tile parameters
    seq:
      - id: start_index
        type: u2
        doc: First tile of animation
      - id: length
        type: u2
        doc: Animation frames count
enums:
  tile_type:
    0: grass
    1: ground
    2: stone
    3: sand
    4: rock
    5: field
    6: water
    7: road
    8: empty
    9: snow
    10: ice
    11: drygrass
    12: snowballs
    13: lava
    14: swamp
    15: highrock


Список типов ландшафта
terrain type Тип
0 Базовый ландшафт
1 Вода без текстуры
2 Текстурированная трава
3 Текстурированная вода


Список типов материалов
material type Тип
0 grass
1 ground
2 stone
3 sand
4 rock
5 field
6 water
7 road
8 (empty)
9 snow
10 ice
11 drygrass
12 snowballs
13 lava
14 swamp
15 highrock

Тип материала должен влиять на проходимость, судя по информации в файле Res/aiinfo.res/tileDesc.reg.


Это интересно: во всех общедоступных описаниях формата, допущена ошибка — поля земли и воды перепутаны по типам.
И опять же: можно спутать эти файлы с сохранениями мультиплеера.

Теперь мы готовы обработать сами части карты. За дело!


SEC

Файл хранит единичный сектор карты — кусок 32×32 метра. Положение на карте хранится в имени файла, которое имеет вид ZonenameXXXYYY.

9-pd_ltybkk7hx_oywo4wsfwrpc.png


Описание структуры 
meta:
  id: sec
  title: Evil Islands, SEC file (map sector)
  application: Evil Islands
  file-extension: sec
  license: MIT
  endian: le
doc: Map sector
seq:
  - id: magic
    contents: [0x74, 0xF7, 0x4B, 0xCF]
    doc: Magic bytes
  - id: liquids
    type: u1
    doc: Liquids layer indicator
  - id: vertexes
    type: vertex
    doc: Vertex array 33x33
    repeat: expr
    repeat-expr: 1089
  - id: liquid_vertexes
    type: vertex
    doc: Vertex array 33x33
    if: liquids != 0
    repeat: expr
    repeat-expr: 'liquids != 0 ? 1089 : 0'
  - id: tiles
    type: tile
    doc: Tile array 16x16
    repeat: expr
    repeat-expr: 256
  - id: liquid_tiles
    type: tile
    doc: Tile array 16x16
    if: liquids != 0
    repeat: expr
    repeat-expr: 'liquids != 0 ? 256 : 0'
  - id: liquid_material
    type: u2
    doc: Index of material
    if: liquids != 0
    repeat: expr
    repeat-expr: 'liquids != 0 ? 256 : 0'
types:
  vertex:
    doc: Vertex data
    seq:
      - id: x_shift
        type: s1
        doc: Shift by x axis
      - id: y_shift
        type: s1
        doc: Shift by y axis
      - id: altitude
        type: u2
        doc: Height (z position)
      - id: packed_normal
        type: normal
        doc: Packed normal
  normal:
    doc: Normal (3d vector)
    seq:
      - id: packed
        type: u4
        doc: Normal packed in 4b
    instances:
      x:
        doc: Unpacked x component
        value: packed >> 11 & 0x7FF
      y:
        doc: Unpacked y component
        value: packed & 0x7FF
      z:
        doc: Unpacked z component
        value: packed >> 22
  tile:
    doc: Tile parameters
    seq:
      - id: packed
        type: u2
        doc: Tile information packed in 2b
    instances:
      index:
        doc: Tile index in texture
        value: packed & 63
      texture:
        doc: Texture index
        value: packed >> 6 & 255
      rotation:
        doc: Tile rotation (*90 degrees)
        value: packed >> 14 & 3

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


Набор алгоритмов распаковки

Распаковка нормали

10 бит на ось z, по 11 на x и y

unsigned packed_normal;

float x = ((float)((packed_normal >> 11) & 0x7FF) - 1000.0f) / 1000.0f;
float y = ((float)(packed_normal & 0x7FF) - 1000.0f) / 1000.0f;
float z = (float)(packed_normal >> 22) / 1000.0f;

Информация о текстуре

6 бит на индекс в атласе, 8 на номер текстуры, 2 на вращение

unsigned short texture;

unsigned char tile_index = f & 63;
unsigned char texture_index = (f >> 6) & 255;
unsigned char rotation = (f >> 14) & 3;


Генерация 3d модели

Получение ландшафта

Вершины идут по 33 элемента в 33 строки, то есть, образуя 32×32 клетки. Длина клетки по стороне — 1 условная единица.

Позиция вершины:
x = индекс по x + x_offset / 254
y = индекс по y + y_offset / 254
z = altitude / 65535 * max_altitude (из .mp файла)

Вершины объединяются в полигоны «гребёнкой», при этом четыре вершины образуют два полигона: 

 0   1 2
   *-*-*
   |/|/| ~
33 *-*-*
   |/|/| ~
66 *-*-*
    ~ ~  ~

Текстура накладывается на сразу че

© Habrahabr.ru