MMT Online won Project Bossanova contest

MMT is a MMORPG game prototype developed using bleeding-edge Ungine 3D engine and RunServer middleware. First presented at GDC 2009 in Moscow on Windows, MMT is being reborn on Linux. We have set out to develop a full-featured MMORPG in a fantasy setting with traditional third-view camera and ASWD control.

When Project Bossanova contest began we got only a rough demo of the game available for Windows in Russian, but this demo was ported to Linux, where development will now be focused, and translated into English. Aside from the game engine itself along with its shader technology, which is out of our control, the client will be open source.

RunServer is about 7 years in commercial server development business. We have fast and stable server capable of handling 2500+ online players per cluster node.
Now with Project Bossanova funding we'll spend most of the time developing client content and storyline instead of fighing network, bugs and lags like 99% of other Indie MMO project do.

Most complete profile of our project is available on IndieDB site with screenshots, movies, concepts and developers' comments:
http://www.indiedb.com/games/mmt

Official project page at RunServer:
http://runserver.net/mmt
Дальше..

MMT Demo entered Project Bossanova Contest!

Two years ago our company created MMORPG game prototype called MMT in medieval fantasy setting. Demo used bleeding-edge Unigine 3D engine and RunServer middleware. It was presented on Moscow GDC 2009 (KRI) and then suspended. While the project were rather proff of concept than real game, it had a lot of functionality including rich gameplay, combat, magic system, leveling, classes, items, loot, etc.
Now in year 2011 MMT is being reborn on Linux. We have set out to develop a full-featured MMORPG in a fantasy setting with traditional third-view camera and ASWD control. Game engine was updated to recent version with a lot of improvements and visal effects and now we run on OpenGL.

Now we are proud to enter Project Bossanova contest to get sponsorship for further development of this game.
You can vote for MMT on following page:
http://www.projectbossanova.com/comp/vote

There are also several gameplay videos available on our YouTube channel:
http://www.youtube.com/user/NomadRunserver

Some more screenshots:

Дальше..

Дебрикинг Нук

Расстановка

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

Дебют

Началось все с того, что приехал мне брикнутый девайс с просьбой попробовать его починить. Симптомы классические - надпись "Restoring to Factory update" и тишина.. Где-то через три дня пайки, собирания шлейфов и медитации над логами и сорцами, я осознал, как именно выглядит наша проблема. Девайс грузит u-boot, которому вообще все-равно с какой памятью работать, затем должен грузиться turboboot (промежуточное ядро, которое и умеет делать апдейт/откат), а затем уже полноценное ядро и система. Так вот, turboboot от версии 1.0.0 (а за ним и основное ядро) при инициализации MMC ругается и не подхватывают NAND память - она использует протокол MMC 4.3 или 4.4, поддержка которых появилась лишь в ядре Линукса 2.6.36, а для B&N прошивок 1.4 и 1.5 была бекпортнута на наше ядро. Кстати, именно по-этому и не стартует 1.5.0k на новых Нуках - там та же ошибка.
К этому же времени правдами и неправдами мне удалось выполнить собственный код на брикнутом Нуке, но вышла глупая ситуация - в системе не создалось устройство для NAND, потому и починить ничего нельзя. Возможно, будь я супер-спецом по процессорам и железу, смог бы написать код для обращения к NAND напрямую, но для меня это темный лес.. Другой идеей было взять код UBoot, выкусить работу с MMC и написать свою программу. Примерная оценка трудозатрат на это - не меньше недели фулл-тайм работы, включая изучение чужого кода, идеологии его работы, отладку и тестирование. Много часов я пытался собрать драйвер MMC в виде модуля, который бы выгрузил имеющийся в ядре код и заменил его (это не бред, в драйвере тачскрина я так и сделал), но оказалось, что поддержка нашего железа прибита гвоздями к внутренностям ядра и сделать это очень и очень тяжело (даже если откинуть в сторону всякие "мелочи" вроде невозможности поиска и выгрузки шины по имени, т.к. код find_bus закомментирован в линуксе очень давно).

Миттельшпиль

На другой день я узнал о такой сказочной фиче как kexec. В двух словах, это возможность запустить еще одно ядро прямо из выполняющегося. Я думал, сам turboboot так и работает, но был жестоко разочарован - там какой-то проприетарный код для перехода на другое ядро, а само ядро скомпилировано без поддержки kexec.. Перерыв кучу форумов, я нашел проект, в котором люди пытались сделать kexec в виде подгружаемого модуля. Это была смелая идея, но как я понял, проект таки не был доведен до ума и работал только на Motorola Milestone и DroidX. Самое неприятное, что сам модуль собирали для другого ядра (2.6.29 или старше), да еще и с ARMv7 кодом (у нас ARMv6 процессор). Не говоря о том, что поиск таблицы системных вызовов там был закоменчен и стоял адрес, к нам отношения не имеющий, а сам код после раскомментирования толком ничего и не искал. Уже не скажу, сколько пришлось его бекпортить и дорабатывать подручными средствами, но таки модуль собрался, научился искать syscall_table и его .ko файл мне удалось подгрузить прямо в работающее ядро turboboot.
На этом этапе еще немного пришлось повозиться (снова подручные средства) с исполняемым кодом kexec-tools, дабы его таки запустить, и оказалось, что попытка загрузки любого ядра приводит к перезагрузке устройства... По-сути, модуль сыроват и не дописан, направление бесперспективное. С этой пессимистичной мыслью я и пошел спать.
На следующий день, занимаясь основной работой я вдруг подумал - а если ребут не результат бага, а запланированное поведение? Так и оказалось - один из драйверов WM8350 при попытке выгрузки считал, что время перезапускать систему и отключал питание :) Повлиять на сам драйвер не получилось, потому пришлось переделывать код выгрузки всех драйверов, чтобы именно этот игнорировался. Я чувствовал, что от этого еще будут проблемы, но решил рискнуть. Как результат - устройство стало не перегружаться, а просто сказало "Bye!" и зависло :)

Пат

Расстраивался я не долго и перебором нашел, что не смотря на поддержку uImage и zImage, kexec грузит только не арихвированные ядра. Тут бы и истории конец, но оказалось, что все самосборные ядра, а заодно и заводские 1.4-1.5 доходят до инициализации GPIO и зависают.. Чуть дальше загружалось ядро, выкушенное из turboboot, но потом валилось при загрузке драйвера LCD экрана, да и в целом пользы от него было бы не много. Следующие день или два (казалось, что прошла целая вечность) я собирал собственные ядра, выкидывал оттуда все, что можно (зачем нам e-ink или звук, когда надо только перепрошиться?) и комментировал места, где происходили зависания. В общих случаях так делать нельзя - ядро без GPIO и работать-то не должно, но тут мне таки повезло и я собрал супер-обрезанное ядро, которое умело буквально только работать с MMC (поддержку протокола 4.3 я уже бекпортнул из старших версий ядра). Заодно я сделал собственный образ рам диска для этого ядра и написал скрипт, который при загрузке зальет на MMC карту turboboot и остановится. Тут еще оказался мелкий казус с размещением turboboot - из-за каких-то багов скрипт не мог узнать размер MMC карты (кривой бекпорт? особенность запуска из-под kexec?), потому я рассчитал точное размещение и вбил в скрипт фиксированное число. Это было очень опасно - смещение хоть на один байт привело бы к полному окирпичиванию, но все прошло успешно. На устройство залился новый turboboot, который видел внутреннюю память. Это была почти полная победа - оставалось лишь убедить нового turboboot сделать откат на заводскую прошивку. Он теперь видел NAND и корректно развернул туда заводской образ.. только вот этот образ оказался версии 1.0.0..

Эндшпиль

Не знаю, как туда попала 1.0.0 (видимо, ошибка B&N при изготовлении Refurbished нука), но получилось, что загружается новый turboboot, а затем грузит старое ядро, которое все еще не видит NAND. Более того, на этом этапе я уже не мог выполнить свой код, а нук не загружался и периодически откатывался на прошивку 1.0.0. Причем, в этой заводской прошивке не было turboboot.img, потому и нельзя было вернуться к предыдущему состоянию, потому ситуация выглядела откровенно плохо. Решив не расстраиваться, я вчитался в логи и заметил, что связка turboboot от 1.5 и kernel и 1.0.0 при каждом старте пытается загрузить файл /init (загрузчик Android), причем если вставить SD карточку, то файл ищется и на ней. Издав ликующий звук я записал туда скрипт для загрузки модуля kexec_load.ko и вызова kexec, но снова уперся головой в стену багов: ядро 1.0.0 отличалось от того, что внутри turboboot 1.0.0 и не имеет поддержки /proc/iomem. Это устройство должно сообщать, по каким адресам расположена физическая память, без чего kexec работать не может. Адреса этой памяти далеко не 0-0x1000000, как можно подумать, но к счастью в тоннах логов нужные адреса нашлись и я прописал их в коде самого kexec.
Загрузилось мое мини-ядро, но теперь я заливал на NAND не turboboot, а целиком bravo_update.dat от прошивки 1.5.0n. Конечно, адреса пришлось заранее высчитать на калькуляторе, но тут ошибка уже не была так страшна, да и в целом все прошло успешно - устройство откатилось на "заводскую" 1.5.0n и стало полностью работоспособным.

Вывод

Как видите, ничего особо сложного в этой операции не было, и если кто-то захочет, то без проблем сможет пройти мой путь, написать нужные патчи, собрать модуль kexec, нужные рамдиски и скрипты, научиться выполнять код на брикнутом нуке. Я только буду этому рад :)
А пока этого не произошло, я готов восстановить любое количество брикнутых нуков за небольшое вознаграждение. Пишите на g.a@ua.fm, договоримся.
Когда же мне это надоест - я выложу свои исходники kexec-mod, kexec-tools, модуля mmc и пр. Может кому-то пригодится.

Дальше..

Эвристика в поиске пути

Когда наша команда впервые столкнулась с задачей поиска пути, мы не смогли удержаться от попытки изобрести собственный "велосипед". Путь был тупиковым, что стало ясно уже через несколько недель экспериментов и поиск пути отложили почти на год. И вот через год задачу снова подняли и решили использовать обычный A*. Его описаний в интернете достаточно и в 99% случаев достаточно просто реализовать алгоритм по шаблону. В моем случае именно так и получилось, поиск пути занял свое место в Runserver.Math и в серверах на его основе. Через несколько месяцев появились сообщения, что траектория выходит не очень красивой - агенты довольно неестественно движутся под углами, кратными 45-ти градусам. Через некоторое время мне встретился сайт тов. Amit Pate с описанием и примерами эвристической функции. Вчитавшись я осознал, что в мой код прокралась критическая ошибка..

Теория

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

Манхэттенское расстояние

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

h = D * (|x-fx| + |y-fy|)

x, y - текущие координаты, fx, fy - координаты конечной точки пути, D - вес одного шага.
Главный недостаток этого алгоритма - "ступенчатость" траектории.

Диагональное расстояние

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

ax = |x-fx|
ay = |y-fy|
if ax > ay then
   h = ax * D * √2 + D * (ax - ay)
else
   h = ay * D * √2  + D * (ay - ax)

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

Евклидовое расстояние

Другой подход - использовать реальное расстояние до конечной точки. В этом случае функция получается не идеально сбалансированной, потому что расстояние g считается с учетом движения в 8-ми направлениях, а от точки до конца пути - напрямик. A* все-равно выдаст оптимальный путь, но проверит чуть большее количество точек:

         _________________
h = D * √(x-fx)² + (y-fy)²

Квадрат евклидового расстояния

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

h = D * ((x-fx)² + (y-fy)²)

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

Ситуация усложняется при добавлении препятствий. Квадратичная функция:

Диагональная функция:

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

Алгоритм компаса

Я не придумал, как правильно сформулировать название этого алгоритма. Автор алгоритма (Amit Patel) описал его так:

A different way to break ties is to prefer paths that are along the straight line from the starting point to the goal

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

cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k

sx, sy - координаты начальной точки, k - коэффециент смещения, у автора алгоритма 0.001, cross - модуль векторного произведения вектора движения для текущей и начальной точки.
Для открытых пространств такая функция работает очень хорошо, а вот обход препятствий дает некоторую погрешность, которой можно управлять, меняя значение k. Я так и не нашел баланса этого коэффициента, при котором путь остается оптимальным и не появляется артефакт "возврата":

Алгоритм "наведения"

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

cross = |(x-fx)*(y-py) - (y-fy)*(x-px)|
h = h + cross * k

px, py - координаты предыдущей пройденной точки. Такой подход дает не идеальную картину при движении без препятствий, зато при коэффициенте k = 0.5 обход препятствий смотрится вполне корректно:

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

"Жадный" алгоритм

Результатом дальнейших поисков стала функция, напрочь отрицающая баланс g и h. Это сделало алгоритм из A* явно выраженный Greed Search, который, как ни странно, работает очень быстро и для AI выглядит вполне естественно.
Формула такова:

ax = |x-fx|
ay = |y-fy|
if ax > ay then
   h = ax * D * n
else
   h = ay * D * n
cross = |(x-fx)*(y-sy) - (y-fy)*(x-sx)|
h = h + cross * k

n - весовой фактор, k - коэффициент "наведения".
В приведенной иллюстрации коэффициенты равны 100 и 1 соответственно.

Заключение

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

P.S. Напоследок несколько "живых" примеров работы Greed алгоритма.

Средняя плотность. Расчет занял 228мс, 2689 точек, 5289 проверок видимости:

Большая плотность. Расчет занял 274мс, 2177 точек, 4110 проверок видимости:

Дальше..