Алгоритм поиска пути для юнитов в игре - это то, что большинство игроков не замечает до тех пор, пока он не начинает работать не совсем правильно, и тогда это маленькая проблемка становится источником ненависти и концом мира. В течении разработки StarCraft были моменты, когда алгоритм поиска пути не работал совсем.
Хотя разработка StarCraft шла вперед, казалось, что она никогда не закончится: до запуска игры всегда оставалось два месяца, но похоже что она не подбиралась ближе к мифической дате поставки. "К счастью" - и я использую здесь этот термин намеренно - у Blizzard был опыт выпускать игры позже.
Хотя мы всегда имели "цели" по поводу даты запуска (хотя правильнее было бы назвать их "желания") мы не делали публичных анонсов до тех пор, пока не было высоких шансов, что игра была бы готова к тому времени. Результатом регламента Blizzard для запуска - "когда это будет готово", было то, что никто не имел ни малейшего представления когда же мы закончим; нашим долгом было выпускать качественные продукты.
В результате, к концу проекта мы имели набор проблем, которые препятствовали запуску. Подобно любой игре на поздних стадиях разработки, мы имели изобилие дефектов, которые должны быть найдены и исправлены, и количество багов все еще исчислялось тысячами.
Многие их этих багов были простыми, и требовали только немного внимания для исправления. Было плохо, что не все.
Другие, как баг с синхронизацией в многопользовательском режиме, выскакивали и требовали отдельного внимания от нескольких членов команды разработчиков - иногда недели на одну единственную проблему. Другие разработчики игр рассказывают о похожем опыте с их багом с синхронизацией: Ages of Empires и Supreme Commander.
Некоторые баги относились к процессу разработки как таковому. Carrier протоссов постоянно застревал позади других юнитов - потому что он по своему делал ... всё. В определенный момент времени код для carrier'а был отделен от основной ветки кода и начал расходиться все дальше, без какой-либо надежды на слияние. Постоянно, как только какая-нибудь новая возможность добавлялась к другим юнитам, ее нужно было заново добавлять для Carrier'а. Каждый раз, когда исправлялся баг для других юнитов, подобный баг мог быть найден и в коде carrier'а, только более дьявольский и трудный для исправления.
Но больше всего тянул StarCraft назад алгоритм поиска пути для юнитов.
Нельзя сказать, что алгоритм был полностью неправильным, в большинстве случаев он работал нормально. Но было достаточно пограничных случаев, делающих выпуск игры невозможной.
Юниты могли "застрять" и остановиться на поле боя. Часто они могли старательно искать путь, двигаясь по миллиметру или кружась вокруг, без продвижения к цели. Иногда их совсем клинило, без возможности дальнейшего движения. Целая тактическая группа увязала в пробке, это выглядело как возвращение вечером домой с работы.
Проблема не только разочаровывала игроков, а также ослабляла AI, вследствие чего было невозможно сбалансировать миссии, время на их разработку тратилось впустую.
Хотя я никогда не был первоклассным игроком в RTS, до того, как игра была запущена, я хорошо играл, поскольку выяснил, что Goliath'ы были разбалансированными с сторону усиления атаки, чтобы компенсировать их плохую способность находить путь до цели. Поскольку они были больше, чем остальные наземные юниты, они требовали больше пространства для нахождения пути. Так, аккуратно расставив Goliath'ов рядом с препятсвиями, я мог использовать их огневую мощь чтобы выдержать в критических ситуациях и превзойти "макро" игроков, которые в другой ситуации порвали бы меня на лоскутки. Жаль только мои навыки длились до тех пор, пока Goliath'ов не перебалансировали. Вздох.
Первоначальный алгоритм нахождения пути был грубым - хотя были выбраны хорошие алгоритмы управления движением юнита, они нивелировались плохими решениями, сделанными в течение разработки проекта.
Как мы пришли к такому?
В ранней статье в этом блоге я упоминал трудности нахождения пути. StarCraft был построен на движке Warcraft, который отрисовывал местность, используя плиточный движок, который был оптимизирован для рисования плиток размером 32×32 пикселя, сделанных из 16-ти ячеек размером 8×8 пикселей. Архитектура Warcraft была такой, поскольку он должен был хорошо работать на Super Nintendo и Genesis. Эти консоли имели аппаратную поддержку для отрисовки плиток 8×8 пикселей, но такое поведение было легко эмулировать и на PC.
Поскольку камера в Warcraft I и II смотрела практически сверху вниз, границы объектов (лес, рельеф, постройки) на карте практически одинаковы по горизонтали и вертикали, так что представление мира в виде квадратных плиток способствовало легкому нахождению пути. В этих играх каждая плитка размером 32×32 либо проходима, либо нет. Ниже на рисунке показаны несколько
Но по пути разработчики StarCraft перешли на изометрическую проекцию, чтобы сделать игру более визуально привлекательной (детали в предыдущем посте). Но движок не был перестроен для изометрической проекции, были изменены только изображения.
Новая перспектива выглядела замечательно, но чтобы алгоритм поиска пути работал, необходимо было увеличить разрешение карты для нахождения пути: теперь каждая из 8×8 плиток была либо проходимой, либо нет, увеличивая размер карты для нахождения путь в 16 раз. Хотя лучшее разрешение позволяло уплотнить юниты на карте, это также означало, что поиск пути на карте требовал существенно больших вычислительных затрат из-за большего пространства поиска.
Поиск пути также стал более трудным, поскольку диагональные границы разбивали многие квадратные плитки неровно, делая трудным понимание того, проходима плитка или нет. Удостовериться, что все плитки корректно помечены, требовало скрупулезной работы.
И редактор карт StarCraft было ужасно трудно писать, из-за граничных случаев, которые неизбежно влекло за собой помещение диагональных фигур в карту с квадратными ячейками. Написание специального кода по "исправлению плиток" требовало месяцы программирования.
В отличие от Diablo, которая использовала изометрический движок, разработчики StarCraft сохраняли старый движок, даже когда новые проблемы с этим подходом продолжали выявлялись неделя за неделей.
Это изображение показывает как мост был собран из плиток 8×8; некоторые показаны зеленым. Почти изометрическая перспектива неровно разделяет плитки, образуя ступенчатую фигуру по обеим сторонам моста, как вы можете заметить, красная линия разделяет плитки на неровные фигуры.
Поскольку проект всегда был в двух месяцах от запуска, было немыслимо, что есть достаточно времени на то, чтобы переработать движок, для того чтобы нахождение пути стало проще, так что оставалось только заставить код нахождения пути работать. Для обработки всех хитрых граничных случаев код поиска пути разросся до гигантской машины состояний, в которую были различного вида специализированные "уходим быстро отсюда" хаки.
Час пик
Если и была одна большая проблема с алгоритмом поиска пути, то это та, при которой собирающие ресурсы юниты (Terran SCV, Zerg drone, Protoss probe) попадали в пробку, пытаясь собрать кристаллы или газ (в будущем "минералы"), и они могли крутиться до остановки. Пока игрок был занят подготавливая атаку или отстраивая вторую базу, рабочие на первой базе стояли в пробке, останавливая приток минералов. Когда игрок в следующий раз заглядывал, вся цепочка построек рушилась из-за недостатка денег.
Основная проблема со сбором ресурсов была в том, что игрок хочет достигнуть максимума количества рабочих на одном кристалле для того чтобы максимизировать приток денег. Эти рабочие мотаются между базой и минералами и постоянно втыкаются в идущих навстречу рабочих. Имея много рабочих на небольшом пространстве, очень вероятно, что кто-то из них застрянет и не сможет выбраться пока минералы не закончатся.
Как мы выбрались?
Я или сам попросился, или меня попросили посмотреть что можно сделать; после стольких лет я уже не помню. После долгого изучения кода нахождения пути я понял, что я недостаточно умен, чтобы просто "исправить проблему". Так что вместо этого я применил грязный хак.
Хотя программисты могут быть одержимы нахождением более чистого, общего и даже безупречного решения проблемы, бывает время, когда приходится чем-то жертвовать. Если все сделано хорошо, никто не заметит компромиссов, которые были сделаны, как это описано в статье Brandon Sheffield Dirty Coding Tricks.
Моя идея была простой: когда рабочие на пути к минералам или идут с ними обратно, они игнорируют любые коллизии с
Можно заметить это, если выбрать большую группу рабочих, работающих над одним кристаллом, и приказать им остановиться. Они немедленно расползутся, чтобы занять плитки, не занятые другими рабочими.
Это поведение очевидно, когда вы смотрите, но незаметно при поверхностном взгляде - это не всплывает на уровень осознания, но игроки профессионального уровня и создатели карт/модов замечают.
Коротко, это работает, что и есть лучший вид хака.
И хотя было гораздо больше работы для завершения игры, этот хак было то, что позволило нам выпускаться без серьезных и долгих переработок.
Разработчики смогли обойти некоторые другие проблемы нахождения пути, и просто проигнорировать остальные, тем не менее, Dragoon протоссов в частности, получил дурную репутацию, поскольку, как самый большой наземный юнит, часто плохо находил путь.
В конечном итоге поиск пути заработал достаточно хорошо, а мы все получили хороший урок о надежде и принятии желаемого за действительное как средств составления плана.
