Monday, January 07, 2008

топологическая сортировка

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

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

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

Допустим есть следующие модули: filesystem, logging, render, audio, scene manager, game

filesystem не зависит ни от какого модуля
logging зависит от filesystem
render -> filesystem, logging
audio -> filesystem, logging
scene manager -> filesystem, logging, render, audio
game -> scene manager, filesystem, logging

Тут мы имеем сложный граф зависимостей. Который не является деревом. Этот граф надо преобразовать в список, проходя по которому можно будет последовательно запустить или остановить модули.
Например вот такой: filesystem -> logging -> audio -> render -> scene manager -> game
Хотя различных списков может быть много.
Также надо как-то проверять наличие циклов в графе зависимостей, иначе построить такой список будет невозможно.

Вообщем, я уже почти сам построил нужный алгоритм, как нашёл у себя в сундуке древний манускрипт, называется он "C++ Boost Graph Library", открыв его я узнал, что моя проблема является довольно тривиальной и очень общей. Мне просто надо пройти граф зависимостей по алгоритму depth first search, а построение списков зависимостей является, так называемой, топологической сортировкой. Ну в принципе я тоже самое и придумал, только не знал как называть.

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

#include    <iostream>
#include    <utility>
#include    <algorithm>
#include    <list>
#include    <vector>
#include    <boost/graph/vector_as_graph.hpp>
#include    <boost/graph/topological_sort.hpp>

using   namespace   boost;
int main()
{
    const char* modules[] = {
        "render",
        "filesystem",     
        "scene manager",
        "game",
        "audio",
        "physics"
    };
    const int nModules = sizeof(modules)/sizeof(char*);

    std::vector<std::list<int> >    modulesGraph(nModules);
    modulesGraph[0].push_back(1); // render -> filesystem

    modulesGraph[2].push_back(0); // scene manager -> render
    modulesGraph[2].push_back(1); // scene manager -> filesystem
    modulesGraph[2].push_back(4); // scene manager -> audio
    modulesGraph[2].push_back(5); // scene manager -> physics

    modulesGraph[3].push_back(2); // game -> scene manager
    modulesGraph[3].push_back(1); // game -> filesystem
    modulesGraph[3].push_back(0); // game -> render

    modulesGraph[4].push_back(1); // audio -> filesystem
    modulesGraph[5].push_back(1); // physics -> filesystem

    std::vector<int>    modulesOrder;
    topological_sort(modulesGraph, std::back_inserter(modulesOrder), vertex_index_map(identity_property_map()));

    for (std::vector<int>::iterator it = modulesOrder.begin(); it != modulesOrder.end(); ++it)
        std::cout << modules[*it] << std::endl;
    return  EXIT_SUCCESS;
}Syhi-подсветка кода


на выходе получим следующее:
filesystem
render
audio
physics
scene manager
game

XNE

Некоторое время назад решил собрать воедино все свои наработки и организовать их в виде рабочего игрового движка.

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

Проект будет кроссплатформенным, но без фанатизма. Пока ориентация только на POSIX и Windows. Графический API - OpenGL. Мультиапи не планируется.

Сейчас мне интересно, в первую очередь, разработка правильной фундаментальной архитектуры. Что такое правильная архитектура? Для меня такая архитектура должна быть простой и расширяемой. Что бы работа с системой не вызывала головной боли.
В качестве основы я взял паттерн microkernel.
Конечно там будут и layers, и subsystems, и pipes и много чего другого. Вообще хочу поэкспериментировать с паттернами. Но это уже будет в деталях. Сейчас пока сконцентрируюсь на построении модульной архитектуры с микроядром.

Так же вплотную займусь организацией проекта. Документация, системы сборки, вспомогательные утилиты, code standart и т.д. Это у меня слабое место. Из-за отсутствии чёткой организации всё никак не могу выпустить свою анимационную библиотеку. Надо практиковаться в этом.

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

Проект будет c открытыми исходниками, лицензия, скорее всего, BSD или другая либеральная. А может быть и GPL. Я пока не определился окончательно.

Называется он XNE, расшифровывается как "XNE is Not Engine". Люблю акронимы :)

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