Алёна C++

Статья "Notes On Scalability"

2012-01-14T08:39:00.003+04:00

В статье Notes on Scalability сформулированы пять принципов построения масштабируемых систем. Я привожу краткий перевод, по ссылке все подробнее и интереснее.

1. Build it to Break.
Что бы вы ни разрабатывали, оно сломается. Будьте к этому готовы.

2. Everything is a Feature
Ваше приложение - это набор решений и компромиссов.

3. Scale Out, Not Up
Хорошо, когда проблемы масштабирования можно решить добавлением серверов.

4. Buy More Storage
Много маленьких дисков обычно быстрее одного здорового.

5.You’re Going to Do It Wrong
Вы ошибетесь. Будьте готовы переписывать свой код и пробовать новые идеи.

По ссылке с highscalability.

Карта С++11

2012-01-09T07:24:00.011+04:00

English translation

В последнее время на землях языка С++ происходили масштабные изменения. И старая карта стала безнадежно устаревшей. Поэтому в новогодние праздники мы с Джимом напряглись и изобразили их все на карте. Вернее, изображал все конечно он, умение рисовать не относится к числу моих талантов. Он не только добавил бои за новый стандарт, но и значительно улучшил старые территории.

Так что встречайте новою версию! Осторожно, она здоровая - 13 мегов.

Для тех, кто не осилил закачать 13 мегов (кто вы, люди?) - JPEG на 4 мега

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

О найденных ошибках и опечатках сообщайте в редакцию, пожалуйста. Updated: опечатку с management поправили

Исходники:
cppmap-2012.cdr - собственно исходник
cppmap-2012.svg - он же, конвертнутый в более популярный формат
reikland_paper.jpg - текстура потертой бумаги

Ссылки по теме:
Карта языка C++ (The C++ Lands) - cтарая карта

CodeFlow - тулза для code review

2012-01-06T08:54:00.003+04:00

Обещают нашу внутреннюю тулзу для code review включить в следующий релиз Visual Studio. Статья об этом:
A Bar, an Idea, and a Garage: The Story of CodeFlow

CodeFlow - прекрасная вещь, вся из себя интуитивно понятная, рекомедую. Мы ей пользуемся и довольны.

The Art Of Programming — Выпуск №70 [ Drinking ] / Готовимся к новому году с alenaCPP

2011-12-29T10:11:00.002+04:00

Поучаствовала в новогоднем подкасте The Art Of Programming. Душевно пообщались с golodnyj.

Интервью с Корринной Ю

2011-12-17T23:19:00.003+04:00

Women in Gaming: Halo's Corrinne Yu. Корринна работает в Microsoft Game Studios, занимается архитектурой движка Halo. Интервью просто про жизнь, про программирование там маловато.

Пойду на конференцию GoingNative 2012

2011-12-12T06:33:00.002+04:00

В начале февраля тут у нас в Редмонде будет конференция GoingNative 2012. Рассказывать будут о C++11. Обещают, что там будут Страуструп и Александреску. Схожу, посмотрю на них, потом вам расскажу.

Опубликованы исходники Doom 3

2011-11-23T09:00:00.008+04:00

Помните, Кармак обещал опубликовать исходники Doom 3 после выхода Rage? Он свое слово держит: Doom 3 GPL source release

/*
===========================================================================

Doom 3 GPL Source Code
Copyright (C) 1999-2011 id Software LLC, a ZeniMax Media company.

Это только исходники, без данных. Данные можно взять из самой игры.

Из-за юридических проблем ему пришлось убрать оттуда кусок кода, известный как Carmack's Reverse.

Должно компиляться под Win32, Linux и MacOS.

Написано на С++, но это скорее похоже на С с классами - голые указатели, сишные массивы.

Как это обычно бывает, не все доведено до идеального состояния.

qglDisableClientState( GL_NORMAL_ARRAY );
qglDisable( GL_FRAGMENT_PROGRAM_ARB );
qglDisable( GL_VERTEX_PROGRAM_ARB );
// Fixme: Hack to get around an apparent bug in ATI drivers.  Should remove as soon as it gets fixed.
qglBindProgramARB( GL_VERTEX_PROGRAM_ARB, 0 );

Как видно из кода, для отрисовки используется OpenGL. ~~Почему-то в readme написано, что нужен DirectX. Непонятно.~~ DirectX нужен для DirectInput.

Подменив данные и слегка поменяв код можно написать 3D-шутер своей мечты :-).

Статья The Designer's Notebook: Passion Versus Professionalism

2011-11-05T09:26:00.004+04:00

The Designer's Notebook: Passion Versus Professionalism - статья про то, что игровой индустрии нужны скорее профессионалы, нежели энтузиасты. Но вообще там много интересного написано, что подойдет к любой индустрии.

I would much rather hire someone with professionalism than passion. Professionalism is dedication to doing a great job even if you're not the target audience.

Спасибо анонимному комментатору, который дал в комментариях ссылку на русский перевод статьи: Увлечённость или профессионализм?

via voldmar

Пост Stevey's Google Platforms Rant

2011-10-13T09:36:00.004+04:00

Стив Йеги ~~(я надеюсь, это произносится именно так)~~, который работает в Гугле, случайно опубликовал в открытом доступе свою статью со сравнением API Амазона и Гугла, хвалит там SOA. Ну а также там есть немного сплетен о всяких их внутренних делах.
Эта статья стала хитом среди разработчиков, все о ней пишут, все ретвитят. В итоге статью решили из открытого доступа не убирать. Вот она: Stevey's Google Platforms Rant. Много букв.

...Amazon had transformed culturally into a company that thinks about everything in a services-first fashion. It is now fundamental to how they approach all designs, including internal designs for stuff that might never see the light of day externally.

ISO C++11 опубликован

2011-10-11T10:17:00.003+04:00

Мне уже много раз присылали письма с вопросами "новый стандарт С++ уже вышел, почему у тебя в блоге ничего про это нет???". Однако, официальный пресс-релиз о выходе нового Стандарта появился только сегодня, 10.10.2011, и Твиттер начал радоваться именно сегодня. И да, у нас тут всё еще десятое, хотя у вас у многих уже 11.
Итак, можно открывать шампанское и праздновать, с обязательным зачитыванием вслух пресс-релиза.
Герб Саттер написал об этом радостном событии тут: ISO C++11 Published.
ISO, как обычно, будет продавать финальный вариант Стандарта за деньги и, как обычно, последний черновик Стандарта, который мало чем отличается от финальной версии, можно взять тут.
Ура.

Бесплатный онлайн-курс по машинному обучению

2011-10-10T10:09:00.003+04:00

Стэнфордский университет предлагает бесплатный онлайн-курс по очень модному сегодня направлению - машинному обучению: Stanford Machine Learning class. Всё на английском, есть субтитры.
Туда входят видеолекции, вопросы по каждому разделу и упражнения, в которых надо будет писать код. Есть форум где можно задавать вопросы.
Я начала смотреть, мне нравится.

Интервью со Страуструпом на bigthink.com

2011-09-23T08:34:00.003+04:00

Интервью с Бьярном Страуструпом.

Рассказывает про то, как он создавал С++ и про то какой это хороший язык. :-)
Считает, что каждый программист должен знать 5 языков. Страуструп советует: С++ и набрать еще из Java, Python, Ruby, JavaScript, C, C#, какой-нибудь функциональный язык.

Сказал, что использует ежедневно и Windows, и Linux.

В конце дает совет С++ разработчикам: использовать все фичи С++, в том числе посмотреть новый стандарт. "Почитайте хорошую книгу и посмотрите не застряли ли вы в 80х или 90х".

Мы все еще нанимаем

2011-08-30T07:47:00.010+04:00

Updated 02.09.2011: Мой бывший сокурсник и нынешний коллега о работе в Майкрософте: В рекламе Микрософт я снялся в роли человека с рюкзаком и фотоаппаратом

Дорогие друзья, хочу вам напомнить, что наши рекрутеры все еще ждут ваши резюме до 31 августа. Полный текст объявления тут: Microsoft Advertising нанимает.

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

Мне не ответили, это значит, что я не подхожу?
Наши рекрутеры обычно отвечают в любом случае, даже если человек не подошел. ~~Поэтому, если ответа нет больше недели, лучше написать им еще раз.~~ Updated 15.09.2011: плохой совет, могут и дольше не отвечать.

По визе
Вы получаете H1B визу, по которой можете работать в США на Майкрософт. Переход в другую компанию возможен, но это определенный гемор.
Ваша жена(муж) получает H4 визу и не может работать.
Майкрософт довольно быстро начинает оформление гринкарты. В моем случае где-то через три месяца после начала работы. На сегодня оформить гринкарту для PhD несколько проще чем для магистра, оформить гринкарту для магистра несколько проще чем для бакалавра.

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

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

Отпуск и выходные
Отпуск 3 недели в год, выходных за год получается где-то с 10 дней - это День Независимости и тому подобное. Короче, сильно меньше чем в России.
Суббота и воскресенье выходные как обычно.
Мужчинам предоставляется отпуск по уходу за ребенком (месяц, по-моему).

По переезду
Переезд полностью организован и оплачен, выплачиваются подъемные, предоставляется квартира на первое время. Иногда вместо организации переезда и квартиры просто дается мешок денег.

Съём квартиры
Однобедрумная квартира, это комната и кухня, совмещенная с гостиной, стоит от 1050 в месяц. Коммунальные платежи дороже, чем в России.
Квартира, как правило, сдается c парковочным местом. Иногда за него надо немного доплатить.
Народ живет либо в Редмонде - это деревня в хорошем смысле слова - зелень, зайчики-белочки. Все блага цивилизации присутствуют.
Либо в Беллвью - это небольшой город. Офисы Бинга находятся в Беллвью, можно близко снять квартиру и на работу ходить пешком. В Беллвью дороже.
Либо в Киркленде - он похож на Редмонд.
Очень многие, смотря на карту, видят что там рядом город Сиэтл и думают поселиться там. Вот это плохая идея. Там дороже а, главное, там пробки, по которым очень неудобно добираться на работу. У вас будет уходить на дорогу минут 40, а то и час, вместо 10-20 минут.

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

Налоги
Налог у вас будет ~23-30 процентов. Налоговая система странная и мутная, причем декларацию заполняет каждый человек индивидуально. Проценты с депозитов облагаются налогом. Даже с тех депозитов, что остались в России.
Майкрософт может дать вам в помощь налоговых консультантов.

Еще в Майкрософте есть своя пенсионная программа, можно в ней поучаствовать.

В Майкрософте нет ограничений на пользование устройствами других компаний. То есть вы можете спокойно пользоваться своим iPhon'ом (несколько странный для меня, но частый вопрос).

В Беллвью, Киркленде, Редмонде очень безопасно, это чувствуется, контраст с Москвой разительный.

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

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

Восемь заблуждений о распределенных вычислениях

2011-08-22T08:21:00.003+04:00

В 1994 Питер Дейч сформулировал семь заблуждений о распределенных вычислениях, позже, в 1997, Джеймс Гослинг добавил восьмое. Это типичные ошибки, которые допускают специалисты - новички в разработке распределенных систем.
В википедии об этих заблуждениях есть статья Fallacies of Distributed Computing с ссылками на подробные объяснения. А я, как обычно, изложу их покороче.

Сеть надежна
Всё время что-то ломается. Электричество выключается, сетевые провода обрываются, софт глючит.
Латентность нулевая
Даже если пропускная способность вашей сети большая, ей нужно какое-то время, чтобы раскочегариться. Поэтому ваше прекрасное плавное AJAX приложение надо тестировать не только в корпоративной сетке.
Пропускная способность бесконечна
Несмотря на то, что пропускная способность растет очень быстро, мы всегда найдем, чем ее загрузить: богатые интерфейсы, IP-телефония и интересные видео высокого качества.
Сеть безопасна
Хакеры не дремлют! Повсюду малварь и DDOS атаки.
Топология никогда не меняется
Появляются новые устройства, отключаются старые. В случае мобильных устройств топология меняется постоянно. Так что никогда не стоит думать, что передаваемые данные всегда будут ходить одним и тем же путем.
Администратор всегда только один
Когда в разработке задействованы больше чем одна компания, а проблема где-то на стыке, решить ее бывает несколько сложнее.
Цена передачи данных нулевая
Компьютеры, роутеры, пропускная способность и люди, которые это все обслуживают, стоят денег.
Сеть однородна
В сети работают устройства с разными операционными системами, все время появляются новые - тут опять можно вспомнить про мобильные устройства.

Выступление Джона Кармака на QuakeCon 2011

2011-08-12T11:00:00.004+04:00

Джон Кармак как обычно выступал на QuakeCon, вот видеозапись его выступления.

Расшифровку я не нашла, похоже ее пока нет.
Для тех, кто не готов слушать его полтора часа, коротенький пересказ:
Много говорил про мегатекстурирование в Rage и вообще про Rage. Как Rage получился ему нравится.
Говорил про статический анализ кода, говорит, что это вещь и надо им пользоваться. Хвалил майкрософтовский статический анализатор кода и вообще: "Microsoft Research has a lot of really smart people and they do a lot of work covering a lot of different areas."
Этот анализатор идет в комплекте с тулзами под XBOX 360, поэтому "если вы разрабатываете под 360 и не используете статический анализ, то вы совершаете ошибку.
Также упомянул PVS-studio.
Иногда ему хочется перейти на функциональные языки программирования. На Haskell, например. Но он считает, что тут будут проблемы с прозводительностью, а также с обучением и наймом людей. Поэтому остаемся с С и С++.
Ему 40 лет, ему нравится программировать и у него отлично получается. Лучше чем когда бы то ни было. (Тут сразу вспоминаются мифы про то, что программировать после 30 невозможно.)

Ну и самое главное - Код Doom 3 будет открыт в этом году. (!)

Вопросы и ответы после его выступления:

Ссылки по теме:
Твиттер Кармака
Rage и Tech5
Выступление Джона Кармака на QuakeCon 2008
Перевод выступления Кармака на Quakecon 2004

Microsoft Advertising нанимает

2011-07-25T06:41:00.008+04:00

Microsoft Advertising нанимает. В том числе в нашу команду - Delivery Engine Team. Приходите к нам.

Microsoft Advertising will be hosting a recruiting event in mid-October this year to recruit top talent from all over Russia and neighboring countries specifically focusing on Software Developers of all experience levels who are interested in relocating to the U.S. At this time, we are looking to hire engineers for the roles below. ALL roles require strong coding and development experience.

Software Development Engineer (SDE)
Software Development Engineer II (SDE II)
Principal SDE
Engineering Leads

If interested – please send your information and Resume/CV to the Recruiter organizing this event: eugenial@microsoft.com by Wednesday, August 31st. We are focused on broad-based software development skills when considering potential candidates (across the board – no specific technology/product niche requirements). If you are strong in C++, C# or JAVA, we would love to hear from you!

We are looking for strong Software Development Engineers to help us with a number of hard problems in the following areas:

The Advertising Applications Team

Front End Team
Microsoft Advertising is a unified Ad Monetization platform chartered to monetize the web and other mediums (including devices) by delivering the right ads to right customers at the right time. With the migration of Yahoo advertisers, Microsoft Advertising is now the second largest advertising solution in the world. We are going through an aggressive growth cycle and plan to expand to 35 global markets over the next couple of years. As we onboard thousands of Advertisers into our system, we want to build an intuitive user experience that serves both novice and expert advertisers, an experience that is industry leading and raises the bar for end user productivity. We offer a start-up like atmosphere with tremendous opportunities for fresh perspectives.

Middle Tier Team
Excited about architecting a truly scalable and performing public web services APIs and middle-tier web services? Excited about having a revenue impact of billions of dollars and contributing to Microsoft's bottom-line? Excited to work in a team that is fueled by passion, creativity and innovation? If your answer is yes then read on!
AdCenter is the ad based monetization platform for Microsoft online business. We are the application development team responsible for developing applications used by advertisers to create and manage their millions of ad campaigns. Challenges are to engineer a highly performing, secure & scalable customer facing web services and backend services that can support millions of transactions per day. We are looking for someone who has strong coding skill in C# /C++ and ability to solve complex problems. Candidate should demonstrate good understanding in SQL fundamentals, transact-SQL and stored procedures. Experience in design and development of SOA principles based services in an online business will be an added advantage.

Back End Team
We are working to build a world class application platform fuelled by SQL Server and other data processing technologies with unprecedented scale, performance, partitioning and geo distribution with Petabyte size databases. Our OLTP systems have 10K transactions/sec and billions of transactions flowing through the system on a daily basis. You will be working with a highly motivated team on cutting edge software using agile development strategies and rapid release cycles.

The Advertising Delivery Engine Team

The Ad Delivery Platform team owns the online ad tracking and delivery system. This is a real-time platform that hosts data and code for various auction algorithms for advertisers and content publishers, click-fraud, merchant fraud, content classification, categorization, demographics prediction, search patterns. We are storing and managing TBs of information which enables us to run the auction algorithms and choose the best ads out of hundreds of thousands choices. And we do all that in just a few milliseconds, while sustaining tens of thousands of requests per second, with an uptime of 99.9%. In this environment, only the best designs and architecture will cut it. The amount of data we handle demands building, managing and monitoring a distributed system; ensuring the system health in the presence of individual failures. The Ad Delivery Engine runs 24/7/365.

The Revenue and Relevance Team

Do you want to work on technology at the heart of online monetization? The Revenue and Relevance team is looking for skilled developers- in particular, someone who has deep knowledge of large-scale data mining, machine learning, and/or quantitative analytics for online systems. As an engineer on this team, you should be able to translate design ideas into practical implementation in code, and to improve and evolve existing systems. A qualified candidate should have a degree in computer science, math, or a statistics degree and experience with software systems and/or applied research in appropriate areas of Computer Science. The algorithms we develop produce the final selection of the ads that are presented to the user upon entering the search query. As such, our algorithms are at the very heart of the Advertising technology that monetizes Bing and Yahoo. Our technology area combines systems, machine learning, data analysis, and economics --- in short, a very technically challenging area. This work makes a direct contribution to Microsoft’s bottom line.

The Business Intelligence Team
The Microsoft Advertising Business Intelligence (BI) team in Online Advertising is responsible for providing our customers with high quality analytics and reporting, giving them vital insights into their search advertising on Bing. The Reporting team within BI delivers the Middle Tier, API, and Reporting UI components that connect Microsoft Advertising BI to our customers. We are focused on providing our customers with a great user experience, a robust Middle Tier and API, and a highly reliable operational system. We work simultaneously on delivering a great product for our customers, improving our engineering processes, and growing our SDE’s skills and abilities.

Display
Microsoft: Online Services Division: Display Advertising Platform

Do you want to be part of one of the fastest growing industries in software today? Do you want to help Microsoft grow a $2 billion per year business to $5 billion? Interested in developing online services, and being part of an agile development team that ships every week? If so, then we have the right opportunity for you!

The Display Advertising group is…

Delivering the technologies running our online display businesses: Atlas Media Console, Microsoft Media Network (MMN), AdManager, RAPT, and AdExpert - which powers the MSN portal and represented partners.
Competing in a segment of the online advertising industry that is seeing explosive innovation and increased competition.
Poised to make rapid advances in online advertising.
Chartered with building the next generation of display advertiser systems.

Our Display Advertising products and services:

Are responsible for monetizing both internal (MSN, Hotmail, MSNBC, etc.) as well as 3^rd party display properties.
Handle 700+ billion monthly ad requests across globally dispersed data centers
Deliver over $2 billion in annual advertising revenue.

Порядок инициализации статических переменных

2011-07-12T18:22:00.003+04:00

Порядок инициализации глобальных статических переменных из разных единиц трансляции не определен. По-английский это называется красивым термином static initialization order fiasco. Это означает, что если у вас в разных файлах определены глобальные статические переменные x и y, то лучше, чтобы они не зависели одна от другой, а то тут могут быть неприятные сюрпризы.

Это было скучная теория. А вот грустные примеры из практики. Пишем много-много кода с большим количеством нетривиальных глобальных статических переменных. Они как-то самопроизвольно начинают друг от друга зависеть. До поры, до времени компиляция идет таким путем, что они нормально инициализируются. Но в один прекрасный день, после добавления какого-то куска кода, они вдруг начинают инициализироваться в немного другом порядке. И это означает, что надо переосмыслить весь проект целиком. Прямо сейчас.

Updated 12.07.2011:
В комментариях посоветовали два способа продлить агонию, т.е. заставить компилятор инициализировать глобальные переменные в определенном порядке.
Для GCC это init_priority
Для VC++ #pragma init_seg

P.S. Для примеров из жизни я обычно не указываю когда и кем были допущены какие-то ошибки. Это информация для того, чтобы научиться, а не для того, чтобы поглумиться. Мы все ошибаемся.

Статья "Девушки, которые выбирают программирование"

2011-07-12T08:06:00.001+04:00

Написала статью для developers.org.ua про ситуацию с привлечением девушек в IT.
Девушки, которые выбирают программирование.
Она породила немного флейма.

Статья Lessons From FarmVille: How Zynga Uses The Cloud

2011-06-17T04:56:00.001+04:00

Lessons From FarmVille: How Zynga Uses The Cloud - интересный пример использования облачных технологий, что называется, из жизни.

via aruslan

Перевод статьи Summary of the Amazon EC2 and Amazon RDS Service Disruption in the US East Region

2011-06-05T09:54:00.008+04:00

В конце апреля 2011 года не работал облачный сервис Амазона в США. После того, как амазоновцы всё починили, они выпустили постмортем, в котором рассказали о том, что именно произошло, и что они будут делать, чтобы такое больше не происходило.
Вот он: Summary of the Amazon EC2 and Amazon RDS Service Disruption in the US East Region
Я его перевела. Они там налили немного воды, постоянно норовят одну и ту же фразу повторить в нескольких формулировках, это не трудности перевода, оно вот такое. И некоторые детали явно опущены.
Однако этот постмортем полезно почитать, оттуда можно почерпнуть информацию об инфраструктуре облачных сервисов о том, с какого рода проблемами сталкивается распределенный сервис. Да и учиться лучше на чужих ошибках.
Обратите внимание, что они анализируют произошедшее, а не пытаются назначить виноватых.

Анализ сбоя сервисов Amazon EC2 и Amazon RDS в восточном регионе США

Сейчас, когда функциональность всех сервисов полностью восстановлена, мы хотим поделиться с нашими пользователями деталями того, что произошло с вычислительным облаком компании Амазон (“EC2”) на прошлой неделе, рассказать как мы работали над восстановлением наших сервисов и что мы делаем, чтобы предотвратить повторение подобных проблем в будущем. Мы знаем, что многие из наших пользователей серьезно пострадали от этих проблем, и, как обычно в случае серьезных проблем с сервисом, мы намереваемся поделиться деталями событий и рассказать о том, как мы изменим сервис к лучшему для наших пользователей.

Сбой затронул пользователей облака EC2 в одной из Зон восточного региона США, проблемы были с частью хранилищ из Amazon Elastic Block Store (“EBS”), не обслуживались операции чтения и записи. В этом документе мы будем ссылаться на эти хранилища данных как на "зависшие диски". Те, кто пытался использовать эти сломанные диски, тоже подвисал, когда пытался читать с них или писать на них. Чтобы восстановить эти диски и стабилизировать кластер EBS в этой Зоне, мы практически все время держали отключенными все управляющие API (Create Volume, Attach Volume, Detach Volume, и Create Snapshot) для EBS в пострадавшей Зоне. Дважды в течение первого дня сбоя, деградировавший EBS кластер затронул EBS API, что привело к высокому числу ошибок и задержек при вызовах этих API во всем восточном регионе США. Как и любая сложна операционная проблема, эта была вызвана несколькими причинами, влиявшими друг на друга, и таким образом у нас есть несколько направлений, по которым надо работать, чтобы защитить наш сервис от повторения подобных проблем.

Обзор системы EBS
Понимание архитектуры EBS поможет вам лучше понять то, что произошло. EBS - это распределенное реплицированное блочное хранилище данных, которое оптимизировано под консистентность и чтение и запись с низкой латентностью из экземпляров EC2. В EBS два главных компонента. (1) Набор кластеров EBS (каждый из которых находится полностью в одной Зоне), который хранит пользовательские данные и обслуживает запросы экземпляров EC2. (2) - набор сервисов панели управления, которая используется для координации запросов пользователей и распространения их на EBS кластеры, которые работают в каждой Зоне каждого Региона.

Кластер EBS состоит из нескольких узлов EBS. Эти узлы хранят копии данных на дисках EBS и обслуживают запросы на чтение и запись, поступающие от экземпляров EC2. Для лучшей доступности и надежности, данные с дисков EBS реплицированы на несколько узлов EBS. Каждый узел EBS использует стратегию быстрого преодоления отказа, базирующуюся на технологии точка-точка, которая агрессивно создает новые реплики, если хотя бы одна из копий не синхронизирована или недоступна. Узлы кластера EBS соединены друг с другом с помощью двух сетей. Первая сеть с высокой пропускной способностью используется для обычных операций, т.е. для всех соединений с другими узлами EBS, с экземплярами EC2 и с сервисами панели управления EBS. Вторая сеть предназначена для репликации, это сеть с более низкой пропускной способностью, используется как запасная и обеспечивает узлам EBS возможность надежно соединяться с другими узлами кластера EBS и предоставляет дополнительную пропускную способность для репликации данных. Эта сеть не предназначена для того, чтобы работать со всем трафиком первой сети, она нужна для повышения надежности соединения между узлами EBS внутри кластера EBS.

Когда один узел теряет соединение с другим узлом, на который он копирует данные, он думает, что тот другой узел сломан. Чтобы сохранить надежность, он должен найти новый узел, на который он может реплицировать данные (этот процесс называется "перезеркалить"). Как часть процесса перезеркаливания, узел EBS ищет в своем кластере EBS другой узел с достаточными количеством свободного места, устанавливает с ним связь и передает данные. В нормально работающем кластере процесс поиска места для новой реплики занимает миллисекунды. В процессе перезеркаливания данных все узлы, которые имеют копии данных, будут хранить их до тех пор пока они не получат подтверждение, что другой узел теперь владеет их порцией. Это предоставляет новый уровень защиты от потери данных пользователей. Также, когда данные на диске пользователя перезеркаливаются, доступ к данным блокируется до тех пор пока система не идентифицирует новую первичную (или доступную для записи) реплику. Это требуется для обеспечения консистентности данных на диске EBS в случае возникновения ошибок. Пока происходит этот процесс, с точки зрения экземпляра EC2, пытающегося делать операцию ввода-вывода на диск, диск кажется "зависшим".

В дополнение к кластеру EBS, есть набор сервисов панели управления, который принимает запросы пользователя и передает их на нужный кластер EBS. Есть один набор сервисов панели управления EBS на один EC2-регион, но сама панель управления распределена по Зонам, чтобы обеспечить доступность и устойчивость к сбоям. Эти сервисы панели управления также являются авторитетами для кластеров EBS, когда те выбирают первичную реплику для каждого диска кластера (для консистентности, у каждого диска в каждый момент времени должна быть только одна первичная реплика). В панели управления несколько сервисов, мы будем на них на все ссылаться как на "панель управления EBS".

Первый сбой
21-го апреля в 0:47 по дневному тихоокеанскому времени в одной из Зон восточного региона США была произведена смена настроек сети, это была часть обычной работы по масштабированию AWS. Целью смены настроек было увеличение пропускной способности первичной сети. Один из стандартных шагов смены настроек - убрать трафик с одного из роутеров с резервированием в первичной сети EBS, чтобы можно было апгрейдиться. Переключение трафика было произведено некорректно и вместо того, чтобы перенаправить трафик на другой роутер в первичной сети, трафик был перенаправлен в сеть EBS с меньшей пропускной способностью. Для части кластера EBS в пострадавшей Зоне это означало, что у него теперь нет ни правильно функционирующей первичной сети, ни вторичной сети, потому что трафик был специально перенаправлен из первичной сети, а вторичная сеть не могла справиться со всем тем трафиком, что в нее пришел. В результате многие узлы EBS в пострадавшей Зоне были полностью изолированы от других узлов кластера EBS. В отличие от случая нормального прерывания работы сети, это изменение отключило одновременно и первичную, и вторичную сети, затронутые узлы были полностью изолированы друг от друга.

Когда случилась эта проблема со связностью сети, большое число узлов EBS на одном кластере EBS потеряло связь со своими репликами. Когда все вернули обратно и связность была восстановлена, эти узлы тут же начали поиск доступного серверного пространства в кластере EBS, куда бы они могли перезеркалить данные. Повторимся, что в нормально функционирующем кластере это занимает миллисекунды. В данном же случае, из-за того, что одновременно было затронуто много дисков, свободное место на кластере EBS быстро закончилось, многие узлы так и остались зависшими, они продолжали в цикле искать в кластере свободное место. Это быстро привело к "шторму перезеркаливания": большое число дисков зависли, в то время как узлы искали в кластере свободное место, которое им было нужно для реплик. В этот момент примерно 13% дисков в пострадавшей зоне были повисшими.

После вышеописанной цепочки событий деградация кластера EBS немедленно отразилась на панели управления EBS. Когда кластер EBS входит в шторм перезеркаливания и расходует все доступное свободное место, кластер больше не может отвечать на вызов API "CreateVolume". Так как панель управления EBS (а в особенности вызов функции API CreateVolume) была сконфигурирована с большим таймаутом, эти медленные API вызовы начали накапливаться, что привело к голоданию потоков в панели управления EBS. В панели управления EBS есть региональный пул потоков, которые можно использовать для обслуживания запросов. Когда все эти потоки были переполнены большим числом накопившихся запросов, панель управления EBS не могла больше обслуживать API запросы и начала также отказывать API запросам из других Зон этого Региона. 21 апреля в 2:40 команда накатила изменение, которое отключало все новые запросы CreateVolume в пострадавшей Зоне, и к 2:50 уровень ошибок и задержек для всех вызовов API, относящихся к EBS, был восстановлен.

EBS кластер продолжил деградировать по двум причинам. Во-первых, узлы, которые не могли найти новые узлы, не прекращали поиски достаточно быстро, когда они не могли найти свободное место. Вместо этого они продолжали искать. Также в коде узлов EBS было состояние гонки, которое, с очень низкой вероятностью, приводило к их отказу когда они последовательно закрывали большое количество запросов на копирование. На нормально работающем кластере EBS эта проблема привела бы к небольшому числу падений узлов, если бы вообще к ним привела. Однако, во время шторма перезеркаливания количество попыток соединения было очень высоко, и эта проблема начала проявляться чаще. Узлы начали отказывать из-за этого бага, это привело к тому, что еще большему количеству дисков потребовалось перезеркаливание. Это привело к увеличению числа зависших дисков и добавило еще запросов к шторму перезеркаливания.

К 5:30 увеличилось количество ошибок и задержек для вызовов EBS API в Регионе. Когда данные с дисков должны быть перезеркалены, начинаются переговоры между экземплярами EC2, узлами EBS с данными и панелью управления EBS (которая выступает главной в этом процессе), так что только одна копия данных является первичной репликой и экземпляр EC2 распознает ее как место, куда надо слать все запросы на доступ. Это обеспечивает консистентность дисков EBS. По мере того, как все больше узлов EBS начали отказывать из-за состояния гонки, описанного выше, объем переговоров с панелью управления EBS увеличился. Так как данные не были успешно перезеркалены, число подобных вызовов увеличивалось по мере прихода новых запросов. Нагрузка привела к отказу панели управления EBS и это опять затронуло вызовы EBS API по всему Региону. В 8:20 команда начала отключать все соединения между деградировавшим кластером EBS в пострадавшей Зоне и панелью управления EBS. Несмотря на то, что это заблокировало все доступы EBS API в Зоне (мы обсудим восстановление в следующей секции), в целом задержки и уровень ошибок вернулись к нормальным для EBS API данного Региона.

Подавляющее большинство дисков деградировавшего кластера EBS все еще функционировали нормально и нашей целью было восстановить кластер без того, чтобы затронуть еще больше дисков. В 11:30 команда нашла как прекратить бессмысленные попытки серверов EBS из деградировавшего кластера EBS связаться друг с другом (в тот момент на них все равно не было свободного места), не затрагивания при этом другие важные коммуникации между узлами кластера. После того, как это изменение было произведено, кластер прекратил деградировать дальше и ушел риск того, что еще какие-то диски повиснут. Перед тем как это изменение было произведено, серверы, отказавшие по причине состояния гонки, добавили еще 5% к общему числу зависших дисков в Зоне. Однако, хотя и медленно, но перезеркаливание дисков продолжилось, по мере того как место понемногу освобождалось и некоторые зависшие диски отвисли. Общим результатом того изменения было то, что общее количество зависших дисков в пострадавшей Зоне стало 13%.

До полудня 21 апреля пользователи замечали возросшее число ошибок при попытках запустить новые EBS-бакеты экземпляров EC2 в других Зонах, не в той, которая пострадала. Это продолжалось в течение примерно 11 часов, от начала отказа до полудня 21 апреля. Кроме периодов проблем с API, описанных выше, пользователи могли создать EBS-бакеты экземпляров EC2, но количество ошибок и задержки было больше обычного. Новые запуски EBS-бакетов зависят от одного API в панели управления EBS, которое нужно для того, чтобы подключать новые образы дисков. Изначально наша система мониторинга недостаточно хорошо умела работать с этим вызовом API панели управления EBS и ошибки запусков были закрыты общей ошибкой деградировавшего кластера EBS. В 11:30 изменение в панели управления EBS починило это проблему и задержки и уровень ошибок для новых EBS-бакетов экземпляров EC2 быстро снизились и вернулись к почти нормальному уровню к полудню.

Восстановление EBS в затронутой Зоне
К 12:04 21 апреля сбой был изолирован в одной пострадавшей Зоне и деградировавший кластер EBS был стабилизирован. Во всех остальных зонах API работали хорошо и больше не было новых зависших дисков. Теперь нашей целью было завершить восстановление. Примерно 13% дисков в Зоне оставались зависшими и API EBS были отключены в пострадавшей Зоне. Основным приоритетом стало подключение и выведение онлайн дополнительных объемов для хранения данных, что позволило бы зависшим дискам найти достаточно места для создания новых реплик.

Перед командой стояло две проблемы, которые не давали подключить дополнительные объемы. Первая, когда узел отказывает, кластер EBS не будет использовать отказавший узел до тех пор, пока каждая реплика не перезеркалена успешно. Это было осознанное решение, оно нужно было для того, чтобы мы могли восстановить данные, если кластер перестает вести себя как спроектирован. Так как мы не хотели использовать отказавшие диски в других целях до тех пор пока мы не будем уверены, что мы сможем восстановить данные пользователей, оказавшиеся на отказавших узлах, команде пришлось установить много новых дисков, чтобы заменить те отказавшие диски. Это довольно долгий процесс, надо было физически собрать все лишние диски по всему восточному региону США и установить их на деградировавший EBS кластер. И вторая: так как были произведены изменения с целью уменьшить количество коммуникаций между узлами, используемые этими узлами для того, чтобы найти свободное место (что в итоге стабилизировало кластер, как описано выше) у команды были проблемы с добавлением новых дисков в кластер. Команде пришлось очень аккуратно вносить изменения в каналы коммуникации, чтобы новые серверы заработали, не загружая при этом старые запросами, которые те все равно не могли бы обслужить. Этот процесс занял больше времени, чем мы ожидали, так как нашей команде пришлось решить ряд проблем при работе с отключенными коммуникациями. Примерно в два часа ночи 22-го апреля команда смогла добавить значительные дисковые объемы и начала просматривать невыполненные запросы на репликацию. Диски консистентно восстановились в течение последующих девяти часов и все, кроме 2.2% дискового объема затронутой Зоны были восстановлены к 12:30 22-го апреля. Пока восстановленные диски полностью реплицировались, не все они мгновенно становились отвисшими с точки зрения прикрепленных экземпляров EC2, потому что некоторые из них были заблокированы, ожидая пока можно будет подключиться к панели управления EBS, чтобы можно было переподключиться к экземпляру EC2 и выбрать новую копию для записи.

После того, как к кластеру были добавлены достаточные объемы, команда начала работать над тем, чтобы настроить доступ API к панели управления EBS затронутой Зоны и восстановить доступ к оставшимся зависшим дискам. Там накопилось много запросов на смену состояний, которые надо было передать из деградировавших узлов EBS на панель управления EBS и наоборот. Это пришлось делать постепенно, чтобы это не отразилось на восстановленных дисках и на панели управления EBS. Сначала мы пытались включить API в пострадавшей Зоне путем передачи этих состояний таким образом, чтобы не перегрузить панель управления EBS. Мы также начали создавать отдельный экземпляр панели управления EBS, который был бы отделен от пострадавшей Зоны и чтобы тогда передача состояний не отражалась на других Зонах Региона. Мы быстро настроили каналы, но не смогли передать через них правильные запросы и стабилизировать систему. С вечера 22 апреля по утро 23-го мы работали над улучшением этих каналов. К утру субботы мы закончили нашу работу над отдельный панелью управления EBS и над каналами. Первые тесты трафика по направлению к панели управления EBS были успешными и вскоре после 11:30 23-го апреля мы начали потихоньку обрабатывать накопившиеся запросы. К 15:35 мы закончили настраивать связь между панелью управления EBS и деградировавшей Зоной. Это позволило большинству оставшихся дисков, которые все еще ждали ответа панели управления EBS, определить в какую именно реплику будет производиться запись, и прикрепленные к ним экземпляры EC2 могли опять их использовать. В 18:15 23-го апреля, API доступ к ресурсам EBS в пострадавшей Зоне был восстановлен.

С открытием API доступа к пострадавшей Зоне, API теперь работали во всех Зонах Региона. Восстановление оставшихся 2.2% пострадавших дисков потребовало больше ручной работы. В самом начале команда скопировала эти диски в бэкапы S3, это было сделано в качестве меры предосторожности, чтобы не потерять информацию. К тому моменту, команда закончила разрабатывать и тестировать код, который восстанавливал данные из этих копий и запустила процесс восстановления на ночь. в 12:30 24 апреля мы закончили работы с данными, которые мы таким образом могли восстановить и восстановили все, кроме 1.04% пострадавших дисков. В этот момент команда начала изучать оставшиеся диски, которые показывали хардварные ошибки, и с которых мы не могли снять копии. В 15:00 команда начала восстанавливать и их. В итоге, 0.07% дисков в пострадавшей Зоне не могли быть восстановлены в консистентном состоянии.

Последствия для Реляционных сервисов базы данных Amazon (RDS)
Проблемы возникли не только с экземплярами EC2, также был затронут реляционный сервис баз данных (RDS). RDS хранит в EBS базы данных и логи, и в результате часть баз данных RDS, хостящихся в пострадавшей Зоне, была недоступна.

Пользователи могут выбирать, работать ли им с экземплярами RDS в одной Зоне ("одна-AZ") или копировать на несколько Зон ("мульти-AZ"). Сбои в Зоне затрагивают экземпляры базы данных типа одна-AZ. В данном случае, экземпляр базы данных типа одна-AZ был бы поврежден, если завис хотя бы один из дисков EBS, на которые он ссылается. В первой пострадавшей зоне, в пике 45% одна-AZ экземпляров были затронуты зависшим вводом-выводом. Пострадавшая часть RDS несколько больше пострадавшей части EBS, потому что экземпляр базы данных RDS может использовать несколько дисков EBS. Это увеличивает суммарную пропускную способностью ввода-вывода базы данных в нормальных условиях, но это же и означает, что зависший ввод-вывод на одном любом диске базы данных типа одна-AZ может сделать ее нерабочей до тех пор, пока диск не восстановлен. Процент зависших баз типа одна-AZ в пострадавшей Зоне постепенно уменьшался по мере восстановления EBS. Процент зависших экземпляров базы данных типа одна-AZ в пострадавшей Зоне снизился до 41.0% через 24 часа, до 23.5% через 36 часов, до 14.6% через 48 часов. В течение выходных все восстановилось до конца. Несмотря на то, что мы восстановили практически все пострадавшие базы данных, 0.4% экземпляров баз данных типа одна-AZ в пострадавшей Зоне располагались на диске EBS, который восстановить было нельзя. Для этих баз данных пользователи, у которых автоматический бэкап был включен (а он включен по умолчанию), имели опцию начать восстановление базы данных из бэкапа.

Базы данных типа мульти-AZ более устойчивы к сбоям, поскольку синхронно копируют данные между двумя репликами базы данных в различных Зонах. В случае, если первичная реплика недоступна, RDS автоматически это определяет и переключается на вторичную реплику. 2.5% экземпляров баз данных типа мульти-AZ в восточном регионе США не смогли автоматически переключиться, после того как завис ввод-вывод. Основной причиной этого было то, что отключение сети (той, что соединяла первичную от вторичную реплики) и произошедшее сразу после этого зависание ввода-вывода на первичной реплике вызвали к жизни ранее не замеченный нами баг. Этот баг оставлял первичную реплику в изолированном состоянии, в таком случае наш мониторящий агент не мог безопасно переключиться на вторичную реплику без риска потери данных, здесь требовалось вмешательство человека. Сейчас мы активно работаем над починкой этого бага.

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

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

Эффект на несколько Зон
EC2 предоставляет два важных базовых блока доступна: Регионы и Зоны. Согласно дизайну, Регионы совершенно отдельные инсталляции нашей инфраструктуры. Регионы полностью изолированы друг от друга и предоставляют самый высокий уровень независимости. Многие пользователи используют несколько Регионов EC2, чтобы получить устойчивость к ошибкам самого высокого уровня. Однако, если вы хотите переместить данные между Регионами, вам надо делать это самостоятельно с помощью ваших приложений, так как мы не копируем данные между Регионами по запросам пользователей. Вы также должны использовать различные наборы API для управления каждым Регионом. Регионы являются важными базовыми единицами доступности для пользователей, но со стороны разработчиков приложений требуются дополнительные усилия, чтобы использовать преимущества этой изоляции. Мы предоставляем Зоны внутри Регионов, чтобы помочь разработчикам легко строить приложения, устойчивые к ошибкам. Физически и логически инфраструктуры Зон отделены друг от друга, таким образом, чтобы они были независимыми и при этом предоставляли пользователям высокоскоростную сеть с низкой латентностью, простые пути репликации данных и полный и непротиворечивый набор управляющих API. Например, с приложений, запущенных внутри Региона, пользователи могут снимать EBS снэпшоты, которые могут быть восстановлены в любой Зоне и могут программно манипулировать EC2 и EBS ресурсами используя одинаковые API. Мы предоставляем эту слабую связность, потому что она позволяет пользователям легко строить высоконадежные приложения.

Случившиеся привело к двум последствиям. Во-первых, это отразилось на приложениях, запущенных в пострадавшей Зоне, потому что пострадавшие диски EBS зависли. Архитектура сервисов EBS устроена таким образом, что влияние на запущенные образы было ограничено Зоной. В результате пользователи, которые пишут свои приложения таким образом, чтобы использовать несколько Зон, практически ничего не заметили. Некоторые пользователи сообщали, что у них зависли диски EBS в других Зонах, не в той, которая пострадала в четверг. Наша система мониторинга явно показывает эффект шторма перезеркаливания на панели управления EBS и на дисках в пострадавшей Зоне, она не показывала значительного влияния этого на диски EBS в других Зонах Региона. Хотя мы действительно видим, что в не пострадавших Зонах было чуть больше зависших дисков чем обычно, но все равно это очень малое число. Пиковое значение зависших дисков в процентах, которое мы видели в Регионе за пределами пострадавшей Зоны было менее 0.07%. Мы расследовали число это зависших дисков. Чуть большее, чем обычно, число зависших дисков в этих не пострадавших зонах было вызвано задержками в восстановлении из нормального перезеркаливания, потому что возросла латентность и возросло число ошибок в панели управления EBS, как это описано выше; всегда есть какое-то число процессов перезеркаливания в каждый момент времени. Также мы думаем, что работа, описанная ниже, направленная на то, чтобы изолировать панель управления EBS, сможет предотвратить даже такой, не намного больше, чем обычно, уровень ошибок, если случится что-нибудь подобное.

Хотя приложения пользователей, которые использовали преимущества архитектуры нескольких Зон (мульти-AZ), не пострадали от этого сбоя, проблемы с панелью управления EBS повлияли на возможность создавать диски EBS в Регионе и управлять ими. Одно из преимуществ EC2 - это возможность быстро заменять сломанные ресурсы. Когда панель управления EBS деградировала до такого состояния, что стала недоступна, пользователям с пострадавшими дисками стало сложно заменять их диски или загруженные с EBS образы в других, здоровых, Зонах. Наша главная задача - предотвратить подобное в дальнейшем.

Несмотря на то, что мы предоставляем нашим пользователям определенный уровень слабой связности, нашей целью было сделать Зоны неотличимыми от совершенно независимых. Наша панель управления EBS разработана таким образом, чтобы пользователи могли иметь доступ к ресурсам в нескольких Зонах, при этом быть устойчивыми к ошибкам в отдельных зонах. Это событие показало нам, что мы должны и в дальнейшем работать над достижением этой цели. Мы сделаем три вещи, которые предотвратят влияние отдельных Зон на панель управления EBS нескольких Зон. Первое, что мы сделаем, - мы немедленно улучшим нашу логику таймаутов, чтобы предотвратить исчерпание потоков, когда один из кластеров в Зоне слишком долго обрабатывает запросы. Это могло бы предотвратить проблемы с API c 0:50 до 2:40 21 апреля. Чтобы решить вторую проблему, возникшую с API, мы добавим к нашей панели управления EBS возможность знать больше о Зонах и разумно сбрасывать лишнюю нагрузку, когда превышена максимальная нагрузка. Подобное уже есть в нашей системе. Также мы хотим перенести кое-что из нашей панели управления EBS в наши сервисы кластеров EBS. Перенеся часть функциональности из панели управления EBS и развертывая эти сервисы на кластерах EBS (которые работают в той же Зоне, что и кластер EBS, который они поддерживают), мы сможем предоставить лучшую изоляцию Зон от панели управления EBS.

Упростить использование преимуществ нескольких Зон
Мы также намерены упростить возможность использования нескольких Зон. Во-первых, мы предложим несколько Зон для всех наших сервисов, включая виртуальное приватное облако Amazon (VPC). Сегодня пользователи VPC имеют доступ только к одной Зоне. Мы пересмотрим наших планы и дадим пользователям VPC доступ к нескольким Зонам как можно быстрее. Таким образом пользователи VPC смогут строить приложения с выским уровнем доступности используя несколько Зон, точно так же как это EC2 пользователи, не использующие VPC.

Также мы обнаружили, что нам следуем упросить процесс выкатывания приложений на мульти-AZ. Некоторые приложения пользователей (или значительные части этих приложений, например, базы данных), выкладываются только в одной Зоне. Образы других приложений рассредоточены по нескольким Зонам, но все же имеют единые точки отказа в одной Зоне. В таких случаях расходы на оперирование могут негативно сказаться на досупности приложения, в то время как при правильном процессе выкладки на несколько зон приложение должно продолжать работать как будто ничего не случилось. Мы предоставим пользователям более хорошие средства работы по созданию мульти-AZ приложений, и падение всей Зоны целиком не отразится на доступности приложений. Мы знаем, что должны помочь пользователям разрабатывать их приложения используя обычные паттерны проектирования. В данном случае, некоторые пользователи серьезно пострадали, в том время как у других какие-то ресурсы пострадали, но при этом на их приложениях это практически никак не отразилось.

С тем, чтобы продолжить более тесно работать с нашими пользователями и партнерами над лучшими практиками архитектуры в облаке, мы организуем ряд вебинаров стартуя со второго мая. Первая тема, которую мы затронем, будет "дизайн приложений, устойчивых к ошибкам", "архитектура в облаке", и "лучшие практики веб-хостинга". Мы собираемся добавить больше тем в течение ближайших недель и мы продолжим делать это часто и постоянно. В течение ближайших двух недель вебинары будут проводиться по нескольку раз за день для наших пользователей, работающих в различных часовых поясах. Отдельно мы проведем значительное количество вебинаров, посвященных ответам на ваши вопросы. Также будут организованы дискуссии для наших пользователей и партнеров. Это вебинары, а также серия статей по лучшим практикам дизайна архитектуры для AWS облака, доступны на нашем AWS сайте в разделе Архитектура. Мы также продолжим предоставлять дополнительные сервисы такие как S3, SimleDB и мульти-AZ RDS, которые предоставляют автоматическую балансировку для мульти-AZ таким образом, что пользователи могут получать пользу от нескольких Зон не делая ничего особенного сложного в их приложениях.

Сделать восстановление быстрее
Мы займемся над улучшением визуализации, контроля и автоматизации восставновления дисков в кластере EBS. У нас есть набор утилит для управления кластером EBS, но те утилиты, что наша команда использовала для восстановления кластера, будут встроенны напрямую в узлы EBS. Мы также автоматизируем модели восстановления, которые мы использовали для восстановления различных дисков. Это бы сэкономило нам много времени во время восстановления. Мы также посмотрим что можно сделать, чтобы диск продолжал функционировать в периоды деградации кластера, включения возможность снимать полную копию с зависшего диска. Если бы у пользователей была такая возможность, они могли бы гораздо проще восстановить их приложения в других Зонах Региона.

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

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

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

Компенсация пострадавшим пользователям
Пользователям, у которых в пострадавшей Зоне были диски EBS или базы данных RDS, вне зависимости от того, пострадали ли их ресурсы и приложения или нет, мы предоставляем десятидневный кредит равный 100% использования их дисков EBS, образов EC2 и баз данных RDS, которые были запущены в затронутой Зjне. Эти пользователи не должны ничего делать, чтобы получить этот кредит, он будет автоматически включен в их следующий счет AWS. Пользователи могут узнать, будет ли им предоставлен этот кредит или нет, залогинившись в их аккаунт AWS.

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

Искренне ваша,
команда AWS

Ссылки по теме:
Amazon Elastic Compute Cloud
Retrospect on recent AWS outage and Resilient Cloud-Based Architecture
Почему в конце декабря не работал Skype
Facebook - More Details on Today's Outage - про отключение Фейсбука в сентябре 2010.

Радио-Т 238

2011-05-09T22:44:00.002+04:00

Внезапно поучаствовала в подкасте Радио-Т. Выпуск 238.

- Алён, приходи к нам!
- Эмм, ну хорошо, давай...
- Отлично, ты в эфире через полчаса!

На мой взгляд, самое интересное там - это рассказ Umputun'а про использование Protocol Buffers.

Inception in C

2011-04-18T10:16:00.002+04:00

via Moriarty

Доклад Handling ridiculous amounts of data with probabilistic data structures

2011-03-16T22:11:00.002+03:00

Полное название доклада PyCon 2011: Handling ridiculous amounts of data with probabilistic data structures. Но вообще это об использовании фильтра Блума в биоинформатике. Всего 20 минут.

Начались продажи iPad2

2011-03-12T11:21:00.003+03:00

Пока в Москве была ночь... у нас тут был день! И начались продажи iPad2.

Мой коллега Артём не поленился сходить в соседний магазин и заснять толпы людей, алчущих iPad2.

Очередь.

Видео с куском очереди.

Все апплодируют

Артёму спасибо :-)

Критика boost::serialize

2011-02-25T23:43:00.002+03:00

boost::serialization hell - эмоциональный пост про проблемы, возникающие при использовании boost::serialize.
Будет полезно тем, кому в проекте нужна сериализация и кто рассматривает boost::serialize как один из вариантов.

Baidu maps

2011-02-21T09:43:00.000+03:00

Китайский Baidu - один из национальных поисковиков, который обходит Google по популярности. Точно также Яндекс популярнее Google в России.
И у Baidu есть свои карты. И они стоят того, чтобы на них взглянуть.

(via @igrigorik)

Статья про управление памятью

2011-02-20T10:55:00.002+03:00

Alternatives to malloc and new - статья про то, как происходит аллокация памяти, как и почему это ведет к фрагментации. И про то, как можно с этим бороться - управлять памятью самостоятельно. Всё с красивыми и понятными картинками.

Это актуально в разработке игр, например.

Статьи по теме:
Virtual Addressing 101
Start Pre-allocating And Stop Worrying
Region-based memory management

Компьютер IBM играет в "Свою игру"

2011-02-15T09:22:00.003+03:00

И неплохо играет, кстати. В комментариях на YouTube часто вспоминают SkyNet :-)

Вся игра целиком здесь.

via dirty.ru

Статья с сравнением ++it и it++

2011-02-14T08:05:00.002+03:00

В статье Есть ли практический смысл использовать для итераторов префиксный оператор инкремента ++it, вместо постфиксного it++ Андрей Карпов ставит эксперименты с префиксными и постфисными операторами.

Про работу в Майкрософт

2011-01-25T08:24:00.002+03:00

Вопросы по поводу моего устройства в Майкрософт поступают со страшной силой, давайте я расскажу об этом что ли.
Самый часто задаваемый вопрос "Как ты попала в Майкрософт?". Майкрософт летом проводил собеседования в Москве. Я прошла сначала телефонное интервью, потом очное. Также меня спрашивают "было ли сложно?". Прямо даже и не знаю как ответить на этот вопрос. Я пришла, мне задали какие-то вопросы, я на них как-то ответила, потом мне прислали job offer. Вроде несложно :-).

Примеры вопросов можно найти поиском по "Microsoft interview questions". Их там будет много.

Оформление визы, перевозка специалиста (это называется relocation), адаптация специалиста на месте - процесс давно обкатанный. Всё тут хорошо, короче говоря.

Работаю я в городе Бельвью, он находится рядом с Сиэттлом. Сижу в здоровом высотном здании. Работаю в команде Bing Advertising, это контекстная реклама. Программирую на С++. :-)
Меня спрашивали отдельные ли у нас офисы. В основном да, отдельные. Но есть те, кто сидит по двое, я сижу вдвоем с китайцем. Веселый такой парень. Еще видела одну комнату где сидят человек шесть.

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

Для специалистов с опытом вакансии можно найти на careers.microsoft.com. Его читают, на резюме реагируют. ~~Вот вакансии моей группы: раз, два и три.~~ (Updated 16.6.2011 - все эти вакансии закрыты, но есть другие)

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

Для выпускников
Microsoft проведёт очередной набор студентов и выпускников из России, Беларуси и Украины.

Для студентов есть программа стажировки (internship). Поговорила с теми, кто проходил по этой программе, народ доволен. Им оплачивали переезд и платили нормальные деньги во время работы (часто стажерам либо вообще не платят, либо платят смешные деньги). Вполне себе реально приехать по этой программе иностранному студенту, российскому студенту в том числе. Вроде еще не поздно подаваться на этот год (лето 2011).

Есть еще Microsoft JobsBlog, там бывает полезная информация про прохождение собеседований.

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

P.S. Я не буду плодить кучу постов, а по результатам вопросов буду дописывать сюда. И еще фоток кину.

Bufferbloat

2011-01-23T19:41:00.001+03:00

Новый термин bufferbloat появился с легкой руки Джима Гетти (Jim Getty) после серии постов на его блоге в декабре 2010 - январе 2011.
The criminal mastermind: bufferbloat!
Whose house is of glasse, must not throw stones at another.
Bufferbloat in 802.11 and 3G Networks
Там рассказывается о том, что буферизация данных в Интернете приводит к латентности, которой быть не должно. И наши интернеты не так быстры как могли бы быть. И ситуация медленно меняется к худшему.
Плохо это, например, тем, что такие сервисы как Skype не могут качественно работать при такой латентности.

bufferbloat (and a Net Neutrality rant in the footnotes) - пост другого автора на эту же тему, рассказывает о том как эту проблему можно частично решить. Интересен еще и тем, что там упоминается программа написанная русским гениальным программистом. Это приятно.

via Maniac

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

Приняла участие в подкасте Радио Т

2011-01-16T07:00:00.003+03:00

На подкасте Радио Т номер 222 поговорили о языках программирования вообще и о C++ в частности.
Размышления на тему судьбы языка С++ стали особенно актуальны после недели ненависти к С++ на Хабрахабре.

Почему в конце декабря не работал Skype

2011-01-04T07:12:00.002+03:00

Объяснение от разработчиков CIO update: Post-mortem on the Skype outage

Объяснение объяснения от разработчиков Understanding Today's Skype Outage: Explaining Supernodes

via highscalability.com

Ссылки по теме:
Архитектура Skype

Лучшее за 2010 год

2010-12-31T23:35:00.002+03:00

Традиционное подведение итогов прошедшего года. Статьи, которые больше всего читали и на которые больше всего ссылались.

Итак, наш победитель.... барабанная дробь... Выступление Эда Катмулла, президента Пиксара! Оно собрало огромное количество ссылок и уверенно держалось в топах в течение всего года.

Философский пост Хорошо там, где нас нет впечатлил многих. Каждый нашел в нем что-то о себе, люди цитируют разные куски.

Интервью проекту Open Quality и Временные оценки в программировании во многом перекликаются. Они также были популярны.

Интерес вызвали Неделя борьбы с велосипедизмом и запись доклада по ИИ в играх.

Из старенького стабильно популярны Хорошие книги по С++ для начинающих и Своя Компания. Еще народ продолжает рисовать графы.

У меня год выдался неспокойный. У меня появился твиттер, я выступила на ADD-2010. И под самый конец года переехала в Редмонд и с нового года приступаю к работе в компании Майкрософт, буду программировать на С++ в Bing Advertising Team.

Всех с Новым Годом, дорогие друзья!
Пусть ваши выступления на конференциях будут также популярны как выступление Эда Катмулла.
Пусть Ваша Компания будет создана и начнет процветать, а Своя Игра будет дописана.
Пускай временные оценки будут соответствовать действительности, а менеджеры будут спокойными и довольными.
Пусть вам будет хорошо где бы вы ни были.

Оставайтесь с нами :-)

Ссылки по теме:
Лучшее за 2009 год
Лучшее за 2008 год

Книга Exploiting Online Games

2010-12-21T21:20:00.000+03:00

Книга Exploiting Online Games попала ко мне в руки случайно. Я ее прочитала, она мне не понравилась, давайте расскажу почему.

Первые четыре(!) главы книги посвящены пространным размышлениям о том, что хачить нехорошо, а также рассказам о софтверных лицензиях. Читателям, дожившим до пятой главы, дается скупая и щедро разбавленная водой информация, которая как-то относится к теме книги. Также присутствует много отсылок к другим книгам тех же авторов.
Анализа и систематизации информации нет. Причем в большинстве случаев они говорят о WoW, книгу надо было назвать "Как наверное можно похачить WoW".
Эта одна из тех редких книг, из которых мне не удалось узнать вообще ничего нового. Что там есть вообще: у нас есть клиент, он обменивается данными с сервером. Теоретически, можно влезть в клиента, там есть интересная информация о состоянии мира. Можно слать на сервер свои данные. Можно написать бота. По большому счету это все содержимое книги.
Видимо, чтобы книга была толще, туда добавлена базовая информация по языку ассемблера и про DLL injection.

Совершенно непонятно для кого это все написано. Для читера она бесполезна, потому что там нет примеров типа "мы сделали то-то и то-то, получили такой-то результат". Читателю просто бросается какая-то мысль или кусок кода и... всё. Это порождает кучу вопросов. Чего дальше-то было? Оно заработало вообще? Что сказал Warden? Как быстро был закрыт аккаунт?

Для разработчика она бесполезна, потому что разработчик и так знает, что на клиенте много информации и что ее можно вытащить. И что читеры существуют и что ловить их по-одному - дурацкое занятие. Разработчику нужно вообще другое. Мне бы было интересно почитать о паттернах, по которым читеров можно распознать по статистике. Ведь если у одного игрока морковка начинает всходить вдвое быстрее, чем у всех остальных, это же видно хорошо... О реальных нетривиальных случаях читерства, о том, как с ними боролись. О статистике по читам. Что пытаются делать чаще, от чего потери больше.
О том, что вообще с этим делать. Как бороться с читерами, избегая таких сомнительных решений как Warden? Ведь Warden, будем откровенны, это же явное spyware. Как бороться так, чтобы ни в коем случае не обидеть честных игроков? Как держать читеров под контролем?
Как распознать бота? Если у нас игрок уже 24 часа бьет куриц, 1exp за курицу, как понять кто это - бот или усердный корейский студент? Может вывести ему сообщение "Курицы дарят вам 1000exp и просят оставить их в покое" с кнопками "Принять" и "Не принимать" и посмотреть за реакцией?
Большинство проблем происходит из-за того, что приходится доверять клиенту, ведь часть информации хранится на клиенте. Как снизить доверие к клиенту? Можно ли убрать оттуда часть информации? А всю можно? Проводились ли исследования в этой области? Возможны ли решения типа OnLive, когда игроку выдается только видеопоток?

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

Ссылки по теме:
Слайды, в которых есть много информации из этой книги

Я хочу программировать игры! Что мне делать?

2010-12-13T18:20:00.003+03:00

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

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

-Алёна, давай ближе к делу! Лесом ситуацию в индустрии, программить уже давай!

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

-Я поставил себе Visual C++ 2010? Я все правильно сделал?

Если вы работаетет с Windows, то да, лучше Visual C++ и лучше версию поновее. Про разработку игр под Линукс я не в курсе...

-DirectX или OpenGL?

Это зависит... На Windows в основном используется DirectX. Но это вовсе не значит, что OpenGL никому не нужен. На консолях встречаются графические API, сильно похожие на OpenGL, ну и под Линуксом никакого DirectX нет.

-Так все-таки, DirectX или OpenGL?

Ставьте DirectX. :-)
Только DirectDraw смотреть не нужно, им никто не пользуется.
В DirectX есть очень хорошие хелпы и примеры, не игнорируйте их.

-У меня ничего не работает, ничего не компиляется!

Вы не одиноки. Поищите ваши ошибки Гуглом, наверняка найдете таких же несчастных.

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

-Да ну, там все по-английски...

Надо учить английский. На русский переведено мало и для работы этого недостаточно.
Как обычно, Google is your friend. Вот что выдает нам поиск по запросу game programming lectures.
Game Programming 2007
CSE 191: Video Game Programming Seminar
Обзор книг по программированию игр я делала здесь. И вот еще открытые исходники игр.

-Правда, что все игры разрабоатываются на С++?

Игры разрабатываются не только на С++. Активно используются также:
Python, Lua - Для скриптования игровых движков. Также для скриптования могут использоваться языки, специфичные для данного движка. Например, UnrealScript.
C# - утилиты. Очень любим, потому что С++ программистам с ним легко разобраться.
C#, Java - серверная часть MMO.
Java - используется на мобильных платформах
HLSL - используется для программирования шейдеров

Знание С++ не то чтобы обязательно, но он в разработке игр используется очень активно и с ним жизнь упрощается.

-Что такое игровой движок? У меня уже есть DirectX. Это что, не движок?

DirectX работает на уровне "нарисовать треугольник". Игровой движок поднимает вас на уровень выше, здесь будут "объект с трехмерной моделью и поведением", "вода" и т.п.

Игровые движки бывают разные. Например, может быть только графический движок, но без физики. Вы тогда можете писать физику сами или подключить какой-нибудь движок физики. Также отдельно может идти AI движок.

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

Примеры бесплатных движков:
OGRE (Altren в комментариях настаивает, что в OGRE только графика и ничего другого там искать не надо), Irrlicht - игровые движки, графика там в основном, насколько я помню
ODE - движок физики

Игра - это не только DirectX, не только графика. Если вас интересует устройство на работу в качестве разработчика игр, то посмотрите вакансии игровых контор, посмотрите чего они хотят и вам станет понятнее чего учить (Epic games, id Software).

Вот примеры специализаций игровых программистов, с описанием чего надо знать по каждой специализации. Это роли могут различаться, всё-таки всё сильно зависит от конкретной платформы и компании.

Graphics programmer - программист графики. Здесь нужно знание математики (векторы, матрицы, кватернионы). Понимание того, как работают видеокарты, шейдеры.
Physics programmer - программист физики. Нужны довольно специфичные знания физики, ну и математика тоже.
AI programmer - программист искусственного интеллекта. Алгоритмы на графах (A*, Дийкстра), конечные автоматы...
Gameplay programmer, game mechanics programmers - программист игровой механики. Эта роль вызывает больше всего непонимания. Это те программисты, которые пишут в игре всё остальное. Изменение параметров при попадании одного юнита в другого, отображение этого всего в интерфейсе, подгрузка следующего уровня. Куча вот таких мелочей.
Interface programmer - разработчик интерфейсов.
Network programmer - сетевой программист. Нужны стандартные знания по разработке сетевого кода.
Tools Programmer - разработчик утилит. При разработке игры используют дополнительные программы, которые иногда пишутся самостоятельно, иногда покупаются вместе с движком. Пример игровой утилиты - редактор уровней.

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

Для начала не пытайтесь написать игру с нуля. Модифицируйте чужой код, пишите моды.

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

-Да, у меня есть отличная идея MMORPG!

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

-Алён, ты что, шутишь?

ОК, пусть это будет RPG, без MMO. Один, маленький уровень, как можно меньше деталей. Попробуйте получить минимальную играбельную версию.

-Алёна, у меня еще куча вопросов!

Постараюсь ответить. Но не могу обещать, что отвечу на все :-).
Ахинею про то, о чем не знаю, писать не буду. Спрашивайте в комментариях.

Ссылки по теме:
AIGameDev
Вопросы по программированию ИИ в играх

Выложили записи моих докладов с ADD-2010

2010-12-08T19:14:00.014+03:00

Организаторы потихоньку выкладывают записи докладов с ADD-2010, мои уже выложили.

Первый доклад, Искусственный интеллект в играх
Про нечестные приемы, про поиск пути и навигацию.

218-Games-AI-add-2010.avi from Stas Fomin on Vimeo.

Материалы, которые я использовала для подготовки к докладу:
It's not fun if you fake it. Rigged gameplay mechanics are starting to piss me off.
The Pure Advantage: Advanced Racing Game AI
18 Embarrassing Game AI Bugs Caught On Tape... and Fixed!
OpenSteerDemo
The psychology of randomness
WeightedDecayRand
GDC 2010 Keynote Address: Sid Meier
Theta*: Any-Angle Path Planning for Smoother Trajectories in Continuous Environments
Near-Optimal Hierarchical Pathfinding (HPA*)
Сравнение алгоритмов поиска маршрутов в StarCraft и StarCraft 2
There's a Hole in Your NavMesh, Dear Zombie

Второй доклад, C++0x
Я не рассчитала время, доклад получился коротким. Первратим это в плюс.
Короткий, но насыщенный доклад про C++0x! Всего на 25 минут, а если вопросы не слушать, то и того меньше!

225-C0xx-add-2010.avi from Stas Fomin on Vimeo.

Updated 09.12.2010:
Во время доклада был задан вопрос, почему для атрибутов нельзя использовать слово final вместо [[final]]. Там были высказаны предположения, но ответ так и не был дан.
Отвечает Герб Саттер.
Для это пришлось бы использовать контекстный парсинг, а делать это не хотелось, потому что нигде до этого в языке это не использовалось. Но все-таки они решили сделать именно так. И final будет просто final, без каких-либо скобочек.
/Updated

Материалы, которые я использовала для подготовки к докладу:
C++0x features and their support in popular compilers
Initializer List proposed wording
Compile-time 'String' Manipulation with Variadic Templates
C++0x: An overview, by Bjarne Stroustrup
C++0x FAQ
C++0x Core Language Features In VC10: The Table
Summary of C++0x Feature Availability in gcc and MSVC
C++0x. Лямбда-выражения
C++0x lambda

P.S. Лучше все это смотреть в HD и на полный экран

Неделя неслыханной щедрости

2010-12-01T17:05:00.006+03:00

На днях я решила куда-нибудь потратить завалявшиеся у меня на WebMoney деньги и мне в голову пришла светлая мысль. Я много пользуюсь бесплатными программами и ресурсами, но довольно редко делаю им пожертвования. Вечно то лень, то карточка просрочена, то еще чего. Поэтому я решила отвести под это дело отдельный период времени - пускай это будет первая неделя декабря, раз в год можно себя на это сподвигнуть. Предлагаю вам ко мне присоединиться. Приблизить, так сказать, наступление светлого завтра, где правят Разум и Справедливость.

В сегодняшнюю раздачу слонов попали.

Wikipedia
О, неисчерпаемый источник полезной информации. Именно оттуда я узнала, что средняя скорость ленивца два метра в минуту, а когда опасность, то и все четыре. Что энергетический бюджет нашей планеты - 174 петаватта. Что Поль Брэгг умер от сердеченого приступа, а вовсе не утонул.
К тому же там в последнее время появился громадный баннер, Джимми Уэйлс смотрит с него большими печальными глазами и просит денег.
650 рублей Википедии. Баннер после этого никуда не исчез, правда :-)
Donate to Wikipedia

Firefox и Thunderbird - давно пользуюсь этими двумя софтинами. Firefox здоровый, у него течет память (или уже починили?) и я с него все пытаюсь на что-нибудь перелезть, но он служил мне долгие годы.
Отдельно на софтину пожертвовать нельзя, можно перевести пожертвования Mozilla Foundation. Суммы фиксированы. Я выбрала 25 долларов. И они обещают прислать плюшевого дракончика!
Donate to Mozilla Foundation

WinRAR
Отличный архиватор, и он не бесплатный. Лицензия стоит 29 у.е.
Купить WinRAR

Tortoise SVN
Лучший клиент к Subversion под Windows. Пользуюсь много лет, довольна.
Там можно сделать подарок каждому разработчику индивидуально через Амазон, я сначала так и хотела сделать. Но у меня не получилось, вы не поверите. То "мы это не можем доставить", то "не факт, что в регионе получателя этот диск будет играть". Ну нафиг.
Так что просто 10 долларов им перевела.
Donate to Tortoise SVN

Inno setup
Самая лучшая программа создания дистрибутивов под Windows. А я много какие пробовала. Простая, понятная, без дурацких разноцветных кнопочек и может все.
5 долларов
Donate to Inno setup

Были некоторые проекты, которым я хотела дать денег, но не нашла как. Это WireShark, причем у них в рассылке был по этому поводу вопрос, на него никто не ответил. Это Far Manager, и это GCC.

И помните - никогда не поздно поддержать неделю неслыханной щедрости. :-)

Updated:
Меня тут спросили а как поддерживать-то?
Напишите в каком-нибудь твиттере, что это хорошая идея и дайте ссылку.
Напишите, что это глупая и бесполезная затея и дайте ссылку.
Сделайте donation и напишите об этом у себя в блоге и... дайте ссылку
Сами придумайте еще чего-нибудь.

Временные оценки в программировании

2010-11-15T22:02:00.004+03:00

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

Но мы не такие! Мы решаем проблемы, а не ищем виноватых. Мы ищем способ, а не причину. Мы не жалуемся на Злую Судьбу, Законы Вселенной и не вздыхаем обреченно "оно всегда так".

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

Итак, как обычно происходит оценка сроков? Вот очень распространенный сценарий. Программиста спрашивают "сколько времени этой займет?" Ответ ожидается прямо сейчас, у программиста есть несколько секунд на раздумья. У него в голове возникает некий срок. Пускай будет "три недели". При этом программист отбрасывает время, нужное для отладки, учитывается только время кодирования. Потом внутренний голос говорит ему "Ты же крут! Какие три недели! За две справишься!". "Две недели" - отвечает программист. После этого начинается торг. Менеджер пытается уменьшить уже сильно заниженный срок. В итоге они сторгуются на неделе. Это просто какой-то срок, взятый с потолка, который выполнен не будет.

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

Увы, я не знаю волшебных заклинаний и HOWTO как всегда со стопроцентным попаданием рассчитывать сроки. Но есть несколько известных мне приемов, которые ситуацию с оценкой сроков улучшают значительно. Я их все использовала, опробовала на себе. Все они требуют активного сотрудничества между менеджером и программистами. Если такого сотрудничества нет, попробуйте делать временные оценки для себя. Это полезный навык, может потом пригодиться.

Оценка времени программирования задач в часах
Этот способ рекламировал Джоэл Спольски у себя в блоге. Там вы найдете его подробную статью об этом: Evidence Based Scheduling. Разбиваем задачу на подзадачи, оцениваем время каждого этапа в часах.
Если вы привыкли брать сроки с потолка, то оценки по этому методу будут получаться пугающе большими. Это нормально.

Временные отсечения
У нас есть задача, требующая определенных исследований. Наши программисты ни разу такое не делали. И вообще не представляют как это делать. Мы начинаем исследование и бросаем его в определенный срок. Например, 20 мая. Если до этого времени не успели - все. Даже если "почти все готово", даже если "вот сейчас заработает". Откатываемся к предыдущей версии. Беремся за следующую задачу.

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

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

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

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

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

Интервью на OpenQuality.Ru

2010-11-13T12:01:00.006+03:00

На OpenQuality.Ru сейчас публикуются интервью с программистами о разработке софта. Много спрашивают про обеспечение качества.

Пока там всего два интервью. Моё и Александра Дёмина, автора блога Программирование - это просто. У него там есть интересное про организацию работы в Блумберге.

Статьи про рендеринг в Старкрафт 2

2010-11-12T11:40:00.003+03:00

"...вашему вниманию предлагается реверс инжиниринг рендера всем известной игры Старкрафт 2, от не менее известной компании Близзард."
Старкрафт 2: Секреты технологий
Старкрафт 2. Рендер роликов

via lightypp

Впечатления от работы с игровыми консолями

2010-11-09T18:38:00.005+03:00

Меня тут в комментариях как-то просили рассказать о моих впечатлениях от работы с консолями, вот оно.

Пара слов о том, какие бывают игровые консоли. Есть те, которые надо подключать к телевизору, по-русски они обычно называются "приставки". Сейчас наиболее популярны три из них: Microsoft XBOX 360, Sony PS3, Nintendo Wii. Причем Wii всех рвет по продажам.

Есть консоли со своим собственным экраном, самые известные - Nintendo DS и Sony PSP.

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

Архитектура
Пришлось работать с довольно странной архитектурой, это непривычно. На консолях любят big endian. Что создает, хм, некоторые проблемы, если вам хочется двоичные данные с PC перенести на консоль. А вам этого захочется, потому что у вас все дизайнеры уровней сидят на PC.

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

В целом приходится сидеть сильно ближе к железу и вот здесь хорошо себя проявляет С++. Здесь вы можете и данные разложить как вам надо, и с полиморфным наследованием поработать.

Огромный плюс - консоли везде одинаковые. Например, у вас нет зоопарка видеокарт, как на PC, которые это поддерживают, это не поддерживают, а вот тут у нас драйвер устаревший... И это прекрасно.

Контроль качества
В играх под PC сложилась такая нехорошая практика - сразу после выхода игры выходит пачка патчей. Здесь с патчами все сложно. Либо их нет совсем, либо их довольно сложно и неудобно выпускать. При этом, если вы играли в игры на консолях, то, возможно, обращали внимание, крэш игры - это что из ряда вон выходящее. Да и вообще багов не видно.
Потому что тут существует Контроль Качества. Вам не удастся себя уговорить, что "и так сойдет" и "никто не заметит". По ту сторону вас ждет не пользователь, которому, в принципе, можно навешать лапши на уши, а платформодержатель. И стоит он насмерть.

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

Закрытость
Вы не можете задать вопрос в коммьюнити размером с целый мир. У вас есть закрытый форум или список рассылки, это вам не stackoverflow. Особого выбора библиотек тоже нет. Радуйтесь тому, что есть.

Ссылки по теме:
Про консоли
Updated 01.12.2010
Kill the Gatekeepers

Electronic Arts приоткрыла EASTL

2010-10-22T18:36:00.000+04:00

EA открыла немножечко исходников, в том числе EASTL. Насколько я понимаю, далеко не весь.
Чтобы не мучаться и не искать EASTL в этих исходниках самим, можно его посмотреть вот здесь: EASTL.

Там есть аппетитно выглядящие ссылки типа Sims 3, но исходников симов там нет, увы.

В 2007 году у меня был пост про EASTL, где я сказала следующее

Если будут какие-нибудь свободно доступные реализации EASTL, интересно было бы их опробовать.

Прошло три года и счастье наступило. Хотя, когда именно произошло это событие, я не знаю. Никаких официальных пресс-релизов я не вижу. Судя по всему, EA сделала свою версию WebKit, который под LGPL, и ей пришлось выложить исходники, куда попала часть EASTL.

Ссылки:
EA STL released, updated benchmarks - здесь я узнала об этой новости. Как видно из заголовка, там в статье есть бенчмарки

Есть чем заняться на выходных :-).

Доклад Сюзанны Гилдерт о квантовых компьютерах

2010-10-17T00:06:00.004+04:00

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

Доклад лучше смотреть где-то с 3:46, там вначале они проверяли связь и прочее, не понимаю почему не отрезали. Сам доклад около часа, потом вопросы еще на час.
Сюзанна - физик-экспериментатор, специализируется на квантовых устройствах. Работает в компании D-Wave. Которая, помнится, много чего обещала. По слухам, они чего-то с Гуглом мутят.

Ссылки по теме:
Блог Сюзанны
Training a Binary Classifier with the Quantum Adiabatic Algorithm

Отчет об ADD-2010

2010-09-28T18:51:00.004+04:00

Итак, 23-24 сентября прошла конференция ADD-2010, на которой я выступала с двумя докладами. Давайте я расскажу как все прошло, начну с себя, любимой.

Первым в расписании стоял доклад "Искусственный интеллект в играх". Доклад прошел бодро, отзывы в целом хорошие. Плохо было видно мой видеоролик, его можно посмотреть здесь. Это видео из библиотеки OpenSteer, поэтому лучше прямо на их сайте смотреть Java-демки.
Была любительская прямая видеотрансляция. А я и не знала, что есть такие сервисы... Ее делал Максим Высоких, она доступна в записи. Там плохо видно и плохо слышно. :-)
Слайды можно посмотреть тут.

Второй доклад - "С++0х" был менее популярен. Отзывы о нем тоже хорошие.
Слайды тут, любительской записи не было.

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

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

Доклады
Все началось с того, что я опоздала на доклад Евгения Бурмако, где он на глазах у изумленной публики писал код на C# для CUDA. Интересно с технологической точки зрения, сомнительно с практической. Опять же есть любительская запись. Подробнее можно почитать тут: Conflux: GPGPU для .NET
В зале, где читался этот доклад, было несколько мониторов, никогда такого не видела. Удобно код показывать.

Андрей Карпов читал доклад на тему "Устаревание стандартов кодирования и статический анализ кода". Он представляет разработчиков PVS-Studio, реклама которой висит у меня тут сверху. Начало доклада было несколько затянуто. Рассказывал о типичных ошибках программистов, которые они могут своим анализатором обнаружить. Гордятся свой работой с С++0х. Собираются выпускать бесплатную версию. Приятно было узнать, что в Туле ведутся разработки подобного уровня.

Яков Сироткин, доклад "Как стать героем". Рассказал несколько бородатых шуток, получится веселый доклад ни о чем.

Николай Мациевский, "Лицензии для Open-Source". Интересный доклад, основанный на собственном опыте. Тут было про лицензии вообще, а также про специфику, связанную с российским законодательством. Также была затронута скользкая тема про обходы проблем с лицензированием. Добротный подготовленный рассказ, вызвал бурную дискуссию в зале. Статья по этому докладу: Насколько открыт Open Source.

Пара слов про доклады, на которых мне побывать не удалось. Очень все хвалили доклад Никиты Фролова про iPhone. Ну а я собираюсь смотреть в записи доклады про дополненную реальность.

Организация конференции
Все было сделано по уму.

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

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

WiFi был, ловился везде, работал бесперебойно. Розетки были не только в коридоре, но и даже в залах.

Были флипчарты. Там были флипчарт доклады, фотография как раз с одного такого доклада. Но там постоянно кто-то зависал, не только на докладах.

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

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

Замечания
Ну давайте придеремся к чему-нибудь.

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

Туалеты было непросто найти, на это многие жаловались. Я не смогла это сделать без посторонней помощи, мне подсказали.

В конце было затянутое закрытие с вручением призов. Многие уехали к тому моменту, народу было мало.

Размещение. Это общероссийская беда, никто ее не решил. Мне, как докладчику, гостиница была оплачена, это обычная практика. Качество не то чтобы кошмар-кошмар, но цене не соответсвует. Для студентов цены недостижимые просто. Европейцы любят кооперироваться, снимать один номер на двоих. Где-то, по-моему это был QuakeCon, народ спал в спальных мешках прямо в здании конференции. Но, я думаю, такой поворот событий несколько расстроит ДК Железнодорожный :-).

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

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

На конференции слышала фразу "У нас тут конечно не Москва...". Это прекрасно, что не Москва. В Москве любая конференция вырождается в конференцию понтов.

В целом - респекты организаторам. Надеюсь, что конференция будет продолжена.

Игра Alien Swarm, с исходниками

2010-09-16T23:39:00.012+04:00

Этим летом Valve сделала жест невиданной щедрости. Они совершенно нахяляву выложили на Steam игру Alien Swarm. И ~~полные~~ исходники к ней. Я знаю, народ постоянно ищет исходники, чтобы по ним поучиться, вот оно.

Updated 17.09.2010:
Дополнения по результатам разбирательства с исходниками, поисков в интернетах и комментариев:
Игра сделана на движке Source и исходников самого движка нет. Причем, по слухам, движок этот в AlienSwarm модифицирован. Итого - нету кода рендера, физики. Зато AI, похоже, весь есть, по крайней мере все, что мне было нужно, я нашла.
Разбирательства с тем, чего есть, а чего нет, затруднены из-за отсутствия какой-либо документации. Есть wiki по AlienSwarm, информации там мало.
Написан AlienSwarm на С++, а не на своем скриптовом языке, это приятно.
/Updated 17.09.2010:

Давайте я расскажу как это все скачать и куда смотреть, это не очень тривиальный процесс.

Сначала надо зайти на Steam и инсталлировать Alien Swarm. Если вы там не зарегистрированы, вам предложат зарегистрироваться. И заставят скачать и установить их клиента. Игра здоровая! Что-то типа гигабайта.

Исходники Alien Swarm устанавливаются из Steam клиента из меню Tools.

Исходники приедут вот сюда, это путь по умолчанию
C:\Program Files\Steam\steamapps\common\alien swarm\sdk_src

Наверняка вам понадобится дебагная консоль, она включается в Опциях.

Вызывается по тильде, ~

Консоль выглядит вот так:

Команды дебагной консоли, которыми я пользовалась
ai_nodes - показывает все waypoint графа
ai_show_connect - показывает связи между точками waypoint графа

Сейчас еще пороюсь, может еще чего хорошее найду.

Ссылки по теме:
Are Waypoint Graphs Outnumbered? Not in AlienSwarm!
Alien Swarm SDK tutorials

Доказательство Деолаликара скорее всего неправильное

2010-08-26T15:47:00.000+04:00

По предыдущему посту по поводу доказательства P ?= NP проблемы возникли вопросы, поэтому я решила написать еще один пост.

Первый вопрос, о чем вообще речь, что такое P ?= NP ?
Давайте я приведу пару ссылок на упрощенные описания проблемы.
Статья на lenta.ru
P vs. NP for Dummies
К сожалению, эти упрощенные описания настолько упрощены, что на практике они бесполезны. Вы - программисты, ребята умные, поэтому почитайте что-нибудь посерьезнее, например.
Lecture 6: P, NP, and Friends
Complexity theory статья в Википедии, далее следуйте по ссылкам.
Книга Пападимитриу, Стайглица "Комбинаторная оптимизация". Классическая книга, рекомендуется студентам, которые изучают теорию сложности.

Курс лекций по теории сложности обычно читается в вузах студентам, изучающим computer science. Все мои познания по этой теме как раз из курса, который я слушала на ВМиК МГУ. Я не могу сказать, что без этих знаний жить никак нельзя, но как минимум они дадут вам дополнительные очки при прохождении собеседований в компании с уютными офисами из стали и стекла, с названиями, выложенными разноцветными буковками.

Вопрос номер два: а как там дела с проверкой доказательства?
Несмотря на то, что окончательные выводы не сделаны, все говорит о том, что доказательство не верно. Деолаликар, правда, обещает исправить все замечания, но то, что он сможет это сделать, вызвает большие сомнения.

Страничка в формате wiki, посвященная доказательству Deolalikar P vs NP paper. Страница постоянно обновляется, так что самую свежую информацию следует искать здесь.

A Tale of A Serious Attempt At P≠NP Ричард Липтон подробно рассказывает о том, а что вообще это было.

Eight Signs A Claimed P≠NP Proof Is Wrong

Подкаст с участием Алекса Отта

2010-08-19T19:39:00.003+04:00

Алекс Отт рассказывает о функциональном программировании.

Updated 21.09.2010: И продолжение рассказа Алекса: о языке Clojure и жизни программистов в Германии

Буду выступать на ADD-2010

2010-08-15T23:26:00.003+04:00

Конференция ADD-2010 - это конференция разработчиков ПО за вменяемые деньги. Проходит 23-24 сентября, в Ярославле, сейчас стоит 6000 рублей (вместе с обедом, но без проживания).

Меня туда позвал Стас Фомин, надо было только определиться с темой. В процессе раздумий и общения в Твиттере родилось две темы: "C++0x" и "Искусственный интеллект в играх". Надо было выбрать одну из них и тут Стас предложил гениальную идею - а зачем выбирать? Итого: я буду читать два доклада.

C++0x
Доклад о разработке нового стандарта языка С++. Чего хотели добиться, чего получилось, от чего пришлось отказаться.
Разработчики компиляторов не стали дожидаться выхода стандарта и уже много чего реализовали. Поэтому есть уже такие возможности С++0х, которые можно использовать прямо сейчас. О некоторых наиболее интересных возможностях будет рассказано. В основном речь будет вестись о GCC и MSVC++.

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

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

Цена билетов, которая действует на настоящий момент - 6000 рублей. Это сильно дешевле, чем аналогичные московские конференции. Я слышала цену в 15000 на какую-то конференцию, совершенно негуманные цифры. Но все равно дороговато, на мой взгляд.
Проходит ADD-2010 в Ярославле. Оно и понятно, в Москве, насколько я слышала от организаторов других конференций, львиную долю от стоимости билета составляет аренда помещения. Я с удивлением обнаружила, что Ярославль находится недалеко от Москвы. На электричке до него ехать часа четыре, на машине можно и быстрее добраться. В Ярославле в этом году юбилей города, настроение праздничное. Короче, отличный повод выбраться из Москвы и увидеть памятник Ярославу Мудрому не только на тысячерублевке :-).

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

P.S. Стас пишет, что если зарегистрироваться со ссылкой на меня, то можно получить 5% скидку. Для этого надо указать промо код alenacpp.

P != NP, доказательство Виная Деолаликара

2010-08-10T16:28:00.006+04:00

Updated 26.08.2010: Доказательство Деолаликара скорее всего неправильное

6 августа Винай Деолаликар (Vinay Deolalikar) разослал доказательство одной из проблем тысячелетия, которая близка программистам. Это доказательство того, что P != NP. Осталось убедиться в том, что это доказательство верно.

Вот само доказательство: P != NP (Ахтунг! 100 страниц математических формул)

Я поискала в Интернете отзывы математиков и не математиков, вот чего нашла.

Первое упоминание этого доказательства в открытых источниках.

Веселое обсуждение на слэшдоте.

За доказательство проблемы тысячелетия дают миллион долларов. Скотт Ааронсон накинул еще 200 тысяч.

Математик Ричард Липтон опубликовал у себя в блоге две статьи
A Proof That P Is Not Equal To NP?
Issues In The Proof That P≠NP - результаты первой проверки. Есть несколько замечаний по доказательству, но это именно замечания, они не означают, что доказательство неправильное.

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

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

Списки с одновременным доступом Тима Брея

2010-07-30T15:10:00.002+04:00

В посте Concurrent List Update With Shuffling Тим описывает задачу, которую решил когда-то давно.

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

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

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

4: 10, 20, 30, 40

Теперь мы добавляем туда число 15, которое должно разместиться между 10 и 20. Допустим, что у нас есть еще свободное место на странице, а число 4 означает только число элементов, которые используются в данный момент.

Начинаем процесс вмешивания (shuffling-in) нового злемента

4: 10, 20, 30, 40, 40

Теперь увеличиваем счетчик

5: 10, 20, 30, 40, 40

Перемещаем элемент...

5: 10, 20, 30, 30, 40

5: 10, 20, 20, 30, 40

И в конце ставим элемент на его законное место.

5: 10, 15, 20, 30, 40

Удаление происходит аналогично.

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

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

Тим Брей спрашивает, не придумал ли он чего странное, но в комментариях пока ничего эдакого не нашли.

Спасибо Maniac'у за ссылку.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Развернутые списки

2010-07-29T12:30:00.003+04:00

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

Развернутые списки - это простой пример структуры данных, которая знает о существовании кэша и умеет это использовать.

Есть примеры и посложнее, например деревья Ван Эмде Боаса (они же vEB деревья).
Вообще с этими деревьями интересно получилось. По привычке я пошла в Википедию и долго тупила в картинку, пытаясь понять что же там изображено. Я всегда думала, что они выглядят вот так (картинка из слайдов Descent into Cache-Oblivion [.pdf]):

После чего нашла упоминания того, что это ненастоящие деревья Ван Эмде Боаса. Поскольку картинка из Википедии мне ничем не помогла, я попыталась найти труд самого Ван Эмде Боаса. Он называется Design and Implementation of an Efficient Priority Queue и его предлагают покупать за деньги. Короче, если вы знаете ссылку на хорошее описание, киньте ее, пожалуйста.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Ссылки по теме:
Cache-oblivious data structures
Несколько ссылок на материалы про кэш
Unrolled linked lists

Красно-черные деревья

2010-07-28T12:30:00.000+04:00

Прежде чем начинать говорить о красно-черных деревьях, немного о бинарных деревьях вообще. Важно, чтобы дерево было сбалансированным, чтобы длины поддеревьев отличались не больше чем на единицу. Если это не так, работа с таким деревом становится более затратной по времени и смысла в таком дереве уже нет. Однако, при операциях вставки и добавления дерево идет вразнос. Одни ветки становятся сильно длинее других. Его можно сбалансировать и привести ветки в порядок. Для этого придуманы самобалансирующиеся деревья - при вставке элементов им ветки выравнивают. Но балансирование - дорогая операция. Лучше всего - золотая середина. Красно-черное дерево, где узлы помечены черным и красным цветами, называют "достаточно сбалансированным". Длины поддеревьев у него могут отличаться больше, чем на единицу. Но никогда больше чем в два раза.

Пример использования из реальной жизни: std::map'ы обычно реализуют через красно-черные деревья.

Картинка из Википедии, которую обычно приводят в качестве примера красно-черного дерева, мне не нравится.

Эта картинка дает неверное впечатление. Дерево, изображенное на ней, сбалансировано. И разноцветные вершины расположены рядами. И создается ощущение, что оно всегда так. Вот картинка получше (из статьи Advanced Haskell Data Structures: Red-Black Trees):

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

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

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Фильтр Блума

2010-07-27T13:00:00.002+04:00

Фильтр Блума - это структура данных, придуманная Бёртоном Блумом в 1970 году, которая позволяет быстро проверять принадлежность элемента множеству, при этом не затратная по памяти.

Фильтр Блума представляет собой битовый массив, в которой с помощью нескольких хэш-функций отображается каждый элемент. Картинка из Википедии.

Фильтр Блума может сработать ложно. То есть элемента во множестве нет, а он говорит, что есть. И чем больше элементов в множестве, тем выше вероятность ложного срабатывания. Однако, если вы знаете, что основной массы элементов в вашем множестве нет, то этот фильтр очень удобен. Вы сначала прогоняете их все через фильтр. А потом проверяете еще раз каким-нибудь иным более точным образом.
Ложные срабатывания - не единственная проблема фильтра Блума. Еще из него нельзя удалять элементы. Есть различные расширения фильтра Блума, которые все-таки позволяют это делать, но, понятное дело, не бесплатно.

Пример использования из Википедии:
Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Пост Will it optimize?

2010-07-26T22:59:00.004+04:00

Will it optimize? - опросник, в котором вам предлагается угадать будет ли GCC проводить оптимизацию кода. Сложно и познавательно.

Там очень здоровая шапка, чуть вниз отмотайте.

Спасибо Maniac'у за ссылку.

Расстояние Левенштейна

2010-07-26T15:19:00.005+04:00

В институтах всех нас учат сравнивать две строки по принципу равны/не равны и искать строку в подстроке. На практике же, когда строки не равны, интересен вопрос, а насколько отличаются две строки?

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

Алгоритм подсчета расстояния Левенштейна описан в Википедии, с псевдокодом. Есть на русском.

Еще одно описание алгоритма, с ява-апплетом, который умеет считать расстояние Левенштейна.

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

(Пост опубликован в рамках недели борьбы с велосипедизмом)

Неделя борьбы с велосипедизмом

2010-07-26T14:01:00.005+04:00

Все любят смеяться над новичками, которые норовят придумать свой уникальный алгоритм или хэш со сложностью доступа O(n) в лучшем случае (true story!). Однако бывает, что мозг далеко уже не младших программистов порождает нежизнеспособных колченогих уродцев, которые значительно хуже существующих аналогов. А остановить их некому. Поэтому на этой неделе я сделаю несколько постов про алгоритмы и структуры данных, которые не входят в стандартный курс по программированию. Это не какие-то передовые достижения науки, да и информацию по ним по всем можно легко найти в Интернете. Но если не знаешь, что именно искать, то можно так никогда и не найти.

Updated 24.08.2010
В рамках недели были рассмотрены следующие темы
Расстояние Левенштейна
Фильтр Блума
Красно-черные деревья
Развернутые списки
Списки с одновременным доступом Тима Брея
И бонус с дружественного блога Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Ссылки по теме:
What should be in your programming toolbox?
5 more essentials for your programming toolbox
Programmer’s Toolbox Part 3: Consistent Hashing. Об этом же на русском Консистентные хэши (Consistent hashing)

Paris Game AI Conference 2010. Общие впечатления

2010-07-14T19:05:00.003+04:00

Вы думали, про конференцию уже всё? Нифига.

Я причесала старые два поста. Все общие замечания про конференцию я вынесла сюда. Дописала недостающие куски, добавила фотографии, добавила ссылки на слайды, которые выложил Шампандар.

Кроме меня отчеты уже написали: Шампандар, Микко Мононен и Бьярн Кнафла. У Шампандара много фотографий хорошего качества, его жена фотографировала. Микко в отдельном посте выложил слайды и сурсы.

Когда я упоминаю Шампандара, вопрос, который мне чаще всего задают "а кто это?". Это программист, специализирующийся на игровом ИИ, ведет aigamedev.com, работает по контрактам на разные девелоперские конторы. Работал в компании Rockstar, работал над Killzone 2. Организовал конференцию, о которой я так много рассказываю, за что ему большое спасибо.

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

Но программеры, они все прям как у нас. Во время кофе-брейков многие мялись и мучались. Я тоже мялась и мучилась. Тяжело это - общаться.

Веселый студент из Дублина, который сидел рядом со мной, выдвинул интересную теорию. Докладчики отличались по поведению в зависимости от специализации: там были бизнесмены, программисты и преподаватели из вузов. Бизнесмены держались уверенно, напористо и складно говорили, преподаватели также были уверены, но без напора, программисты же с видимым усилием боролись с желанием спрятаться под стол.

Шампандар круто управлял временем, расхождения с расписанием у него были максимум минут десять. Для тех, кто раньше бывал на конференциях, это много о чем должно сказать. Как он это делал: во время вопросов и ответов он в какой-то момент объявлял "следующий вопрос - последний". И все.

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

CNAM

Указатель

Нам туда, вниз

Я получила бэджик!

Зачем-то были закрыты последние ряды. Не знаю зачем.

Конференция была несколько омрачена традиционной французской забавой - забастовкой. Трудящиеся массово бастовали в связи с реформой пенсионной системы. Как несложно догадаться, условия выхода на пенсию меняют в худшую сторону. В связи с чем не работал некоторый транспорт, были отменены авиарейсы. Тут очень хорошо выступил спонсор - рекрутинговая компания Game Talents. Они обновляли информацию о ситуации в аэропортах на доске объявлений в реальном времени (WiFi, как мы помним, отсутствовал). Также они обещали отвезти людей в аэропорты. Отвезли или нет - не знаю, а вот доску объявлений видела своими глазами.

Программка и бэджик

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

Paris Game AI Conference 2010. День второй

2010-06-24T22:52:00.008+04:00

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

Все началось с рассказа Паоло Манинетти про гоночный симулятор. Машины и мотоциклы у них едут по идеальной траектории. На это линии есть целевая точка на определенном расстоянии и машина стремится к ней приблизиться. Траектория содержит в себе информацию об идельной скорости. Когда машин много двигают целевую точку, чтобы избежать столкновения. Они пытаются анализировать информацию о том, что происходит на дороге, пытаются определить опасные ситуации. Это отражается на производительности.
Показывали демки с отладочной информацией. Дебагная информация у них богатая.
Искали золотую середину между честной игрой и читерством. Говорят, что чем честнее, тем правдоподобнее. Но тем дороже по производительности.
Каждая трасса тюнится руками, можно в нее записать что-то дополнительно.
Physics-based Racing AI[.pptx]

Battlefield: Bad Company 2
В соседней аудитории одновременно с нами проходило еще какое-то сборище, они там громко пели хором. Это придало докладу неповторимую атмосферу.
Первую часть этой игры много критиковали за AI, поэтому над AI серьезно поработали.
В игре (они сокращали ее название до BF) есть дружественные агенты. Их сложнее делать, чем вражьих, потому что враги быстро дохнут и если в них и есть какие глюки, то это незаметно.
Также там есть разные виды юнитов - пехота, машины, танки, вертолеты. И мир разрушаемый.
Показали демку, спросили, не заметил ли народ чего подозрительное. Я не заметила, однако были люди, которые просекли, что там танк телепортируется. Причем дважды.
Улучшили анимации смерти - их, правда, всего пять секунд на экране видно.
Сделали автоматическое определение укрытий. Т.е. укрытие должно быть достаточно высоким, защищать от врага. Определяли, нужно ли вставать, чтобы выстрелить в врага или надо уйти в сторону.
Читят они, да. Про танки вы уже поняли. Еще солдаты у них не бегут слишком близко к игроку. И если резко развернуться, то это заметно, выглядит глупо. Солдат тоже телепортируют.
Итого:
-80% bulk AI
-20% memorable moments
Слайды у них красивые были. Модные такие, с вертолетом.
Building the BATTLEFIELD AI Experience[.ppt]

Дальше была panel discussion. Там были Брюс Блумберг, Фредерик де Кастер (Creative Assembly), Ульф Йохансен (IO Interactive). Говорили про контроль качества.
Тестеры отрывают разработчиков от работы, когда находят багу, потому что AI баги сложно повторить. Брюс Блумберг рассказывал, что у них был тестер, которого они прозвали Ангелом Смерти. Если он входил в комнату, значит придется задержаться.
Делают плейтесты. По времени прозвучала оценка полдня в неделю.
Фредерик из Creative Assembly рассказывал, что у каждой команды есть доска, они туда пишут над чем работают сейчас, над чем будут работать.
Ульф рассказывал про их smoke тест. Если игра после запуска работает 40 секунд, то тест пройден. У них есть автоматические тесты. Для повышения воспроизвоимости есть AI fight recorder.
Брюс рассказывал, что у них можно законнектить игру с их тулзой, где отображается граф поведения и можно открутиться назад и посмотреть что происходило.

Дальше Щампандар рассказывал про Multi-threading AI, в основном про то, как оно много и интересно глючило, а он его отлаживал.
Использовал Intel TBB.
Высказал следующую мысль: When dealing with multithreading, denial is a very useful tool to use.
Multithreading in Practice: Uncensored and Uncot[.pptx]

Дальше был доклад про EVE online characters
Рассказывали, что когда игрок подходит к ботам и они на него не реагируют, это выглядит странно. Показали несколько роликов. Действительно странно.
Они сделали некий AI social engine и будут вставлять его в EVE online. Здесь было много информации из области социологии, формирование кластеров общающихся людей, очереди, F-formations.
Human Territoriality for EVE Online's Socially Smart Characters[.ppt]

Дальше был гвоздь программы, Кен Перлин, который Perlin noise, рассказывал про процедурную анимацию. Много говорил о том, что надо делать персонажей более убедительными, живыми. И в процедурную анимацию легче вносить изменения. Чем-то мне это все напомнило Spore. По каким-то базовым принципам генерится анимация персонажей. В зависимости от того, как он анимирован, он может казаться, испуганным, веселым, смущенным, агрессивным. Даже если это не антропорморфная фигурка, а треугольное не пойми что. Здесь опять же было много демок, без них говорить сложно.

Здесь могла бы быть красивая фотография Кена Перлина на фоне его слайда с бущующим морем и надписью Why procedural methods are cool. Не получилось.

Дальше были заключительные слова, организаторы конференции порешили, что Cheating is win, что Pathfinding jokes when struggling to return to the hotel - это плохая идея. Что next big thing - это взаимодействие людей и социальный аспект, то есть то, о чем были последние два доклада.
Шампандар обещал конференцию в следующем году в это же время, наказал ничего другого на эти дни не планировать.

Paris Game AI Conference 2010. День первый.

2010-06-24T00:40:00.010+04:00

Обещала отчитываться о конференции, выполняю обещание.

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

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

Дальше выступил Брюс Блумберг. Он рассказывал об игре World of Zoo, об ИИ животных в зоопарке. Здесь было много красивых роликов. Для анимации они использовали HFSM, для поведения животных "что-то вроде behavior trees".
Его слайды: Intimate Conversations with Interactive Animated Characters[.pdf]

Выступили ребята с коротенькими презентациями различных миддлварей. Здесь я узнала, что Autodesk Kynapse используют Intel TBB и довольны.
MASA специализируются на безопасности, но также делает ИИ миддлварь, показывали ролики с драками, использующими мокап. Ролики красивые.
Ребята из PathEngine не используют флоаты и деление тоже не любят, потому что медленно.
Ребята из Havok'а показали совершенно потрясающую демку с крутящимися вентиляторам, между которыми ходят боты. Это они хвастались своей работой с мобильными препятствиями. Спросила их про эту демку во время кофе-брейка. Сказали, что в Интернет они ее, может, и выложат, а вот детали реализации разглашать не могут. Также рассказывали о том, что умеют генерить NavMesh динамически.

Navigation Loop, Микко Мононен
Navigation Loop, слайды и исходники
Рассказывал про агентов, которые вместо того, чтобы сталкиваться, кооперируются друг с другом с тем, чтобы выработать траектории, которые не столкнутся. Здесь было много красивых демок.
К нему было много вопросов. Спросили про нейронные сети. Ну какая ИИ конференция без нейронных сетей. Так вот, Микко Мононен нейронные сети не любит и их не использует.
Также его спрашивали, чего это у него все демки работают с окружностями, что делать с более сложными формами. Ответ Микки: с более сложными формами работать, хм, сложнее, поэтому работаем с окружностями.

Дальше опять panel discussion. Это когда несколько человек сажают в ряд и задают им вопросы, а они отвечают.

Здесь были (справа налево): Алекс Шампандар, Микко Мононен, Кен Перлин, тот самый, который Perlin noise и два разработчика Heavy Rain. Оба французы, оба произносили Heavy Rain с французским акцентом, "эви рейн" у них получался.
Обсуждали генерацию толпы. Здесь я узнала, что в Heavy Rain'е используется для толпыт fluid simulation (эмуляция жидкостей), они пробовали flocking (один из видов steering behaviors), но оно плохо работало для 1000+ человек, большая нагрузка на CPU была. Также они там читят, людей телепортируют иногда.
Спросили их, есть ли какая-то специальная обработка ситуации, когда игрок следует за одним агентом в толпе. Один из них сказал, что следовать за кем-то одним невозможно, потому что народу слишком много. "И потому что у нас телепорт" - добавил второй.
Еще сказали, что motion capture толпы людей непонятно как делать, потому что люди друг друга будут скрывать.

Байлор Ветцел рассказывал о бесчеловечных экспериментах над студентами. В простой игре с боями в стиле Heroes of Might and Magic реализовал несколько стратегий боя. Некоторые умные - они пытались атаковать самых сильных противников. Некоторые - откровенно дурацкие, типа первым атаковать противника с самым длинным названием или атаковать противников по очереди сверху вниз. Просил угадать какая именно стратегия где используется. Угадывали плохо. Просил оценить каждую из стратегий по трем критериям: Fun, Difficulty и Realism. Выяснил, что Random - один из топовых по Fun'у. Также выяснил, что Difficulty и Realism связаны друг с другом, а вот с Fun'ом никак не связаны.
Inside Your Players' Mind With Playtesting[.ppt]

Гваредд Маунтайн рассказывал про психологические опыты в SILENT HILL: SHATTERED MEMORIES.
В процессе игры игроку предлагается беседовать с психологом. По этим беседам состовляется психологический портрет играющего, и в зависимости от него меняется контент. От этого зависело будете ли вы беседовать с секси копом или просто с копом. Меняются одежда людей, мебель, внешний вид монстров.
Контента у них было много. Минимум 3 варианта каждой сцены.
Производит сильное впечатление. Но при этом игра больная на всю голову. Да простят меня поклонники Silent Hill.

Один из задававших вопросы отметил, что идея отличная, но ее бы лучше использовать для чего-нибудь более полезного.
Personality Profiling in SILENT HILL: SHATTERED MEMORIES

Paris Game AI началась

2010-06-23T17:02:00.006+04:00

Привет всем! Конференция Paris Game AI уже началась, но там нет WiFi, поэтому прямая трансляция в Твиттер у меня не получится.

Шампандар выступил в начале, было выступление по World of Zoo, сейчас обед. Самое интересное впереди.

Народ общается в основном на английском и французском. Слышала и другие европейские языки. Русских пока не вижу. Если кто есть - откликнитесь!

Первые фотки:

Статья Mea Culpa

2010-06-13T22:50:00.003+04:00

Mea Culpa - отличная статья программиста, который любил наворачивать сложность и сделал супергибкую систему.

I spent those decades debugging the Frankenstein. In the OS crash debugger. In hex. Because wasn’t it oh so clever and efficient to build a radically new kind of database with extreme reliability requirements as a highly multithreaded kernel extension to the OS?

Ну и вывод

That experience taught me a lot about what really matters in programming. It is not about solving puzzles and being the brightest kid in the class. It is about realizing that the complexity of software dwarfs even the most brilliant human; that cleverness cannot win. The only weapons we have are simplicity and convention.

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

Спасибо maniac'у за ссылку.

Пост "Проблемы с delete[]"

2010-06-10T16:26:00.002+04:00

В посте Проблемы с delete[] Александр рассказывает про undefined behavior вот такого кода:

A* a = new B[T];
delete[] a;

Рекомендую.

Updated 11.07.2010: Eugene K. справедливо уточняет

Вообще-то для получения проблем необязательно удалять. Достаточно выполнить какой-нибудь доступ к элементу "массива" a с индексом больше нуля.

A* a = new B[T];
a[1].p = 42; // запишет не туда

То есть проблема собственно в строке выделения "A* a = new B[T];". Если над ней помедитировать, то можно догадаться, что она лишена смысла.

Вышел Robocalypse - Beaver Defense

2010-05-31T23:50:00.010+04:00

Updated 07.06.2010
Nintendo Life 8/10
This is a fun tower defence game with enough unique features and strategic elements to keep it interesting and a sense of humour to set it apart from its competitors. While it suffers presentation-wise, don't let that throw you off as for those who enjoy the genre, this one's a must-have.

IGN 7/10
The silly style's still the same, but this is a whole different kind of Robocalypse.

Какой-то пользователь gamespot'а поставил 9/10. Это не официальный рейтинг, но все равно приятно.

Отзывы тех, кто играл, в основном положительные.
Выдыхаем...

Updated 04.06.2010 Сегодня, 4 июня, Бобер вышел и в Европе (31 мая был релиз на Северную Америку). Подозреваю, что это должно означать, что его видно в российском Wii Store. У кого есть Wii посмотрите, плз...

Сегодня вышел Robocalypse - Beaver Defense, на котором я была ведущим программистом, а также временами менеджером. Жанр игры - Tower Defense. Платформа - Nintendo Wii, вернее WiiWare - это игры под Wii, которые можно скачивать через online-магазин. Сюжет игры строится вокруг злобного бобра, который решил всех поработить. Он насылает на вас орды роботов, вам надо строить башни и от него обороняться.

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

Было интересно поработать с консолью, много отличий от работы с PC. И да, телевизор в качестве устройства вывода - это ужасно.

Теперь ждем реакции игроков, нервничаем.

Скриншоты

Интервью с нашим продюсером, Аланом Мартином

Еще одно интервью с Аланом, много букв.
Официальный сайт.
Офицальный пресс-релиз Нинтендо.

P.S. Увы, осенью Вогстер закрыл свое московское отделение. С тех пор я успела поработать в IT-Territory, которую внезапно купил Mail.Ru. В итоге сейчас я работаю в Mail.Ru, программирую под Windows. На C++, разумеется :-).

Неинициализированный указатель и вызов функции

2010-05-28T15:45:00.006+04:00

С неинициализированными указателями на экземпляр класса связан один неприятный момент. Допустим, у нас есть класс CBase, в котором есть функция, которая не обращается к переменным класса. То есть указатель this не использует.

class CBase
{
    int i;
public:
    void f() { std::cout<<"CBase::f"<<std::endl;}
};

И если где-то дальше вы написали код вроде такого:


CBase* p = NULL;
p->f();

То по стандарту это undefined behavior. Однако очень часто функция отрабатывает нормально. Visual Studio 2008, например, генерит вполне себе работающий код. А чего, вызов этой функции был разрешен на этапе компиляции, указатель this не нужен. И довольно долго может создаваться ощущение, что все нормально работает. Можно даже привести более страшно выглядящий пример

((CBase*)0)->f();

Но на самом деле далеко не все нормально. Как только появляется обращение к this, то программа начинает "падать". Примеры:

class CBase
{
    int i;
public:
    virtual void f() { std::cout<<"CBase::f"<<std::endl;}
};

class CBase
{
    int i;
public:
    void f() { std::cout<<"CBase::f"<<std::endl; i=0;}
};

Все это приводит к очень интересным трудно отлавливаемым багам.

Ссылка по теме:
comp.lang.c++.moderated - Functions that don't use this, called with uninitialized pointers

Вебинар с Гербом Саттером

2010-05-11T21:19:00.003+04:00

Герб Саттер у себя на блоге рекламирует вебинар с собой: May 12 Webinar on Multicore Parallelism. Я зарегистрировалась, постараюсь быть.
Точная дата - May 12, 2010 at 8 a.m. PT/11 a.m. ET. Это семь вечера по Москве.

P.S. Ролик выложили. Как дать туда прямую ссылку я так и не поняла.

Paris Game AI conference 2010

2010-05-06T00:33:00.002+04:00

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

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

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

Итак, Париж 23-24 июня, схема проезда есть на официальном сайте и, cлава Гуглу, мы можем посмотреть где именно это будет.

Язык конференции - английский. Здесь список докладов: Program Highlights

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

После конференции я напишу отчет, а в процессе буду твитить, если там будет WiFi. Хэштэг #AIGD10.

Книга Debugging

2010-05-02T14:17:00.001+04:00

Полное название этой книги Debugging: The 9 Indispensable Rules for Finding Even the Most Elusive Software and Hardware Problems. Поэтому обычно не нее ссылаются по более короткому названию - Debugging. Автор - David J. Agans.
Редкая книга в своем роде. Потому что книг по отладке мало, очень мало.
Написана весело, с юмором, простым языком. На Amazon'е высокий рейтинг и прекрасные отзывы, что неудивительно. В книге приведено очень много реальных примеров отладки. Примеры в основном по отладке харда, немного по софту и примеры из жизни, из серии "что-то водопровод у нас странно глючит". Описанные в этой книге принципы универсальные, они везде работают. Поэтому будет полезна не только программистам, но и всем занятым в разработке софта.

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

Несколько ссылок на материалы про кэш

2010-04-29T20:49:00.001+04:00

Производительность программы можно улучшить, если знать как именно происходит работа с кэшем, тогда можно минимизировать промахи кэша (cache miss). Несколько ссылок про это.

Be nice to your cache - небольшая вводная статья
Gallery of Processor Cache Effects - большая подробная статья
Pitfalls of OOP - очень известные слайды с картинками

Updated 05.05.2010:
At Least We Aren’t Doing That: Real Life Performance Pitfalls - слайды+аудио про производительность, в том числе про кэш

Если вам интересно еще почитать про кэш, поищите по ключевым словам cache-aware и cache-oblivious.
По cache-aware вы найдете про затачивание алгоритмов и структур данных под какой-то конкретный процессор, а по cache-oblivious - про затачивание под кэш в принципе.

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

Материалы с GDC2010

2010-03-29T00:24:00.002+04:00

Game Developer Conference проходит ежегодно в марте. GDC этого года уже прошла и в Интернете начали появляться материалы оттуда.

На русском
orvind рассказывает о GDC2010: раз, два и три.
_winnie перессказывает orvind'а
Updated 28.04.2010: gdc san francisco 2010

На английском
Пит Исенси, Микрософт, Effective Management: Getting the Best from Your Team [.ppt]

GDC 2010: Reading the Player’s Mind Through His Thumbs: Inferring Player Intent Through Controller Input

GDC 2010 Networked Physics Slides + Demo (Glenn Fiedler, Sony Santa Monica) - много интересных бенчмарков пропускной способности интернетов. Подробно с примерами рассказывает о синхронизации игроков в мультиплеерных играх.

The AI of BioShock 2, Kent Hudson, 2K. Все материалы в каком-то кривом формате.

Пол-Кристиан Энгстад, Naughty Dog. Слайды про PS3 SPU. Часть1 и часть2. Они по ним раньше вновь прибывших учили, а теперь решили поделиться знаниями с миром.

Сид Мейер (он Цивилизацию придумал) рассказывает о психологии игроков.

Рассказывает, что есть некоторые игроки, которые перед каждым боем сохраняются. И, если бой прогрывают, то загружают сейв и переигрывают битву заново. (это обо мне, ага :-) ). Так вот, они стали запоминать с сейвом некий ключ. И исход битвы будет таким же, сколько ни перегружайся. "Ха-ха-ха" - добавляет в конце Сид.

Небольшая презентация от Havok'а. У них теперь есть Havok AI.

Еще много ссылок тут: GDC 2010 proceedings

Приставочные игры через видеопоток

2010-03-23T00:34:00.003+03:00

Знаю о двух проектах, которые собираются давать играть через видеопоток.

Spawn Labs - нужен специальный девайс, который уже продается. И можно удаленно играть на собственной приставке. Отзывов покупателей не нашла.

onlive.com - тоже нужен специальный девайс. Это сервис, то есть своя приставка не нужна. Работать собираются по подписке. Открываются летом.

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

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

Хорошо там, где нас нет

2010-03-21T14:50:00.001+03:00

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

Веб-программисты иногда думают о том, чтобы попрограммировать "по-настоящему". Не на PHP, а на C++. Лучше на С. Чтобы близко к железу. Это и есть настоящее программирование и там живут суровые системные программисты. И платят там больше.

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

Программистам из разных финансовых организаций много платят. Но здесь скучно. И ты - человек второго сорта. На первом месте тут финансисты, извините. И это совсем не то, о чем мечталось. Хотелось заниматься разработкой игр, вот там весело. А тут на работу надо ходить к 9 и в костюме. Иногда эти программисты выбираются из уютных кьюбиклов и приходят на собеседования в геймдев, пугая геймдевелоперов неадекватными зарплатными ожиданиями.

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

Так что где бы вы ни работали, что бы вы ни программили, помните, что где-то в далеком офисе сидит человек, который страшно завидует именно вам. :-)

Lock-free контейнеры

2010-03-17T15:18:00.004+03:00

Пост Андрея Гулина(Яндекс, Поиск) с реализацией TLockFreeQueue и обсуждение на rsdn. По ссылкам - много полезной информации по lock-free контейнерам и готовый код.

Спасибо orvind'у за ссылку.

Питер Норвиг отвечает на вопросы reddit-коммьюнити

2010-03-05T22:55:00.002+03:00

Питер Норвиг ответил на вопросы, которые ему задавали пользователи reddit'а. Работает ли Гугл над strong AI, почему Лисп не используется широко в Гугле, кьюбиклы или отдельные офисы. В целом забавно, но никаких откровений. И да, рубашка у него зачетная :-).

Нашла по ссылке отсюда.

Вопросы с собеседования: общие вопросы

2010-03-05T10:44:00.003+03:00

Это пятая часть вопросов. Все вопросы можно найти здесь.

(5a) Как ИИ должен взаимодействовать с системой анимации? Какие проблемы возникают при взаимооднозначном отображении между поведениями и анимациями? Дайте примеры ситуаций, когда ИИ требуется взять контроль над частями тела юнита, а не просто играть анимацию всего тела, опишите реализацию каждого такого примера.

(5b) Как должна ИИ-система выбирать анимации для проигрывания? Другими словами, какими должны быть интерфейсы для кода и для данных, каким образом данные должны быть абстрагированы, чтобы ИИ-система могла как можно проще доступаться до анимаций? Опишите достоинства и недостатки различных путей описания анимаций и доступа к ним.

(5c) Расскажите о самой крутой ИИ-системе, которую вы видели в игре. Что именно вас впечатлило? Как вы думаете, как именно она была реализована. Каковы возможны проблемы по производительности у такой системы?

(5d) Как можно использовать машинное обучение(ML) в играх. Какие проблемы ML помогло вам решить? Каковы достоинства и недостатки различных подходов? Каковы характеристики по производительности различных ML-подходов? Какие ML-подходы могут быть использованы в реалном времени, а какие лучше считать заранее? Дайте различные примеры использования ML, неважно, успешные или нет.

(5e) У вас есть игра, в которой 1000 ботов ищут путь через сложный уровень игры, у каждого из них разные цели и система поведения. Сделаем допущение для данного вопроса, что это вражеские солдаты и офицеры, патрулирующие и защищающие базу в шутере от первого лица. Каким образом вы будете оптимизировать производительность ИИ для ваших ботов?

Вопросы с собеседования: поиск пути и навигация

2010-03-04T10:17:00.007+03:00

Это четвертая часть вопросов. Все вопросы можно найти здесь.

(4a) Расскажите об алгоритме A*. Сравните его с другими алгоритмами, почему его обычно используют в играх с расчетами в реальном времени? В каких случаях у A* низкая производительность?

A* - алгоритм поиска на графе с эвристикой.
Алгоритм A* для новичков - простое и наглядное описание.
У него хорошая производительность, эвристику можно потюнить если чего.
Хуже всего отрабатывает тогда, когда пути для цели нет. Перебирает все возможные узлы графа и может сожрать много памяти.

(4b) Назовите как минимум 3 способа представить пространство поиска так, чтобы на нем можно было делать поиск пути. Каковы достоинства и недостатки каждого из этих подходов, когда какой из них вы будете использовать?

Можно разделить на клеточки: квадратные, шестиугольные. Плохо подходят для трехмерных миров. Занимают много памяти. Требуют дополнительной интерполяции пути юнитов, иначе юниты, которые ходят по клеточкам, будут выглядеть глупо. Но зато есть random access look-up.
Waypoints. Найденный путь не всегда оптимальный. Хорошо работает в трехмерных играх.
Navigation mesh. Нужно хранить большое количество полигонов, если мир сложный. Хорошо работают как на открытых пространствах, так и в закрытых. Можно генерировать автоматически. Но сложно.
Использование сильно зависит от задачи.
Все это подробно и с картинками изложено здесь: Pathfinding: Search Space Representations

(4c) Назовите все способы, какие знаете, для оптимизации поиска пути без потери качества найденного пути. Перечислите все дополнительные расходы (например, увеличившийся расход памяти) для каждой из этих оптимизаций.

Речь будет идти про А*, поскольку он самый популярный.
Оптимизировать можно двумя путями: пространство поиска и сам алгоритм. Сначала про пространство поиска:
Можно разделить пространство поиска на клеточки покрупнее, алгорим будет работать быстрее.
Есть HPA* (hierarchical pathfinding A*) - Иерархию двух пространств поиска. Грубо говорят - клеточки покрупнее, которые делятся на клеточки поменьше. Сначала ищем по крупным клеточкам, потом, когда путь найден, уточняем по мелким. Больше двух никто не делает - получается сложно, выигрыш маленький, не нужно это.
Оптимизация самого алгоритма:
Играем с эвристикой.
Если идет несколько поисков одновременно, можно запоминать промежуточные данные одного поиска и использовать их в другом.
Можно аллоцировать необходимую для алгоритма память заранее.

Также см. Game Parogramming Gems, глава A* Speed Optimizations

(4d) Ваша система поиска пути была написана с расчетом на солдата, и она хорошо работает для солдат. Посередине разработки дизайнеры решают добавить 3 новых типа юнитов: инопланетянина ростом 15 футов, который не пролезает через большУю часть дверей в игре, очень широкую машину на воздушной подушке, которая не пролезает в узкие коридоры и через маленькие двери, и солдата на мотоцикле, который довольно медленно поворачивает( например, 15 градусов в секунду на любой скорости). Какие изменения вы внесете в свой AI, чтобы они все заработали нормально?

(4e) У вас есть система поиска пути, которая отлично работает, но она не умеет работать с динамическими объектами (ящиками, бочками, машинами, другими юнитами). Игрок играет супергероем, который может использовать суперспособность "бросить автомат с газировкой на пути юнита". ИИ-юнит не может подвинуть или уничтожить этот автомат. Когда юнит видит, что автомат заблокировал его путь, какими способами он может найти способ обойти его, при этом придерживаясь своего начального направления движения и дойдя до цели? Что будет, если автомат сбросили на точку назначения? Что если автомат заблокировал дверь, через которую юнит должен пройти согласно своему предрассчитанному пути?

Ставим автомату вектор отталкивания, соответственно модифицируем вектор движения нашего юнита.
Если закрыло точку назначения - встаем до нее, чего делать.
Если заблокировало дверь - пересчитываем путь, когда в эту дверь упремся.
Подробнее здесь: Avoiding Dynamic Obstacles and Hazards

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

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

(4i) Ваш дизайнер поиграл в игру, где он видел отряд юнитов двигающихся по коридору таким образом, что только один их них двигался в каждый момент времени, а остальные его прикрывали (т.е. юнит из тыла всегда двигается вперед). Он впечатлен и он хочет такое же. Опишите пути реализации такой системы. Каким образом ИИ будет понимать, когда ему двигаться, когда остановиться, когда открывать заградительный огонь?

Вопросы с собеседования: стиринги

2010-03-03T10:16:00.009+03:00

Это третья часть вопросов. Все вопросы можно найти здесь.

Это вопросы по steering behaviors, в просторечье "стиринги". Я видела перевод "стайное поведение", но он мне не очень нравится.

(3a)Как работают системы, эмулирующие стаю? Каковы компоненты такой системы и как они объединены? Когда поведение стаи не работает или дает нежелательный результат? Есть ли в стандартной стайной модели Крэйга Рейнольдса (Craig Reynolds) проблемы с производительностью? Если да, то как с ними справиться?

Модель Крейга Рейнольдса тут.

(3b)Что такое аттракторы и репульсоры? (в оригинале "attractors and repulsors", хороший перевод не придумала) Какое отношение они имеют к стиринг-системе. Когда они полезны, каковы их ограничения? Когда они могут быть использованы для огибания препятствий, а когда их недостаточно?

Можно задать притяжение (это attractors) или отталкивание (repulsor) между объектами. Их можно использовать в дополнении к существующему поиску пути, в дополнении к стирингам. Притяжение и отталкивание не обязательно должны быть линейными. Можно нарисовать всякие интересные кривые. Можно кривые менять во времени. Например, зайцы убегают от волка. Но если у волка мало здоровья, то они убегают вяленько.
Страдают от проблемы локального минимума.
Не нашла ничего в открытом доступе, поэтому отсылаю вас к Game Programming Gems 4, Глава 4.6, Attractors and repulsors.

(3c)Вы начинаете работать над игрой, и один из ваших коллег предлагает полностью отказаться от поиска пути и использовать потенциальные поля для поиска пути и навигации. Он предлагает покрыть весь мир двумерной сеткой, в каждой ячейке которой записано расстояние для ближайшего препятствия. Хорошая ли это идея? Почему "да" или почему "нет"? Когда с этим решением возможны проблемы? Вне зависимости от ответа на этот вопрос, где еще может быть использована такая система?

Идея не хорошая, потому что у потенциальных полей много проблем, они любят застревать в локальных минимумах. Можно их использовать на тайловых малодетализированных уровнях. Подробнее: Motion Planning Using Potential Fields и Using Potential Fields in a Real-time Strategy Game Scenario (Tutorial)

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

Краткий ответ. Если надо просто выстроиться в месте назначения - заранее определяем кто где будет стоять и направляем юнитов туда, это просто. Если надо сохранять порядок при передвижении - разделяем юниты по скорости. Обсуждение это вопроса есть тут.
Подробнее смотрите статьи: Movement Issues Facing Game Developers и Implementing Coordinated Movement.

(3e)Вам поручено реализовать толпу людей, прогуливающихся по улицам города. Расскажите о нескольких способах, которыми можно это реализовать быстро и эффективно. Как вы сделаете так, чтобы люди в толпе не дотрагивались друг до друга во время движения? Как они будут уступать друг другу дорогу и не застревать при этом, пытаясь обойти друг друга?

(3f)Дополнение к предыдущему вопросу. Толпа должна разбегаться, когда начинается драка. Как вы реализуете такое разбегание? Как вы сделаете так, чтобы толпа не возвращалась тут же обратно? Как вы сделаете так, чтобы толпа с течением времени "забывала" об этом инциденте и возвращалась обратно?

Repulsor, который с течением времени затухает.

(3g)У вас в игре есть машина на воздушной подушке и дизайнеры хотят, чтобы она двигалась линейно по определенным точкам. Она должна доходить до точки, останавливаться, стрелять в игрока несколько секунд, а затем случайно двигаться к следующей или к предыдущей точке из последовательности. Путь до новой точки должен занимать 4-5 секунд. Как вы реализуете движение такой машины, чтобы оно выглядело как можно более убедительно? Нужно ли здесь использовать физику, если да, то почему?

Я бы сгладила путь сплайнами, ну и всё. Без физики. Если бы это было не воздушная подушка, а грузовик на колесах, пришлось бы делать реалистичный разворот, учитывать радиус разворота.
Подробнее об этом рассказывается в AI game programming wisdom, глава Realistic Turning between Waypoints.

Вопросы с собеседования: работа с пространством и скриптование

2010-03-02T11:45:00.006+03:00

Это вторая часть вопросов. Все вопросы можно найти здесь.

Работа с пространством
(2a)На примере системы ИИ из игры Thief из прошлой серии вопросов (1f) расскажите, каким образом вы реализуете поведение стражников "поиск игрока" и пустите их разведывать территорию так, чтобы это выглядело праводоподобно? Как вы убедитесь, что это поведение не слишком сложное для игрока, что игрока нельзя найти, если он играет хорошо?

Можно составить карту влияния (influence map) по результатам работы сенсоров. Также можно ввести уровень пароноидальности ботов. А дальше все это надо долго и нудно настраивать в зависимости от того, чего хотят геймдизайнеры. Не встречала никаких статей по тулзам Thief'а, предполагаю, что они это все программили в обнимку с геймдизайнерами.
Подробнее обсуждается тут.

(2b)Ваша задача реализовать компьютерного игрока в стратегии реального времени (RTS). Допустим, туман войны не нужен. Как ваш компьютерный игрок будет определять какие части карты контролируются вражескими игроками, а какие можно исследовать? Как вы определите геостратегические регионы карты? Как вы найдете границу между частями карты под вашим контролем и частями под контролем врагов? Как вы определите готовящуюся атаку врага, изменение в уровне агрессии врага?

Опять influence map. Каждое здание "излучает" влияние. Сила влияния зависит от здания. Те места, где влияния нет, никому не принадлежат и их можно исследовать. Вражеские атаки тоже можно определить через влияния. Тут его будут "излучать" юниты врага.
Геостратегические регионы (английский термин лучше и короче - choke points ) - мосты, ущелья и т.п. Можно напрячь дизайнеров уровней их помечать на карте. Если дизайнеры уровней сопротивляются или если эти точки можно создавать динамически, то можно пытаться карту анализировать как-то так: если между двумя смежными регионами A и B можно пройти только через R, то R - choke point.
Подробное обсуждение тут.

(2c)В вашей RTS игре компьютер время от времени посылает разведчиков разведывать территорию. Дизайнеры хотят, чтобы каждый разведчик двигался полуслучайно и обходил различные части карты, предпочитая те, которые были открыты недавно. Допустим, что игра использует сетку и что есть туман войны. Также допустим, что разведчики стоят дешево и их не жалко, их можно пускать на вражеские базы и в другие опасные места. Как вы реализуете систему, которая будет решать куда идти разведчику? Какие структуры данных вам понадобятся? Как вы поймете, что разведчики достаточно хорошо исследуют карту? Дайте оценку по производительности вашего решения. Есть ли риск того, что разведчик будет пытаться добраться до недоступного места и застрянет?

Скриптование

Ответы на большинство вопросов по скриптованию можно найти тут: Дзэн-3, скрипт

(2d)Как связаны скриптование и ИИ? Когда следует контролировать ИИ с помощью скриптов? Когда дизайнеры используют ИИ для контроля над ИИ-агентами, на каком уровне скрипт должен взаимодействовать с ИИ?

(2e)Расскажите о нескольких системах скриптования, которые вы использовали в работе, или которые видели в других играх. Расскажите о достоинствах и недостатках тех или иных подходов к скриптованию.

(2f)Каковы достоинства и недостатки скриптования в целом? Когда скриптование использовать не надо?

(2g)Возьмите для примера любую игру и опишите лучший путь построения системы скриптования, которая даст дизайнерам возможность на каком-то уровне контролировать ИИ в игре. Также опишите идеальные инструменты для отладки описанной вами системы.

Вопросы с собеседования: поведенческий ИИ

2010-03-01T11:30:00.012+03:00

Это первая часть вопросов. Все вопросы можно найти здесь.

(1a)Какая разница между конечным автоматом(FSM) и иерархическим конечным автоматом(HFSM)? Дайте пример иерархического конечного автомата, который нельзя будет легко заменить конечным.

Конечные автоматы: http://en.wikipedia.org/wiki/Finite-state_machine
Иерархический конечный автомат, как многие догадались - это автомат, в качестве состояния у которого тоже автомат. http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
Иерархический автомат всегда можно представить в виде неирархического. Но при определенном размере обычный конечный автомат получится такой здоровый, что с ним будет очень тяжело работать.
Также см. ответ тут

(1b)Какие есть недостатки у конечных автоматов? Когда разумно использовать конечные автоматы, а когда их недостаточно, чтобы реализовать нужное поведение в игре?
Не умеют работать с параллельными и асинхронными задачами.

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

(1c)Что такое дерево принятия решений (decision tree)? Когда вы будете использовать такое дерево? Дайте оценки по производительности. Как сгенерировать дерево принятия решений автоматически из набора данных? Реально ли это сделать в рантайме, делалось ли это раньше в коммерческой игре? В каких ситуациях так следует делать и каким образом должны быть организованы данные, чтобы это было возможно?

http://en.wikipedia.org/wiki/Decision_tree
Минусы - каждый раз надо гнать заново сначала, не умеют хранить уже принятые решения, error propagation.
Автоматически генерятся с помощью алгоритмов типа C4.5 и ID3.
Игра Black&White использовала ID3. См. тут и тут[.ppt].

(1d)Вы реализуете схватку с боссом в 3D игре. У босса есть 15 вариантов атаки. Геймдизайнеры попросили вас сделать так, чтобы игрок в течение схватки видел как можно больше из этих 15 вариантов атак и чтобы он редко (а лучше никогда) видел одну и ту же атаку два раза подряд. Каким образом тут следует реализовать алгоритм атаки? Имейте в виду, что не все атаки досупны в каждый момент времени. Например, у босса есть атака, которая возможна только в ближнем бою, атака бомбами, которая возможна только если игрок далеко.

Рандом с весами (такой вариант был в комментариях). Флажками помечаем атаки, которые недоступны, по остальным гоним рандом. Нельзя убирать атаку, которая только что была, потому что если она всего одна, то нехорошо получится. Нужно уменьшать ее вес.
Также см. обсуждение и другие варианты ответов тут.

(1e)В одной комнате в вашей игре есть лифт, который боты должны использовать, чтобы убежать от игрока. Чтобы использовать лифт, они должны подойти к специальной кнопке на стене, нажать ее, чтобы вызывать лифт, затем зайти в лифт и нажать другую кнопку, чтобы лифт начал подниматься. Каким образом вы задизайните систему, в которой все эти действия будут выполняться в нужном порядке? Допустим, у вас три бота в комнате, как вы задизайните систему при условии что они все могут убежать одновременно? Что случится, если один их них умрет во время убегания, как вы убедитесь, что остальные не застряли и его не ждут?

Узнаем у геймдизайнеров один ли лифт в игре. Скорее всего он один, поэтому скриптуем его.
Здесь можно реализовать групповое поведение, например на blackboard'ах. Основной проблемой тут будут проверки, много проверок. Что убежавший до кнопки добежал и кнопку нажал, убедиться, что лифт приехал и не пихать их всех в шахту, что все влезают в лифт и т.п.
Обсуждение и более подробно описанные варианты решения тут.

(1f)Вам дана задача разработать игру похожую на Thief: The Dark Project и вам нужно сделать стражников с неидеальными слухом и зрением и посадить их в тускло освещенные замки. Они могут искать игрока, если они думают, что к ним кто-то вторгся. Как вы смоделируете систему сенсоров для этих стражников, как вы будете собирать аудио, визуальные и другие стимулы системы? Как вы реализуете различные уровни тревоги стражников и почему?

Система сенсоров Thief'а описана здесь.

(1g)Что такое планирование? Как оно используется и в чем его преимущества? Реально ли использовать планирование в реалтайм игре? Если да, то назовите игры, в которых планирование было реализовано как часть ИИ. Опишите архитектуру систему ИИ с планированием для любого жанра игры.

В целом про планирование: The Planning System.
Правильные ключевые слова: GOAP, STRIPS, HTN.
Также см. тут.

(1h)Вы работаете над игрой, в которой есть дуэль волшебников. У каждого волшебника есть как минимум дюжина заклинаний, некоторые их них наносят урон, некоторые на какое-то время оглушают или останавливают игрока, замедляют его, не дают ему использовать его заклинания недолгое время, телепортируют кастовавшего на короткое расстояние или дают ему временную броню. Волшебник может накладывать только одно заклинание за раз, у каждого заклинания есть фиксированный кулдаун (время, через которое заклинание может быть использовано снова) и стоимость в мане (регенеранции маны нет). Опишите реализацию ИИ для такого волшебника.

Делим все заклинания на "атакующие", "защитные" и еще какие-нибудь по вкусу. В зависимости от того, сколько маны и хитпоинтов у нас, сколько у противника используем заклинание из нужной группы, выбираем его рандомно.
Более подробное описание см. тут.
Этого должно хватить. Если геймдизайнерам это не понравится, можно использовать более умные методы.

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

Что-то не густо с ответами на мою задачу. Как и обещал хозяйке поста - мои варианты решения задачи. Их несколько, ну как и у любой интересно задачи. Первая реализация, которую я сразу придумал занимаясь когда-то этой задачей называется Steering behaviour. Реализация в моем случае была достаточно простая: к НПЦ, идущим по просчитанному заранее пути прикладываются силы. Первая возникает только тогда, когда НПЦ отклоняется от просчитанной траектории и старается "вернуть" НПЦ на траекторию. Вторая возникает когда поблизости возникает другой НПЦ. НПЦ отталкиваются друг от друга как одинаковые заряды. Этот способ конечно не нов и использовался уже в играх (я на КРИ пару раз слышал такие идеи от АИ программистов). Что-то подобное реализовано, как я понимаю, тут http://opensteer.sourceforge.net/
Второй подход - реализовать все с помощью коллижена. НПЦ ходят в виде больших вертикальных цилиндров. Когда на некотором апдейте они заколлизятся то их их скорости просто вычитается проекция вектора скорости на линию центров (нужно конечно немножко читить чтобы при этом скорость не оказалась равна 0). Визуально выглядит этот вариант не очень красиво :(
Третий подход, о котором я сам недавно узнал - на основании данных о размерах и желаемых скоростях объектов составлять и решать некоторую оптимизационную задачу. В результате решения задачи получим скорость, применяя которую на данном апдейте мы гарантированно не заколлизимся. Статья с подробным описанием для интересующихся тут http://gamma.cs.unc.edu/CA/

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

Updated: вопросы вызвали неожиданную реакцию и народ предался самоуничижению, что отнюдь не было моей целью. Думайте, ошибайтесь. Эти вопросы, они для того, чтобы научиться, чтобы посмотреть на реальные примеры задач из работы ai-программера.

Вопросы из собеседования по ИИ в играх

2010-03-01T00:46:00.007+03:00

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

Там не только чисто теоретические вопросы, но и много задач, которые реально возникали у него в работе.

Я думаю, многим будет интересно на них посмотреть и попробовать самим поотвечать. Поэтому в течение недели я буду их переводить и постить пачками каждый день с понедельника по пятницу. А в выходные ~~будут танцы!~~ допишу к ним ответы.
Оглавление:
Поведенческий ИИ
Работа с пространством и скриптование
Стиринги
Поиск пути и навигация
Общие вопросы

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

Updated:
Вопросы задавал Пол Тозур(Paul Tozour): Interviewing AI Developers
Часть ответов можно найти на форумах aigamedev.com и тут: Response to AI Developer Interview Questions - Part 1.