Octree, или Сказ о поиске пути в 3D

Резерв

Доклад принят в программу конференции

Мнение Программного комитета о докладе

Тему "Алгоритмы и структуры данных" часто воспринимают как нудную, сложную и не особо нужную в реальной жизни. В докладе наглядно и интересно рассказано о том, как одна из структур данных (восьмеричные деревья) помогает эффективно решать практическую задачу геймдева — поиска пути в 3D-пространстве.

Целевая аудитория

Доклад будет интересен разработчикам игр и специалистам, интересующимся экономными алгоритмами поиска пути.

Тезисы

Поиск пути в трехмерном пространстве — настоящий вызов для приложения, особенно если к скорости вычисления предъявлены жесткие требования.

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

Обладатель премии «Team Lead — Анархист 2022». Бас-гитарист и Java-программист в одном лице. Более 10 лет в игровом бизнесе в качестве backend-разработчика.

IT Territory

IT Territory — студия разработки игр с 18-летней историей. Создали 17 браузерных и мобильных проектов, в которые играют более 100 миллионов человек по всему миру. Сейчас сфокусированы на мобильном направлении и, являясь студией полного цикла, успешно разрабатывают и продвигают собственные проекты. В портфолио компании такие хиты, как Rush Royale, Hawk: Freedom Squadron, «Эволюция 2», «Легенда: Наследие драконов», «Аллоды Онлайн», Juggernaut Wars и многие другие. IT Territory — команда профессионалов: гейм-дизайнеров, программистов, художников, маркетологов, тестировщиков и многих других. Их уже 250 и всех их объединяет одно — любовь к играм. Входит в MY.GAMES — международную игровую компанию, объединяющую более десятка игровых студий, создающих продукты мирового класса для консолей, PC и мобильных устройств.

Заглянул в мир Java-геймдева из науки и сразу же влюбился в разработку. Более трёх лет занимается поддержкой и разработкой бэкенда таких игр, как «Аллоды Онлайн» и Rush Royale.

IT Territory

IT Territory — студия разработки игр с 18-летней историей. Создали 17 браузерных и мобильных проектов, в которые играют более 100 миллионов человек по всему миру. Сейчас сфокусированы на мобильном направлении и, являясь студией полного цикла, успешно разрабатывают и продвигают собственные проекты. В портфолио компании такие хиты, как Rush Royale, Hawk: Freedom Squadron, «Эволюция 2», «Легенда: Наследие драконов», «Аллоды Онлайн», Juggernaut Wars и многие другие. IT Territory — команда профессионалов: гейм-дизайнеров, программистов, художников, маркетологов, тестировщиков и многих других. Их уже 250 и всех их объединяет одно — любовь к играм. Входит в MY.GAMES — международную игровую компанию, объединяющую более десятка игровых студий, создающих продукты мирового класса для консолей, PC и мобильных устройств.

Видео