Недавно я делал тестовое задание в одну некогда известную в нашей стране игровую компанию. Честно говоря, я по-началу был несколько ошарашен дерзостью — ни много ни мало, нужно было всего лишь сделать “прототип клиент-серверной стратегии”. Тянет на несколько дней плотной работы! Но я все же решил ввязаться в это. Ну, мне ведь не слабо, да?
Постановка задачи довольно простая: плоский ячеечный мир, от 7 до 12 клеток по каждой оси. На старте создается до 5 юнитов, юниты можно выбирать и перемещать. Двигаются юниты по горизонтали или по вертикали, без диагональных перемещений. Вся логика на сервере, клиент должен только отображать то, что получает с сервера.
Первые шаги
Честно говоря, меня сразу увлекло это задание. Именно в этот момент мне нужно было обновлять поддержку TextMesh Pro (т.к. у них появился новый, третий способ распространения, с третьим набором Guid’ов — ура!), но очень уж хотелось кодить это задание. Мне удалось воздержаться непосредственно от кодирования, но, тем не менее, я начал набрасывать некоторую структуру в голове и на бумаге.
Будет у нас сервер на чистом .NET (это условие задачи), будет клиент на Unity 5.6 (а это — пожелание)… хм, видимо, будет пошаренный код, как минимум сетевые сообщения. Первый интересный момент: как передавать перемещения юнитов с сервера на клиент? Я долгое время придерживался идеи про сообщения вида UnitMoving <Id> <From> <To> <StartTime> <EndTime>. То есть, мы говорим, что юнит будет двигаться из клетки From в клетку To с момента времени StartTime до момента времени EndTime. Клиенту остается только интерполировать позицию. Но тогда нам еще нужно синхронизировать время… и, вообще, вводить понятие “времени” на клиенте и его соответствие времени на сервере. В итоге я решил откатиться к буквальному трактованию ТЗ, в котором было написано “получает позиции”. Ок, пускай получает позиции — так будет проще. Но тут возникает другой вопрос: какой протокол использовать? Если мы передаем позиции, то гарантия доставки не важна. И в этом свете очень привлекательным начинает выглядеть UDP. Но ведь остаются сообщения, доставку которых гарантировать нужно (инициализация мира, пользовательские команды). Так что, останавливаемся на TCP и не грузим мозг лишними заботами. В конце концов, это всего лишь прототип!
Хорошо, а что насчет поиска пути?
Про поиск пути
Изначально я подумал “ха, ну это просто A* — наверное они хотят проверить, что я в курсе такой базовой штуки”. Потом понял, что конфигурация поля может менятся в процессе перемещения юнита, поскольку другие юниты тоже могут перемещаться. В процессе поисков и размышлений я наткнулся на Multi-agent Pathfinding. Позалипал в пару пейперов, конечно, ничего не понял. Подумал — ага, значит вы хотите проверить, как я умею решать NP-сложные задачи! Точнее, смогу ли я понять и реализовать алгоритм из научной статьи1 Но чем больше я погружался в тему, тем сильнее понимал, что это навряд ли смысл задания был в этом. И что если я буду копать в эту сторону, то потрачу несколько дней только на эту задачу, а ведь нужно еще все остальное сделать. Да и потом, MAPF сам по себе не решает проблему меняющейся среды. Он решает другую проблему: дать юниту знать о том, что соседняя клетка освободится через полсекунды и лучше просто подождать эти полсекунды на месте, чем тратить две секунды на обход. Это, конечно, must have для полноценной игры, но в прототипе… можно обойтись без.
Итак, в итоге получается, что мне все-таки нужно пересчитывать маршрут каждый кадр? Точнее, каждый раз, когда какой-либо из юнитов переходит из одной ячейки в другую. Это случается реже, чем раз в кадр, но все же довольно часто. Зачем вообще пересчитывать маршрут? Ну, во-первых, ушедший юнит мог освободить более прямой путь к точке назначения. Во-вторых, что более важно, другой юнит мог заградить предполагаемый маршрут. Можно было бы обойтись более простой логикой: пересчитываем маршрут, когда сталкиваемся с препятствием на текущем, а на первый пункт просто забить. Но… как-то это не красиво. Увидь я такое в игре, я бы хмыкнул. Мол, программисты…
Ну хорошо, если при движении по пути все равно нужно проверять коллизии, то, может быть, вообще убрать путь? Пытаемся двигаться в нужном направлении, если есть препятствия — пытаемся обойти. О! А это идея. И потом, у нас же всего до 5 юнитов на карте! Ну разве из них получится составить препятствие, которое сложно обойти? На самом деле — можно, хотя тут вопрос в том, что значит “сложно”.
В итоге этих размышлений я пришел к компромиссному варианту: а почему бы мне не посчитать путь на N клеток вперед? Ну, скажем, на 3 клетки вперед. На столько, сколько нужно для эффективного обхода препятствий на карте, где может быть до 5 юнитов. Так и решил сделать.
Первые ошибки
На самом деле не все вышеописанные размышления я провел ДО начала кодирования. Я вообще придерживаюсь очень инкрементального подхода в разработке. Так что, до начала кодирования я только посмотрел пейперы MAPF и пришел к выводу, что реализовывать все это мне не нужно. Ну а после переключился на код.
Итак, нужно сделать минимальные клиент и сервер. Просто чтобы подключались друг к другу. Вроде бы все просто, но тут я как-то умудрился влезть в яму. Я решил, что использовать блокируемые IO-операции — это как-то… неэкологично и потому решил использовать асинхронные. В .NET 3.5. И в общем-то все шло неплохо, до какого-то момента. А потом я понял, что далее поддерживать этот ад и добавлять в него корректную обработку разрыва соединения — это уже слишком, и выкинул написанное2. Практически все, за исключением разве что сериализации сообщений. И написал заново, без всякой асинхронщины. Старые добрые Read, Write и циклы.
Я потратил несколько часов, может даже полдня, на этот асинхронный эксперимент. И это расстроило. Показало свою ограниченность. Не то, что я асинхронщину не затащил. А то, что я ее вообще начал делать. Зачем? Почему, каждый раз убеждаясь в том, что самое простое решение — это почти всегда то, что надо, я все равно периодически попадаю в эту ловушку? Ну да ладно.
Протокол
Тут все в итоге получилось очень просто (хотя для этого и пришлось влезть в эксперимент с асинхронщиной). Есть иерархия Message’ей — сообщений, которыми по сети обмениваются клиент и сервер. Они сами себя сериализуют. Да, обычно сериализацию принято отделять, т.к.:
- способов сериализации может быть много (двоичный, человеко-читаемый…)
- разделение ответственности (зачем нести в модуль то, что можно сделать в другом модуле?)
Но я решил сделать проще и положиться на виртуальные методы для этой задачки. Иерархия классов берет начало от базового Message и сразу же делится на две ветки:
- Command — то, что клиент шлет серверу
- StatePortion — “кусочек стейта” — то, что сервер шлет клиенту
Были предчувствия, что такое строгое разделение может аукнуться в дальнейшем. Что, если появится какая-то статусная информация, которую клиент должен слать серверу? Да и черт с ним: появится — разберемся. А для данного прототипа такая схема выглядит очень привлекательной, на мой вкус.
Сообщения живут в сборке Common, которая разделяется между клиентом и сервером. Здесь же есть класс RemoteSide — обобщенное представление удаленной стороны, которое позволяет отправлять и принимать Message’ы. В итоге я сделал этот класс Generic’ом: при специализации нужно задать тип отправляемых и получаемых сообщений. Можно сделать RemoteSide<Message, Message> и, таким образом, отказаться от специализации. Но мне очень понравился подход с использованием RemoteSide<StatePortion, Command> на клиенте и RemoteSide<Command, StatePortion> на сервере. Таким образом код, работающий с RemoteSide’ом, имеет хорошую типизацию. Мне не нужно писать обработку ситуации, когда на сервер пришло не то сообщение. Такая ситуация отловится на самом низком уровне — при десериализации сообщения. Т.е., я, по сути, типизирую данные так скоро, как мне это удается. Я обычно не фатанею со статитческой типизации, но конкретно такое применение мне очень понравилось.
Вот UML-диаграмма3 того, что получилось:
Клиент
А на клиенте у нас классическое Unity-приложение. “Точка входа” — класс Client, который сводит воедино всю логику клиентской части:
- Следит за подключением к серверу и, когда подключения нет, отображает соответствующий UI.
- Принимает сообщения с сервера. Некоторые из них обрабатывает сам, остальные — делегирует тому, кто может обработать.
- Подписывается на действия игрока. Когда игрок пытается отправить юнитов, шлет соответствующее сообщение на сервер.
Изначально, конечно, этот класс выглядел не совсем так. Он делал больше работы самостоятельно. Мне вообще кажется, что это один из самых универсальных подходов к разработке: сначала сделай прямо здесь, если ответственности становится много — выноси в отдельное место. При нормально написанном коде это обычно не проблема, ты просто, буквально, берешь куски кода и переносишь их в другое место. Я обычно копирую класс, затем удаляю лишнее из одной версии и из другой. Точнее, с C# я чаще использую глючныйчудесный Rider, но в этом проекте был вынужден обходиться без него.
Итак, Client работает с тремя другими объектами: RemoteServer, PlayerControls и World.
RemoteServer представляет удаленную сторону. Он держит внутри себя отдельный поток для сетевых взаимодействий. Сами взаимодействия проводит с помощью упомянутого ранее RemoteSide, а с основным потоком обменивается через очередь4:
PlayerControls отвечает за пользовательское управление: выбор юнитов и их отправку. Конкретно выбором юнитов заведует отдельный UnitSelector, которому PlayerControls поручает обработку некоторых событий ввода. Внутри PlayerControls есть довольно запутанная стейт-машина, выраженная if’ами и мутабельными полями… была идея попробовать это как-то переписать на корутинах, но так и не дошли руки.
World отвечает за отображение мира игры. Он генерирует объекты-ячейки и юнитов, а также двигает юнитов при получении соответствующего состояния от сервера.
Все описанные классы являются MonoBehaviour’ами. Я вообще люблю MonoBehaviour’ы в Unity. Мне кажется, это довольно удобная штука, в том числе и для представления т.н. “контроллеров”, т.е. классов, которые не являются монстром, мобом или какой-то конкретной особенностью (прыгать, бегать, умирать), а скорее представляют какую-то часть логики всего приложения (выбор юнитов, перемещение юнитов, условия завершения матча). Тем более, Unity имеет встроенный DI-фреймворк, который мне очень нравится использовать, по крайней мере на небольших проектах.
Думаете “WUT, какой DI в Unity”? Дешевый и сердитый: сериализация ассетов. Вы можете создать сцену и накидать в ней иерархию объектов, связать их друг с другом как вам надо. И все. Оно будет само создаваться и связываться — не нужно делать это руками. И не нужно тащить какой-то DI-фреймворк. Нет, конечно, на большом проекте вы, возможно, устанете делать все мышкой и вообще запутаетесь в этих связях (а в связях, создаваемых кодом, не запутаетесь?..). Тогда да, возможно какой-то Zenject — то что надо.
Чтобы было наглядней, вот о чем я говорю:
Сервер
Ну а на сервере у нас старое доброе “Console Application (C#)”:
В Execute() размещается главный цикл сервера, который выглядит вот так:
Тут наверное все и так понятно, но все же. В самом начале мы создаем ClientAcceptor, который в отдельном потоке слушает TCP-порт и принимает входящие подключения. Подключенных клиентов он закидывают в очередь (опять используем тот самый самопальный ConcurrentQueue), из которой их и забирает Server.
Далее мы попадаем в основной цикл сервера, который каждый кадр:
- Забирает у Acceptor’а новых клиентов и “вводит” их в мир (для этого он просто отправляет им текущее состояние мира).
- Удаляет отвалившихся клиентов (RemoteSide, о котором я писал выше, имеет свойство Connected, которое автоматически сбрасывается при любой проблеме).
- Принимает команды от клиентов и скармливает их симуляции. Симуляция в ответ отдает дельту состояния, которая сразу же рассылается всем клиентам.
- Выполняет простенькую синхронизацию: мы просто ждем столько времени, сколько должно быть между кадрами при желаемой частоте. Да, это некорректный способ достичь желаемого, но для прототипа и прототипных нагрузок это работает.
Самая интересная часть сервера — класс World. На сервере World это такая штука, которая хранит состояние всего мира и умеет симулироваться. Вот как выглядит его интерфейс:
Как видите, здесь тоже активно используется та фишка с разделением сообщений на команды и “кусочки стейта”. Да, Message’ы идут прямо в World, т.е. в самую-самую “бизнес-логику”. А почему нет? Кто сказал, что Message — сетевой класс? Из-за сериализации? Ну так ее можно совершенно спокойно убрать оттуда. Да, возможно, на более крупных проектах нужна большая слоенность. Но слоенность ради слоенности… нет.
Возможно некоторого пояснения требует свойство InstantState. Эта штука используется в IntroduceNewClients(), когда сервер должен отправить всем новым клиентам текущее состояние мира. Т.е. InstantState возвращает такой список StatePortion’ов, применение которых должно дать текущее состояние мира. Это, конечно, куда меньший набор изменений, чем все, что происходило в течение игры. На самом деле, это совсем крошечный набор изменений, который на данный момент собирается крайне просто:
Т.е. мы просто шлем размер мира и текущие позиции всех юнитов.
World делегирует перемещение юнитов отдельному классу — UnitMover‘у. Тот, в свою очередь, использует Pathfinding, хотя и не знает об этом: в конструктор UnitMover’у передается функция для нахождения пути из точки A в точку B. Эта функция, в свою очередь, параметризирована другой функцией — предикатом, сообщающим, занята указанная клетка или нет. Кстати, выход за границы карты тоже реализован через этот предикат: мы просто сообщаем, что за границей игровой области все непроходимо, и потому поиск пути никогда не идет туда. Все это звучит немного более запутано, чем есть на самом деле. Чтобы прояснить, как все это связано, вот выжимка кода из трех упомянутых классов:
Когда UnitMover’у требуется найти маршрут, он вызывает findPath и
передает в него версию occupied, опирающуюся на переданный ей в конструктор grid:
Собственно Grid, о котором ничего не упоминалось ранее — это регулярная двухмерная сетка, в которой мы можем размещать юнитов. Grid умеет быстро делать две операции: сообщать, в какой позиции находится указанный юнит и сообщать, какой юнит находится в указанной позиции. По сути, это двунаправленный словарь. Собственно, так он и реализован на данный момент.
Когда я говорил про взаимосвязи UnitMover’а и Pathfinding, внимательный читатель мог заметить несостыковку с тем, о чем я говорил ранее. Ранее я говорил про поиск пути на N клеток вперед, а в существующем коде нет никаких упоминаний про N. Неужто захардкожено прямо в Pathfinding? Нет, не захардкожено.
Действительно, в какой-то из промежуточных версий в findPath передавался дополнительный параметр — максимальная длина маршрута. Но оказалось, что N должно быть довольно большим, чтобы легко обходить препятствия. Либо нужно делать какую-то дополнительную логику непосредственно в UnitMover’е. Например, запрещать перемещения назад. В противном случае юнит может зациклится между двумя вариантами пути, проходя по N клеток то в одну сторону, то в другую. В общем, в итоге я решил все несколько упростить, просто убрав оптимизацию и считая весь путь.
Ну а в том, что касается оптимизаций, можно применить более простой способ: пересчитывать маршрут только когда кто-то из юнитов “наступает” на чужой маршрут. Для этого нужно завести карту, сопоставляющую клетки мира с маршрутами юнитов. Дело нехитрое, но делать я этого не стал. В прототипных масштабах и полный поиск при каждом перемещении работает отлично. Да даже полный поиск каждый кадр сработал бы! :-)
Заключение
Очень много текста вышло, простите за это. И как-то даже не понятно, что я вообще хотел сказать. На самом деле никакой особой морали в этой истории не было. Просто небольшая задачка, съевшая несколько дней моего времени. Довольно забавная. После такого старта даже захотелось развивать прототип дальше и действительно сделать какую-то многопользовательскую стратегию!
Ну а вам, может быть, было занятно понаблюдать за мыслью какого-то разработчика в процессе решения задачи. Я лично люблю истории, построенные на личном опыте, наверное потому и пишу подобное.
Ах да, чуть не забыл, вот что получилось в итоге:
А что касается тестового задания: в ту компанию я “прошел”, но работать к ним не пошел, как и предполагал изначально. Зачем делал? Было интересно побывать у них, пообщаться и послушать, чем живут. Ну и… мне же не слабо? :-)
Примечания
- Это может быть куда сложнее, чем звучит. Например, не так давно у меня возникала потребность слегка модифицировать алгоритм Мейестера для Distance Field трансформаций. Было тяжко.
- Пожалуйста, не расценивайте это как заявление, что в .NET 3.5 невозможно делать асинхронный IO. Просто чтобы его сделать, требуется слишком много усилий. В данном проекте не очень разумно тратить столько усилий на технические прелюдии.
- Хотел было просто привести фрагменты кода, но решил для разнообразия сделать UML. Скачал какую-то программу и словно очутился в начале 2000-х. Серьезно, кто-то думает, что вот это — эффективный способ проектировать ПО? Помню, в Visio был похожий подход. В общем, вряд ли вы еще увидите UML в этом блоге…
- Здесь ConcurrentQueue — мой велосипед (работаем на .NET 3.5), так что если заметили некорректное использование API, не спешите :-)
Было любопытно почитать. Спасибо автору.