Баланс в настольном геймдизайне: строим графы с помощью Google App Script и Gephi

Всем привет! Меня зовут Никита, и я хотел бы поделиться с вами некоторыми практическими аспектами разработки моей настольной игры “Письма призрака” (в этом месяце будет выпущена издательством "Экономикус"). Мы старались подходить к процессу разработки максимально системно, так что наш опыт может оказаться для кого-то интересным.

"Письма призрака" – детективная настольная игра с тайными ролями на дедукцию, блеф и ассоциативное мышление. Если вы любите играть в "Мафию" или "Имаджинариум" – уверен, вам она тоже понравится. Из современных настолок по жанру она ближе всего к "Мистериуму" и "Криминалисту".

Поставленные задачи

Основная механика “Писем призрака” строится на ассоциациях между картами с изображениями различных предметов (картами улик). И на одном из ранних этапов разработки мы задались вопросом: “А можно ли просчитать и выстроить баланс в игре на ассоциации?”. Собственно, почему бы не попробовать.

Задача балансировки ассоциаций состояла примерно в следующем:

• Минимизировать количество сильных “однозначных” ассоциаций. Каждая карта в идеале должна примерно с равной силой ассоциироваться с несколькими другими.

• Избежать “обособленных групп ассоциаций”. Не должно быть групп карт, которые ассоциируются только друг с другом и не ассоциируются ни с какими другими картами.

• Добиться максимальной равномерности и хаотичности распределения ассоциаций по всему множеству карт.

Для задач, в которых нужно отслеживать связи между многочисленными сущностями, лучше всего подходит визуализация в виде графа. Поскольку в игре используется 150 карт улик, строить такой граф вручную – явно не лучшая идея. Дальше пойдёт речь о сервисах и программах, позволивших частично автоматизировать этот процесс.

Инструменты

Google Docs

В последнее время я полностью перешёл на браузерные онлайн-сервисы Google для работы с текстовыми документами и таблицами, чему несказанно рад. Основные преимущества по сравнению с десктопным офисным софтом и синхронизацией офлайн-документов через облако:

• Автоматизация с помощью Google App Script. При наличии минимальных навыков программирования на JS даёт практически безграничные возможности для анализа и формирования данных, а также интеграции с другими онлайн-сервисами.

• Коллективное редактирование документов в реальном времени, режим внесения и одобрения правок. Особенно актуально на этапе финальной доработки и вычитки правил игры, если над проектом работает больше одного человека.

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

Gephi

Довольно мощная бесплатная программа для построения и обработки графов. Для базового ознакомления рекомендую эту статью.

Позволяет строить даже вот такие масштабные штуки:

Подготовка данных

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

Мы условно разделили ассоциации на 4 уровня по силе:

0 – полное отсутствие ассоциаций
1 – слабая ассоциация либо сходство по форме, цвету или материалу
2 – достаточно крепкая ассоциация
3 – однозначная ассоциация

Естественно, ассоциации – явление достаточно субъективное, но мы постарались учесть самые очевидные и часто возникающие.

Чтобы прописать связи между всеми уликами, надо заполнить половину таблицы 150 на 150 ячеек (вторая половина получается зеркальной, так как ассоциации между двумя картами “симметричные”). Достаточно трудоёмкий процесс, который крайне трудно автоматизировать. Разработка нейросети, анализирующей ассоциации между изображениями, в теории возможна, но явно выходит за рамки нашего проекта.

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

Фрагмент получившейся таблицы:

Для этой автоматизации как раз потребовалось использовать скрипты. По координатам выделенной ячейки определяются id карт, которые надо вывести в углу таблицы. Изображения карт берутся из другой таблицы, куда загружены все картинки с соответствующими id.

// Обновление изображений в углу таблицы
function RefreshPictures() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  // Таблица ассоциаций
  var sheet_a = ss.getSheetByName("Ассоциации");
  var range_a = sheet_a.getDataRange();
  // Таблица с картинками
  var sheet_p = ss.getSheetByName("Картинки");
  var range_p = sheet_p.getDataRange();
  
  // Получаем координаты выделенной ячейки
  var row = sheet_a.getActiveCell().getRow();
  var col = sheet_a.getActiveCell().getColumn();
  
  // Получаем id карт
  var id1 = range_a.getCell(row, 1).getDisplayValue().toString();
  var id2 = range_a.getCell(1, col).getDisplayValue().toString();
  
  // Ищем в таблице картинок нужную строчку по id
  var pos_pic1 = RowOfId(id1, range_p);
  var pos_pic2 = RowOfId(id2, range_p);
  
  // Проверяем, удалось ли найти картинки с нужными id
  if (pos_pic1 != -1) {
    // Картинки подгружены в таблицу в виде формул,
    // содержащих ссылки на файлы в облаке
    var pic1_f = range_p.getCell(pos_pic1, 2).getFormula();
    range_a.getCell(2, 1).setFormula(pic1_f);
  }
  else
  {
    range_a.getCell(2, 1).setValue("X");
  }
  
  if (pos_pic2 != -1) {
    var pic2_f = range_p.getCell(pos_pic2, 2).getFormula();
    range_a.getCell(2, 2).setFormula(pic2_f);
  }
  else
  {
    range_a.getCell(2, 2).setValue("X");
  }
}

// Поиск в таблице картинок нужной строчки по id
function RowOfId(id, rng) {  
  var height = rng.getHeight();
  var data = rng.getValues();
  
  for (var i = 1; i < height; i++) {    
    if (data[i][0].toString() == id) {
      return i + 1;
    }
  }
  
  return -1;
}

С загрузкой картинок в таблицу тоже пришлось повозиться. Загружать 150 картинок по одной совсем не хотелось, а закинуть сразу все функционал Google Sheets пока не позволяет (сама возможность вставлять картинки в ячейки таблицы появилась сравнительно недавно). Я написал отдельный скрипт для загрузки всех изображений из папки на гугл-диске, через Google App Script довольно удобно работать с другими их сервисами.

// Загрузка картинок в таблицу из папки в Google Drive
function LoadPicturesFromDrive() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet_p = ss.getSheetByName("Картинки");
  var range_p = sheet_p.getDataRange();
  
  var art_folder = DriveApp.getRootFolder().getFoldersByName("Папка с картинками").next()
  var files = art_folder.getFiles();
  
  // Перебираем все файлы в папке
  var i = 1;
  while (files.hasNext()) {
    var file = files.next();
    
    var file_name = file.getName();
    // Вытаскиваем из имени файла id карты
    var id = file_name.slice(0, file_name.indexOf("."));
    
    // Записываем id в таблицу
    sheet_p.getRange(i + 1, 1).setValue(id);
    
    // Устанавливаем права доступа к файлу
    file.setSharing(DriveApp.Access.ANYONE_WITH_LINK, DriveApp.Permission.VIEW);
    var file_id = file.getId();
    
    // Вставляем картинку в ячейку с помощью формулы IMAGE
    sheet_p.getRange(i + 1, 2).setFormula("=IMAGE(\"" + "https://drive.google.com/uc?export=download&id=" + file_id + "\")");
    
    i = i + 1;
  }
}

Но тут выяснилось, что разработчики из гугла не сумели полноценно подружить Google Sheets и Google Drive, из-за чего примерно 10% всех изображений просто не отображались. Пошарив по форумам, я выяснил, что далеко не первый столкнулся с этой проблемой, и этот баг пока не исправлен. Пришлось дополнительно разбираться с API Dropbox, чтобы сделать загрузку изображений уже оттуда. Поскольку Dropbox не является частью гугловской экосистемы, это потребовало гораздо больше манипуляций, зато в итоге всё заработало безотказно.

// Загрузка картинок в таблицу из папки в Dropbox
function LoadPicturesFromDropbox() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet_p = ss.getSheetByName("Картинки");
  var range_p = sheet_p.getDataRange();
  
  // Задаём параметры для POST-запроса
  var data = {
    "path": "",
    "recursive": false,
    "include_media_info": false,
    "include_deleted": false,
    "include_has_explicit_shared_members": false,
    "include_mounted_folders": true,
    "include_non_downloadable_files": true
  };
  var payload = JSON.stringify(data);
  
  var options = {
    "method" : "POST",
    "contentType" : "application/json",
    "headers" : {
       "Authorization" : "Bearer [код авторизации]"
    },
    "payload" : payload,
    muteHttpExceptions : true
  };
  
  // Отправляем POST-запрос для получения списка файлов в папке
  var url = "https://api.dropboxapi.com/2/files/list_folder";
  var response = UrlFetchApp.fetch(url, options);
  var json = JSON.parse(response.getContentText());
  
  // Обрабатываем полученный список файлов
  for (var i = 0; i < json.entries.length; i++) {
    var name = json.entries[i].name;
    // Создаём публичную ссылку на файл
    CreateSharedLink(name);
    var sh_link = GetSharedLink(name);
    
    // Вытаскиваем из имени файла id карты
    id = name.slice(0, name.indexOf("."))
  
    // Вставляем картинку в ячейку с помощью формулы IMAGE
    sheet_p.getRange(i + 2, 1).setValue(id);
    sheet_p.getRange(i + 2, 2).setFormula("=IMAGE(\"" + sh_link+"\")");
  }
}

// Создание публичной ссылки на файл 
function CreateSharedLink(name) {
  // Задаём параметры для POST-запроса
  var data = {
    "path": ("/" + name),
    "settings": {
        "requested_visibility": "public",
        "audience": "public",
        "access": "viewer"
    }
  };
  var payload = JSON.stringify(data);
  
  var options = {
    "method" : "POST",
    "contentType" : "application/json",
    "headers" : {
       "Authorization" : "Bearer [код авторизации]"
    },
    "payload" : payload,
    muteHttpExceptions : true
  };
  
  // Отправляем POST-запрос для создания публичной ссылки на файл
  var url = "https://api.dropboxapi.com/2/sharing/create_shared_link_with_settings";
  var response = UrlFetchApp.fetch(url, options);
}

// Получение публичной ссылки на файл
function GetSharedLink(name) {
  // Задаём параметры для POST-запроса
  var data = {
    "path": ("/" + name)
  };
  var payload = JSON.stringify(data);
  
  var options = {
    "method" : "POST",
    "contentType" : "application/json",
    "headers" : {
       "Authorization" : "Bearer [код авторизации]"
    },
    "payload" : payload,
    muteHttpExceptions : true
  };
  
  // Отправляем POST-запрос для получения публичной ссылки на файл
  var url = "https://api.dropboxapi.com/2/sharing/list_shared_links";
  var response = UrlFetchApp.fetch(url, options);
  var json = JSON.parse(response.getContentText());
  
  // Вытаскиваем ссылку на файл из полученного ответа
  var urlForDownload = json.links[0].url.slice(0, -1) + '1';
  
  return urlForDownload;
}

Получившаяся таблица ассоциаций была преобразована в специальный вид для загрузки в Gephi (опять таки с помощью скриптов) и экспортирована в формате CSV. Нужны две таблицы: таблица меток вершин (столбцы: id, label) и таблица связей между вершинами (столбцы: source, target, weight).

// Преобразование получившейся матрицы в таблицу меток и таблицу связей
function CreateGraph() {
  var ss = SpreadsheetApp.getActiveSpreadsheet();
  var sheet_a = ss.getSheetByName("Ассоциации");
  var range_a = sheet_a.getDataRange();
  var data = range_a.getValues();
  var height = range_a.getHeight();
  
  // Таблица меток вершин
  var sheet_lbl = ss.getSheetByName("Graph Labels");
  // Таблица связей между вершинами
  var sheet_edg = ss.getSheetByName("Graph Edges");
  
  // Массив допустимых весов для связей
  var weights = new Array("1", "2", "3");
  var edg_num = 0;
  
  // Заголовок таблицы меток вершин
  var lbl_header = ["Id", "Label"];
  // Заголовок таблицы связей между вершинами
  var edg_header = ["Source", "Target", "Weight"];
  
  // Очищаем таблицы
  sheet_lbl.clear();
  sheet_edg.clear();
  
  // Добавляем заголовки в таблицы
  sheet_lbl.appendRow(lbl_header);
  sheet_edg.appendRow(edg_header);
  
  // Список, в котором мы будем накапливать связи между вершинами
  var tmp_arr = [];
  var tmp_arr_len = 0;
  
  // Перебираем все ячейки матрицы (без учёта зеркальных)
  for (var i = 2; i < height; i++) {
    var id1 = data[i][0];
    var name1 = data[i][1];
    
    // Добавляем запись в таблицу меток вершин
    var lbl_row = [id1, name1];
    sheet_lbl.appendRow(lbl_row);
    
    for (var j = i + 1; j < height; j++) {
      var wt = data[i][j].toString();
      
      if (weights.includes(wt)) {
        var id2 = data[0][j];
        edg_num += 1;
        
        var edg_row = [id1, id2, wt];
        
        tmp_arr.push(edg_row);
        tmp_arr_len += 1;
        
        // Как только накопим в списке 100 записей, добавляем их в таблицу связей.
        // Если добавлять записи по одной сразу в таблицу, программа выходит за
        // максимальное допустимое время выполнения Google App Script
        if (tmp_arr_len >= 100) {
          sheet_edg.getRange(sheet_edg.getLastRow() + 1, 1, tmp_arr_len, 3).setValues(tmp_arr);
          tmp_arr = [];
          tmp_arr_len = 0;
        }
      }
    }
  }
  
  // Добавляем оставшиеся в списке записи в таблицу связей
  if (tmp_arr_len > 0) {
    sheet_edg.getRange(sheet_edg.getLastRow() + 1, 1, tmp_arr_len, 3).setValues(tmp_arr);
    tmp_arr = [];
    tmp_arr_len = 0;
  }
}

Построение графа

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

Нагляднее всего получается, если настроить отображение так, чтобы толщина ребра соответствовала силе связи между вершинами. Сразу стало заметно, что связи с силой “1” визуально перегружают граф, так как их слишком много. Поэтому я решил отображать только связи со значениями “2” и “3”. Размер вершины соответствует количеству ведущих от неё связей.

Тем не менее, рёбер всё ещё очень много, и нужно использовать дополнительные настройки визуализации, чтобы можно было извлечь что-то полезное из полученного графа. В данном случае отлично подходит раскраска вершин по “кластерам”, то есть группам наиболее тесно связанных между собой вершин. Для этого используется функция “Модулярность” в разделе “Статистики” программы Gephi. Вот что получилось на одном из этапов разработки, когда в колоду были добавлены около 100 улик:

Видно, что граф полностью связный, нет “обособленных” групп вершин. Связи распределены достаточно равномерно, чего мы и добивались. По распределению цветов на графе можно судить об относительном количестве улик в “кластерах”. Мы ориентировались на это при добавлении новых улик в колоду, стараясь соблюдать примерно одинаковые размеры кластеров.

Конечно, в плане наглядности визуализации графа и способов его анализа ещё есть над чем работать, но данный подход уже неплохо себя проявил. Если вы тоже использовали графы в разработке своих игр, будет очень интересно узнать про ваш опыт.

Если вам интересно следить за развитием проекта, подписывайтесь на группу игры ВКонтакте и Instagram. Там я выкладываю заметки о разработке, сюжетные фрагменты и многое другое.