Как я писал кросплатформенный 3d игровой движок

    Приветствую Хабр! Многие из нас наверняка задумывались «а не написать ли мне игру самому». Сейчас я веду проект «Open tomb» — попытка создать переносимый движок для игры в первые 5 частей «Tomb raider», который выложен на sourceforge.com, однако, судя по своему опыту, многим будет интересна история с некоторыми деталями о том, как движок писался с нуля и с практически отсутствующими знаниями в этой области. Даже сейчас многих знаний не хватает, а иногда просто не хватает мотивации что-то сделать лучше, или правильнее, однако лучше перейти к тому, как все же проект оживал шаг за шагом.

    Что меня побудило писать движок

    Началась история довольно давно и с того, что мне захотелось поиграть в замечательную логическую головоломку «Pusher» на Vista 64. Однако оригинальная игра была 16 битной и напрочь отказывалась запускаться. Ничего лучше, чем написать на Си её клон, я не придумал (иногда не лучшее изначально решение приводит к более полезным результатам). Спустя небольшое время я реализовал игру на платформе SDL v1.2 + OpenGL.

    image

    Для удобства переноса карт добавил редактор уровней и вручную клонировал все 64 карты. Через какое-то время интерес к «Pusher» ослаб, и мне уже захотелось погонять в Tomb raider 1 с 3dfx графикой. И как многие уже догадались, существующие решения это сделать меня не особо порадовали (скорее даже субъективно) и я занялся поиском портов. Кроме известного проекта Open raider я ничего не нашел. До сих пор помню как мучился с его сборкой под windows с помощью компилятора mingw (среду разработки не помню, либо code::blocks, либо netbeans). Результат сборки меня совсем не порадовал: загрузка уровня около минуты и черный экран в итоге. Умения ковырять чужой код, понимать его структуру и смысл функций у меня не было. Попытки собрать «лучше» прекратились. Однако я загорелся идеей собрать хоть один из открытых движков вручную, не автоконфигом Die GNU Autotools, а с самостоятельно собранного проектника в среде разработки.

    Таким образом, после кучи времени за монитором, определенного количества мата и т.д., я собрал Quake Tenebrae без звука. Зато он работал! Это была маленькая победа, которая принесла плоды: я стал лучше разбираться в чужом коде и наконец-то стал хоть что-то понимать в организации работы компилятора – без чего вообще никак нельзя. После было сделано несколько мелких доработок, устранены некоторые баги и запущен звук, но проект так и не был залит в интернет (даже тогда он был морально устаревшим, особенно с учетом наличия Dark places engine). Однако из кода движка Quake Tenebrae я узнал как организована работа игры в целом, отдельных её компонентов и менеджера памяти (я добавил в него функцию realloc, пусть довольно простую, но все работало без вылетов).

    Пишем движок

    Когда я немного освоился, то решил начать писать свой движок с нуля. Просто ради интереса и саморазвития. Базой для создания движка служило следующее: компилятор GCC-TDM v4.Х.Х + msys и среда разработки Netbeans; библиотеки: SDL v1.2 + OpenGL. Первая реализованная функция была созданием скриншота и его сохранением в файл *.bmp с применением самописной библитечки для работы с этим форматом. Какой движок может обойтись без консоли для ввода читов команд и вывода текста – наверное никакой, поэтому следующим делом я изучил вопрос о том, как выводить текст в окно OpenGL и выбрал связку freetype 1 + gltt. Первой распознаваемой командой была команда exit и уже после – команды для игры с размерами шрифтов, строк и т.д…. Для справки: мне понравился код, используемый в Quake I для парсинга строк и последовательного его разбития на токены, который до сих пор присутствует в движке:

    char *parse_token(char *data, char *token)
    {
        int c;
        int len;
    
        len = 0;
        token[0] = 0;
    
        if(!data)
        {
            return NULL;
        }
    
    // skip whitespace
        skipwhite:
        while((c = *data) <= ' ')
        {
            if(c == 0)
                return NULL;                    // end of file;
            data++;
        }
    
    // skip // comments
        if (c=='/' && data[1] == '/')
        {
            while (*data && *data != '\n')
                data++;
            goto skipwhite;
        }
    
    // handle quoted strings specially
        if (c == '\"')
        {
            data++;
            while (1)
            {
                c = *data++;
                if (c=='\"' || !c)
                {
                    token[len] = 0;
                    return data;
                }
                token[len] = c;
                len++;
            }
        }
    
    // parse single characters
        if (c=='{' || c=='}'|| c==')'|| c=='(' || c=='\'' || c==':')
        {
            token[len] = c;
            len++;
            token[len] = 0;
            return data+1;
        }
    
    // parse a regular word
        do
        {
            token[len] = c;
            data++;
            len++;
            c = *data;
            if (c=='{' || c=='}'|| c==')'|| c=='(' || c=='\'' || c==':')
            {
                break;
            }
        } while (c>32);
        token[len] = 0;
        return data;
    } 


    Забегая вперед: когда потребовалась поддержка скриптов я решил использовать подход к разработке движка как в «ID software» на примере «DOOM 3 engine», который был очень хорошо описан здесь, на Хабре =) (хочется еще раз сказать огромное спасибо авторам за статью, перевод и написавшим интересные комментарии к ней людям). Под впечатлением статьи я решил внедрить в свой движок LUA не только для внутриигровых скриптовых нужд, но еще для парсинга конфигурационных файлов и консольных команд (т.е. везде используется единообразная система). Подход оправдал себя абсолютно.

    Перейдем к 3d

    Мне повезло, что в институте мне нравились линейная алгебра, матричные преобразования, вектора и численные методы. Без этих основ к программированию движка с нуля приступать очень опрометчиво (разве для того, чтобы изучить эти разделы на примерах, однако без определенной теоретической базы знаний это будет мало реально). В освоении графики мне сильно помогла книга А. Борескова «Графика трехмерной компьютерной игры на основе OPENGL». Перечитал ее не один раз (для ознакомления с математическим аппаратом, типами рендереров и структурой движков). Без понятия о принципе построения сцены и предназначения видовой матрицы и матрицы проекции продвинуться никуда не удастся. После изучения некоторого материала в интернете и просто литературы, я решил делать портальный рендерер. Первое что было реализовано в движке – это свободно летающая камера и несколько порталов, которые можно было увидеть только друг через друга.

    После хардкодом была добавлена wireframe сцена из 3-х комнат (две побольше и коридор). Но разве интересно летать в таком примитивном мире… И тут я решил воспользоваться загрузчиком ресурсов из Open raider и порендерить уровни. Результат меня порадовал и тут уже окончательно было решено реализовывать замысел по созданию порта для игры в Tomb raider, хотя бы в первую её часть. Для позиционирования объектов в пространстве я использовал матрицу в формате OpenGL так как это позволяет обращаться к базовым векторам локальной системы координат объекта, задавать положение объекта одной командой glMultMatrixf(transform) и задавать ориентацию объекта в физическом движке bullet одной командой setFromOpenGLMatrix(transform), о чем чуть позже. Ниже приведено изображение со структурой матрицы OpenGL с выше приведенной ссылки:

    image

    Для ведения истории изменений в движке и возможности бэкапа и просто для саморазвития было решено использовать систему контроля версий mercurial. Её применение позволило не только прослеживать прогресс в написании кода, но и дало возможность загрузить результаты на sourceforge.com. Следует отметить, что когда в движок начала загружаться информация о порталах с реальных карт, сразу всплыло огромное количество недоработок моей реализации портальной системы. На борьбу с пропадающими объектами и вылетами ушло немало времени, и даже сейчас я считаю, что портальный модуль нуждается в серьезной доработке. Сейчас рендерер движка в зависимости от положения камеры и ее ориентации начинает прохождение по порталам комнат и добавляет в список только видимые комнаты. Потом рендерер рисует комнаты и их содержимое из списка. Понятно, что для больших открытых пространств такой подход не самый удачный, однако для целей проекта его вполне достаточно. Вот пример рекурсивной функции обхода по комнатам:

    **
     * The reccursion algorithm: go through the rooms with portal - frustum occlusion test
     * @portal - we entered to the room through that portal
     * @frus - frustum that intersects the portal
     * @return number of added rooms
     */
    int Render_ProcessRoom(struct portal_s *portal, struct frustum_s *frus)
    {
        int ret = 0, i;
        room_p room = portal->dest_room;                                            // куда ведет портал
        room_p src_room = portal->current_room;                                     // откуда ведет портал
        portal_p p;                                                                 // указатель на массив порталов входной ф-ии
        frustum_p gen_frus;                                                         // новый генерируемый фрустум
    
        if((src_room == NULL) || !src_room->active || (room == NULL) || !room->active)
        {
            return 0;
        }
    
        p = room->portals;
    
        for(i=0; i<room->portal_count; i++,p++)                                     // перебираем все порталы входной комнаты
        {
            if((p->dest_room->active) && (p->dest_room != src_room))                // обратно идти даже не пытаемся
            {
                gen_frus = Portal_FrustumIntersect(p, frus, &renderer);             // Главная ф-я портального рендерера. Тут и проверка
                if(NULL != gen_frus)                                                // на пересечение и генерация фрустума по порталу
                {
                    ret++;
                    Render_AddRoom(p->dest_room);
                    Render_ProcessRoom(p, gen_frus);
                }
            }
        }
        return ret;
    }


    Скелетные анимированные модели

    И вот началась одна из самых кропотливых работ в проекте. Рендерить статичные комнаты со статичными объектами оказалось сравнительно несложно, но вот когда дело дошло до анимированных скелетных моделей… Первое что я понял: загрузчик ресурсов Open raider не грузит всю необходимую информацию о скелетной модели. Количество фреймов в анимации определяется некорректно, из-за чего одна анимация содержит в себе фреймы сразу от нескольких.
    В ходе попыток решения этих проблем я нашел различные документации по формату уровней Tomb raider и заодно проект vt, в котором был свой загрузчик ресурсов. Пусть в этом проекте не было загрузки кадров анимации моделей, зато в нем был более структурированный код, удобный для чтения и доведения до ума. Так я заменил загрузчик в проекте на vt. Для примера: в Open raider все 5 частей Tomb raider грузятся одной длинной функцией с кучей if и switch по номеру версии игры, что заметно усложняло чтение кода и поиск ошибок. В vt было 5 модулей, каждый из которых отвечал за свою версию уровня, благодаря чему код читался достаточно легко, и внесение изменений не представляло трудностей.

    Главной проблемой с анимациями оказалось извлечение углов поворотов костей в скелетной модели. Дело в том, что для экономии места углы хранились в байткоде с шагом в 2-4 байта. В первые 2 байта входит флаг о том один ли здесь поворот и вокруг какой оси, или сразу три и сами углы. В случае 3-х поворотов флаги и углы хранятся в 4-х байтах, в случае одного используются только 2 байта. При этом углы для всех моделей, анимаций и кадров хранятся в одном массиве и смещения надо вычислять. К тому же в этом байткоде еще хранятся заголовки отдельных фреймов модели и путаница со смещениями критична, а теперь прибавим то, что количество фреймов грузится некорректно (в последствии оказалось, что количество фреймов дано для «интерполированных» анимаций с частотой 30 fps, а реально, кадры могут хранятся в «ужатом» виде с fps со множителями 1, 1/2, 1/3 и 1/4). После допиливания загрузчика фреймов анимаций, скелетные модельки перестали выворачиваются наизнанку и превращаться в кашу из искаженных полигонов! Теперь надо «оживить» Лару. Ниже приведен код функции, генерирующей скелетную модель, сохранена орфография и закомментированые участки кода для отладки:

    void GenSkeletalModel(struct world_s *world, size_t model_num, struct skeletal_model_s *model, class VT_Level *tr)
    {
        int i, j, k, l, l_start;
        tr_moveable_t *tr_moveable;
        tr_animation_t *tr_animation;
    
        uint32_t frame_offset, frame_step;
        uint16_t *frame, temp1, temp2;              ///@FIXME: "frame" set, but not used
        float ang;
        btScalar rot[3];
    
        bone_tag_p bone_tag;
        bone_frame_p bone_frame;
        mesh_tree_tag_p tree_tag;
        animation_frame_p anim;
    
        tr_moveable = &tr->moveables[model_num];                                    // original tr structure
        model->collision_map = (uint16_t*)malloc(model->mesh_count * sizeof(uint16_t));
        model->collision_map_size = model->mesh_count;
        for(i=0;i<model->mesh_count;i++)
        {
            model->collision_map[i] = i;
        }
    
        model->mesh_tree = (mesh_tree_tag_p)malloc(model->mesh_count * sizeof(mesh_tree_tag_t));
        tree_tag = model->mesh_tree;
        tree_tag->mesh2 = NULL;
        for(k=0;k<model->mesh_count;k++,tree_tag++)
        {
            tree_tag->mesh = model->mesh_offset + k;
            tree_tag->mesh2 = NULL;
            tree_tag->flag = 0x00;
            vec3_set_zero(tree_tag->offset);
            if(k == 0)
            {
                tree_tag->flag = 0x02;
                vec3_set_zero(tree_tag->offset);
            }
            else
            {
                uint32_t *tr_mesh_tree = tr->mesh_tree_data + tr_moveable->mesh_tree_index + (k-1)*4;
                tree_tag->flag = tr_mesh_tree[0];
                tree_tag->offset[0] = (float)((int32_t)tr_mesh_tree[1]);
                tree_tag->offset[1] = (float)((int32_t)tr_mesh_tree[3]);
                tree_tag->offset[2] =-(float)((int32_t)tr_mesh_tree[2]);
            }
        }
    
        /*
         * =================    now, animation loading    ========================
         */
    
        if(tr_moveable->animation_index < 0 || tr_moveable->animation_index >= tr->animations_count)
        {
            /*
             * model has no start offset and any animation
             */
            model->animation_count = 1;
            model->animations = (animation_frame_p)malloc(sizeof(animation_frame_t));
            model->animations->frames_count = 1;
            model->animations->frames = (bone_frame_p)malloc(model->animations->frames_count * sizeof(bone_frame_t));
            bone_frame = model->animations->frames;
    
            model->animations->id = 0;
            model->animations->next_anim = NULL;
            model->animations->next_frame = 0;
            model->animations->state_change = NULL;
            model->animations->state_change_count = 0;
            model->animations->original_frame_rate = 1;
    
            bone_frame->bone_tag_count = model->mesh_count;
            bone_frame->bone_tags = (bone_tag_p)malloc(bone_frame->bone_tag_count * sizeof(bone_tag_t));
    
            vec3_set_zero(bone_frame->pos);
            vec3_set_zero(bone_frame->move);
            bone_frame->v_Horizontal = 0.0;
            bone_frame->v_Vertical = 0.0;
            bone_frame->command = 0x00;
            for(k=0;k<bone_frame->bone_tag_count;k++)
            {
                tree_tag = model->mesh_tree + k;
                bone_tag = bone_frame->bone_tags + k;
    
                rot[0] = 0.0;
                rot[1] = 0.0;
                rot[2] = 0.0;
                vec4_SetTRRotations(bone_tag->qrotate, rot);
                vec3_copy(bone_tag->offset, tree_tag->offset);
            }
            return;
        }
        //Sys_DebugLog(LOG_FILENAME, "model = %d, anims = %d", tr_moveable->object_id, GetNumAnimationsForMoveable(tr, model_num));
        model->animation_count = GetNumAnimationsForMoveable(tr, model_num);
        if(model->animation_count <= 0)
        {
            /*
             * the animation count must be >= 1
             */
            model->animation_count = 1;
        }
    
        /*
         *   Ok, let us calculate animations;
         *   there is no difficult:
         * - first 9 words are bounding box and frame offset coordinates.
         * - 10's word is a rotations count, must be equal to number of meshes in model.
         *   BUT! only in TR1. In TR2 - TR5 after first 9 words begins next section.
         * - in the next follows rotation's data. one word - one rotation, if rotation is one-axis (one angle).
         *   two words in 3-axis rotations (3 angles). angles are calculated with bit mask.
         */
        model->animations = (animation_frame_p)malloc(model->animation_count * sizeof(animation_frame_t));
        anim = model->animations;
        for(i=0;i<model->animation_count;i++,anim++)
        {
            tr_animation = &tr->animations[tr_moveable->animation_index+i];
            frame_offset = tr_animation->frame_offset / 2;
            l_start = 0x09;
            if(tr->game_version == TR_I || tr->game_version == TR_I_DEMO || tr->game_version == TR_I_UB)
            {
                l_start = 0x0A;
            }
            frame_step = tr_animation->frame_size;
    
            //Sys_DebugLog(LOG_FILENAME, "frame_step = %d", frame_step);
            anim->id = i;
            anim->next_anim = NULL;
            anim->next_frame = 0;
            anim->original_frame_rate = tr_animation->frame_rate;
            anim->accel_hi = tr_animation->accel_hi;
            anim->accel_hi2 = tr_animation->accel_hi2;
            anim->accel_lo = tr_animation->accel_lo;
            anim->accel_lo2 = tr_animation->accel_lo2;
            anim->speed = tr_animation->speed;
            anim->speed2 = tr_animation->speed2;
            anim->anim_command = tr_animation->anim_command;
            anim->num_anim_commands = tr_animation->num_anim_commands;
            anim->state_id = tr_animation->state_id;
            anim->unknown = tr_animation->unknown;
            anim->unknown2 = tr_animation->unknown2;
            anim->frames_count = GetNumFramesForAnimation(tr, tr_moveable->animation_index+i);
            //Sys_DebugLog(LOG_FILENAME, "Anim[%d], %d", tr_moveable->animation_index, GetNumFramesForAnimation(tr, tr_moveable->animation_index));
    
            // Parse AnimCommands
            // Max. amount of AnimCommands is 255, larger numbers are considered as 0.
            // See http://evpopov.com/dl/TR4format.html#Animations for details.
    
            if( (anim->num_anim_commands > 0) && (anim->num_anim_commands <= 255) )
            {
                // Calculate current animation anim command block offset.
                int16_t *pointer = world->anim_commands + anim->anim_command;
    
                for(uint32_t count = 0; count < anim->num_anim_commands; count++, pointer++)
                {
                    switch(*pointer)
                    {
                        case TR_ANIMCOMMAND_PLAYEFFECT:
                        case TR_ANIMCOMMAND_PLAYSOUND:
                            // Recalculate absolute frame number to relative.
                            ///@FIXED: was unpredictable behavior.
                            *(pointer + 1) -= tr_animation->frame_start;
                            pointer += 2;
                            break;
    
                        case TR_ANIMCOMMAND_SETPOSITION:
                            // Parse through 3 operands.
                            pointer += 3;
                            break;
    
                        case TR_ANIMCOMMAND_JUMPDISTANCE:
                            // Parse through 2 operands.
                            pointer += 2;
                            break;
    
                        default:
                            // All other commands have no operands.
                            break;
                    }
                }
            }
    
    
            if(anim->frames_count <= 0)
            {
                /*
                 * number of animations must be >= 1, because frame contains base model offset
                 */
                anim->frames_count = 1;
            }
            anim->frames = (bone_frame_p)malloc(anim->frames_count * sizeof(bone_frame_t));
    
            /*
             * let us begin to load animations
             */
            bone_frame = anim->frames;
            frame = tr->frame_data + frame_offset;
            for(j=0;j<anim->frames_count;j++,bone_frame++,frame_offset+=frame_step)
            {
                frame = tr->frame_data + frame_offset;
                bone_frame->bone_tag_count = model->mesh_count;
                bone_frame->bone_tags = (bone_tag_p)malloc(model->mesh_count * sizeof(bone_tag_t));
                vec3_set_zero(bone_frame->pos);
                vec3_set_zero(bone_frame->move);
                bone_frame->v_Horizontal = 0.0;
                bone_frame->v_Vertical = 0.0;
                bone_frame->command = 0x00;
                GetBFrameBB_Pos(tr, frame_offset, bone_frame);
    
                if(frame_offset < 0 || frame_offset >= tr->frame_data_size)
                {
                    //Con_Printf("Bad frame offset");
                    for(k=0;k<bone_frame->bone_tag_count;k++)
                    {
                        tree_tag = model->mesh_tree + k;
                        bone_tag = bone_frame->bone_tags + k;
                        rot[0] = 0.0;
                        rot[1] = 0.0;
                        rot[2] = 0.0;
                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                        vec3_copy(bone_tag->offset, tree_tag->offset);
                    }
                }
                else
                {
                    l = l_start;
                    for(k=0;k<bone_frame->bone_tag_count;k++)
                    {
                        tree_tag = model->mesh_tree + k;
                        bone_tag = bone_frame->bone_tags + k;
                        rot[0] = 0.0;
                        rot[1] = 0.0;
                        rot[2] = 0.0;
                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                        vec3_copy(bone_tag->offset, tree_tag->offset);
    
                        switch(tr->game_version)
                        {
                            case TR_I:                                              /* TR_I */
                            case TR_I_UB:
                            case TR_I_DEMO:
                                temp2 = tr->frame_data[frame_offset + l];
                                l ++;
                                temp1 = tr->frame_data[frame_offset + l];
                                l ++;
                                rot[0] = (float)((temp1 & 0x3ff0) >> 4);
                                rot[2] =-(float)(((temp1 & 0x000f) << 6) | ((temp2 & 0xfc00) >> 10));
                                rot[1] = (float)(temp2 & 0x03ff);
                                rot[0] *= 360.0 / 1024.0;
                                rot[1] *= 360.0 / 1024.0;
                                rot[2] *= 360.0 / 1024.0;
                                vec4_SetTRRotations(bone_tag->qrotate, rot);
                                break;
    
                            default:                                                /* TR_II + */
                                temp1 = tr->frame_data[frame_offset + l];
                                l ++;
                                if(tr->game_version >= TR_IV)
                                {
                                    ang = (float)(temp1 & 0x0fff);
                                    ang *= 360.0 / 4096.0;
                                }
                                else
                                {
                                    ang = (float)(temp1 & 0x03ff);
                                    ang *= 360.0 / 1024.0;
                                }
    
                                switch (temp1 & 0xc000)
                                {
                                    case 0x4000:    // x only
                                        rot[0] = ang;
                                        rot[1] = 0;
                                        rot[2] = 0;
                                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                                        break;
    
                                    case 0x8000:    // y only
                                        rot[0] = 0;
                                        rot[1] = 0;
                                        rot[2] =-ang;
                                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                                        break;
    
                                    case 0xc000:    // z only
                                        rot[0] = 0;
                                        rot[1] = ang;
                                        rot[2] = 0;
                                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                                        break;
    
                                    default:        // all three
                                        temp2 = tr->frame_data[frame_offset + l];
                                        rot[0] = (float)((temp1 & 0x3ff0) >> 4);
                                        rot[2] =-(float)(((temp1 & 0x000f) << 6) | ((temp2 & 0xfc00) >> 10));
                                        rot[1] = (float)(temp2 & 0x03ff);
                                        rot[0] *= 360.0 / 1024.0;
                                        rot[1] *= 360.0 / 1024.0;
                                        rot[2] *= 360.0 / 1024.0;
                                        vec4_SetTRRotations(bone_tag->qrotate, rot);
                                        l ++;
                                        break;
                                };
                                break;
                        };
                    }
                }
            }
        }
    
        /*
         * Animations interpolation to 1/30 sec like in original. Needed for correct state change works.
         */
        SkeletalModel_InterpolateFrames(model);
        GenerateAnimCommandsTransform(model);
        /*
         * state change's loading
         */
    
    #if LOG_ANIM_DISPATCHES
        if(model->animation_count > 1)
        {
            Sys_DebugLog(LOG_FILENAME, "MODEL[%d], anims = %d", model_num, model->animation_count);
        }
    #endif
        anim = model->animations;
        for(i=0;i<model->animation_count;i++,anim++)
        {
            anim->state_change_count = 0;
            anim->state_change = NULL;
    
            tr_animation = &tr->animations[tr_moveable->animation_index+i];
            j = (int)tr_animation->next_animation - (int)tr_moveable->animation_index;
            j &= 0x7fff;
            if(j >= 0 && j < model->animation_count)
            {
                anim->next_anim = model->animations + j;
                anim->next_frame = tr_animation->next_frame - tr->animations[tr_animation->next_animation].frame_start;
                anim->next_frame %= anim->next_anim->frames_count;
                if(anim->next_frame < 0)
                {
                    anim->next_frame = 0;
                }
    #if LOG_ANIM_DISPATCHES
                Sys_DebugLog(LOG_FILENAME, "ANIM[%d], next_anim = %d, next_frame = %d", i, anim->next_anim->id, anim->next_frame);
    #endif
            }
            else
            {
                anim->next_anim = NULL;
                anim->next_frame = 0;
            }
    
            anim->state_change_count = 0;
            anim->state_change = NULL;
    
            if((tr_animation->num_state_changes > 0) && (model->animation_count > 1))
            {
                state_change_p sch_p;
    #if LOG_ANIM_DISPATCHES
                Sys_DebugLog(LOG_FILENAME, "ANIM[%d], next_anim = %d, next_frame = %d", i, (anim->next_anim)?(anim->next_anim->id):(-1), anim->next_frame);
    #endif
                anim->state_change_count = tr_animation->num_state_changes;
                sch_p = anim->state_change = (state_change_p)malloc(tr_animation->num_state_changes * sizeof(state_change_t));
    
                for(j=0;j<tr_animation->num_state_changes;j++,sch_p++)
                {
                    tr_state_change_t *tr_sch;
                    tr_sch = &tr->state_changes[j+tr_animation->state_change_offset];
                    sch_p->id = tr_sch->state_id;
                    sch_p->anim_dispath = NULL;
                    sch_p->anim_dispath_count = 0;
                    for(l=0;l<tr_sch->num_anim_dispatches;l++)
                    {
                        tr_anim_dispatch_t *tr_adisp = &tr->anim_dispatches[tr_sch->anim_dispatch+l];
                        int next_anim = tr_adisp->next_animation & 0x7fff;
                        int next_anim_ind = next_anim - (tr_moveable->animation_index & 0x7fff);
                        if((next_anim_ind >= 0) &&(next_anim_ind < model->animation_count))
                        {
                            sch_p->anim_dispath_count++;
                            sch_p->anim_dispath = (anim_dispath_p)realloc(sch_p->anim_dispath, sch_p->anim_dispath_count * sizeof(anim_dispath_t));
    
                            anim_dispath_p adsp = sch_p->anim_dispath + sch_p->anim_dispath_count - 1;
                            int next_frames_count = model->animations[next_anim - tr_moveable->animation_index].frames_count;
                            int next_frame = tr_adisp->next_frame - tr->animations[next_anim].frame_start;
    
                            int low  = tr_adisp->low  - tr_animation->frame_start;
                            int high = tr_adisp->high - tr_animation->frame_start;
    
                            adsp->frame_low  = low  % anim->frames_count;
                            adsp->frame_high = (high - 1) % anim->frames_count;
                            adsp->next_anim = next_anim - tr_moveable->animation_index;
                            adsp->next_frame = next_frame % next_frames_count;
    
    #if LOG_ANIM_DISPATCHES
                            Sys_DebugLog(LOG_FILENAME, "anim_disp[%d], frames_count = %d: interval[%d.. %d], next_anim = %d, next_frame = %d", l,
                                        anim->frames_count, adsp->frame_low, adsp->frame_high,
                                        adsp->next_anim, adsp->next_frame);
    #endif
                        }
                    }
                }
            }
        }
    }


    Выход в свет

    Когда скелетные модели заработали, уже можно было переходить к их расстановке по уровню и «оживлять» Лару, что требовало наличия физики. Для начала было решено писать свой физический движок, чтобы лучше ознакомиться с темой и потом уже более основательно подойти к выбору уже готовых продуктов. Первое что требуется для создания контроллера персонажа – это определение высот. Изначально была написана (на основе барицентрического алгоритма) функция определения пересечения треугольника и луча. После были добавлены такие базовые методы, как определение пересечения движущихся отрезков, треугольника и сферы, треугольника и треугольника. Следует отметить, что такой подход исключает возможность появления так называемого «туннельного эффекта» (когда из-за большой скорости объекты с большими скоростями могут пролететь друг сквозь друга без столкновения), присущего impulse based физическим движкам.

    И вот Лара бегает по уровням, пусть и минуя все ступени любых размеров, зато не вываливается за пределы карты! Когда проект был в таком состоянии мне написал Анатолий Lwmte о том, что круто, что хоть кому-то интересны первые части Tomb raider. Так началась переписка, благодаря которой к проекту начал заново появляться интерес. После я зарегистрировался на tombraiderforums.com (Анатолий был там уже достаточно долго, со своим проектом по улучшению движка четвертой части Tomb raider). Благодаря нему на этом форуме появилась тема с моим движком и много доработок в коде: менеджер звука, переделка системы контроля состояний (до этого у меня был switch по номерам анимаций, теперь он по номерам состояний) и т.д. Наличие заинтересованных в проекте людей хорошо мотивирует развивать проект.

    Физика + оптимизация рендерера

    Поскольку я использовал свою физику, да еще и с плохой оптимизацией, в некоторых местах стало проседать fps. Путем долгих ковыряний различных физических движков с открытым исходным кодом был выбран bullet. Первой делом я добавил фильтр на столкновения в случае пересекающихся комнат. Дело в том, что дизайн оригинальных уровней допускает пересечение 2-х и более совершенно различных комнат в одном месте, при этом объекты одной комнаты ни как не должны влиять на объекты другой; аналогично и с отрисовкой. В настоящее время я стараюсь довести до ума контроллер персонажа: устранить возможность прохода сквозь стены (происходит в ряде анимаций в упор к стене) и доделать реакцию и поведение персонажа в случае климбинга по стенам и потолку.

    Вернемся к OpenGL. Изначально в движке отрисовка полигонов велась с помощью glVertex3fv(...) и т.д.; Про производительность такого подхода и скорость работы движка можно сказать одно: их нет. Поэтому после изучения части, касающейся VBO (Vertex Buffer Object), я сделал оптимизацию и стал по возможности хранить данные вершин полигонов в видео памяти и отрисовывать меш одним заходом. Скорость заметно возросла. Однако из-за того, что для одного меша текстуры могли лежать в разных массивах пикселей, переключение OpenGL текстур было чаще чем надо, а то, что текстуры многих различных объектов могут храниться в одном массиве пикселей, создавало «артефакты» при включенном сглаживании. Cochrane с tombraiderforums.com взялся за оптимизацию рендерера и написал текстурный атлас с границами между текстурами. Благодаря этому нововведению все текстуры уровня хранятся в 1 – 2 OpenGL текстурах и сглаживание не приводит к появлению «артефактов». К тому же он сделал порт проекта на MacOS.

    Когда совсем не было идей за что и как браться в движке, я просто искал ошибки в коде, подправлял его структуру или менял подключаемые библиотеки. Таким образом было проведено «переселение» с SDL1 на SDL2, с freetype1 + gltt к freetype2 + ftgl. Аналогичным образом мне пришла идея добавить сглаживание анимациям с помощью сферической интерполяции slerp. Здесь я хочу добавить: будьте внимательны к математическим алгоритмам, особенно когда дело касается «арок» (asin, acos, atan…) – потеря знака чревата убойными кадрами с перекошенным и перекрученным скелетом. Советую посмотреть реализацию slerp в исходном коде bullet. После добавления сглаживания, я уже не мог смотреть на несглаженные анимации. Далее возникла необходимость грузить и проигрывать звук, а то бегать по уровням в гробовой тишине не очень-то, хоть и Tomb raider.

    Добавляем звук

    Для использования звука применение SDLAudio + SDLMixer совершенно недостаточно, а лезть в алгоритмы преобразования звукового потока и делать велосипеды для создания эффектов – совсем плохая идея. Посоветовавшись с Анатолием было решено использовать OpenAL. Поскольку я руководствовался тем, чтобы как можно больше платформо-зависимого кода переложить на SDL, то ничего лучше написания SDL_backend для OpenAL я не придумал. Однако оно сработало, я добавил инструмент в движок, а Анатолий заставил все играть когда надо, где надо и еще с нужными эффектами.

    И вот подошла пора оживлять всевозможные рычаги, ловушки и прочие триггеры игрового мира. Фактически здесь разработка шла по логике: мне нужно что-то реализовать, какие для этого нужны инструменты, как их реализовать. Основная функция, применяемая для работы скриптов – это получение указателя на объект по числовому id, дальше любая LUA функция сможет обрабатывать все необходимые объекты. Для динамического добавления и удаления объектов и возможности быстрого доступа к ним по id я применил красно-черные деревья. По идее можно было применить хэш таблицы, но тут скорее уже сработали личные предпочтения.
    В итоге уже сейчас скриптовая система позволяет проводить практические любые манипуляции с объектами и анимациями, создавать задачи (и на их основе таймеры), подбирать предметы, нажимать рычании и кнопки, открывая и закрывая тем самым двери и не только. Благодаря стараниям людей из сообщества tombraiderforums.com был добавлен gameflow_manager, отвечающий за переход с одного уровня на другой, загрузку нужных скриптов и экранных заставок, загрузка информации об источниках света и реализация простейшего lightmap на основе корректировки цветов вершин и cmake скрипт для сборки под OS Lunux.

    Послесловие

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

    Дальнейшие планы в проекте просты:

    1) исправить существующие баги, в особенности с физикой, и расширить возможности контроллера персонажей;
    2) «оживить» врагов на картах, добавить ИИ и оружие;
    3) расширить систему управления анимациями скелетных моделей для переключения мешей;
    4) расширить возможности скриптовой системы и написать ключевые уровневые скрипты, чтобы можно было пройти по нормальному игру;
    5) улучшить графику в игре, добавить эффекты, однако здесь я рассчитываю на помощь более квалифицированных программистов OpenGL;

    Напоследок несколько видео с примером работы движка:




    Спасибо за внимание!
    Поделиться публикацией
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 15
    • +1
      Круто! Зря я отложил в долгий ящик работу с SDL+OpenGL, сейчас бы поучаствовал в разработке…
      • +3
        Спасибо! Я сам не сразу за эту связку взялся. До этого и вин апи пробовал и glut и другие прослойки к OpenGL. В принципе при знании Си и основ OpenGL связку SDL+OpenGL несложно освоить даже на ходу.
      • 0
        Никак не пойму, а где здесь C++? И «красное-черные деревья» Вы судя по статье сами реализовывали, когда есть std::map с практически канонической реализацией на rb-tree.
        • +3
          Никак не пойму, а где здесь C++?
          Можно уточнить — это к тому, что примеры кода на чистом Си, или к тому, что не рассмотрены особенности языка С++ на конкретных примерах? Выбор C++ обоснован тем, что весь проект написан на C++, однако большая часть кода написана в стиле Си. Если дело в отсутствии текста об особенностях языка, то спасибо за замечание, буду аккуратнее относиться к выбору хабов.
          По поводу std::map: думал что реализация основана на хеш таблицах (видно что-то левое прочел по этому поводу) — спасибо за информацию, буду знать. Поскольку реализация есть уже своя, то переделывать особого смысла пока не вижу, зато в других проектах скорее воспользуюсь std::map.
          • 0
            Моё внимание привлек тег game development вкупе с C++. Именно представленный код ввел в некоторое заблуждение, потому что например переменные для цикла for объявлены вне тела цикла (хотя современные версии стандарта C вроде разрешают объявление в первом элементе for?) и активное использование elaborated type specifier'ов.
            А на C++ Вы в движке ничего не пишете? Было бы интересно посмотреть :)
        • +2
          Рекомендую посмотреть в сторону Gameplay3d. Неплохая обёртка над opengl & bullet & openal с хорошей поддержкой мобильных девайсов. В своё время перешел на неё после того как понял что мобильный opengl слегка отличается от десктопного :)
          • +2
            Gameplay3d — впервые слышу, надо будет изучить и поковырять исходники, спасибо за инфу. Надеюсь со скриптами там проблем тоже нет.
            • +1
              А чем отличается-то?
              У нас прекрасно один и тот же код работает на десктопе и на мобилках.
              Единственное отличие — на десктопе при загрузке шейдера автоматически в фрагментном шейдере комментируется строка precision mediump float;
              В остальном код идеентичный…
              • +1
                Гм, ну возможно это я просто не так его готовил. Уже точно не помню в чем были отличия, но кажется что-то связанное с тем что в gles2 нет всяких glLoadIdentity, glOrtho, glDrawElements не умеет GL_QUADS, etc.
                • +2
                  Этого всего уже и на десктопе нет. :(
                  Перечисленный вами функционал depricated c 2008 года и доступен в режиме совместимости на OpenGL 3.0. А с 2010 новый OpenGL вообще это все не поддерживает.
            • +1
              В первом видео 1:11 — даже этот небезызвестный прыжок реализовали, респект за внимание к деталям!
              • +1
                а улучшенная графика будет? или планируется полное совпадение с оригиналом?
                • +2
                  Улучшение графики планируется (и похоже для этого придется капитально или вообще с нуля переписывать рендерер), но только после решения основных задач геймплея. Просто как неоднократно показывала практика, наличие исходного кода с прописанным геймплеем практически всегда гарантирует последующее добавление улучшенной графики (например jDOOM, Risen3D, Quake Darkplaces, berserker quake II и т.д.).
                • +1
                  TR1 и 2 одни из самых любимых игр. Перепройдены вдоль и поперёк со всеми возможными секретами и читами. А в вашей версии будет предусмотрен знаменитый corner bug?

                  www.youtube.com/watch?v=xRUQN1vOdEE
                  • 0
                    Понимаю, у меня любимые части 1-ая и 4-ая (т.к. была первой из тех что я играл). С применяемой в данной момент физикой такой баг поблематично реализовать даже специально, т.к. в поекте пименяется физический impulse based движок bullet, который использует реальную геометрию уровня (не самый лучший подход, поскольку для рендеинга могут применяться высокополигональные модели, а физическая модель, как правило, сильно упрощена).
                    В оригинале каждая комната разбита (2d) на т.н. «сектоа», или квадраты (размер 1024х1024 иговые единицы, напимер размер у кубов которые можно толкать по полу и на которые можно влезть равен 1024х1024х1024). Высоты пола / потолка высчитываются с помощью карты высот из т.н. floor_data, уникальных для каждого сектоа. Когда Лара «влезает» в угол, то она попадает в сектор с большой высотой и игра просто «исправляет» текущую координату высоты Лары так, чтобы она стояла на полу, а не под полом.

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