Этот текст предназначен для тех, кто только осваивает программирование. Основная идея в том, чтобы показать этап за этапом, как можно самостоятельно сделать игру à la Wolfenstein 3D. Внимание, я совершенно не собираюсь соревноваться с Кармаком, он гений и его код прекрасен. Я же целюсь совсем в другое место: я использую огромную вычислительную мощность современных компьютеров для того, чтобы студенты могли создавать забавные проекты за несколько дней, не погрязая в дебрях оптимизации. Я специально пишу медленный код, так как он существенно короче и просто понятнее. Кармак пишет 0x5f3759df, я же пишу 1/sqrt(x). Мы преследуем разные цели.

Я убеждён, что хороший программист получается только из того, кто кодит дома в своё удовольствие, а не только просиживает штаны на парах в университете. В нашем университете программистов учат на бесконечной череде всяких библиотечных каталогов и прочей скукоте. Брр. Моя цель — показать примеры проектов, которые интересно программировать. Это замкнутый круг: если интересно делать проект, то человек проводит над ним немало времени, набирается опыта, и видит вокруг ещё больше интересного (оно же стало доступнее!), и снова погружается в новый проект. Это называется проектное обучение, вокруг сплошной профит.

Простыня получилась длинная, поэтому я разбил текст на две части:

• Часть первая: отрисовка стен
• Часть вторая: населяем наш мир + оконный интерфейс

Выполнение кода из моего репозитория выглядит вот так:


Это не законченная игра, но только заготовка для студентов. Пример законченной игры, написанной двумя первокурсниками, смотрите во второй части.

Рождение концепции Remote Reality

История нашего «безумного» проекта началась три года назад, когда размышляя о будущих перспективах развития игровой индустрии, мой друг Леша сказал: «Представь себе будущее, в котором люди в виде развлечения, из любой части мира управляют на игровом полигоне настоящими роботами, как «аватарами»».

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

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

Мы сразу решили, что эти мысли укладываются больше в концепцию развлекательного аттракциона, а не компьютерной игры. Люди любят развлечения и хотят чего-то нового, и мы знали, что им предложить. Как и в любом бизнесе, сразу всплыл вопрос окупаемости, ведь на первый взгляд кажется, что наша физическая модель ограничена количеством роботов. Но умножив роботов на 24 часа и на цену часа в 5-10 долларов, сомнения отпали. Финансовая модель не являлось «Клондайком», но вполне окупалась даже при 10% загрузке.

Очень быстро у нас в голове появилось название новой концепции: Remote Reality, по аналогии с Virtual Reality и Augmented Reality.

Навигация по лесу

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


В оригинале статьи все изображения интерактивны.

Как один алгоритм решает обе эти задачи? Давайте начнём с краткого описания того, как работает A*.

Алгоритм A*

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

На каждом шаге алгоритма A* оценивает множество частичных путей и генерирует новые пути, расширяя наиболее многообещающий путь из множества. Для этого A* хранит частичные пути в очереди с приоритетами, отсортированном по приблизительной длине — истинной измеренной длине пути плюс примерное оставшееся расстояние до цели. Это приближение должно быть недооценкой; то есть приближение может быть меньше истинного расстояния, но не больше него. В большинстве задач поиска пути хорошей преуменьшенной оценкой является геометрическое расстояние по прямой от конца частичного пути до конечной точки. Истинный наилучший путь до цели от конца частичного пути может быть длиннее, чем это расстояние по прямой, но не может быть короче.

Тем, кто занимается системами машинного обучения и компьютерным зрением, хорошо знакома такая библиотека как OpenBLAS (Basic Linear Algebra Subprograms). OpenBLAS написан на C и используется повсеместно там где нужна работа с матрицами. Так же у него есть несколько альтернативных реализаций таких как Eigen и двух закрытых имплементацией от Intel и Apple. Все они написаны на С\С++.

В настоящий момент OpenBLAS используется в матричных манипуляциях в таких языках как Julia и Python (NumPy). OpenBLAS крайне хорошо оптимизирована и значительная её часть вообще написана на ассемблере.

Однако так ли хорош для вычислений чистый C, как это принято считать?

Встречайте Mir GLAS! Нативная реализация библиотеки линейной алгебры на чисто D без единой вставки на ассемблере!

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

«Мутации» машинного кода

В качестве примера возьмём приставку NES (известную у нас как Dendy), в которой используется процессор 6502. Система команд у него очень проста — опкод представлен всегда одним байтом, и каждый из 256 хоть что-то, да делает. Никаких «защит» от дурака не предусмотрено, и почти любой случайный набор байт будет выполняться без сопротивления со стороны процессора. Таким образом, мы можем взять ROM какой-нибудь игры, исправить в нём случайные биты (будем называть это «мутациями») — и после запуска наблюдать забавные глюки в разных неожиданных местах, но при этом в целом игра скорее всего будет работоспособной. Похоже, что на YouTube имеется целый жанр подобного видео. Полученный таким образом машинный код наверняка не очень корректен, но в большинстве случаев процессор сможет его выполнить и что-то сделать.

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

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



Сегодня мы расскажем о паре взаимодополняющих протоколов, которые нашли применение в IoT. Первый – это Modbus. Он служит для организации связи между устройствами, расположенными недалеко друг от друга. Второй – MQTT. Он обладает гораздо более широкими возможностями, поддерживает работу в локальных сетях и в Интернете. С его помощью можно организовать обмен данными между «вещами» в глобальных масштабах.

Мы любим делать интервью с нашими докладчиками. На этот раз — интервью с Андреем shodan Аксеновым, создателем поискового движка SphinxSearch(не знаю как сейчас, но раньше хабр использовал именно этот движок для поиска по сайту) и, как оказалось, еще пары движков. На нашей конференции он будет рассуждать на извечную тему: Devs vs CTO vs CEO. Само интервью вышло довольно интересным. Андрей честно и откровенно ответил на вопросы, за что ему большой респект :)

Я тебя знаю как разработчика Sphinxsearch, но, как показывает твоя краткая биография, которую ты дал в описании доклада, похоже компьютерная графика — твоя главная страсть?

Все одновременно проще и сложнее, какой-то главной мегастрасти нету :) Есть сколько-то интересные области, есть безразличные. Делать всякий низкий уровень, типа поискового движка, 3D игры, обработки видеозахвата, крохотного недогипервизора (V8086), патчить MySQL или ядро операционки, писать спецмодули к Апачику, улучшать известный алгоритм сжатия или даже просто ковыряться с особо толстыми и тормозными SQL запросами — все это бывает довольно интересно (а бывает нет! но чаще интересно). А вот рисовать формочки для GUI, неважно, на моднейшем Node.js или дохлом Delphi, или там править унылые отчеты в 1C — таки не очень. Говорю по личному опыту, тк. в какой-то мере занимался всем вышеперечисленным и еще всяким.

Введение

При работе в сфере RTB (Real Time Bidding) одной из ключевых характеристик является время, затраченное на показ рекламы пользователю, зашедшему на сайт. Оно складывается из нескольких этапов, один из которых – аукцион за рекламное место, проводимый SSP (Supply Side Platform) между несколькими DSP (Demand Side Platform) системами. В этом случае критической величиной является время, за которое DSP успеет ответить своим инвентарем и денежной ставкой за данный показ. Как правило, верхняя граница этого времени составляет примерно 100 миллисекунд. С учетом того, что для оптимальной производительности рекламных кампаний требуется десятки тысяч запросов в секунду, выполнение данного требования может стать весьма нетривиальной задачей.

Для встраиваемых систем на базе процессоров с архитектурами MIPS и ARM нередко используются специализированные генераторы дистрибутивов ОС GNU/Linux: buildroot, openwrt и прочие Yocto.
Но иногда интересно запустить на такой системе универсальную ОС Debian. Установить Debian на ЭВМ с процессором архитектуры x86/amd64 — дело несложное, а вот со встраиваемыми системами, поверьте, у нас не всё так однозначно...
В данной публикации я расскажу как можно при помощи debootstrap установить, а затем как при помощи QEMU запустить ОС Debian для ЭВМ с процессорами MIPS и ARM.

В Беларуси появился первый миллиардер. Приятно, что это не какой-то олигарх, а 39-летний программист Виктор Кислый, основатель компании Wargaming.net, разработчик условно-бесплатной игры World of Tanks. Издание Bloomberg внесло его в список миллиардеров, оценив состояние в $1 млрд, исходя из оценки зарегистрированного на Кипре бизнеса в $1,5 млрд и доли Виктора 64%. По оценке Bloomberg, в прошлом году компания Wargaming.net выручила $590 млн на продаже премиальных аккаунтов и др.

Двадцать лет назад заядлый геймер Виктор Кислый со своим братом начали разработку в квартире своих родителей в Минске. Теперь хобби превратилось в огромную субкультуру из 150 миллионов игроков по всему миру.

Последние несколько месяцев ресурс Sci-Hub стал центром академических дебатов о копирайте в науке. Несмотря на то, что с ресурсом пытаются судиться крупнейшие издательства научной литературы, сайт продолжает работать, и сейчас его популярность максимальна — никогда прежде у Sci-Hub не было столько посетителей. В день ресурс помогает скачивать около 200 тысяч научных статей.

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

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

Онлайн-курсы

Начну с конца: если вы не заканчиваете школу или бакалавриат в этом году, то вы всё равно можете поучиться в Академическом университете благодаря нашим (совместно с Computer Science центром) онлайн курсам! (Кстати, скоро появятся курсы по физике от наших коллег, следите за новостями!)

Бакалавриат

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



Подробности о поступлении в бакалавриат

Магистратура

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

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

Если бы язык С был оружием

От автора: Наброски для этой статьи появились еще в начале 2015 года, правда, до публикации материалов дело так и не дошло. Наконец, решив, что в ящике моего письменного стола от вышеупомянутого «черновика» не будет никакой пользы, представляю его вашему вниманию в исходном виде. Единственное, что изменилось в тексте – год, с 2015 на 2016.

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

Итак, статья ...

Первое правило программирования на С – не используйте его, если можно обойтись другими инструментами.

Когда найти альтернативный метод не удается, самое время вспомнить о современных заповедях программиста.

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

HL7 и Office of the National Coordinator for Health Information Technology (ONC) устраивают конкурс на разработку средств просмотра HL7 CDA документов. Разработки можно присылать до 31 мая 2016.

Требования к подобному средству просмотра или viewer, достаточно расплывчатые и требуют не только знания структуры CDA, но и типичных проблем возникающих у врачей при работе с ними (преобразование на основе CSS встроено в CDA по умолчанию).



Призы

1-ое место — $15'000 USD
2-ое меcто — $5'000 USD

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

Процессоры, используемые в наших продуктах — это, в основном, 16- и 32-битные микроконтроллеры Microchip, имеющие RAM от 8 до 32 кБ, и ROM от 128 до 512 кБ, без MMU. Иногда, для самых простых устройств, используются еще более скромные 8-битные чипы.

Очевидно, что у нас нет (разумных) шансов использовать ядро Linux. Так что нам нужна какая-нибудь RTOS (Real-Time Operating System). Находятся даже люди, которые не используют никаких ОС в микроконтроллерах, но я не считаю это хорошей практикой: если железо позволяет мне использовать ОС, я ее использую.

Несколько лет назад, когда мы переходили с 8-битников на более мощные 16-битные микроконтроллеры, мои коллеги, которые были гораздо более опытными, чем я, рекомендовали вытесняющюю RTOS TNKernel. Так что это — та ОС, которую я использовал в разных проектах в течение пары лет.

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

Подошедший к концу GopherCon 2015, длившийся с 7 по 10 июля в Денвере, отметился немалым количеством интересных выступлений. Видео докладов еще недоступно, однако, конспекты некоторых из них доступны на английском языке по этому адресу; в официальном блоге также можно прочитать программную речь Расса Кокса. Вниманию читателей предлагается конспект доклада об истории создания языка, который открыл второй день конференции.

Роберт Грисмер (@robertgriesemer) — разработчик в Google, один из авторов языка Go. В прошлом Роберт работал над генерацией кода для высокопроизводительного JavaScript, занимался языком программирования Sawzall и разработкой современной реализации Smalltalk — Strongtalk. По собственному заявлению, он «провел слишком много времени в виртуальных Java-машинах, но так и не понял, как ими пользоваться».

Интерес Роберта к языкам программирования возник при знакомстве с Pascal — до этого момента он в основном писал на BASIC. Будучи аспирантом, он обучался у Никлауса Вирта, создателя Pascal.

Когда Роберт закончил учебу и окунулся в реальный мир индустрии профессионального программирования, то почувствовал себя так, словно совершил огромный шаг назад. Во время обучения в академии он использовал Оберон — язык, позволяющий программисту достигать очень высокой личной эффективности. Теперь же Роберт тратил свое время на размышления о языках программирования в надежде придумать способ, как ему вернуться на былой уровень производительности. После 15 лет опыта программирования на С++ он понял, что впереди у него только два пути: или продаться, или спасаться. Вместе с Робом Пайком и Кеном Томпсоном они выбрали второй вариант.

Содержание

1. Что такое тензор и для чего он нужен?
2. Векторные и тензорные операции. Ранги тензоров
3. Криволинейные координаты
4. Динамика точки в тензорном изложении
5. Действия над тензорами и некоторые другие теоретические вопросы
6. Кинематика свободного твердого тела. Природа угловой скорости
7. Конечный поворот твердого тела. Свойства тензора поворота и способ его вычисления
8. О свертках тензора Леви-Чивиты
9. Вывод тензора угловой скорости через параметры конечного поворота. Применяем голову и Maxima
10. Получаем вектор угловой скорости. Работаем над недочетами
11. Ускорение точки тела при свободном движении. Угловое ускорение твердого тела
12. Параметры Родрига-Гамильтона в кинематике твердого тела
13. СКА Maxima в задачах преобразования тензорных выражений. Угловые скорость и ускорения в параметрах Родрига-Гамильтона
14. Нестандартное введение в динамику твердого тела
15. Движение несвободного твердого тела
16. Свойства тензора инерции твердого тела
17. Зарисовка о гайке Джанибекова
18. Математическое моделирование эффекта Джанибекова

Введение

Что такое угловая скорость? Скалярная или векторная величина? На самом деле это не праздный вопрос.

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

Угловая скорость твердого тела — это первая производная от угла поворота тела по времени

А вот потом, при рассмотрении каноничной формулы Эйлера для скорости точки тела при вращении


обычно дается следующее определение

Угловая скорость тела — это псевдовектор, направленный вдоль оси вращения тела в ту сторону, откуда вращение выглядит происходящим против часовой стрелки

Ещё одно частное определение, которое, во-первых, утверждает неподвижность оси вращения, во-вторых навязывает рассмотрение лишь правой системы координат. И наконец термин «псевдовектор» обычно объясняется студентам так: «Посмотрите, ведь мы показали, что омега — скалярная величина. А вектор мы вводим для того, чтобы выписать формулу Эйлера».

При рассмотрении сферического движения оказывается потом, что ось вращения меняет направление, угловое ускорение направлено по касательной к годографу угловой скорости и так далее. Неясности и вводные допущения множатся.

Учитывая уровень подготовки школьников, а так же вопиющую глупость, допускаемую в программах подготовки бакалавров, когда теормех начинается с первого (вдумайтесь!) семестра, такие постепенные вводные, на палках, веревках и желудях наверное оправданы.

Но мы с вами заглянем, что называется, «под капот» проблемы и, вооружившись аппаратом тензорного исчисления, выясним, что угловая скорость — это псевдовектор, порождаемый антисимметричным тензором второго ранга.

Думаю для затравки вполне достаточно, а поэтому — начнем!

Не так давно мне пришлось обращаться к хранилищу ZooKeeper из кода на C++. Приличной С++-обёртки для сишной библиотеки libzookeeper не нашлось, поэтому её пришлось написать самому. В процессе реализации я существенно видоизменил подход авторов java-библиотеки к построению API и теперь хочу поделиться с вами причинами и результатами принятых решений. Несмотря на ключевые слова С++ и ZooKeeper, подход, описанный в статье, подходит для организации доступа к любым хранилищам, и вполне реализуем на языках, отличных от С++.