火力基地:游戏中如何匹配对手?
-
21-12-2019 - |
题
我正在实现一个社交国际象棋游戏。每个用户都可以创建一个新游戏,他们会等待系统为他们找到对手。
当用户创建游戏时,他们指定约束:他们想玩的颜色,以及对手的最低国际象棋等级。
对手可以匹配也可以不匹配。 例如,将匹配以下两个对手:
// 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
} }
我担心的是数千名用户同时创建新游戏的场景。如何确保我与对手匹配而不造成僵局?IE。如何防止出现用户 1、用户 2 和用户 3 同时尝试寻找对手且其匹配算法返回用户 99 的情况。如何从这种情况中恢复,仅将用户 99 分配给其中一个?
您将如何利用 Firebase 的强大功能来实现这样的匹配系统?
解决方案
在 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
}
}
其他提示
起点的明显选择是颜色,因为这是一项排他性要求。其他的看起来更像是加权结果,因此它们可以简单地增加或减少权重。
利用最小/最大范围的优先级,并将每个范围保留在单独的“索引”中。然后获取每个的匹配项并创建一个并集。考虑这个结构:
/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 子句。然而,这里正确的答案是搜索应该由搜索引擎执行。这不是简单的 where 条件。这是对最佳匹配的加权搜索,因为颜色等字段不是可选的,或者只是 最好的 匹配,而其他的(可能是排名)是任一方向最接近的匹配,而有些只是影响 质量 比赛的。
查看 手电筒 用于简单的 ElasticSearch 集成。通过这种方法,您应该能够利用 ES 出色的加权工具、动态排序以及执行正确匹配算法所需的一切。
关于僵局。在每秒有数百笔交易之前(即,我不会在这里过多关注)数十万用户参与比赛)。拆分我们将写入接受连接并执行事务的路径,以确保只有一个人成功获取它。将其与读取的数据分开,以便该路径上的锁定不会减慢处理速度。将事务保持在最小大小(如果可能,单个字段)。