• Дейкстра за линейное время

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


    Предыстория


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

    Читать дальше →
  • Статический анализ в Go: как мы экономим время при проверке кода


      Привет, Хабр. Меня зовут Сергей Рудаченко, я техлид в компании Roistat. Последние два года наша команда переводит различные части проекта в микросервисы на Go. Они разрабатываются несколькими командами, поэтому нам понадобилось задать жесткую планку качества кода. Для этого мы используем несколько инструментов, в этой статье речь пойдет об одном из них — о статическом анализе.


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


      В статьях по этой теме часто встречается термин «линтер». Для нас это удобное название простых инструментов для статического анализа. Задача линтера — поиск простых ошибок и некорректного оформления.

      Читать дальше →
    • Создание разрушаемых мешей

      • Перевод
      image

      Часть 1. Знакомство с Marching cubes


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

      Вот пример из No Man’s Sky: видео.

      Аналогичная техника применяется для отображения изображений с МРТ, metaball-ов и для вокселизации рельефа.

      В этой части я расскажу о технике создания разрушаемого рельефа Marching Cubes, а в более общем применении — для создания плавного граничного меша твёрдого объекта. В этой статье мы начнём с рассмотрения двухмерной техники, затем трёхмерной, а в третьей части рассмотрим Dual Contouring. Dual Contouring — это более совершенная техника, создающая тот же эффект.
      Читать дальше →
      • +30
      • 9,4k
      • 3
    • Имитация естественного движения: Steering Behaviors — 2

      • Перевод
      Первая часть статьи здесь.


      Часть 6. Избегание коллизий


      Для правильной навигации NPC часто требуется способность избегать препятствий. В этой части мы рассмотрим steering behavior collision avoidance (избегание коллизий), позволяющее персонажам благополучно уворачиваться от препятствий в окружении.



      Введение


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

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


      Анализируются препятствия перед персонажем и выбирается ближайшее (наиболее угрожающее).

      Поведение избежания коллизий — это не алгоритм поиска путей. Оно заставляет персонажей двигаться по окружению, избегая препятствий, постепенно находя путь сквозь блоки — но в случаях с препятствиями в виде L или T, например, оно действует не очень хорошо.
      Читать дальше →
      • +23
      • 5,8k
      • 2
    • Имитация естественного движения: Steering Behaviors

      • Перевод
      image

      Steering behaviors помогают автономным персонажам реалистично двигаться благодаря применению простых сил, сочетание которых создаёт естественно выглядящее и импровизированное движение по окружению. В этом туториале я расскажу об основах теории steering behaviors, а также об их реализации.

      Идеи, на которых построены такие поведения, предложены Крейгом Рейндольдсом; они не основаны на сложных стратегиях с использованием планирования пути или глобальных вычислений, а применяют локальную информацию, например, силы соседних объектов. Благодаря этому они просты в понимании и реализации, но в то же время способны создавать очень сложные паттерны движения.
      Читать дальше →
      • +39
      • 6,4k
      • 7
    • Рендерим облака на мобильных девайсах

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

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



      Про фотореалистичный рендеринг облаков написано много статей, но если хочется рисовать облака на смартфоне, приходится придумывать кучу всяких хаков, упрощений и допущений.
      Под катом подробное описание рендеринга облаков на мобильных и много html5 гифок.
      Поехали!
    • ТАУ для самых маленьких: пример реализации ПИД-регулятора в Unity3D

      • Tutorial

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


      Системы автоматического управления (САУ) предназначены для автоматического изменения одного или нескольких параметров объекта управления с целью установления требуемого режима его работы. САУ обеспечивает поддержание постоянства заданных значений регулируемых параметров или их изменение по заданному закону либо оптимизирует определенные критерии качества управления.

      Читать дальше →
    • Объёмное атмосферное рассеяние света

      • Перевод
      image

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

      GIF

      Статья разбита на следующие части:

      • Часть 1. Объёмное атмосферное рассеяние
      • Часть 2. Теория атмосферного рассеяния
      • Часть 3. Математика рэлеевского рассеяния
      • Часть 4. Путешествие сквозь атмосферу
      • Часть 5. Атмосферный шейдер
      • Часть 6. Пересечение атмосферы
      • Часть 7. Шейдер атмосферного рассеяния
      Читать дальше →
    • Микросервисы: опыт использования в нагруженном проекте



        На конференции HighLoad++ 2016 руководитель разработки «М-Тех» Вадим Мадисон рассказал о росте от системы, для которой сотня микросервисов казалась огромным числом, до нагруженного проекта, где пара тысяч микросервисов — обыденность.

        Тема моего доклада — то, как мы запускали в продакшн микросервисы на достаточно нагруженном проекте. Это некий агрегированный опыт, но поскольку я работаю в компании «M-Tех», то давайте я пару слов расскажу о том, кто мы.

        Если коротко, то мы занимаемся видеоотдачей — отдаём видео в реальном времени. Мы являемся видеоплатформой для «НТВ-Плюс» и «Матч ТВ». Это 300 тысяч одновременных пользователей, которые прибегают за 5 минут. Это 300 терабайт контента, который мы отдаем в час. Это такая интересная задача. Как это всё обслужить?

        Про что сама эта история? Это про то, как мы росли, как проект развивался, как происходило какое-то переосмысление каких-то его частей, какого-то взаимодействия. Так или иначе, это про масштабирование проекта, потому что это всё — ради того, чтобы выдержать ещё больше нагрузки, предоставить клиентам ещё больше функционала и при этом не упасть, не потерять ключевых характеристик. В общем, чтобы клиент остался доволен. Ну и немного про то, какой путь мы прошли. С чего мы начинали.
        Читать дальше →
      • Дизайн UI в играх на примере NieR:Automata

        • Перевод
        image


        Привет, меня зовут Хисаёси Кидзима, я дизайнер UI и мехов для NieR:Automata. Игровой UI (интерфейс пользователя) часто остаётся незамеченным, поэтому я рад услышать, что фанаты нашли дневник разработчиков NieR:Automata и спросили о моей работе!

        Когда директор NieR:Automata Йоко Таро работает над играми, он всегда чётко знает, чего хочет, и UI не стал исключением. Я хочу рассказать вам о моей работе над UI для NieR:Automata, а также о тех заданиях, которые мне давал Йоко-сан.
        Читать дальше →
        • +33
        • 16,5k
        • 3