As I wrote a cross-platform 3d game engine

    Greetings Habr! Many of us probably thought, "Wouldn’t I write the game myself." Now I’m running the “Open tomb” project - an attempt to create a portable engine for playing in the first 5 parts of “Tomb raider”, which is available at sourceforge.com, however, judging from my own experience, many people will be interested in the story with some details about how the engine It was written from scratch and with virtually no knowledge in this area. Even now, many knowledge is not enough, and sometimes there is simply not enough motivation to do something better or more correctly, but it’s better to go on to how the project came to life step by step.

    What prompted me to write the engine

    The story began a long time ago and with the fact that I wanted to play the wonderful logic puzzle "Pusher" on Vista 64. However, the original game was 16 bit and completely refused to start. Nothing better than writing a clone in C, I didn’t come up with (sometimes not the best solution initially leads to more useful results). After a short time, I implemented the game on the SDL v1.2 + OpenGL platform .

    image

    For the convenience of map transfer, I added a level editor and manually cloned all 64 cards. After some time, interest in “Pusher” waned, and I already wanted to drive in a Tomb raider1 with 3dfx graphics. And as many have already guessed, the existing solutions to do this did not really please me (rather, even subjectively), and I started looking for ports. In addition to the famous Open raider project, I did not find anything. I still remember how I was tormented with building it under windows using the mingw compiler (I don’t remember the development environment, either code :: blocks or netbeans ). The build result did not please me at all: loading the level for about a minute and a black screen in the end. I did not have the ability to pick someone else's code, understand its structure and the meaning of functions. Attempts to put together "better" have stopped. However, I got the idea to assemble at least one of the open engines manually, not by auto-config Die GNU Autotools, but with a self-assembled designer in the development environment.

    Thus, after a lot of time behind the monitor, a certain amount of mat, etc., I put together Quake Tenebrae without sound. But he worked! It was a small victory that paid off: I began to better understand other people's code and finally began to understand at least something in the organization of the compiler - without which it is impossible at all. After that, several minor improvements were made, some bugs were fixed and the sound was started, but the project was not uploaded to the Internet (even then it was obsolete, especially considering the presence of Dark places engine ). However, from the Quake Tenebrae engine codeI learned how the work of the game as a whole, its individual components and the memory manager is organized (I added the realloc function to it , albeit quite simple, but everything worked without crashes).

    Writing an engine

    When I got a little accustomed, I decided to start writing my engine from scratch. Just for fun and self-development. The basis for creating the engine was the following: GCC-TDM v4.X.X + msys compiler and Netbeans development environment ; libraries: SDL v1.2 + OpenGL . The first function implemented was to take a screenshot and save it to a * .bmp file using a self-written library to work with this format. Which engine can do without a console for entering command cheats and displaying text is probably none, so the next thing I studied was how to display text in an OpenGL window and chose the freetype 1 + gltt bunch. The first recognizable command was the exit command, and after that the command to play with font sizes, lines, etc ... For reference: I liked the code used in Quake I for parsing strings and breaking it into tokens sequentially, which is still present in the engine:

    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;
    } 


    Jumping ahead: when support for scripts was required, I decided to use the approach to developing the engine as in ID software using the DOOM 3 engine as an example, which was very well described here in Habré =) (I would like to once again thank the authors for the article, translation and people who wrote interesting comments on it). Impressed by the article, I decided to implement LUA in my engine not only for in-game scripting needs, but also for parsing configuration files and console commands (i.e., a uniform system is used everywhere). The approach paid off absolutely.

    Let's move on to 3d

    I was lucky that at the institute I liked linear algebra, matrix transformations, vectors and numerical methods. Without these basics, it’s very reckless to start programming the engine from scratch (unless in order to study these sections with examples, however, without a certain theoretical knowledge base, this will be little realistic). The book of A. Boreskov helped me a lot in mastering the graphics ."Graphics of a three-dimensional computer game based on OPENGL." I re-read it more than once (to familiarize myself with the mathematical apparatus, types of renderers, and the structure of the engines). Without a concept of the principle of constructing the scene and the purpose of the species matrix and the projection matrix, progress will not be possible. After studying some material on the Internet and just literature, I decided to do a portal renderer. The first thing that was implemented in the engine was a freely flying camera and several portals that could only be seen through each other.

    After the hardcode, a wireframe scene of 3 rooms was added (two more and a corridor). But is it really interesting to fly in such a primitive world ... And then I decided to use the resource loader from Open raiderand render levels. The result pleased me and it was finally decided to implement the plan to create a port for playing Tomb raider , at least in the first part. To position objects in space, I used an OpenGL matrix, since this allows you to access the basic vectors of the local coordinate system of the object, set the position of the object with one command glMultMatrixf (transform), and set the orientation of the object in the physical engine bullet with one setFromOpenGLMatrix (transform) command , about which a little bit later. Below is an image with the OpenGL matrix structure from the link above:

    image

    To maintain a history of changes in the engine and the possibility of backup and just for self-development, it was decided to use the mercurial version control system . Its application allowed not only to track the progress in writing code, but also made it possible to upload the results to sourceforge.com. It should be noted that when information about portals from real maps began to be loaded into the engine, a huge number of shortcomings of my implementation of the portal system surfaced. It took a lot of time to deal with disappearing objects and crashes, and even now I believe that the portal module needs serious revision. Now the engine's renderer, depending on the position of the camera and its orientation, starts passing through the portals of the rooms and adds only visible rooms to the list. Then the renderer draws the rooms and their contents from the list. It is clear that for large open spaces this approach is not the most successful, but for the purposes of the project it is quite enough. Here is an example of a recursive room traversal function:

    **
     * 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; iportal_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;
    }


    Skeletal animated models

    And so began one of the most painstaking work in the project. Rendering static rooms with static objects was relatively easy, but when it came to animated skeleton models ... The first thing I realized: the Open raider resource loader does not load all the necessary information about the skeleton model. The number of frames in the animation is not determined correctly, which is why one animation contains frames from several at once.
    While trying to solve these problems, I found various documentation on the format of Tomb raider levels and at the same time the vt project, which had its own resource loader. Although this project did not have loading frames of model animation, it contained more structured code, convenient for reading and bringing to mind. So I replaced the loader in the project with vt . For example: in Open raider, all 5 parts of Tomb raider are loaded with one long function with a bunch of if and switch according to the version number of the game, which greatly complicates reading the code and finding errors. There were 5 modules in vt , each of which was responsible for its version of the level, so that the code was easy to read, and making changes was not difficult.

    The main problem with animations was the extraction of the angles of rotation of the bones in the skeletal model. The fact is that to save space, the corners were stored in bytecode in increments of 2-4 bytes. The first 2 bytes include a flag on whether there is one turn here and around which axis, or just three corners themselves. In the case of 3 turns, flags and angles are stored in 4 bytes, in the case of one, only 2 bytes are used. Moreover, the angles for all models, animations and frames are stored in one array and the offsets must be calculated. In addition, the headers of the individual frames of the model are still stored in this bytecode, and the confusion with offsets is critical, but now we add that the number of frames is loaded incorrectly (later it turned out that the number of frames is given for “interpolated” animations with a frequency of 30 fps, but really, frames can be stored in a “snapshot” form with fps with factors of 1, 1/2, 1/3 and 1/4). After completing the animation frame loader, skeletal models stopped turning inside out and turned into a mess from distorted polygons! Now we need to “revive” Lara. Below is the code of the function generating the skeletal model, spelling and commented sections of code for debugging are saved:

    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;imesh_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;kmesh_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;kbone_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;ianimation_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;jframes_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;kbone_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;kbone_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;ianimation_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;jnum_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;lnum_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
                        }
                    }
                }
            }
        }
    }


    The publication

    When the skeletal models started working, it was already possible to move on to their leveling and “revive” Lara, which required the presence of physics. To begin with, it was decided to write your own physics engine in order to better familiarize yourself with the topic and then more thoroughly approach the selection of ready-made products. The first thing you need to create a character controller is determining the heights. It was originally written (based on the barycentric algorithm) the function of determining the intersection of a triangle and a ray. After that, basic methods were added, such as determining the intersection of moving segments, a triangle and a sphere, a triangle and a triangle. It should be noted that this approach eliminates the possibility of the appearance of the so-called “tunnel effect” (when, due to the high speed, objects with high speeds can fly through each other without a collision), which is inherent in impulse based physical engines.

    And so Lara runs through the levels, even though passing all the steps of any size, but she doesn’t fall out of the map! When the project was in this state, Anatoly Lwmte wrote to me that it’s cool that at least someone is interested in the first parts of Tomb raider. Thus began the correspondence, thanks to which interest in the project began to reappear. After I registered at tombraiderforums.com (Anatoly has been there for quite some time, with his project to improve the engine of the fourth part of Tomb raider ). Thanks to him, a topic with my engine and many improvements in the code appeared on this forum : sound manager, alteration of the state control system (before that I had a switch by animation numbers, now it is by state numbers), etc. The presence of people interested in the project motivates well to develop the project.

    Physics + Renderer Optimization

    Since I used my physics, and even with poor optimization, fps began to sag in some places. By long picking various open-source physics engines, bullet was chosen . The first thing I did was add a collision filter in case of intersecting rooms. The fact is that the design of the original levels allows the intersection of 2 or more completely different rooms in one place, while the objects of one room should not affect the objects of another in any way; similarly with rendering. Currently, I am trying to bring to mind the character’s controller: to eliminate the possibility of passing through walls (occurs in a number of animations point-blank to the wall) and to complete the reaction and behavior of the character in case of clipping on the walls and ceiling.

    Back to OpenGL. Initially, in the engine, polygons were drawn using glVertex3fv (...), etc .; One thing can be said about the performance of this approach and the speed of the engine: there are none. Therefore, after studying the part related to VBO (Vertex Buffer Object), I made an optimization and began to store the data of the vertices of the polygons in the video memory as much as possible and draw the mesh in one go. The speed has increased markedly. However, due to the fact that for one mesh textures could lie in different arrays of pixels, switching OpenGL textures was more often than necessary, and the fact that the textures of many different objects could be stored in one array of pixels created “artifacts” when anti-aliasing was turned on. Cochrane with tombraiderforums.comtook up the optimization of the renderer and wrote a texture atlas with borders between textures. Thanks to this innovation, all level textures are stored in 1–2 OpenGL textures and smoothing does not lead to the appearance of “artifacts”. In addition, he made a project port on MacOS.

    When there were no ideas what and how to tackle the engine, I just looked for errors in the code, corrected its structure or changed the connected libraries. Thus, a “relocation” was carried out from SDL1 to SDL2 , from freetype1 + gltt to freetype2 + ftgl . Similarly, I came up with the idea of ​​adding anti-aliasing to animations using slerp spherical interpolation. Here I want to add: be careful about mathematical algorithms, especially when it comes to “arches” (asin, acos, atan ...) - losing a sign is fraught with killer frames with a skewed and twisted skeleton. I advise you to look at the implementation of slerp in the source code of bullet. After adding anti-aliasing, I could no longer look at non-anti-aliased animations. Further, there was a need to load and play sound, and then to run through the levels in deathly silence is not very, though Tomb raider .

    Add sound

    To use sound, using SDLAudio + SDLMixer is completely insufficient, and getting into audio stream conversion algorithms and making bikes to create effects is a bad idea. After consulting with Anatoly, it was decided to use OpenAL . Since I was guided by the fact that as much as possible platform-specific code was transferred to SDL , I did not come up with anything better than writing SDL_backend for OpenAL . However, it worked, I added the tool to the engine, and Anatoly made everyone play when necessary, where necessary and with the desired effects.

    And now it's time to revive all kinds of levers, traps and other triggers of the game world. In fact, the development here went according to the logic: I need to implement something, what tools are needed for this, how to implement them. The main function used for scripts is to get a pointer to an object by a numerical id, then any LUA function will be able to process all the necessary objects. To dynamically add and remove objects and the ability to quickly access them by id, I used red-black trees . In theory, you could use the hash of the table , but personal preferences have probably worked out here.
    As a result, now the scripting system allows you to carry out almost any manipulations with objects and animations, create tasks (and timers based on them), select objects, press growls and buttons, thereby opening and closing doors and more. Thanks to the efforts of people from the tombraiderforums.com community, a gameflow_manager was added that is responsible for moving from one level to another, loading the necessary scripts and screen savers, loading information about light sources and implementing a simple lightmap based on vertex color adjustment and a cmake script for building under OS Lunux .

    Afterword

    In the end, I want to draw attention to the fact that when you use third-party resources, it’s easier with tests and you don’t have to burden with creating content, however this imposes restrictions on the architecture of the engine or leads to the need to convert formats at boot time so as not to make terrible crutches inside game engine. And there are a lot of crutches in the original Tomb raider .

    Further plans in the project are simple:

    1) fix existing bugs, especially with physics, and expand the capabilities of the character controller;
    2) “revive” the enemies on the maps, add AI and weapons;
    3) expand the animation control system of skeletal models for switching meshes;
    4) expand the capabilities of the scripting system and write key level scripts so that you can go through the normal game;
    5) improve the graphics in the game, add effects, but here I am counting on the help of more qualified OpenGL programmers;

    Finally, a few videos with an example of the engine:




    Thanks for attention!

    Also popular now: