Octree, или Сказ о поиске пути в 3D
Мнение Программного комитета о докладе
Тему "Алгоритмы и структуры данных" часто воспринимают как нудную, сложную и не особо нужную в реальной жизни. В докладе наглядно и интересно рассказано о том, как одна из структур данных (восьмеричные деревья) помогает эффективно решать практическую задачу геймдева — поиска пути в 3D-пространстве.
Целевая аудитория
Доклад будет интересен разработчикам игр и специалистам, интересующимся экономными алгоритмами поиска пути.
Тезисы
Поиск пути в трехмерном пространстве — настоящий вызов для приложения, особенно если к скорости вычисления предъявлены жесткие требования.
На примере игры "Пираты: штурм небес" мы покажем проблемы, возникающие при использовании традиционных алгоритмов. Одним из способов увеличения скорости поиска является использование октодерева, которое позволяет экономно хранить информацию о коллизиях в мире и грамотно выбирать гранулярность сетки. В рамках доклада мы пройдем путь от идеи использования до конечной реализации в "Пиратах", а на десерт нас ждет несколько оптимизаций, позволяющих еще сильнее ускорить поиск пути.
Спикеры
IT Territory
