Огневая база:Как подобрать противников в игре?

Question

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

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

Соперники могут как совпадать, так и не совпадать. Например, следующие два противника будут соответствовать:

// User 1 with rating 1700              // User 2 with rating 1800
// creates this game                    // creates this game
game: {                                 game: { 
  color: 'white',                         minRating: 1650
  minRating: 1600                       }
}                                       // User did not specify a preferred color,
                                        // meaning they do not care which color to play

Итак, если Пользователь 1 является первым пользователем в системе и создал свою игру, он подождет.Как только Пользователь 2 создаст свою игру, он должен быть немедленно сопоставлен с Пользователем 1.

С другой стороны, следующие два противника не будут соответствовать друг другу, потому что они оба хотят играть белыми.В этом случае обоим следует подождать, пока кто-нибудь другой не создаст игру с color: 'black' (или цвет не указан), и minRating это будет соответствовать требованиям.

// User 1 with rating 1700              // User 2 with rating 1800
// creates this game                    // creates this game
game: {                                 game: { 
  color: 'white',                         color: 'white'  
  minRating: 1600                         minRating: 1650
}                                       }

Меня беспокоят сценарии, в которых тысячи пользователей одновременно создают новые игры.Как мне убедиться, что я подбираю противников, не создавая тупиков?то естькак предотвратить сценарии, когда Пользователь 1, Пользователь 2 и Пользователь 3 одновременно пытаются найти противника, а их алгоритмы сопоставления возвращают Пользователя 99.Как мне выйти из этого сценария, назначив пользователя 99 только одному из них?

Как бы вы использовали возможности Firebase для реализации такой системы сопоставления?

Answer 1

Это сложная задача в среде NoSQL, особенно если вы хотите сопоставить несколько полей.

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

indexes: {
  color:{
     white:{
        REF_WITH_PRIORITY_TO_RATING: true
     },
     black:{
        REF_WITH_PRIORITY_TO_RATING: true
     }
  }
}

если вы хотите получать информацию каждый раз, когда матч открывает игру:

ref = new(Firebase)('URL');
query =ref.child('color_index/white/').startAt(minPriority);
query.on('child_added',function(snapshot){
  //here is your new game matching the filter
});

Однако это станет более сложным, если вы, например, введете несколько полей для фильтрации игр. dropRate, timeZone, «Игры сыграны» и т. д.В этом случае вы можете вложить индексы глубже:

indexes: {
  GMT0: {
    color:{
       white:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
       black:{
          REF_WITH_PRIORITY_TO_RATING: true
       },
  }
  GMT1: {
       // etc
  }
}

Answer 2

Очевидным выбором в качестве отправной точки будет цвет, поскольку это исключительное требование.Остальные больше похожи на взвешенные результаты, поэтому их можно просто увеличить или уменьшить вес.

Используйте приоритеты для диапазонов мин/макс и сохраняйте каждый из них в отдельном «индексе».Затем возьмите спички для каждого и создайте союз.Рассмотрим эту структуру:

/matches
/matches/colors/white/$user_id
/matches/ranking/$user_id (with a priority equal to ranking)
/matches/timezones/$user_id (with a priority of the GMT relationship)

Теперь, чтобы выполнить запрос, я бы просто взял совпадения в каждой категории и ранжировал их по количеству совпадений.Я могу начать с цветов, потому что это, по-видимому, не факультативный или относительный рейтинг:

var rootRef = new Firebase('.../matches');

var VALUE = {
   "rank": 10, "timezone": 5, "color": 0
}

var matches = []; // a list of ids sorted by weight
var weights = {}; // an index of ids to weights

var colorRef = rootRef.child('colors/black');
colorRef.on('child_added', addMatch);
colorRef.child('colors/black').on('child_removed', removeMatch);

var rankRef = rootRef.child('ranking').startAt(minRank).endAt(maxRank);
rankRef.on('child_added', addWeight.bind(null, VALUE['rank']));
rankRef.on('child_removed', removeWeight.bind(null, VALUE['rank']));

var tzRef = ref.child('timezone').startAt(minTz).endAt(maxTz);
tzRef.on('child_added', addWeight.bind(null, VALUE['timezone']));
tzRef.on('child_removed', removeWeight.bind(null, VALUE['timezone']));

function addMatch(snap) {
   var key = snap.name();
   weights[key] = VALUE['color'];
   matches.push(key);
   matches.sort(sortcmp);
}

function removeMatch(snap) {
   var key = snap.name();
   var i = matches.indexOf(key);
   if( i > -1 ) { matches.splice(i, 1); }
   delete weights[key]; 
}

function addWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] += amt;
      matches.sort(sortcmp);
   }
}

function removeWeight(amt, snap) {
   var key = snap.name();
   if( weights.hasOwnProperty(key) ) {
      weights[key] -= amt;
      matches.sort(sortcmp);
   }
}

function sortcmp(a,b) {
   var x = weights[a];
   var y = weights[b];
   if( x === y ) { return 0; }
   return x > y? 1 : -1;
}

Хорошо, теперь я дал то, о чем все просят в этом примере использования — как создать элементарное предложениеwhere.Однако правильный ответ здесь заключается в том, что поиск должна выполняться поисковой системой.Это не простое состояние.Это взвешенный поиск лучших совпадений, поскольку такие поля, как цвет, не являются обязательными или просто лучший совпадают, в то время как другие (возможно, ранжированные) являются наиболее близкими совпадениями в любом направлении, а некоторые просто влияют на качество матча.

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

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