Search
Write a publication
Pull to refresh
249
0
Денис Ольшин @deNULL

Пользователь

Send message

Генератор подземелий на основе узлов графа

Reading time11 min
Views29K
image

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

Введение


Алгоритм был написан как часть работы на получение степени бакалавра и основан на статье Ma et al (2014). Целью работы было ускорение алгоритма и дополнение его новыми функциями. Я вполне доволен результатом, потому что мы сделали алгоритм достаточно быстрым, чтобы использовать его во время выполнения игры. После завершения бакалаврской работы мы решили превратить её в статью и отправить на конференцию Game-ON 2018.

Алгоритм


Для создания уровня игры алгоритм получает в качестве входных данных набор полигональных строительных блоков и граф связности уровня (топологию уровня). Узлы графа обозначают комнаты, а рёбра определяют связи между ними. Цель алгоритма — назначить каждому узлу графа форму и расположение комнаты таким образом, чтобы никакие две формы комнат не пересекались, и каждая пара соседних комнат могла соединяться дверьми.

JS-битва: как я написал свой eval()

Reading time21 min
Views17K
Вы можете помнить Александра Коротаева по браузерной версии «Героев Меча и Магии»: расшифровка его доклада о ней собрала на Хабре громадное количество просмотров. А теперь он сделал игру, ориентированную на программистов: играть в неё надо JS-кодом.

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



В итоге Александр снова сделал доклад на HolyJS, а мы (организаторы конференции) снова подготовили для Хабра текстовую версию.
Читать дальше →

Создаём эффект распространения цвета в Unity

Reading time8 min
Views12K

На этот эффект меня вдохновил эпизод Powerpuff Girls. Я хотела создать эффект распространения цвета в чёрно-белом мире, но реализовать его в координатах мирового пространства, чтобы видеть, как цвет закрашивает объекты, а не просто плоско распределяется по экрану, как в мультике.

Эффект я создала в новом Lightweight Rendering Pipeline движка Unity, встроенном примере конвейера Scriptable Rendering Pipeline. Все концепции применимы и к другим конвейерам, но некоторые встроенные функции или матрицы могут иметь другие названия. Также я воспользовалась новым стеком постобработки, но в туториале опущу подробное описание его настройки, потому что о ней достаточно хорошо рассказывается в других руководствах, например в этом видео.
Читать дальше →

Оптимизация графики. Интересный Concave Hull

Reading time4 min
Views10K
В один прекрасный момент, в ходе разработки игры, я столкнулся с вопросом производительности на современных ПК. У нашего моделлера достаточно мощный современный компьютер красной сборки. Но у него наш проект жутко тормозил, загружая одно ядро процессора.

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



На средней игровой карте, при максимальном отдалении и при большом скоплении пальм — 15 824 756 треугольников! Почти 16 миллионов! Огромная цифра.
Читать дальше →

Разработка hexapod с нуля (часть 3) — кинематика

Reading time6 min
Views20K

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

Этапы разработки:
Часть 1 — проектирование
Часть 2 — сборка
Часть 3 — кинематика
Часть 4 — математика траекторий и последовательности
Часть 5 — электроника
Часть 6 — переход на 3D печать
Часть 7 — новый корпус, прикладное ПО и протоколы общения
Часть 8 — улучшенная математика передвижения
Часть 9 — завершение версии 1.00
Читать дальше →

NLP. Основы. Техники. Саморазвитие. Часть 1

Reading time12 min
Views78K

Привет! Меня зовут Иван Смуров, и я возглавляю группу исследований в области NLP в компании ABBYY. О том, чем занимается наша группа, можно почитать здесь. Недавно я читал лекцию про Natural Language Processing (NLP) в Школе глубокого обучения – это кружок при Физтех-школе прикладной математики и информатики МФТИ для старшеклассников, интересующихся программированием и математикой. Возможно, тезисы моей лекции кому-то пригодятся, поэтому поделюсь ими с Хабром.

Поскольку за один раз все объять не получится, разделим статью на две части. Сегодня я расскажу о том, как нейросети (или глубокое обучение) используются в NLP. Во второй части статьи мы сконцентрируемся на одной из самых распространенных задач NLP — задаче извлечения именованных сущностей (Named-entity recognition, NER) и разберем подробно архитектуры ее решений.


Читать дальше →

Mkcert: валидные HTTPS-сертификаты для localhost

Reading time2 min
Views99K

В наше время использование HTTPS становится обязательным для всех сайтов и веб-приложений. Но в процессе разработки возникает проблема корректного тестирования. Естественно, Let’s Encrypt и другие CA не выдают сертификаты для localhost.

Традиционно есть два решения.
Читать дальше →

Создание игровых 3D-моделей «для бедных»: путь инди

Reading time13 min
Views47K
Вы когда-нибудь задумывались о том, как работает небольшая инди-студия, занимающаяся разработкой видеоигр?

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

Мы — небольшая команда из Польши. Нас всего три человека, но полный рабочий день занимаются проектом всего двое.


Сегодня мы расскажем о процессе создания персонажей для нашей игры «The end of the Sun». Имейте в виду, что показанные в статье скриншоты взяты из проекта, который пока находится в разработке.

Этот текст посвящён только статичным элементам персонажей: мы расскажем, как сканировали персонажа и одежду, как создавались дополнительные элементы, а также о том, как мы настроили движок Unity, чтобы получить такие скриншоты:
Читать дальше →

История 13 места на Highload Cup 2017

Reading time13 min
Views18K

Image


11 августа компания Mail.Ru Объявила об очередном конкурсе HighloadCup для системных программистов backend-разработчиков.


Вкратце задача стояла следующим образом: докер, 4 ядра, 4Гб памяти, 10Гб HDD, набор api, и нужно ответить на запросы за наименьшее количество времени. Язык и стек технологий неограничен. В качестве тестирующей системы выступал яндекс-танк с движком phantom.


О том, как в таких условиях добраться до 13 места в финале, и будет эта статья.

Читать дальше →

Играем в Mortal Kombat с помощью TensorFlow.js

Reading time18 min
Views19K
Экспериментируя с улучшениями для модели прогнозирования Guess.js, я стал присматриваться к глубокому обучению: к рекуррентным нейронным сетям (RNN), в частности, LSTM из-за их «необоснованной эффективности» в той области, где работает Guess.js. В то же время я начал играться с свёрточными нейросетями (CNN), которые тоже часто используются для временных рядов. CNN обычно используют для классификации, распознавания и обнаружения изображений.


Управление MK.js с помощью TensorFlow.js

Исходный код для этой статьи и МК.js лежат у меня на GitHub. Я не выложил набор данных для обучения, но можете собрать свои собственные и обучить модель, как описано ниже!
Читать дальше →

Под капотом Graveyard Keeper: Как реализованы графические эффекты

Reading time5 min
Views57K
Всем привет! Целых 4 года я не писал на Хабр. Последняя моя серия постов была о различных инструментах и приемах, которые мы применяли на нашей прошлой игре (разрабатывая ее на Unity). С тех пор игру ту мы благополучно выпустили, а также выпустили и новую. Так что теперь можно немного выдохнуть и написать несколько новых статей, которые могут быть кому-то полезны.


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

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

Для начала, кратко перечислю из чего собирается картинка в нашей игре:
Читать дальше →

Тридцать шесть градусов красоты

Reading time11 min
Views17K
Сеточные системы координат, в которых плоскость делится на одинаковые симметричные элементы — на квадраты, треугольники, шестиугольники, достаточно известны. Им соответствуют квадратная, треугольная, шестиугольная симметрия. Но еще существует симметрия десятиугольная.

В ней плоскость не делится на десятиугольники, вместо этого все линии расположены под углами кратными 36°. Координаты в этой системе можно записывать целыми числами, по два целых числа на горизонтальное и вертикальное направление.



Расскажу как это нарисовать.
Читать дальше →

Рендеринг воды в экранном пространстве

Reading time14 min
Views9K
image

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

Мне не очень нравится подход с voxelized / marching cubes при рендеринге воды (см. например, рендеринг симуляции жидкости в Blender). Когда объём воды находится в том же масштабе, что и используемая для рендеринга сетка, движение получается заметно дискретным. Эту проблему можно решить, увеличив разрешение сетки, но для тонких струй на относительно длинные расстояния в реальном времени это просто непрактично, потому что сильно влияет на время выполнения и занимаемую память. (Есть прецедент использования разреженных воксельных структур, улучшающий ситуацию. Но я не уверен, насколько хорошо это работает для динамических систем. Кроме того, это это не тот уровень сложности, с которым я бы хотел работать.)

Первой альтернативой, которую я исследовал, были меши экранного пространства Мюллера (Müller’s Screen Space Meshes). В них используется рендеринг частиц воды в буфер глубин, его сглаживание, распознавание соединённых фрагментов похожей глубины и построение из результата меша с помощью marching squares. Сегодня этот способ, вероятно, уже стал более применимым, чем в 2007 году (поскольку теперь мы можем создавать меш в compute-шейдере), но он всё равно связан с бОльшим уровнем сложности и затрат, чем бы мне хотелось.

В конце концов я нашёл презентацию Саймона Грина с GDC 2010 «Screen Space Fluid Rendering For Games». Она начинается точно так же, как и Screen Space Meshes: с рендеринга частиц в буфер глубин и его сглаживания. Но вместо построения меша получившийся буфер используется для затенения и композитинга жидкости в основной сцене (с помощью записи глубины явным образом.) Именно такую систему я и решил реализовать.
Читать дальше →

Введение в программирование шейдеров для верстальщиков

Reading time18 min
Views34K


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


Все это побудило создать введение в те аспекты работы с шейдерами, которые наиболее вероятно пригодятся в работе именно верстальщику для создания различных 2d-эффектов с картинками на сайте. Конечно с поправкой на то, что сами по себе в дизайне интерфейсов они у нас применяются относительно редко. Мы сделаем стартовый шаблон на чистом JS без сторонних библиотек и рассмотрим идеи создания некоторых популярных эффектов, основанных на сдвиге пикселей, которые сложно сделать на SVG, но при этом они легко реализуются с помощью шейдеров.

Обзор техник реализации игрового ИИ

Reading time55 min
Views61K
image

Введение


Эта статья познакомит вас с широким диапазоном концепций искусственного интеллекта в играх («игрового ИИ»), чтобы вы понимали, какие инструменты можно использовать для решения задач ИИ, как они работают совместно и с чего можно начать их реализацию в выбранном движке.

Я буду предполагать, что вы знакомы с видеоиграми, немного разбираетесь в таких математических концепциях, как геометрия, тригонометрия и т.д. Большинство примеров кода будет записано псевдокодом, поэтому вам не потребуется знание какого-то конкретного языка.

Что же такое «игровой ИИ»?


Игровой ИИ в основном занимается выбором действий сущности в зависимости от текущих условий. В традиционной литературе по ИИ называет это управлением "интеллектуальными агентами". Агентом обычно является персонаж игры, но это может быть и машина, робот или даже нечто более абстрактное — целая группа сущностей, страна или цивилизация. В любом случае это объект, следящий за своим окружением, принимающий на основании него решения и действующий в соответствии с этими решениями. Иногда это называют циклом «восприятие-мышление-действие» (Sense/Think/Act):

  • Восприятие: агент распознаёт — или ему сообщают — информацию об окружении, которая может влиять на его поведение (например, находящиеся поблизости опасности, собираемые предметы, важные точки и так далее)
  • Мышление: агент принимает решение о том, как поступить в ответ (например, решает, достаточно ли безопасно собрать предметы, стоит ли ему сражаться или лучше сначала спрятаться)
  • Действие: агент выполняет действия для реализации своих решений (например, начинает двигаться по маршруту к врагу или к предмету, и так далее)
  • … затем из-за действий персонажей ситуация изменяется, поэтому цикл должен повториться с новыми данными.
Читать дальше →

Создание ИИ методом «глокой куздры». Интеллектуальная одиссея

Reading time33 min
Views18K
Захотелось мне написать разговаривающую программу. Очень захотелось, позарез.

Конечно, мне далеко до профессиональных программистов, и лингвистом я тоже не являюсь, но системное мышление имеется, и чувство языка на месте. Тем более что тематикой ИИ давно интересуюсь, даже пару-тройку постов накатал в свое время. Отчего не реализовать познания в программном коде? Ну и попробовал, насколько смог.

Знакомьтесь, Ваня Разумный.


Ниже находится описание проблем, возникших передо мной на этом хоженом-перехоженом пути, и способов их преодоления.

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

Внимание, материал объемный.
Читать дальше →

5 приемов работы с CSS, о которых вам следует знать

Reading time6 min
Views46K


Наблюдая за потоком вопросов по CSS на Тостере уже давно заметил, что многие из них повторяются много-много раз. Да, есть совсем глупые вопросы, на которые так и тянет ответить RTFM! Но есть и более занятные. Они связаны с не совсем стандартной версткой. Не такой, чтобы глаза на лоб лезли, но и заметно выходящей за рамки условного бутстрапа и традиционных туториалов для новичков. Похожие вопросы довольно сложно загуглить — обычно вся суть в картинке, но и отвечать каждый раз надоедает. В этой статье мы постараемся посмотреть некоторые приемы, охватывающие довольно широкий круг подобных вопросов. Информация в первую очередь адресуется начинающим верстальщикам, но возможно и опытным будет, чем вдохновиться.

Как устроены технические индикаторы на фондовых рынках

Reading time5 min
Views25K
Любой кто когда-нибудь интересовался фондовыми или криптовалютными рынками видел эти дополнительные линии. И вы наверно слышали мнения от матерых трейдеров о том, что они не работают и как они не используют ничего. Но многим они очень помогают и мой торговый терминал, в который я лениво смотрю раз в день, выглядит примерно как на картинке ниже.

Как же все таки они устроены? И кому это может быть полезно? Вам определенно с этим следует ознакомиться, если:

  1. Вы ими пользуетесь в своей торговле
  2. Вы планируете написать торгового робота
  3. Вы хотите реализовать торговую стратегию сами

технические индикаторы
Читать дальше →

Создание следов на снегу в Unreal Engine 4

Reading time12 min
Views27K

Если вы играете в современные AAA-игры, то могли заметить тенденцию использования покрытых снегом ландшафтов. Например, они есть в Horizon Zero Dawn, Rise of the Tomb Raider и God of War. Во всех этих играх у снега есть важная особенность: на нём можно оставлять следы!

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

В этом туториале вы научитесь следующему:

  • Создавать следы с помощью захвата сцены для маскировки объектов, близких к земле
  • Использовать маску с материалом ландшафта, чтобы создавать деформируемый снег
  • Для оптимизации отображать следы на снегу только рядом с игроком
Читать дальше →

Бесконечный узор на основе простых чисел

Reading time1 min
Views26K
image

Привет, Хабр! Однажды утром мне пришла в голову идея находить "исключающее ИЛИ" между координатами точки пространства и проверять полученное число на простоту. Результат такого простого алгоритма вы можете видеть на картинке. Подробнее под катом.

Information

Rating
Does not participate
Location
Саратов, Саратовская обл., Россия
Registered
Activity