Pull to refresh
-20
0

User

Send message

Деревья квадрантов и распознавание коллизий

Reading time 13 min
Views 25K
image

Эта неделя была короткой, в понедельник и вторник я продолжал работать над системой 2D-освещения. Остальное время я потратил на реализацию деревьев квадрантов (quadtree).

В этой статье я поделюсь своей реализацией и мыслями, возникшими в процессе её проектирования.

Во-первых, мне нужно сказать, почему я решил реализовать дерево квадрантов.

Quadtree — это структура данных разбиения пространства. Её основное преимущество по сравнению с другими структурами данных заключается в адаптивности. Оно обеспечивает хорошую производительность при вставке, удалении и поиске. То есть мы можем использовать это дерево в динамическом контексте, где данные часто меняются. Более того, эту структуру довольно легко понять и реализовать.

Если разбиение пространства для вас новая тема, то рекомендую прочитать эту статью Роберта Нистрома. Если вы хотите более подробно узнать о деревьях квадрантов, то прочитайте эту или эту статьи.
Читать дальше →
Total votes 46: ↑46 and ↓0 +46
Comments 7

Как использовать диаграммы Вороного для управления ИИ

Reading time 8 min
Views 14K
image

Какой маршрут будет самым безопасным, где больше всего врагов и где ближайшая аптечка? Все эти часто встречающиеся задачи о пространственных связях можно эффективно решать при помощи математических разбиений под названием «диаграммы Вороного». Из этого поста вы узнаете, как анализировать игровые карты и получать информацию, обеспечивающую реализм и успех искусственного интеллекта.



Пространственные отношения


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

Такие отношения постоянно используются в видеоиграх и могут предоставлять очень полезную информацию ИИ, а также самому игроку.



У Вороного есть ответ


Диаграмма Вороного описывает пространственное отношение между близко расположенными точками или их их ближайшими соседями. Это множество соединённых многоугольников, полученных из точек или локаций. Каждая линия «области» Вороного находится посередине между двумя точками.
Читать дальше →
Total votes 40: ↑40 and ↓0 +40
Comments 8

Генерируем тайловые уровни и прячем квадраты от игрока

Reading time 8 min
Views 18K

Генерация уровней в Unexplored 2


Мы очень гордимся генератором уровней игры Unexplored 2, это программа, отвечающая всем современным требованиям. В посте я расскажу о том, как создаются уровни игры.

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

Имитация «человеческого» дизайна уровней


Генератор уровней разбивает процесс генерации уровня на целое множество управляемых этапов. Он проходит путь от высокоуровневого планирования до низкоуровневой детальной карты уровня. По сути, он сначала создаёт набросок уровня, а затем начинает добавлять детали, пока уровень не станет завершённым и заполненным.
Читать дальше →
Total votes 50: ↑50 and ↓0 +50
Comments 7

Логика сознания. Часть 7. Самоорганизация пространства контекстов

Reading time 26 min
Views 23K

Ранее мы говорили о том, что любая информация имеет как внешнюю форму, так и внутренний смысл. Внешняя форма — это то, что именно мы, например, увидели или услышали. Смысл — это то, какую интерпретацию этому мы дали. И внешняя форма, и смысл могут быть описаниями, составленными из определенных понятий.

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

Правила трактовки зависят от тех сопутствующих обстоятельств, в которых мы пытаемся дать интерпретацию информации. Эти обстоятельства принято называть контекстом, в котором трактуется информация.

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

Был показан механизм кодирования и хранения информации, который позволяет каждой миниколонке коры иметь свою полную копию памяти о всех предыдущих событиях. Наличие собственной полной памяти позволяет каждой миниколонке проверить, насколько ее интерпретация текущей информации согласуется со всем предыдущим опытом. Те контексты в которых трактовка оказывается «похожа» на что-то ранее знакомое составляют набор смыслов, содержащихся в информации.
Total votes 37: ↑35 and ↓2 +33
Comments 37

Как рендерится кадр нового Doom

Reading time 15 min
Views 105K


Выпущенный в 1993 году первый DOOM внёс фундаментальные изменения в разработку игр и механик, он стал мировым хитом и создал новых идолов, таких как Джон Кармак и Джон Ромеро.

Сегодня, 23 года спустя, id Software принадлежит Zenimax, все основатели уже покинули компанию, но это не помешало коллективу id продемонстрировать весь свой талант, выпустив отличную игру.
Читать дальше →
Total votes 156: ↑155 and ↓1 +154
Comments 94

Spatial hashing для самых маленьких

Reading time 5 min
Views 40K


Spatial hashing это простая техника, которая используется в базах данных, физических и графических движках, симуляциях частиц и вообще везде, где нужно быстро что-то найти. Если в кратце, то суть в том, что мы разбиваем пространство с объектами на ячейки и складываем в них объекты. Затем вместо поиска по значению очень быстро ищем по хэшу.

Предположим, что у вас есть несколько объектов и вам нужно узнать нет ли между ними столкновений. Простейшим решением будет посчитать расстояние от каждого объекта до всех остальных объектов. Однако, при таком подходе количество необходимых вычислений растёт слишком быстро. Если на десятке объектов приходится делать сотню проверок, то на сотне объектов выходит уже десяток тысяч проверок. Это и есть печально известная квадратичная сложность алгоритма.
Можно улучшить ситуацию, если...
Total votes 88: ↑82 and ↓6 +76
Comments 21

Представление движений в 3D моделировании: интерполяция, аппроксимация и алгебры Ли

Reading time 14 min
Views 29K
В этой статье мне бы хотелось рассказать об одном интересном математическом приеме, который будучи весьма интересным и полезным мало известен широкому кругу людей, занимающихся компьютерной графикой.

Сколько существует разных способов представить обыкновенный поворот в трехмерном пространстве? Большинство людей, когда-либо занимавшихся 3D-графикой или 3D-моделированием, сходу назовут три основных широко распространенных варианта:

  • Матрица поворота 3x3;
  • Задание поворота через углы Эйлера;
  • Кватернионы.

Люди с богатым опытом добавят сюда почему-то не пользующийся популярностью четвертый пункт:
  • Ось поворота и угол.

Мне бы хотелось рассказать о пятом способе представления вращений, который симпатичен тем, что удобен для параметризации, позволяет эффективно строить полиномиальные аппроксимации этих параметризаций, проводить сферическую интерполяцию, и главное, универсален — с минимальными изменениями он работает для любых видов движений. Если вам когда-либо был нужен метод, который позволял бы легко сделать «аналог slerp, но не для чистых вращений, а для произвольных движений, да еще и с масштабированием», то читайте эту статью.
Читать дальше →
Total votes 54: ↑53 and ↓1 +52
Comments 14

Видео-туториалы запуска вычислительных задач на Python, R, С++, Octave и Blender во FlyElephant

Reading time 1 min
Views 8.6K
Пару недель назад, наша команда выпустила свежий релиз FlyElephant — платформа для ученых, которая предоставляет готовую вычислительную инфраструктуру для проведения расчетов, помогает находить партнеров и совместно работать над проектами, а также управлять всеми данными из одного места.

В качестве вычислительного ресурса сейчас используется облако Azure, а пользователи могут запускать вычислительные задачи, написанные с помощью С++ (с поддержкой OpenMP), R, Python, Octave, Scilab, Java, Julia, OpenFOAM, GROMACS, Blender на серверах с количеством ядер от 1 до 32 и оперативной памятью до 448 ГБ.

Сегодня мы хотим поделиться видео-туториалсами запуска задач во FlyElephant. Под катом вы найдете видео, как запускать вычислительные задачи, написанные с помощью С++, R, Python, Octave и рендерить изображения с помощью Blender, а также промо-код для получения бесплатных дополнительных часов работы ваших задач.
Читать дальше →
Total votes 20: ↑18 and ↓2 +16
Comments 9

Построение диаграмм и графов в Doxygen

Reading time 9 min
Views 59K


Данная статья входит в получившийся цикл статей о системе документирования Doxygen:

  1. Документируем код эффективно при помощи Doxygen
  2. Оформление документации в Doxygen
  3. Построение диаграмм и графов в Doxygen

Она завершает цикл статей о системе документации Doxygen. На этот раз статья посвящена построению различных диаграмм и графов в Doxygen. В ней мы рассмотрим основные их виды, различные способы их настройки и оформления, а также приведём ряд примеров и советов по их использованию.
Читать дальше →
Total votes 23: ↑23 and ↓0 +23
Comments 2

Документируем код эффективно при помощи Doxygen

Reading time 18 min
Views 342K


Данная статья входит в получившийся цикл статей о системе документирования Doxygen:

  1. Документируем код эффективно при помощи Doxygen
  2. Оформление документации в Doxygen
  3. Построение диаграмм и графов в Doxygen

Это первая и основная статья из упомянутого цикла и она представляет собой введение в систему документирования исходных текстов Doxygen, которая на сегодняшний день, по имеющему основания заявлению разработчиков, стала фактически стандартом для документирования программного обеспечения, написанного на языке C++, а также получила пусть и менее широкое распространение и среди ряда других языков.

В этой статье мы сначала познакомимся с самой системой и её возможностями, затем разберёмся с её установкой и базовыми принципами работы, и, наконец, завершим знакомство рассмотрением различных примеров документации, примеров того, как следует документировать те или иные части кода. Словом, познакомимся со всем тем, что позволит вам освоиться и начать работать с этой замечательной системой.
Читать дальше →
Total votes 52: ↑52 and ↓0 +52
Comments 39

Магия Ctrl-C Ctrl-V, или как перестать сохранять картинки и начать жить

Reading time 9 min
Views 40K
image

Одна из немногих стандартных утилит Windows, которой я пользуюсь практически каждый день — это snippingtool, или, попросту говоря, «Ножницы». Свою задачу она выполняет на ура (впрочем, многого от неё я и не требую), а из прочих полезностей можно отметить вставку выделенного региона напрямую в Skype, без необходимости сохранять изображение в файл — достаточно всего лишь нажать Ctrl-V в окне ввода сообщений. Приятно, что название файла в таком случае будет состоять из даты и времени вместо, например, хеша.

Несмотря на то, что в самом Snipping Tool имеется возможность обводить определённые части изображения, порой этого недостаточно:

  • Во-первых, «Ножницы» не умеют обрабатывать комбинацию клавиш Ctrl-Z, т.е. сделать в них Undo не получится, в связи с чем одна-единственная ошибка в редактировании может заставить начать всё с начала
  • Во-вторых, обводить изображение можно только при помощи Pen'а и Highlighter'а, что не очень удобно, когда надо, например, указать на прямоугольную область

Именно по этим причинам я зачастую обращаюсь к mspaint. А вот у него есть обратный недостаток — вставить изображение напрямую из буфера обмена в Skype уже не получится.

В чём же причина такого поведения? Можно ли его исправить? Давайте разберёмся.

Как протекал процесс, и что из этого вышло, читайте под катом.
Читать дальше →
Total votes 59: ↑55 and ↓4 +51
Comments 31

Объединяем Qt и AdMob

Reading time 4 min
Views 9.2K
image
В один момент понадобилось мне интегрировать рекламу в мобильное приложение на Qt и я был сильно удивлен, обнаружив, что решений, в общем-то, и нет. Нет, есть конечно, V-Play AdMob плагин, но вы меня извините, 160 баксов за то, что можно сделать за выходные — это чересчур. Последующие поиски привели меня к этой статье на хабре, которая послужила материалом для Android реализации, а в итоге получился небольшой фреймворк, для работы с AdMob рекламой на IOS и Android.
Читать дальше →
Total votes 16: ↑13 and ↓3 +10
Comments 2

Система расширений Qt Creator

Reading time 33 min
Views 81K

Предисловие


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

Введение


Это заметка, в которой я хотел бы немного описать архитектуру и систему расширений среды разработки Qt Creator. Изначально, я предполагал лишь перевести документ Writing-Qt-Cretor-plugins.pdf, но так уж вышло, что развитие Qt Creator не стоит на месте и во первых, данный документ уже не столь актуален (сам устарел, API поменялось, куски кода не полные и часто не работают), а во вторых со времени его написания появлись дополнительные возможности расширения Qt Creator, которые хотелось бы описать.

Тем не менее, не будь этого документа, не было бы и данной заметки: из него я взял очень много, вплоть до структуры поста, при этом постаравшись где-то что-то выкидывая/заменяя/добавляя сделать пост актуальным для последней на текущий момент времени версии Qt Creator 2.4.0.

Кому может быть полезен данный документ? В первую очередь это конечно же Qt-программисты, которые выбрали данную IDE как основную среду разработки.

Кроме того, благодаря продуманной системе расширений Qt Creator, данный материал будет полезен тем, кто собрался создавать собственные средства разработки, но не хотят начинать писать их с чистого листа: человек может отключить все ненужные ему расширения Qt Creator и написать свои собственные, пользуясь при этом готовыми примерами в исходниках Qt Creator.

Итак, что же нас ожидает под катом (жирным отмечены готовые разделы):

  1. Сборка Qt Creator
  2. Первое расширение
  3. Добавление новых меню и пунктов меню
  4. Архитектура Qt Creator
  5. Добавление нового редактора (Editor)
  6. Добавление боковой навигационной панели
  7. Добавление страницы в диалог настроек
  8. Добавление фильтра в диалог поиска
  9. Добавление нового типа проекта

Напомню, что Qt Creator является кросс-платформенной свободной IDE для работы с фреймворком Qt, разработанной Trolltech (Nokia). Что не мешает сделать из него простой текстовый редактор с подсветкой синтаксиса, простым отключением всех расширений. Внимание, сотни картинок!
Читать дальше →
Total votes 42: ↑42 and ↓0 +42
Comments 25

GammaRay — средство интроспекции Qt-приложений

Reading time 4 min
Views 15K
Фреймворк Qt предоставляет неплохие средства разработки — входящая в него IDE Qt Creator включает дизайнер, отладчик, профайлер и другие удобные вещи. К сожалению, даже со всем этим иногда не очень понятно, почему приложение в данные момент выглядит так, как выглядит: чего-то не видно, что-то выглядит не так, как ожидалось, где-то неподходящий размер шрифта или неверная картинка.

Часть этих проблем может быть решена в Qt Designer, но только часть. Qt Designer имеет несколько существенных недостатков: во-первых, он неверно отображает положение Qt Quick компонентов в случае активного использования Javascript при расчете их координат и размеров, во-вторых в дизайнере мы видим состояние только «пустой» формы, без загруженных в неё данных. В общем, очень не хватает чего-то вроде инструментов разработчика в любом современном браузере: чтобы можно было посмотреть всё дерево компонентов, найти нужный, увидеть его положение относительно других, свойства, поправить на лету что-то, подобрать цвет\шрифт\размер, увидеть какие обработчики повешены на события и т.д.

И такой инструмент в мире Qt появился! Встречайте — GammaRay, средство интроспекции приложений на Qt. GammaRay понимает, что такое Qt, из чего состоит ваше Qt-приложение, как в нём взаимодействую компоненты, как они выглядят, как генерируются и обрабатываются события и т.д. Давайте посмотрим, что умеет GammaRay.


Читать дальше →
Total votes 28: ↑28 and ↓0 +28
Comments 6

Размещай и властвуй! Используем размещающий new для оптимизации кода на C++

Reading time 14 min
Views 46K


Создавая объект за объектом, мы часто не обращаем внимания на такую «мелочь», как динамическое выделение памяти. Наравне с копированием и сериализацией, выделение памяти из кучи через new постепенно сводит на нет преимущества C++ в скорости. Чем интенсивнее мы пользуемся заветным new, тем сложнее становится приложению, поскольку память кончается, фрагментируется и всячески стремится утекать. Эта участь уже постигла удобные, но неявно опасные для производительности контейнеры STL: vector, string, deque, map. Особенно обидно терять скорость на выделении небольших объектов в больших количествах. Но есть способ обработать размещение памяти таких объектов на стеке, при этом скрывая детали реализации в специальный класс данных. В этом нам поможет механизм размещающего new — непревзойденный способ оптимизации приложения, полного частых и мелких выделений памяти из кучи.
Читать дальше →
Total votes 29: ↑23 and ↓6 +17
Comments 31

Введение в дискретно-ориентированные многогранники для задачи определения столкновений

Reading time 5 min
Views 34K


Обнаружение столкновений (collision detection) виртуальных объектов является довольно значимой частью для задач визуализации.
Читать дальше →
Total votes 34: ↑34 and ↓0 +34
Comments 8

Заметки о вращении вектора кватернионом

Reading time 5 min
Views 106K

Структура публикации


  • Получение кватерниона из вектора и величины угла разворота
  • Обратный кватернион
  • Умножение кватернионов
  • Поворот вектора
  • Рысканье, тангаж, крен
  • Серия поворотов


Получение кватерниона из вектора и величины угла разворота


Ещё раз – что такое кватернион? Для разработчика – это прежде всего инструмент, описывающий действие – поворот вокруг оси на заданный угол:

(w, vx, vy, vz),

где v – ось, выраженная вектором;
w – компонента, описывающая поворот (косинус половины угла).
Читать дальше →
Total votes 24: ↑19 and ↓5 +14
Comments 23

10 советов по прототипированию в Sketch

Reading time 4 min
Views 56K


Так как Sketch был создан специально для работы над мобильными и веб-интерфейсами, неудивительно что он стал одним из самых быстрых и гибких инструментов для прототипирования. Эти 10 советов сделают его еще более мощным средством.
Читать дальше →
Total votes 33: ↑31 and ↓2 +29
Comments 15

Сфера из двух треугольников

Reading time 7 min
Views 61K
История этой демки такова: однажды один мой друг сделал для своей игры генератор карт планет и захотел, чтобы созданные таким образом карты показывались в виде вращающейся сферы. Однако, при этом он не хотел использовать 3D-графику, а вместо этого сгенерировал множество кадров с этой самой сферой, повёрнутой на разные углы. Количество используемой памяти было… скажем так, избыточным, ну а скорость генерации кадров (как и качество их исполнения) сильно страдала. Чуть подумав, мне удалось помочь ему оптимизировать этот процесс, но в целом меня не покидало справедливое ощущение того, что это задача для OpenGL, а вовсе не для 2D-графики.

И вот, однажды, когда меня мучила бессонница, я решил попробовать совместить эти два подхода: нарисовать вращающуюся сферу (с натянутой на неё картой планеты) через OpenGL, но при этом оставив её плоской.
Читать дальше →
Total votes 78: ↑75 and ↓3 +72
Comments 66

Объемные планеты в 2D через шейдер

Reading time 7 min
Views 58K
А помните, как вы просили меня про шейдеры написать? Помните? Нет? А вот я помню и даже написал. Милости просим, поговорим о прекрасном.

Сегодня я поведу речь о том, как я делал объемные вращающиеся планеты для нашей игры blast-off. Тоесть они, конечно, совершенно плоские, всего пара треугольников, но выглядят как объемные.



Заинтересовало? Прошу под кат. Картинок прилично.
Читать дальше →
Total votes 77: ↑75 and ↓2 +73
Comments 39

Information

Rating
Does not participate
Location
Россия
Date of birth
Registered
Activity