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

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

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

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

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


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

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

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

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

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

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

Книга Exploiting Online Games

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

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

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

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

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

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

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

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

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

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

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

-Я поставил себе 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

Организаторы потихоньку выкладывают записи докладов с 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 и на полный экран

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

На днях я решила куда-нибудь потратить завалявшиеся у меня на 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 и напишите об этом у себя в блоге и... дайте ссылку
Сами придумайте еще чего-нибудь.

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

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

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

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

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

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

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

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

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

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

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

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

---

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

---

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

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

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

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

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

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



via lightypp

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

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

Пара слов о том, какие бывают игровые консоли. Есть те, которые надо подключать к телевизору, по-русски они обычно называются "приставки". Сейчас наиболее популярны три из них: 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

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

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

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

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

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

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

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

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

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


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


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

Отчет об ADD-2010

Итак, 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, с исходниками

Этим летом 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

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

По предыдущему посту по поводу доказательства 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 - результаты первой проверки. Есть несколько замечаний по доказательству, но это именно замечания, они не означают, что доказательство неправильное.

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

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

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

В посте 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'у за ссылку.


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

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

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

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

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

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

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

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

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

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

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

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



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


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



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

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

Фильтр Блума

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

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

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

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

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

Пост Will it optimize?

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

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

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

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

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

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

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

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

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

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

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

Все любят смеяться над новичками, которые норовят придумать свой уникальный алгоритм или хэш со сложностью доступа 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. Общие впечатления

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

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

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

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

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

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

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

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

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


CNAM


Указатель


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


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


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


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


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













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

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

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

Все началось с рассказа Паоло Манинетти про гоночный симулятор. Машины и мотоциклы у них едут по идеальной траектории. На это линии есть целевая точка на определенном расстоянии и машина стремится к ней приблизиться. Траектория содержит в себе информацию об идельной скорости. Когда машин много двигают целевую точку, чтобы избежать столкновения. Они пытаются анализировать информацию о том, что происходит на дороге, пытаются определить опасные ситуации. Это отражается на производительности.
Показывали демки с отладочной информацией. Дебагная информация у них богатая.
Искали золотую середину между честной игрой и читерством. Говорят, что чем честнее, тем правдоподобнее. Но тем дороже по производительности.
Каждая трасса тюнится руками, можно в нее записать что-то дополнительно.
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 - это взаимодействие людей и социальный аспект, то есть то, о чем были последние два доклада.
Шампандар обещал конференцию в следующем году в это же время, наказал ничего другого на эти дни не планировать.