Ищем хайлайты в матчах Dota 2 на примере Collapse на Magnus в рамках The International 2021

Недавно в Dota 2 появилась возможность нарезать видео-ролики в формате .mp4 при просмотре записей матчей. Я не удержался и решил сделать простой алгоритм поиска интересных моментов aka хайлайтов. Вот что из этого получилось на примере последней карты гранд-финала The International 2021, где Collapse из Team Spirit катал PSG.LGD на своем Magnus’е.

Видео ускорено в 1.5 раза.

Под катом

1. Формат записей матчей в Dota 2

2. Парсинг реплеев

3. Анализ событий матча

4. Кластеризация методом DBSCAN

5. Идеи по усовершенствованию подхода

6. Ссылки

Формат записей матчей в Dota 2

Запись матча в Dota 2 называется Replay и представляет из себя файл <match_id>.dem с набором protobuf-событий: клики, урон, хил, сообщения в чат и так далее. Если подсунуть файл клиенту игры, то он воспроизведет все события соответствующего матча. Это замечательная фича, которая позволяет вам открыть пивко и залипнуть в годную каточку после тяжелого дня расковырять структуру реплеев.

Но мы сегодня протобафы ковырять не будем. Вместо этого воспользуемся результатами умельцев из комьюнити (ссылка на репозиторий в конце статьи).

Парсинг реплеев

Естественно умельцы не остановились на достигнутом и реализовали парсер с говорящим названием Clarity. Он написан на Java и представляет из себя набор processor’ов, обрабатывающий события разных типов.

Чтобы не возиться с настройками, поднимем контейнер в Docker. Скачаем репозиторий.

git clone https://github.com/odota/parser.git

Запустим Docker.

sudo service docker start

И выполним build-скрипт.

sudo bash parser/scripts/rebuild.sh

sudo docker build -t odota/parser . sudo docker rm -fv parser sudo docker run -d --name parser --net=host odota/parser

У нас появился парсер.Теперь нужен реплей матча. Есть несколько способов его получить.

I. Скачать через клиент игры

Вы можете скачивать реплеи через вкладку Watch в клиенте игры. Я использовал
match_id = 6227492909.

Результат сохраняется в корневую папку игры. Пример пути на машинах под Windows.

C:\Program Files (x86)\Steam\steamapps\common\dota 2 beta\game\dota\replays\

II. Скачать с OpenDota

Есть возможность скачать реплей с сайта OpenDota (ссылка в коцне статьи). Ребята эмулируют поведение игрового клиента и вытаскивают ссылки на CDN Valve. Последний в свою очередь отдает файлы в сжатом формате, поэтому их нужно предварительно распаковывать.

bzcat replays/6227492909_1934613958.dem.bz2 > replays/6227492909.dem

Допустим мы справились с поиском .dem файла. Прогоним его через парсер.

curl localhost:5600 --data-binary "@replays/6227492909.dem" > replays/6227492909.jsonlinesines

На выходе получим JSON’ы, разделенные символами переноса строки и сохраненные в отдельный файл .jsonlines.

Анализ событий матча

Для удобства дальнейшего анализа расчехлим Python и Jupyter. Считаем файл с предыдущего шага и посчитаем количество событий.

import os import json  REPLAYS_DIR = os.path.join('../replays/')   dem_path = os.path.join(REPLAYS_DIR, '6227492909.jsonlines') with open(dem_path, 'r') as fin:     jsonlines = [json.loads(event) for event in fin.readlines()]      len(jsonlines) > 205385

40-минутный матч превратился в ~200k событий. Посмотрим на их структуру.

jsonlines[10] > {'time': -852, 'type': 'player_slot', 'key': '8', 'value': 131}

jsonlines[100212]  >  {'time': 1011,  'type': 'DOTA_COMBATLOG_MODIFIER_REMOVE',  'value': 0,  'attackername': 'npc_dota_badguys_tower2_top',  'targetname': 'npc_dota_hero_enchantress',  'sourcename': 'dota_unknown',  'targetsourcename': 'dota_unknown',  'attackerhero': False,  'targethero': True,  'attackerillusion': False,  'targetillusion': False,  'inflictor': 'modifier_tower_aura_bonus'}

Видим, что разные события имеют разные поля. Но все события имеют поля type — тип события и time — время в секундах с начала матча. Стоит отметить, что время может принимать отрицательные значения. Это позволяет отделять события до и после выхода крипов (00:00 по часам матча).

Посчитаем количество событий разных типов.

from collections import Counter  Counter([e['type'] for e in jsonlines])  > Counter({'DOTA_COMBATLOG_GAME_STATE': 8,          'player_slot': 10,          'interval': 30580,          'draft_start': 1,          'draft_timings': 24,          'actions': 113360,          'CHAT_MESSAGE_ITEM_PURCHASE': 58,          'DOTA_COMBATLOG_GOLD': 2612,          'DOTA_COMBATLOG_MODIFIER_ADD': 7058,          'DOTA_COMBATLOG_PURCHASE': 522,          'DOTA_ABILITY_LEVEL': 406,          'DOTA_COMBATLOG_ABILITY': 1245,          'chatwheel': 22,          'DOTA_COMBATLOG_ITEM': 1658,          'chat': 10,          'DOTA_COMBATLOG_MODIFIER_REMOVE': 7021,          'pings': 482,          'obs': 34,          'DOTA_COMBATLOG_PLAYERSTATS': 225,          'DOTA_COMBATLOG_DAMAGE': 27580,          'DOTA_COMBATLOG_DEATH': 3260,  ...

Я предположил, что интересными могут оказаться те моменты, когда герои наносят друг другу урон. Рассмотрим подробнее события DOTA_COMBATLOG_DAMAGE. Для начала посчитаем, сколько урона игроки нанесли друг другу.

import pandas as pd  df_damage = pd.DataFrame([     e for e in jsonlines      if e['type'] == 'DOTA_COMBATLOG_DAMAGE' and     e['attackerhero'] and e['targethero'] ])  df_damage.groupby(['attackername', 'targetname']).agg({'value': 'sum'})

Полученные значения я сравнил с выводами на все том же сайте OpenDota и остался доволен, потому что они совпали.

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

df_damage['attackername'].unique()  > array(['npc_dota_hero_ember_spirit', 'npc_dota_hero_kunkka',        'npc_dota_hero_enchantress', 'npc_dota_hero_bane',        'npc_dota_hero_tiny', 'npc_dota_hero_magnataur',        'npc_dota_hero_lycan', 'npc_dota_hero_skywrath_mage',        'npc_dota_hero_winter_wyvern', 'npc_dota_hero_terrorblade'],       dtype=object)

Визуализируем таймлайн урона от игрока Collapse на Magnus по персонажам других игроков.

import matplotlib.pyplot as plt  mask = df_damage['attackername'] == 'npc_dota_hero_magnataur' df_player_damage = df_damage[mask].copy() df_player_damage['ones'] = 1  fig, ax = plt.subplots(figsize=(19, 5)) plt.scatter(     x=df_player_damage['time'] / 60,      y=df_player_damage['ones'] ) plt.plot()

Матчи в Dota 2 можно условно разделить на 2 большие стадии: лайнинг и основная. В случае Collapse это разделение проходит по границе ~10 минут с момента выхода крипов. Герой Magnus раскрывается как раз в основной стадии за счет покупки Blink Dagger и обилия массовых драк. Поэтому отсечем события до 10 минуты, а также увеличим размер точек в зависимости от нанесенного урона.

df_player_late_damage = df_player_damage[df_player_damage['time'] > 10 * 60].copy()  fig, ax = plt.subplots(figsize=(19, 5)) plt.scatter(     x=df_player_late_damage['time'] / 60,      y=df_player_late_damage['ones'],      s=df_player_late_damage['value'] ) plt.plot()

Кластеризация методом DBSCAN

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

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

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

Мы воспользуемся алгоритмом DBSCAN. Суть проста: объединить объекты, которые находятся — окрестности друг друга. Расстояние между объектами можно считать с помощью разных метрик, но в нашем примере хватит самой привычной — Евклидовой.

Причем мы не будем использовать абсолютное значение урона, а только время события. Т.е. для мы просто группируем события с интервалом не более ~30 секунд.

Вторым важным параметром алгоритма является min_samples. Он определяет минимальное число объектов в кластерах. Если вокруг точки мало соседей, то ей присваивается метка -1 — выброс. В данном примере можно взять min_samples = 1 и ничего не сломается, но на практике это может привести к клипам с хайлайтами, у которых начало будет совпадать с концом.

from sklearn.cluster import DBSCAN  dbscan = DBSCAN(eps=30, min_samples=2) cluster = dbscan.fit_predict(df_player_late_damage[['time', 'ones']]) df_player_late_damage['cluster'] = cluster  fig, ax = plt.subplots(figsize=(19, 5)) plt.scatter(     x=df_player_late_damage['time'] / 60,      y=df_player_late_damage['ones'],      s=df_player_late_damage['value'],     c=df_player_late_damage['cluster'] )

Осталось только вспомнить, что кластеры в данном случае — временные промежутки матча. Для нарезки клипов с хайлайтами выделим начало и конец каждего кластера.

df_player_late_damage['stime'] = df_player_late_damage['time'].apply(     lambda t: f'{t // 60}:{str(t % 60).zfill(2)}') df_action = df_player_late_damage.groupby('cluster').agg({'stime': ['first', 'last']}) df_action.sort_values(('stime', 'first'))

Успех! Осталось воспользоваться фичей игры и нарезать клипы. Итоговое видео вы уже видели в начале статьи.

Идеи по усовершенствованию подхода

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

2. Некоторые моменты получились не очень насыщенными. Как отсортировать временные промежутки по эпичности?
   Подсказка: можно использовать не только события урона.

3. Как реализовать автоматическую запись видео, чтобы не приходилось запускать клиент игры и накликивать руками?
   Подсказка: существуют консольные команды demo_goto, demo_gototick.

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

Ссылки

• Структура protobuf

• Clarity

• Fork Clarity от OpenDota

• Матч Team Spirit vs PSG.LGD на OpenDota

• Ссылка на реплей

• Описание алгоритма DBSCAN

• Документация по DBSCAN в scikit-learn

• Примеры метрик