Часть первая – историческая.

Введение

Существующие алгоритмы сжатия данных можно разделить на два больших класса – с потерями, и без. Алгоритмы с потерями обычно применяются для сжатия изображений и аудио. Эти алгоритмы позволяют достичь больших степеней сжатия благодаря избирательной потере качества. Однако, по определению, восстановить первоначальные данные из сжатого результата невозможно.
Алгоритмы сжатия без потерь применяются для уменьшения размера данных, и работают таким образом, что возможно восстановить данные в точности такими, какие они были до сжатия. Они применяются в коммуникациях, архиваторах и некоторых алгоритмах сжатии аудио и графической информации. Далее мы рассмотрим только алгоритмы сжатия без потерь.
Основной принцип алгоритмов сжатия базируется на том, что в любом файле, содержащем неслучайные данные, информация частично повторяется. Используя статистические математические модели можно определить вероятность повторения определённой комбинации символов. После этого можно создать коды, обозначающие выбранные фразы, и назначить самым часто повторяющимся фразам самые короткие коды. Для этого используются разные техники, например: энтропийное кодирование, кодирование повторов, и сжатие при помощи словаря. С их помощью 8-битный символ, или целая строка, могут быть заменены всего лишь несколькими битами, устраняя таким образом излишнюю информацию.

Вашему вниманию представляю свой вольный перевод, обещанный г-ном Takezo в его комменте о будущем ИИ в GameDev.

Введение

Прикольно наблюдать за внутриигровой визуализацией, особенно если ты сам ее и создал! Однако, в погоне за этим ярким впечатлением легко забыть, что не нужно визуализировать все подряд.
Ниже вы найдете видео туториал по визуализации геймплея и ИИ, записанный в секретной исследовательской лаборатории AiGameDev.

Как всем известно, 71% поверхности Земли занимает вода. К сожалению или к счастью, корректно изобразить океан умеют единицы. Иван Айвазовский вошел в учебники живописи благодаря одним только морским пейзажам. В компьютерных играх все еще сложнее. Когда-то море в них обозначали скоплением синих пикселей, раскрашенных белыми квадратами пены. Со временем виртуальные моря стали больше похожи на снимки из отпуска, научились качать волну и покрываться рябью, в которой иногда даже отражались очертания парусников. Но они оставались самостоятельной стихией: натолкнувшись на берег, волна превращалась в незамысловатые угловатые полигоны. Настоящий прибой логично взаимодействует с пляжем, увлажняет песок и с шуршанием откатывается назад. Такого правдоподобия удалось добиться только в современных играх. В том числе в нашем Skyforge. И хоть в основные события будут разворачиваться на суше, игроки попадут и на тропические острова, и в шумные порты. Вода будет постоянно рядом. Ее «правильный» облик будет играть большую роль. И воссоздание морской стихии – серьезная математическая задача. Расскажу об этапах ее реализации.

В данной статье я расскажу об алгоритме смешивания текстур, который позволяет привести внешний вид ландшафта ближе к естественному. Этот алгоритм легко может быть использован как в шейдерах 3D игр, так и в 2D играх.

Статья рассчитана на начинающих разработчиков игр.

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

Предположим, что у вас есть несколько объектов и вам нужно узнать нет ли между ними столкновений. Простейшим решением будет посчитать расстояние от каждого объекта до всех остальных объектов. Однако, при таком подходе количество необходимых вычислений растёт слишком быстро. Если на десятке объектов приходится делать сотню проверок, то на сотне объектов выходит уже десяток тысяч проверок. Это и есть печально известная квадратичная сложность алгоритма.

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

Давно хотел сделать демку VSDCT на мобильном телефоне. VSDCT (Virtual Shadow Depth Cubemap Texture) это представление cubemap текстуры, когда вместо 6 отдельных граней используется одна обычная 2D текстура-атлас, в которой исходные грани кубической карты помещены в виде плотно упакованных тайлов. Посмотрим, как сделать тени от точечного источника света, использую эту технику.

Привет, Хабр! Мой сегодняшний пост по программированию графики будет не таким объемным, как предыдущие. Почти в любом сложном деле иногда есть место несерьезному, и сегодня мы будем рендерить котиков. Точнее я хочу рассказать о реализации алгоритма рендеринга меха Shells and Fins (SAF) традиционно для Direct3D 11 и OpenGL 4. За подробностями прошу под кат.

Инди разработчик должен быть безумным. Безумие очень полезно — оно подталкивает на риски, усиливает мотивацию и, как морфий, уменьшает болезненные ощущения от неудач.

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

По крайней мере, таков план.

Но как же именно вам, как разработчику игры, отрендерить такой эффект?

Содержание:

1. Поиск и анализ цветового пространства оптимального для построения выделяющихся объектов на заданном классе изображений
2. Определение доминирующих признаков классификации и разработка математической модели изображений мимики"
3. Синтез оптимального алгоритма распознавания мимики
4. Реализация и апробация алгоритма распознавания мимики
5. Создание тестовой базы данных изображений губ пользователей в различных состояниях для увеличения точности работы системы
6. Поиск оптимальной аудио-системы распознавания речи на базе открытого исходного кода
7. Поиск оптимальной системы аудио распознавания речи с закрытым исходным кодом, но имеющими открытые API, для возможности интеграции
8. Эксперимент интеграции видео расширения в систему аудио-распознавания речи с протоколом испытаний

Вместо введения

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

Цели:

Определить наиболее оптимальную аудио-систему распознавания речи (речевой движок) на базе открытого исходного кода (Open Source), которую можно интегрировать в разрабатываемую систему видео-определения движения губ пользователя.

Задачи:

Определить аудио-системы распознавания речи, которые попадают под понятие общественного достояния. Рассмотреть наиболее известные варианта речевых систем преобразования голоса в текст, для перспектив интеграции видео-модуля в наиболее оптимальную голосовую библиотеку. Сделать выводы целесообразности использования аудио-систем распознавания речи на базе открытого исходного кода под наши цели и задачи.

Введение

Согласно лингвистическим особенностям человеческой речи, дополнительные артикуляционные данные позволяют более точно выявить речь диктора и автоматически разбить звуковую волну на отдельные фрагменты. Также, при общем анализе аудиовизуального голосового сигнала во временной динамике имеется перспектива фиксирования открытых и закрытых слогов, звонких, шипящих, ударных, безударных гласных/согласных и другие речевые единицы. Именно поэтому в задаче высококачественного распознавания речи крайне важно создание библиотеки данных, которые бы могла бы учитывать эти показатели совместно. Данное направление может быть реализовано в том случае, если имеется открытый доступ к языковым единицам. Именно поэтому для решения нашей задачи (реализация видеорасширения для увеличения точности программ распознавания речи) крайне важно рассмотреть аудио-системы распознавания речи с открытым исходным кодом.

Типы лицензий

Большинство современных продуктов имеют два самых распространенных типа лицензий:
• Проприетарный (собственнический) тип, когда продукт является частной собственностью авторов и правообладателей и не удовлетворяющий критериям свободного ПО (наличия открытого программного кода недостаточно). Правообладатель проприетарного ПО сохраняет за собой монополию на его использование, копирование и модификацию, полностью или в существенных моментах. Обычно полуприетарным называют любое несвободное ПО, включая полусвободное.
• Свободные лицензии (open-source software) — программное обеспечение с открытым исходным кодом. Исходный код таких программ доступен для просмотра, изучения и изменения, что позволяет пользователю принять участие в доработке самой открытой программы, использовать код для создания новых программ и исправления в них ошибок — через заимствование исходного кода, если это позволяет совместимость лицензий, или через изучение использованных алгоритмов, структур данных, технологий, методик и интерфейсов (поскольку исходный код может существенно дополнять документацию, а при отсутствии таковой сам служит документацией).

Среди рассматриваемых систем распознавания речи с открытым исходным кодом нам встретились 2 вида сублицензий BSD и GPL. Рассмотрим их более подробно

Adobe объединила усилия с Google для выпуска нового набора шрифтов Asian OpenType, который охватывает китайский, японский и корейский языки, пишет The Next Web. Шрифт Adobe, названный Source Han Sans, — это новый открытый шрифт для гарнитуры Pan-CJK.

Google одновременно выпустил собственную версию этого шрифта под названием Noto Sans CJK как часть плана по созданию своего семейства шрифтов Noto Pan-Unicode. Оба набора шрифтов, разработанные в сотрудничестве, идентичны, за исключением названия. Фактически они послужат 1,5 миллиарда человек — около четверти населения земного шара.

Продолжаем тему процесса создания игры Insomnia, начатую со статьи Как мы перестали бояться Огра и начали делать на нем игру

Об истуканах

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

О жизни

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

Тонкая душевная организация

Для начала общая схема:

Что такое «Инверсная кинематика»?

Задачей инверсной кинематики является поиск такого набора конфигураций сочленений, который обеспечил бы максимально мягкое, быстрое и точное движение к заданным точкам. Однако, множество существующих ныне методов страдают от таких недостатков как высокая вычислительная сложность и неестественность результирующих поз. В этой статье описан новый (вероятно, на момент написания статьи — 2010 г.) эвристический метод под названием «Метод прямого и обратного следования» ( Forward and Backward Reaching Inverse Kinematics, далее просто FABRIK),
FABRIK избегает использования вращений и матриц в пользу непосредственного получения точки на прямой. Благораря этому, дело обходится всего несколькими итерациями, имеет низкую стоимость вычислений и визуально естественную позу в результате. FABRIK так-же без проблем справляется с наложением ограничений а так-же использованием нескольких цепей и/или конечных точек. Именно об этом методе этот пост.

Как совершать ошибки. 2011г

Как следует из названия, в далеком 2011 году мы совершили третью ошибку, выбрав в качестве основы для игрового движка Ogre3D. Третью, потому что первой ошибкой было решение делать игру, а второй — делать ее на своем движке. К счастью, это были те самые ошибки, с которых начинается увлекательная история. Это приключение, в котором мы прошли почти весь путь развития игровых движков, как зародыш проходит все этапы эволюции.
Конечно же, как и все начинающие разработчики, мы слабо представляли себе, что и зачем мы собираемся делать. Нами двигало желание рассказать свою историю, создать свой вымышленный мир, свою вселенную, и на волне популярности ММО, естественным позывом было сделать свою ММО с блекджеком и всем причитающимся. Позыв случился еще в 2010, а к 2011 была готова первая версия диздока. Земля же была безвидна и пуста, и тьма над бездною, и Дух Фоллаута витал над нами.



Мы шли путем проб и ошибок, собирая по пути все косяки и грабли. Как и большинство проектов, мы начали с самого простого. В плане графики (а я буду рассказывать только о графической части) первая версия движка позволяла использовать только диффузную карту и стенсильные тени.

Каждый год 31 декабря David Eppstein публикует обзор препринтов за прошедший год, посвященных структурам данных и алгоритмам, опубликованным на arxiv.org. По ссылкам можно познакомиться с материалами за 2010 и 2011 (мой перевод) годы.

Раздел cs.DS развивается хорошими темпами: в этом году появилось 935 препринтов по алгоритмам и структурам данных, в то время как за 2011 их было 798. Раздел пока не дотягивает до сотни в месяц, хотя в июле (98 препринтов) этот порог был очень близок.

Это мой личный список из десятка препринтов, которые кажутся мне особенно интересными. Как обычно, я не вношу в него мои собственные работы и некоторые другие, о которых я писал раньше. Кроме того, здесь нет результатов (например, более быстрый алгоритм нахождения максимального потока), не появлявшихся на arxiv.org.

Вот они, в хронологическом порядке: