Хак поиска кратчайшего пути в StarCraft

Один из ведущих разработчиков Warcraft и Starcraft Патрик Вайат периодически публикует воспоминания о своей работе в компании Blizzard в 90-е годы. Очень интересно посмотреть изнутри на процесс разработки игр, которые стали впоследствии культовыми. В последней заметке Патрик поведал замечательную историю, как пришлось впопыхах исправлять баги в StarCraft перед выпуском игры и что из этого получилось.

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

Финальный релиз игры откладывался снова и снова, проходили годы, но дедлайн «два месяца» оставался неизменным. Отсюда и растут ноги у тех «грязных хаков», о которых рассказывает Патрик Вайат.

Почему компания поставила такой дедлайн? Дело в том, что на игровой конференции E3 в 1996 году компания Ion Storm неожиданно показала потрясающую демку Dominion Storm.

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

Какую бы игру вы купили, будь у вас выбор, задаёт риторический вопрос Патрик Вайат. Разработчики Blizzard отошли от шока и приняли решение переписать графический движок StarCraft под изометрические тайлы.

Графический движок полностью переделали, и в условиях дедлайна Патрика Вайат с коллегами бросились закрывать баги. Он говорит, что их были «тысячи». Некоторые мог выявить и устранить один разработчик за пару часов. Другие — как баг синхронизации в многопользовательском режиме — требовали сконцентрированной работы нескольких разработчиков в течение нескольких дней. Был и третья категория багов, которые связаны с пробелами в процессе разработки. Например, код протосса-авианосца (Protoss Carrier) в своё время выделили в отдельную ветку, и не смогли влить её обратно. Таким образом, этот протосс существовал отдельно от основного кода, и любые изменения, которые вносились во все юниты, нужно было потом отдельно вносить в него. Так же, и любые выявленные баги в игре нужно было отдельно исправлять в авианосце. В итоге вышло, что он вообще всё делал особым образом, выделяясь среди всех юнитов. Можно было бы и «убить» этот юнит, но уж очень он всем полюбился, так что авианосец решили оставить.

Патрик Вайат говорит, что особенно большое количество багов возникло с работой движка по поиску маршрутов для юнитов (path-finding). Если графический движок переписали под изометрические тайлы, то алгоритм поиска маршрутов в условиях дедлайна решили взять старый, от Warcraft (в отличие от Diablo, куда встроили полноценный изометрический движок передвижения юнитов). Он был оптимизирован под тайлы 32х32 пиксела, составленные из 16 ячеек по 8х8 пикселов. Такую схему выбрали в своё время, чтобы оптимизировать графику под 8-битную приставку Super Nintendo, поскольку там имелось аппаратное ускорение для рендеринга тайлов 8х8.

Поскольку камера в Warcraft I и II смотрит сверху вниз, края графических объектов (лес, строения, объекты местности) имеют либо горизонтальное, либо вертикальное положение, и поиск маршрута для юнитов осуществлялся без проблем. Каждый тайл 32х32 был либо проходим целиком, либо непроходим. На скриншоте проходимые и непроходимые тайлы показаны зелёным и красным цветом.

Но для StarCraft графику сделали изометрический, так что игра стала визуально более привлекательной. Но чтобы старый движок поиска маршрутов работал на изометрической графике, пришлось увеличить разрешение карты: теперь каждый тайл 8х8 должен быть проходим или непроходим. Хотя лучшее разрешение позволило поместить больше юнитов на карту, но нагрузка для вычисления маршрута увеличилась в 16 раз!

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

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

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

Патрик Вайат изучил проблему и понял, что у него не хватит ума решить её фундаментальным образом, изменив алгоритм. Юниты постоянно меняют свои координаты и должны, следовательно, постоянно пересчитывать маршрут, в зависимости от маршрутов других юнитов (кстати, эта задача близка к NP-полным задачам). Поэтому он решил, что здесь не обойтись без грязного хака — поэтому Патрик полностью удалил часть кода, которая отвечала за предотвращение столкновений рабочих юнитов с другими юнитами.

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

P.S. Релиз StarCraft состоялся в мае 1998 года. Кстати, игра Dominion Storm вышла только через месяц после StarCraft, и вообще не оправдала ожиданий. Как выяснилось, в компании Ion Storm в те годы разразился острый конфликт между руководством и разработчиками. Патрик Вайат ссылается на эту статью и в качестве примера приводит «свою любимую» цитату, чтобы понять, как общались в компании: «Ещё скажи спасибо, что мы списали твою машину и дом, грёбаная ты крысолицая с#ка». Очевидно, что в такой рабочей атмосфере трудно было сделать выдающуюся игру. Да и вышеупомянутая демка на игровой конференции E3 в 1996 году, как выяснилось, была фальшивкой. Впрочем, Патрик не обижается на конкурентов, а даже благодарен им за то, что они «дали нам хорошего пинка под зад» и вынудили сделать игру качественно иного уровня.

По теме:
Патрик Вайат, «Создание Warcraft» (перевод): первая часть, вторая часть, третья часть