Work

Mar. 27th, 2009 02:54 am
   За последние пару недель сделал на работе охуительный pathfinding.

   Поиск пути занимает копейки.
   Вычисления при изменении проходимости занимают в худшем случае порядка миллиона тактов для всей карты, которые размазаны по нескольким фреймам.
   Все алгоритмы целочисленные (=numerically stable, ниибу как это будет по-русски), удобные для кэша проца, памяти щитанные килобайты.
   Как тока игру анонсируют, возможно нопешу подробнее — щас NDA не позволяет.

   Как обычно, сначала для отладки олгаритма на реальных данных нопесал демку под Windows. И как обычно, после портирования от ключевого кода демки осталасть тока половина, остальное перепейсал или поменял в рамках интеграции с остальным кодом игры.
   During the last 2 weeks I've designed & implemented an uber-cool pathfinding algorithm.

   The path finding itself takes few μsecs.
   The pre-calculations required when passability is changed take ~1E6 CPU ticks for the whole map, which are spreaded across several frames.
   All the math is integer (=numerically stable), cache friendly, and the data size is only few kilobytes.
   Maybe I'll post a bit more details about that as soon as the game I'm working on will be officially announced: currently the NDA is shutting me up.

   As usual, my first step was creating a Windows GUI application for a trial of the algorithm on the real data. And as usual, only ~50% of the demo code survived porting to the target platform: the other half had to be rewritten for the integrating into the existing codebase.

July 2017

S M T W T F S
      1
2345678
9101112131415
16171819202122
23242526272829
3031     

Syndicate

RSS Atom

Most Popular Tags

Page Summary

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 20th, 2017 08:13 pm
Powered by Dreamwidth Studios