GameObject и длииииииииинные асинхронные операции

Хорошо, когда игровой объект писать легко и приятно – простой линейный код радует глаз скриптера. Всё легко, красиво, понятно.


[code lang="cpp"]
// если мы стоим на земле
if ( RayTrace ( Vector3(0,-1,0),2 ) )
PlaySound();
[/code]
Рис.1

Только очень и очень медленно. RayTrace – медленная функция. Хуже, система коллизий хорошо умеет трассировать десятка два лучей сразу. Ещё хуже – система коллизий умеет работать асинхронно (на другой нитке, на SPU, как-то ещё), и возвращать результат тогда, когда он готов.

Аналогично PlaySound тоже не играет звук мгновенно. Объект добавляется в спискок для проигрывания звуков, а потом кто-то где-то его играет.

Одно из типичных решений – сделать из игрового объекта стейт-машину; мелко нарезать, размешать, замучаться отлаживать.

[code lang="cpp"]
...
beginTrace:
result = RayTrace ( Vector3(0,-1,-),2 );
switchToState(waitForResult);
return;
...
waitForResult:
if ( result.IsReady() )
switchToState(continueWorking);
return;
...
[/code]

Если есть удобный и кошерный скрипт (наприме LUA), то можно пользоваться сопрограммами.

Если хочется писать на С++, то забивать гвозди можно fiber-ами. Завести fifo объектов, вызывать fiber-ы пока все не закончат. Тех, кто не закончил, класть в начало fifo. Тех кто закончил больше не обрабатывать. Кстати, примерно так-же GPU от NVIDIA обрабатывает пиксели.

После чего длинные функции переписываются в терминах yield-а, а код остаётся таким-же простым и линейным, как на Рис.1

[code lang="cpp"]
Vector3 RayTrace ( Vector3 dir, float length )
{
result = Physics::RayTrace(dir,length);
while ( !result.IsReady() )
Yield();
return result.value;
}
[/code]

Плохонький пример реализации ниже. Идею, впрочем, он вполне себе иллюстрирует.

[code lang="cpp"]
/// игровой объект
class CGameObject
{
friend class CGameObjectManager;

public:
CGameObject()
: m_fiber(NULL)
, m_isDone(false)
{};

protected:
/// вот эту функцию мы перекрываем
virtual void OnTick() = 0;

/// подождать результата
void Yield();

/// закончили с кадром
void Done() { m_isDone = true; }

private:
CGameObjectManager * m_pManager; ///< менеджер этого объекта
LPVOID m_fiber; ///< его файбер
bool m_isDone; ///< OnTick для данного кадра кончился?
};

/// менеджер игровых объектов
class CGameObjectManager
{
friend class CGameObject;

public:
CGameObjectManager();
~CGameObjectManager();

/// основной игровой цикл
void OnTick();

/// добавить объект в обработку в этом цикле
void PushBack ( CGameObject * pObj );

private:
/// запускаем объект в отдельном fiber-е
static void __stdcall TickGameObject ( LPVOID pObj );

private:
std::list m_mainFifo; ///< FIFO с объектами
LPVOID m_mainFiber; ///< главный fiber
};

void CGameObject::Yield()
{
SwitchToFiber(m_pManager->m_mainFiber);
}

CGameObjectManager::CGameObjectManager()
{
ConvertThreadToFiber(NULL);
m_mainFiber = GetCurrentFiber();
}

CGameObjectManager::~CGameObjectManager()
{
ConvertFiberToThread();
m_mainFiber = NULL;
}

void __stdcall CGameObjectManager::TickGameObject ( LPVOID pObj )
{
CGameObject * pGameObj = (CGameObject *) pObj;
pGameObj->m_isDone = false;
SwitchToFiber(pGameObj->m_pManager->m_mainFiber);

// вот в этом цикле теперь и будет крутиться наш объект
for ( ;; )
{
pGameObj->OnTick();
pGameObj->Done();
pGameObj->Yield();
}
}

void CGameObjectManager::PushBack ( CGameObject * pObj )
{
if ( pObj->m_fiber==NULL )
{
// если объект ещё никто не обрабатывал
// то для него надо сделать fiber
pObj->m_pManager = this;
pObj->m_fiber = CreateFiber ( 65536, CGameObjectManager::TickGameObject, pObj );
SwitchToFiber ( pObj->m_fiber );
}
pObj->m_isDone = false;
m_mainFifo.push_back(pObj);
}

void CGameObjectManager::OnTick()
{
// пока fifo не пустая
while ( m_mainFifo.size() )
{
// вынимаем из fifo
CGameObject * pObj = *m_mainFifo.begin();
m_mainFifo.pop_front();
// обрабатываем
SwitchToFiber(pObj->m_fiber);
// если не закончили, засовываем опять в fifo
if ( !pObj->m_isDone )
m_mainFifo.push_back(pObj);
}
}

//////////////////////////////////////////////////////////////////////////

class CMyObj : public CGameObject
{
private:
int m_id;

public:
CMyObj ( int id ) : m_id(id) {};

virtual void OnTick ()
{
printf ( "%i: begin tick\n", m_id );
printf ( "%i: try 1\n", m_id );
int res = SomeLongRoutine();
if ( res>50 )
{
printf ( "%i: try 2\n", m_id );
res = SomeLongRoutine();
}
printf ( "%i: res=%i, done\n", m_id, res );
}

int SomeLongRoutine ( void )
{
// здесь мы эмулируем процедуру, которая долго ждёт результата
Yield();
static int value = 13;
value += 117;
int result = value;
Yield();
return result % 100;
}
};

//////////////////////////////////////////////////////////////////////////

int main()
{
std::vector allObjects(5);
for ( int i=0; i<5; i++ )
allObjects[i] = new CMyObj(i);
CGameObjectManager manager;
for ( ;; )
{
printf ( "Game loop\n" );
for ( int i=0; i<5; i++ )
manager.PushBack(allObjects[i]);
manager.OnTick();
printf ( "\n" );
}
return 0;
}
[/code]

Замечу, что наличие стека означает, что большую часть состояния объекта можно (и нужно) хранить на нём. И вместо OnTick делать ещё более длинную функцию, на весь LifeTime объекта. Код высокого уровня (пойти из точки а в точку б, итп) – будет такой-же линейный и простой. Как если-бы объект существовал в единственном экземпляре.

Такой подход предполагает целый ряд (решаемых) сложностей во взаимодействии с другими объектами, но про это я писать не буду :) Выводов тоже не будет.

Ну и, наконец, внятные файберы вполне себе можно реализовать на setjmp\longjmp – если на платформе их почему-то нет. Вполне себе дешевые будут.

P.S. Стек конечно можно и нужно мельче. Пример-то плохонький :)

  • http://aras-p.info Aras Pranckevicius

    +1.

    Though I think it is spelled “yield”, not “yeild”.

  • look4awhile

    I’m illiterate :(

  • IronPeter

    А цена переключения файбера какая? Чисто теоретично – надо сохранить и восстановить все регистры. Как тысячу килобайт переслать, от ста до тысячи тактов. Чисто фича пользовательского режима. Оно syscall в винде делает?

  • IronPeter

    исправление : как килобайт переслать.

  • CEMEH

    Где-то так делали?

    И все-таки, как взаимодействовать с другими объектами? Позвать ему, скажем, функцию, если все его состояние – на стеке?

  • IronPeter

    По крайней мере статьи пейсали: Game Programming Gems 2 – Micro-Threads for Game Object AI.

    На самом деле совсем не очевидно, что для вызова функции необходимо аллоцировать место на стеке. Можно ( чисто теоретически ) взять и сказать malloc на локальный контекст выполнения функции. Делать так по надобности и освобождать контексты по выходе из функций. Если мы заменим stack аллокацию контекста функции на heap аллокацию – то идея сопрограмм станет совсем вопиюще очевидной.

    Впрочем, все stackless языки убоги как-то.

  • http://users.livejournal.com/_zerg/ _zerg

    CEMEH
    First off, EVE is a very very multithreaded application and far more so than most you will encounter. We use Stackless Python to get microthreading abilities within the single process running on each CPU.

    To better clarify that, right now, the EVE cluster is running 110 threads on 110 CPU’s. Within those threads we have 100′s to 1000′s of microthreads running various services.

    http://myeve.eve-online.com/devblog.asp?a=blog&bid=286

  • Balmer

    Кстати, теоретически фиберы должны быть очень дешевы при переключении.
    Даже если системные фиберы дороги,
    (применительно в Visual C++), можно запомнить ebp, esp, eip и переключаться на другой стек.

    А эта идея хороша, особенно если больше двух процессоров в системе. То бишь для XBox 360 она рулить должна.

  • look4awhile

    можно переключаться с setjmp\longjmp. будет очень и очень дешево
    готовые файберы проще – не хотел ещё и этот небольшой кусок писать руками

    stackless не надо. надо пользовать стек для состояния объекта
    и писать функции на весь лайфтайм объекта

  • Toxe3

    А вот еще вариант, с помощью хака, совместимого со стандартным C:
    http://www.sics.se/~adam/pt/

  • Dmitry Tyurev

    _zerg
    У нас на сервере ММОРПГ крутятся несколько десятков тысяч сопрограмм.

  • http://users.livejournal.com/_zerg/ _zerg

    Dmitry Tyurev
    Я верю, но по еве это то что я смог найти в инете. А что вы за ММОРПГ разрабатываете я, к сожалению, не знаю.

  • dDIMA

    Отличный пост. Линейный код всегда легче отлаживается, чем событийная система вызовов. Если выбросить Yield’ы, всегда можно посмотреть логику развития функции. Впрочем, отмечу несколько, на мой взгляд, важных минусов системы:

    1. Про елды в коде забывать нельзя. Нужно знать особенности реализации чужих подсистем, например, между вызовами RayTrace() и GetIntersectionPoint() нужно напихивать елды. Понятно, что при наличии достаточного количества потоков и елдов результат все равно будет подсчитан, но здоровье программы будет уже не тем, каким могло бы быть :)

    2. Несмотря на кажущуюся линейность, логика переключений – она все равно вшита внутрь системы, поэтому могут возникать интересные коллизии. Например, в том случае, если какая-то подсистема неожиданно сильно увеличила время своих внутренних вычислений и другие процессоры стали обрабатывать очередь запросов, может нарушиться ожидаемый порядок вызовов. Понятно, что на эти порядки завязываться нельзя, но ведь все равно кто-нибудь да завяжется :). Особенно это критично для “разшареных” подсистем, которых вызывают все, кому ни лень, и которые должны быть тщательно прописаны с соблюдением всех законов программирования параллельных вычислений.

  • eagle

    look4awhile
    У меня дежавю или
    http://www.gamedev.ru/site/forum/?id=10713&page=8
    пост 115
    Все таки кто автор?

  • look4awhile

    2dDIMA:

    про елды можно и нужно забывать. автор системы пишет Yield прям внутрь RayTrace-а. причём не делает дополнительную буферизацию, а уверен – что Yield не пройдёт, и что параметры RayTrace-а всё это время будут лежать на стеку файбера.

    порядок вызовов можно делать эксплиситно, прямо yield-ить пока кто-то не поставит флажок – “эта часть готова”. и синхронизации даже не надо.

    2 eagle:
    автор чего?

  • eagle

    look4awhile
    Идеи

  • http://aruslan.livejournal.com/ aruslan

    eagle
    Какой идеи?
    Там про другие проблемы и, соответственно, другие решения.

    Я люблю coroutines и, в пределе, CSP из-за линейности кода.
    Но категорически не люблю разбросанные там-сям yields, особенно когда они stateful.
    Подход Adam Dunkels (который http://www.sics.se/~adam/pt/) мне сильно ближе в этом смысле.

    А еще ближе таки классический CSP, благо он работает на пять если правильно вструнивать.

  • eagle

    aruslan
    Мне показалось там тоже попытка бороться с нелинейностью кода завязана на fibers,
    а wait по смыслу – тот же yield

  • http://aruslan.livejournal.com/ aruslan

    Ммм, в теории – возможно да. Но оно разные задачи слишком решало.

    Yield не спасает от seek-time и ассоциированных лагов в CreateFile на DVD.
    Именно поэтому в у нас для загрузки, сетки и звука были полноценные потоки, а не fibers.
    Благо что зашаренных данных я удобно избегал благодаря Лёше (LFlip).

    А в yields про которые Боря говорит описаны несимметричные coroutines без устойчивых каналов обмена данными.
    Т.е. Хоаровский CSP (Communicating Sequential Processes) без этого самого Communicating.
    Для игрового кода такое удобно, но тогда уж проще сразу на любом скрипте или том же ЕЗЫГЕ.

    Мы с нелинейностью не боролись потому что она не была проблемой совсем.
    Иногда хотелось странного – и тогда я просил Лёшу сделать Wait с кондишенами.
    Но вообще это просто очень lightweight messaging protocol + нативные потоки с lightweight мониторами, которые не видны программерам – и соотственно лишены тупых deadlock/livelock etc.

    А в игровом коде я вообще предпочитаю видеть опять же простые и ясные Оккамовские/CSP примитивы.
    На coroutines они внутри или нет – в целом всё равно.
    Но благодаря каналам они опять же лишены тупых deadlock/livelock.

    Поэтому если сходство и есть – то только с точностью до CreateFile и ВСЕГО кода, покрытого шанкрами yield/cocall.
    Я же предпочитаю иметь чистый код без шанкров.
    Но это очевидно уже религия.