последняя редакция статьи доступна на сайте makeloft.xyz

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

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

Сегодня мы посмотрим на структуру данных, называемую Scapegoat-деревом. «Scapegoat», кто не в курсе, переводится как «козёл отпущения», что делает дословный перевод названия структуры каким-то странным, поэтому будем использовать оригинальное название. Деревьев поиска, как вы, возможно, знаете есть очень много разных видов, и в основе всех их лежит одна и та же идея: "А хорошо бы при поиске элемента перебирать не весь набор данных подряд, а только какую-то часть, желательно размера порядка log(N)".

Для этого каждая вершина хранит ссылки на своих детей и какой-то критерий, по которому при поиске точно понятно, в какую из дочерних вершин надо перейти. За логарифмическое время это всё будет работать тогда, когда дерево является сбалансированным (ну или стремится к этому) — т.е. когда «высота» каждого из поддеревьев каждой вершины примерно одинакова. А вот способы балансировки дерева уже у каждого типа деревьев свои: в красно-чёрных деревьях в вершинах хранятся маркеры «цвета», подсказывающие когда и как нужно перебалансировать дерево, в АВЛ-деревьях в вершинах хранится разница высот детей, Splay-деревья ради балансировки вынуждены изменять дерево во время операций поиска и т.д.

Scapegoat-дерево тоже имеет свой подход к решению проблемы балансировки дерева. Как и для всех остальных случаев он не идеален, но вполне применим в некоторых ситуациях.

К достоинствам Scapegoat-дерева можно отнести:

• Отсутствие необходимости хранить какие-либо дополнительные данные в вершинах (а значит мы выигрываем по памяти у красно-черных, АВЛ и декартовых деревьев)
• Отсутствие необходимости перебалансировать дерево при операции поиска (а значит мы можем гарантировать максимальное время поиска O(log N), в отличии от Splay-деревьев, где гарантируется только амортизированное O(log N))
• Амортизированная сложность операций вставки и удаления O(log N) — это в общем-то аналогично остальным типам деревьев
• При построении дерева мы выбираем некоторый коэффициент «строгости» α, который позволяет «тюнинговать» дерево, делая операции поиска более быстрыми за счет замедления операций модификации или наоборот. Можно реализовать структуру данных, а дальше уже подбирать коэффициент по результатам тестов на реальных данных и специфики использования дерева.

К недостаткам можно отнести:

• В худшем случае операции модификации дерева могут занять O(n) времени (амортизированна сложность у них по-прежнему O(log N), но защиты от «плохих» случаев нет).
• Можно неправильно оценить частоту разных операций с деревом и ошибиться с выбором коэффициента α — в результате часто используемые операции будут работать долго, а редко используемые — быстро, что как-то не хорошо.

Мы тут весь год общались с детскими психологами и вообще много думали о теме детского образования. Как один из результатов — сделали игру на развитие логики.



В общем, юному программисту нужно будет написать стек действий для таксиста. Чтобы довезти пассажира куда надо с первого раза. Сразу говорю — можно играть и с 4-5 лет. Как обычно, если ребёнок — сын инженера, смело вычитайте 2 года из минимального возраста.

Доброго времени суток, многоуважаемый %USERNAME%. Меня зовут Голованов Сергей, и я всё еще являюсь ведущим вирусным аналитиком в «Лаборатории Касперского». Я понимаю, что название этого поста в корпоративном блоге компании может вызвать смех, грусть, а у некоторых даже эпилептический припадок, но дайте мне всё объяснить.

Я понимаю, что для всех батники выглядят как нечто очень простое и со времен AUTOEXEC.BAT уже практически забытое, в то же время эксплойты, если вы конечно не профессиональный исследователь уязвимостей, выглядят очень сложно и практически неправдоподобно, особенно для некоторых разработчиков. Но! В данном посте я постараюсь перевернуть эти представления и рассказать, что всё как будто наоборот. Батники чуть легче и сильнее по функционалу brainfuck'а, а эксплойты не страшнее сортировки пузырьком на basic'е.


(Осторожно! 3 МБ иллюстрированного потока сознания и куча скриптов)

Это перевод публикации «Les Forges Pixel Art Course».

Часть 1: Правильные инструменты
Часть 2: Линии и кривые
Часть 3: Перспективы
Часть 4: Тень и свет
Часть 5: Палитры цветов
Часть 6: Сглаживание
Часть 7: Текстуры и размытие
Часть 8: Мир тайлов

Часть 3: Перспективы

Проблема перспективы в 2D играх, это вопрос который возникает часто, и это возможно то, почему так много любительских игр имеют множество противоречивостей в этой области. В частности эта часть адресуется к типичным перспективам в RPG, так что если вы ищете информацию о виде сбоку или от первого лица, вам следует поискать где-нибудь ещё. Это важно, помнить что перспектива — это «искусство представления трёхмерных объектов на плоской поверхности (в данном случае это ваш экран) как их увидел бы наблюдатель.»

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

После поста о восстановлении флешек, оказалось, что у многих теперь есть рабочие, бесхозные флешки, которые обязательно нужно задействовать. Почему бы не сделать из них загрузочные флешки с дистрибутивами необходимых ОС? Это может здорово пригодиться при установке/переустановке операционных систем на нетбуки, где отсутствуют приводы оптических носителей. А иногда может даже ускорить процесс установки и сделать его намного тише на компьютере, где привод есть.
Хотя на Хабре уже описывались варианты создания загрузочных флешек, но вариант, который предлагаю я — слишком прост и по своему универсален, чтобы обойти его стороной.

Разделы можно пропускать без ущерба для понимания, ровно как и любые непонятные/неинтересные места в них.

Перенаправления

Как обычно:

echo foo > bar
echo foo 2> bar
echo foo > bar 2>&1

Пожалуй, начну с того, что если перегружаться 15 раз в год, то любой «тюнинг» процесса загрузки отнимает больше времени, чем будет выиграно на перезагрузках за все время жизни системы. Однако, спортивный интерес берет свое, тем более, что люди интересуется процессом оптимизации быстродействия. А загрузка оказалась самым очевидным кандидатом в примеры того, как на мой взгляд должен выглядеть этот самый процесс. Сразу скажу, что грузиться будем с 5400 rpm винта, грузиться будем в «рабочую» систему: помимо недобитой вендорской крапвари там стоит еще куча всякого типа вижуал студии, антивируса, скайпа, стима, гуглапдейтера и пр…

Про то, почему отключение pagefile-а скорее вредно, чем полезно — как нибудь в другой раз, а пока…

Привет.

Я студент-партнер Microsoft, и в этой статье я хотел бы поделиться с вами своим опытом публикации приложения в Windows Store и рассказать о некоторых особенностях сертификации и публикации.

Продолжение.

Начало здесь: Нейробиология и искусственный интеллект: часть первая — ликбез,
и здесь: Нейробиология и искусственный интеллект: часть полуторная – новости от Blue Brain Project.

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

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

И как же интеллект связан с деятельностью нейронов?

Понедельник

• Новости: ученые изобрели машину времени, вышел новый ноутбук толщиной 80 нанометров, Google покупает Microsoft, Facebook увольняет 1000 программистов.
• Вылез стартап. Попиарился, лёг под хабраэффектом, встал, собрал замечания, поблагодарил, пропал навсегда.
• Вышла новая версия третьего слева линукса. Качать срочно.
• Я негодую — счет за телефон оператор округлил до кратности числу Пи.

Вторник

• Опровержение новостей: ученые изобрели всего-лишь более точные часы, 80 нанометров — это техпроцесс, а не толщина ноутбука, Google покупает какой-то стартап, который отказался купить Microsoft, Facebook набирает 5000 программистов.
• Начало холивара, модного на этой неделе (чай vs кофе, бинокль vs подзорная труба, черное vs белое)
• Очень важный технический ресурс (ЖЖ, порнолаб, Sony Network) взломан (заДДОСен, конфискован УБОПом). Паника и отчаяние.

Вчера увидела свет новая, уже четвёртая по счёту версия инновационного и популярного пакета создания и редактирования трехмерной графики Luxology Modo. Разработчики потратили почти полтора года на разработку новой версии программы и за это время она успела обрасти новыми и весьма полезными функциями, среди которых:

• Волосы и мех.
• Объемный свет.
• Репликаторы.
• Улучшенные превью и рендеринг.
• Улучшенная анимация.
• Улучшенный моделлинг.
• Улучшенные рисование и скульптинг.

Побробнее с программой и всеми нововведениями можно ознакомиться в подробном описании на сайте разработчика www.luxology.com/modo/tour
К сожалению пробная версия программы пока не доступна, но по заверению разработчиков она будет доступна сразу как снизится нагрузка на серверы компании от скачивания дистрибутивов пользователями уже оплатившими продукт.

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

Мы – российская студия, более двенадцати лет занимающаяся разработкой компьютерных игр. Нами были созданы «Мор. Утопия» (Pathologic), «Тургор» (Tension), «Тургор. Голос цвета» (The Void), «Эврика!» (Cargo! The Quest for Gravity) и «Тук-тук-тук» (Knock-Knock).

Несколько лет назад – по совету нашего опережающего время друга – мы решили опробовать краудфандинговую площадку Kickstarter в качестве источника финансирования небольшого игрового проекта.

Несмотря на сомнения, первая кампания успешно завершилась в середине сентября 2012 года. Мы собрали сорок одну тысячу долларов при заявленных тридцати. На полученные деньги была разработана и доставлена вкладчикам игра «Тук-тук-тук» (Knock-knock).

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

Поэтому мы решили провести еще одну кампанию. Мы собираемся сделать графически, технологически и геймплейно более совершенный ремейк нашей первой игры «Мор. Утопия» (Pathologic).

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

(вторая часть перевода статьи Разоблачение алгоритмов растеризации шрифтов)

Linux

Наследуя худшее

Windows растеризует шрифты плохо, Linux ещё хуже. Во всех Linux-системах, которые я видел, используется FreeType [10] Дэвида Тёрнера, Роберта Вильгельма и Вернера Лемберга. Это отличная библиотека, но способ её использования, к сожалению, нельзя назвать удачным. Типичный скриншот Linux выглядит так:



Вот полный скриншот:
ссылка

Сразу заметна проблема — чёрные пятна в скругленных углах, образовавшиеся в результате сглаживания. Вцелом, можно сказать, что косые штрихи выглядят тяжелее чем вертикальные, что в регультате производит впечатление «грязи». Вы можете возразить, что FreeType и Linux могли бы использовать схожую с ClearType субпиксельную растеризацию, но по мне это не даёт заметных преимуществ.

Привет, Хабр!
Ничего не писал со времен своей первой статьи, решил, что пора это исправить.

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

Ниже я даю рецензии на книжки, которые считаю очень полезными в различных разделах computer science, которые используются в геймдеве. Я намеренно опускаю книги по C++ и алгоритмам: мне кажется, эта тема уже настолько изучена и освещена, что больше про нее не стоит рассказывать.

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

А какие книжки нравятся вам?
Также в комментах можете писать, на какие темы вам были бы интересны посты.

Этот цикл статей является вольным переводом книги «Rust by Example», которую пишет Хорхе Апарисио на Github.

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

Давайте начинать!

Как вы, возможно, знаете в мире Windows для рисования графики часто используется DirectX. В последних версиях (10, 11.x) библиотека серьёзно шагнула вперёд и именно на них построены движки многих современных игр. Кроме того, DirectX используется не только в играх — сам интерфейс ОС Windows тоже с непомню-какой версии (Vista?) рисуется через него, да и казалось-бы не сильно связанные с графикой программы, желая увеличить производительность и плавность зума\скрола переходят на последние версии DirectX. Так некоторое время назад на DirectX11 перешел рендер Google Chrome (вроде бы с версии 36).

Когда-то во времена Windows 95 и Pentium II была такая шутка, что чем медленнее компьютер — тем лучше можно понять работу операционной системы — невооруженным глазом видно в каком порядке прорисовываются элементы окон, обрабатываются события. Сегодня для подобных целей относительно DirectX есть отдельные инструменты — графические отладчики, позволяющие понять, как именно рисуется каждый пиксель каждого кадра, какие операции выполняет движок DirectX, какие ресурсы он использует, насколько быстро и правильно всё работает. Один из таких инструментов — RenderDoc от компании Crytek мы сегодня и рассмотрим. А в качестве примера разберём уже упомянутый выше новый рендер Google Chrome.

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

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

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

Недавно на руборде в разделе Программирование был задан вопрос: «Зачем Win32-приложению манифест? На что он влияет?». Первое, что сразу приходит в голову большинству программистов — это темы оформления. Но на самом деле в современных виндах манифест нужен не только для этого. Я подумал и написал пять ключевых аспектов, на которые влияет манифест или его отсутствие. После этого сразу несколько человек попросили оформить этот пост в виде более развернутой статьи.