• Обучаем нейросеть играть в «Змейку» и пишем сервер для соревнований



      • В этот раз выбрана игра «Змейка».
      • Создана библиотека для нейросети на языке Go.
      • Найден принцип обучения, зависимый от «глубины» памяти.
      • Написан сервер для игры между разработчиками.
      Читать дальше →
      • +22
      • 17k
      • 9
    • Модульные боты-муравьи с памятью

      • Translation

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

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

      Я уже реализовал базовую систему конвейера задач на Javascript (потому что это упростило мою жизнь), но мне хотелось чего-то более надёжного и масштабируемого, поэтому этот проект я написал на C++. На это меня сподвиг конкурс по реализации процедурного сада в сабреддите /r/proceduralgeneration (отсюда и соответствующая тема).

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

      Для увеличения сложности я хотел, чтобы акторы сохраняли информацию о предыдущем опыте взаимодействия с миром и использовали знания об этих взаимодействиях в будущих действиях.
      Читать дальше →
      • +53
      • 17.4k
      • 8
    • Алгоритм быстрого и простого объёмного рендеринга

      • Translation

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

      У моего ShaderToy были три основные задачи:

      1. Выполнение в реальном времени
      2. Простота
      3. Физическая корректность (… или типа того)

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

      1. Трассировка лучей непрозрачных объектов. Все объекты являются примитивами с простыми пересечениями с лучами (1 плоскость и 3 сферы)
      2. Для вычисления освещения используется затенение по Фонгу, а в трёх сферических источниках света применется настраиваемый коэффициент затухания света. Лучи теней не требуются, потому что мы освещаем только плоскость.

      Вот как это выглядит:

      ShaderToy screenshot
      Читать дальше →
      • +52
      • 10k
      • 6
    • Рендерим облака на мобильных девайсах

      • Tutorial
      3 года назад художник спросил меня:
      — Слушай, а можно в нашу мобильную игру добавить красивые облачка?
      — Нет, это абсолютно невозможно, у нас постоянно вращается камера, так что билборды будут смотреться очень фальшиво даже если на них добавить карты нормалей, а другие способы…
      *художник погружается в летаргический сон*

      Для меня нет большего удовольствия, чем выяснять, что я был неправ.



      Про фотореалистичный рендеринг облаков написано много статей, но если хочется рисовать облака на смартфоне, приходится придумывать кучу всяких хаков, упрощений и допущений.
      Под катом подробное описание рендеринга облаков на мобильных и много html5 гифок.
      Поехали!
    • Простой шейдер для точечных источников света в тумане

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

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


      Небольшая сцена с космическим кораблём, отрендеренная в тумане при помощи моей техники
      Читать дальше →
      • +11
      • 3.2k
      • 3
    • Реалистичный боевой ИИ для 2D-игры

      • Translation
      image

      Хотя Close Quarters преимущественно является многопользовательской игрой, в ней всё равно должны присутствовать сложные ИИ-боты, чтобы игроки продолжали играть при плохом Интернет-соединении или отсутствии других онлайн-игроков. Кроме того, боты играют важную вспомогательную роль в некоторых режимах игры. Поэтому они должны вести себя правдоподобно и демонстрировать набор сложных поведений, в том числе использование укрытий, применение предметов в подходящее время, обход с флангов, бросание гранат и убегание от них.

      Окружение и ограничения


      Игровое окружение состоит из полигонов. Большинство полигонов блокирует движение, область видимости и стрельбу, однако есть и «низкие» полигоны, только блокирующие движение. Окружение плотно заставлено препятствиями и укрытиями.

      ИИ тоже ограничен несколькими техническими факторами. Самый важный из них: сервер, на котором выполняются боты, когда онлайн находится мало игроков, должен быстро работать на недорогом VPS как минимум при десяти ботах. Кроме того, нагрузка на ЦП должна оставаться достаточно низкой, чтобы можно было выполнять несколько инстансов сервера на одном VPS без превышения лимита ЦП, и не при этом вызвать санкций со стороны поставщика услуг VPS.
      Читать дальше →
      • +40
      • 9.5k
      • 2
    • Реализация эффекта акварели в играх

      • Translation
      image

      Введение


      Когда в январе 2019 года мы начали обсуждать нашу новую игру tint., то сразу решили, что важнейшим элементом будет эффект акварели. Вдохновлённые этой рекламой Bulgari, мы понимали, что реализация рисования акварелью должна соответствовать высокому качеству остальных ресурсов, которые мы планировали создать. Мы обнаружили интересную статью исследователей из Adobe(1). Описанная в ней техника создания акварели выглядела замечательно, а благодаря своей векторной (а не пиксельной) природе она могла работать даже на слабых мобильных устройствах. Наша реализация основана на этом исследовании, мы изменили и/или упростили отдельные его части, потому что наши требования к производительности были другими. tint. — это игра, поэтому кроме самого рисования нам нужно было в одном кадре рендерить всё 3D-окружение и выполнять игровую логику. Также мы стремились к тому, чтобы симуляция выполнялась в реальном времени и игрок сразу видел нарисованное.
      Читать дальше →
      • +18
      • 4.2k
      • 2
    • Усложняем Sci-fi-модели процедурно: что такое Greeble и как его использовать

      • Translation
      image

      Для начала позвольте мне пожаловаться, что «greeble» — ужасное слово, которое нужно изгнать из словаря.

      Ну, сняв камень с души, перейдём к объяснениям. Greeble — это мелкие повторяющиеся детали, добавляемые к модели, чтобы придать ей ощущение масштаба и определённой эстетики. Гриблы стали популярны благодаря классическим научно-фантастическим фильмам, в которых «моделью» часто была физическая скульптура:


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

      Однако вы могли заметить, что представленный выше туториал рассматривает только экструдирование треугольников, в то время как на изображении в начале статьи гриблы квадратные. Мне пришлось настроить меш так, чтобы он был разделён на четырёхугольники, и многие меши часто состоят из полигонов с более чем тремя индексами. Поэтому в этом туториале мы узнаем, как экструдировать полигон с n индексами и применим этот алгоритм ко всему мешу, чтобы создать гриблы. Также мы узнаем пару способов внесения вариаций в алгоритм гриблинга для получения менее однородных результатов.
      Читать дальше →
    • Vertex Wireless VW210: редкий роутер и его внутренний мир

      Лирическое отступление: всё описанное в данной статье производилось исключительно в образовательных целях, цели извлечения материальной выгоды не преследовалось, ни одного котика в процессе (надеюсь) не пострадало. Всё, что здесь описано вы повторяете на свой страх и риск.
      КДПВ курильщика (для тех, у кого дорогой трафик)

      КДПВ курильщика (для тех, у кого дорогой трафик)

      Несколько лет в глухой деревне трудится, не покладая рук, этот неуловимый Джо сетевой промышленности. Выбор пал на него, благодаря поддержке единственно рабочего решения для данной местности, а именно CDMA 450 от местного оператора «Сотел» (аля SkyLink). В отличии от других роутеров/модемов для данного стандарта того времени он единственный позволил добиться устойчивой связи с помощью какой-то матери и направленной антенны. Но вот беда: сайт производителя (а возможно и он сам) исчез с горизонта этих наших интернетов в далёком 2011 году. Осталось лишь пафосное видео на YouTube и упоминания их продуктов у разномастных продавцов и операторов.
      Внимание! Под спойлером много картинок большого размера и с гикпорн содержанием!
    • Как я создавал карты континентов для своей игры

      • Translation
      image

      Часть 1. SVG и системы координат


      До недавнего времени размеры карт в моей игре Dragons Abound были фиксированными и несколько недетерминированными. Я считал их «региональными» — не картами всего мира, но его значительными частями, такими например, как западное побережье США или часть Европы. Меня вполне устраивал этот масштаб, но я хотел немного поэкспериментировать с игрой, чтобы посмотреть, смогу ли я генерировать карты целого мира (или хотя бы большего размера). Но прежде чем я приступлю к этому, давайте немного поговорим о картах фэнтези-миров.

      Мир — это большое пространство. Большинство карт фэнтезийных «миров» даже близко не походят на истинный размер. Возьмём, например, Средиземье, в котором происходит действие «Властелина колец»:


      Хоть и кажется, что на ней запечатлён огромный мир, на самом деле Средиземье создано на основе Европы.
      Читать дальше →
      • +53
      • 30.4k
      • 3
    • Laplace Blur — Можно ли блюрить Лапласом вместо Гаусса, во сколько раз это быстрее, и стоит ли того потеря 1/32 точности

        image

        «Блюр» в простонародье — эффект размытия, в цифровой обработке изображений. Бывает очень эффектен и сам по себе, и как составляющее анимаций интерфейса, или более сложных производных эффектов (bloom/focusBlur/motionBlur). При всем этом честный блюр в лоб довольно медленен. И часто реализации встроенные в целевую платформу оставляют желать лучшего. То скорость печальна, то артефакты режут глаза. Ситуация рождает множество компромиссных реализаций, лучше или хуже подходящих для определенных условий. Оригинальная реализация с хорошим качеством достоверности и высочайшей скоростью, при этом нижайшей зависимостью от аппаратной части ждет вас под катом. Приятного аппетита!
        Читать дальше →
      • Бесшовный Wi-Fi-роуминг: теория на практике

          Разбираемся с технологиями роуминга (Handover, Band steering, IEEE 802.11k, r, v) и проводим пару наглядных экспериментов, демонстрирующих их работу на практике.


          Читать дальше →
        • Learn OpenGL. Урок 4.10 — Инстансинг

          • Translation
          • Tutorial
          OGL3

          Инстансинг


          Представьте, что вы задумали сцену, содержащую огромное количество моделей объектов, причем преимущественно эти модели содержат одинаковые вершинные данные, разнятся только матрицы трансформации, примененные к ним. Например, сцена с травяным полем, где каждая былинка представлена маленькой моделью, составленной буквально из пары треугольников. Конечно же, для достижения нужного эффекта придется отрендерить эту модель не один раз, а тысячу, десять тысяч раз за кадр. Поскольку в каждом листике содержится буквально пара треугольников, то его рендер будет практически мгновенным. Но вот тысячи повторных вызовов функций рендера совокупно очень заметно ударят по производительности.
          Читать дальше →
          • +39
          • 15.2k
          • 4
        • Дейкстра за линейное время

          Приветствую всех и особенно тех кто интересуется задачами дискретной математики и теорией графов.


          Предыстория


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

          Читать дальше →
        • Конкурс по программированию: Торговля

            UPDATE: Объявления для участников.
            UPDATE 2: Промежуточные результаты и объявления.

            Компания Hola вновь объявляет конкурс по программированию! Победителей ожидают призы:

            1. Первое место: 3000 USD.
            2. Второе место: 2000 USD.
            3. Третье место: 1000 USD.
            4. Жюри может присудить по своему усмотрению специальный приз в 400 USD.
            5. Если Вы отправите кому-то ссылку на этот конкурс, поставив наш адрес в CC, и этот человек займёт призовое место, Вы получите половину суммы приза (разумеется, не в ущерб награде победителя). За одного победителя такую награду может получить только один человек — тот, кто отправил ссылку первым.

            Авторы интересных решений будут приглашены на собеседования.



            Правила


            Условия конкурса на английском языке размещены на GitHub. Ниже — перевод на русский язык.
            Читать дальше →
          • Google's Shell Style Guide (на русском)

            • Translation
            • Tutorial

            Предисловие


            Какой Shell использовать


            Bash единственный язык shell скриптов, который разрешается использовать для исполняемых файлов.


            Скрипты должны начинаться с #!/bin/bash с минимальным набором флагов. Используйте set для установки shell опций, что бы вызов вашего скрипта как bash <script_name> не нарушил его функциональности.


            Ограничение всех shell скриптов до bash, дает нам согласованный shell язык, который установлен на всех наших машинах.


            Единственное исключение составляет если вы ограничены условиями того под что вы программируете. Одним из примеров могут стать пакеты Solaris SVR4, для которых требуется использование обычного Bourne shell для любых скриптов.


            Когда использовать Shell


            Shell следует использовать только для небольших утилит или простых скрптов-оберток.


            Хотя shell-скриптинг не является языком разработки, он используется для написания различных утилит во всем Google. Это руководство по стилю является скорее признанием его использования, а не предложением использовать его в широком применении.

            Читать дальше →
          • Modbus-RTU на скриптах

            Аннотация


            Здесь описан способ реализации протокола Modbus-RTU при помощи shell-скрипта и обвязки в виде js-кода. Обсуждаемый метод может быть использован для реализации других потоковых протоколов, где нужно оперировать массивами байт в ограниченном окружении (роутер).



            Идея в трёх строчках


            Для нетерпеливых показываю основную идею:

            printf "\x00\x03\x00\x00\x00\x01\x85\xDB" > $tty
            ( dd if=$tty of=$ans count=256 2> /dev/null ) & /usr/bin/sleep $timeout; kill $!
            echo "[`hexdump -ve '1/1 "%d,"' $ans | sed 's/\(.*\),/\1/'`]"
            
            Читать дальше →
            • +3
            • 21.3k
            • 1
          • Огромные пятна гигантских планет


              Большое красное пятно Юпитера и Земля в масштабе

              Ураганы происходят на Земле постоянно, но только на 4 планетах-гигантах из внешней области Солнечной системы они достигают поистине гигантским масштабов: их длительность измеряется годами (вместо пары недель на Земле), а скорость в них может почти на порядок превосходить скорость в земных ураганах.
              Читать дальше →