diff options
| -rw-r--r-- | schema.sql | 80 | ||||
| -rw-r--r-- | server.js | 286 | ||||
| -rw-r--r-- | views/about.pug | 20 | ||||
| -rw-r--r-- | views/admin_match.pug | 53 | ||||
| -rw-r--r-- | views/header.pug | 2 | ||||
| -rw-r--r-- | views/match.pug | 71 |
6 files changed, 512 insertions, 0 deletions
@@ -208,6 +208,44 @@ create table if not exists setups ( unique (title_id, player_count, scenario) ); +create table if not exists tickets ( + ticket_id integer primary key, + user_id integer, + setup_id integer, + pace integer, + time real, -- julianday + unique (user_id, setup_id, pace) +); + +drop view if exists ticket_rating_view; +create view ticket_rating_view as + select + tickets.*, + coalesce(rating, 1500) as rating + from tickets + join setups using(setup_id) + left join ratings using(title_id, user_id) + where time < julianday('now', '-30 seconds') +; + +drop view if exists matchmaking_view; +create view matchmaking_view as + select + setup_id, + pace, + count(1) / player_count as n, + julianday() - min(time) as age + from + tickets + join setups using(setup_id) + where + time < julianday('now', '-30 seconds') + group by + setup_id, pace + having n > 0 + order by age desc +; + -- Friend and Block Lists -- create table if not exists contacts ( @@ -525,6 +563,47 @@ begin games.game_id = old.game_id; end; +drop trigger if exists trigger_part_check; +create trigger trigger_part_check before delete on players +begin + select + raise(abort, 'Cannot remove players from matches and/or finished games!') + where + old.user_id > 0 and exists ( + select 1 from games where games.game_id=old.game_id and ( is_match or status > 1 ) + ) + ; +end; + +-- Log matchmaking runs and expired tickets + +create table if not exists matchmaking_log ( + time datetime default current_timestamp, + setup_id integer, + pace integer, + age real, + score integer, + tickets json, + matches json +); + +drop view if exists matchmaking_log_view; +create view matchmaking_log_view as + select + time, title_id, player_count, scenario, pace, age, score, tickets, matches + from + matchmaking_log + join setups using(setup_id) +; + +create table if not exists expired_tickets_log ( + user_id integer, + setup_id integer, + pace integer, + ctime datetime, + xtime datetime +); + -- Trigger to remove game data when filing a game as archived drop trigger if exists trigger_archive_game; @@ -570,6 +649,7 @@ begin delete from threads where author_id = old.user_id; delete from game_chat where user_id = old.user_id; delete from ratings where user_id = old.user_id; + delete from tickets where user_id = old.user_id; update games set owner_id = 0 where owner_id = old.user_id; update players set user_id = 0 where user_id = old.user_id; end; @@ -96,6 +96,20 @@ function set_has(set, item) { return false } +function array_remove(array, index) { + let n = array.length + for (let i = index + 1; i < n; ++i) + array[i - 1] = array[i] + array.length = n - 1 +} + +function array_remove_item(array, item) { + let n = array.length + for (let i = 0; i < n; ++i) + if (array[i] === item) + return array_remove(array, i) +} + /* * Notification mail setup. */ @@ -170,6 +184,7 @@ app.locals.SITE_URL = SITE_URL app.locals.ENABLE_MAIL = !!mailer app.locals.ENABLE_WEBHOOKS = !!WEBHOOKS app.locals.ENABLE_FORUM = process.env.FORUM | 0 +app.locals.ENABLE_MATCHES = process.env.MATCHES | 0 app.locals.EMOJI_LIVE = "\u{1f465}" app.locals.EMOJI_FAST = "\u{1f3c1}" @@ -1961,6 +1976,277 @@ function update_elo_ratings(game_id) { } /* + * MATCHMAKING + */ + +const MATCH_LIMIT = 300 + +var _seed = random_seed() + +function random(range) { + // An MLCG using integer arithmetic with doubles. + // https://www.ams.org/journals/mcom/1999-68-225/S0025-5718-99-00996-5/S0025-5718-99-00996-5.pdf + // m = 2**35 − 31 + return (_seed = _seed * 200105 % 34359738337) % range +} + +function shuffle(list) { + // Fisher-Yates shuffle + for (let i = list.length - 1; i > 0; --i) { + let j = random(i + 1) + let tmp = list[j] + list[j] = list[i] + list[i] = tmp + } +} + +const SQL_SELECT_TICKETS_FOR_PACE = SQL("select users.name, rating, setup_id, datetime(time) as time from ticket_rating_view join users using(user_id) where pace=? order by setup_id,time") + +const SQL_SELECT_MATCHMAKING = SQL("select setup_id, n, age from matchmaking_view where pace=?") +const SQL_INSERT_MATCHMAKING_LOG = SQL("insert into matchmaking_log (setup_id,pace,age,score,tickets,matches) values (?,?,?,?,?,?)") + +const SQL_SELECT_TICKETS_FOR_USER = SQL("select tickets.* from tickets join setups using(setup_id) where user_id=? order by pace, title_id, setup_id") +const SQL_SELECT_TICKETS_FOR_SETUP = SQL("select * from ticket_rating_view where setup_id=? and pace=? order by rating") +const SQL_INSERT_TICKET = SQL("insert or replace into tickets (user_id, setup_id, pace, time) values (?,?,?,julianday())") +const SQL_DELETE_TICKET = SQL("delete from tickets where user_id=? and ticket_id=?") +const SQL_DELETE_TICKET_PACE = SQL("delete from tickets where user_id=? and pace=?") +const SQL_DELETE_TICKET_USER = SQL("delete from tickets where user_id=?") + +const SQL_DELETE_TICKET_EXPIRE = SQL("delete from tickets where pace=? and time < julianday('now',?)") +const SQL_INSERT_TICKET_EXPIRE_LOG = SQL(` + insert into expired_tickets_log + (user_id, setup_id, pace, ctime, xtime) + select + user_id, setup_id, pace, datetime(time), datetime() + from + tickets where pace=? and time < julianday('now',?) +`) + +app.get('/games/match', must_be_logged_in, function (req, res) { + res.render('match.pug', { + user: req.user, + limit: check_join_game_limit(req.user), + tickets: SQL_SELECT_TICKETS_FOR_USER.all(req.user.user_id), + }) +}) + +app.get('/admin/match', must_be_administrator, function (req, res) { + res.render('admin_match.pug', { + user: req.user, + live_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(1), + fast_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(2), + slow_tickets: SQL_SELECT_TICKETS_FOR_PACE.all(3), + }) +}) + +app.post('/api/match/queue', must_be_logged_in, function (req, res) { + let pace = req.body.pace | 0 + if (req.body.setups) { + if (typeof req.body.setups === "string") + SQL_INSERT_TICKET.run(req.user.user_id, req.body.setups|0, pace) + else + for (let setup of req.body.setups) + SQL_INSERT_TICKET.run(req.user.user_id, setup|0, pace) + } + res.redirect("/games/match") +}) + +app.post('/api/match/unqueue', must_be_logged_in, function (req, res) { + if (req.body.pace) { + SQL_DELETE_TICKET_PACE.run(req.user.user_id, req.body.pace|0) + } + if (req.body.tickets) { + if (typeof req.body.tickets === "string") + SQL_DELETE_TICKET.run(req.user.user_id, req.body.tickets|0) + else + for (let ticket of req.body.tickets) + SQL_DELETE_TICKET.run(req.user.user_id, ticket|0) + } + res.redirect("/games/match") +}) + +function tick_matches(pace, min_matches, max_age) { + for (let info of SQL_SELECT_MATCHMAKING.all(pace)) { + let setup = SETUP_TABLE[info.setup_id] + console.log("MATCH MAKING TICK (", pace, setup.setup_name, min_matches, max_age.toFixed(2), ") => ", info.n, info.age.toFixed(2)) + if (info.n >= min_matches || info.age >= max_age) + create_matches(setup, pace, info.age) + } +} + +function is_blacklist_match(m) { + for (let a of m) + for (let b of m) + if (a !== b && set_has(a.blacklist, b.user_id)) + return true + return false +} + +function score_ticket_pair(a, b) { + return Math.min(MATCH_LIMIT, Math.abs(a.rating - b.rating)) +} + +function score_ticket_pair_fast(a, b) { + let rd = Math.abs(a.rating - b.rating) + let td = Math.abs(a.time % 1 - b.time % 1) + if (td > 0.5) + td = 1 - td + // Ignore first 3 hour diff, then linearly approach limit at 9 hours + td = Math.max(0, td - 3/24) * (24/6) * MATCH_LIMIT + return Math.min(MATCH_LIMIT, (rd + td) | 0) +} + +function score_match(F, m) { + if (is_blacklist_match(m)) + return MATCH_LIMIT + if (m.length === 2) + return F(m[0], m[1]) + let score = 0 + let n = m.length + for (let a = 0; a < n; ++a) + for (let b = a+1; b < n; ++b) + score += F(m[a], m[b]) ** 2 + return Math.sqrt(score / (n / 2 * (n-1))) | 0 +} + +function add_best_ticket(F, this_match, tickets) { + let best_score = MATCH_LIMIT + let best_ticket = tickets[0] + for (let t of tickets) { + this_match.push(t) + let this_score = score_match(F, this_match) + this_match.pop(t) + if (this_score < best_score) { + best_score = this_score + best_ticket = t + } + } + this_match.push(best_ticket) + array_remove_item(tickets, best_ticket) +} + +function score_partition(F, partition) { + let score = 0 + for (let m of partition) + score += score_match(F, m) ** 2 + return Math.sqrt(score / partition.length) +} + +function partition_matches(F, N, original_tickets, attempts) { + let M = (original_tickets.length / N) | 0 + + let best_partition = null + let best_score = (M * MATCH_LIMIT) ** 2 + + for (let i = 0; i < attempts; ++i) { + var this_partition = [] + + let tickets = original_tickets.slice() + if (i > 0) + shuffle(tickets) + + while (tickets.length >= N) { + let this_match = [ tickets.pop() ] + while (this_match.length < N) + add_best_ticket(F, this_match, tickets) + this_partition.push(this_match) + } + + let this_score = score_partition(F, this_partition) + if (this_score < best_score) { + best_score = this_score + best_partition = this_partition + } + } + + if (best_partition) { + best_partition = best_partition.filter(m => score_match(F, m) < MATCH_LIMIT) + return { score: best_score, matches: best_partition } + } + + return { score: MATCH_LIMIT, matches: [] } +} + +function create_matches(setup, pace, age) { + let N = setup.player_count + let F = score_ticket_pair + let A = 47 + + let tickets = SQL_SELECT_TICKETS_FOR_SETUP.all(setup.setup_id, pace) + for (let t of tickets) + t.blacklist = SQL_SELECT_CONTACT_BLACKLIST.all(t.user_id) + + if (tickets.length < N) + return + + if (pace === PACE_FAST) + F = score_ticket_pair_fast + + let info = partition_matches(F, N, tickets, A) + if (info.matches.length > 0) { + SQL_INSERT_MATCHMAKING_LOG.run(setup.setup_id, pace, age, info.score, JSON.stringify(tickets), JSON.stringify(info.matches)) + for (let match of info.matches) + start_match(setup, pace, match) + } +} + +function start_match(setup, pace, tickets) { + let game_id = 0 + console.log("START MATCH", PACE_NAME[pace], setup.setup_name, tickets.map(t=>t.rating).join(",")) + SQL_BEGIN.run() + try { + game_id = SQL_INSERT_GAME.get( + 0, setup.title_id, setup.scenario, setup.options, setup.player_count, + pace, 0, 1, null, 1 + ) + for (let i = 0; i < tickets.length; ++i) { + SQL_INSERT_PLAYER_ROLE.run(game_id, "Random " + (i+1), tickets[i].user_id, 0) + + if (SQL_COUNT_ACTIVE_GAMES.get(tickets[i].user_id) + 1 >= LIMIT_ACTIVE_GAMES) + SQL_DELETE_TICKET_USER.run(tickets[i].user_id) + else if (pace === PACE_LIVE) + SQL_DELETE_TICKET_PACE.run(tickets[i].user_id, PACE_LIVE) + else + SQL_DELETE_TICKET.run(tickets[i].user_id, tickets[i].ticket_id) + } + SQL_COMMIT.run() + } finally { + if (db.inTransaction) + SQL_ROLLBACK.run() + } + start_game(SQL_SELECT_GAME.get(game_id)) +} + +function tick_slow_matches() { + tick_matches(PACE_SLOW, 3, 1) + SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_SLOW, "-14 days") + SQL_DELETE_TICKET_EXPIRE.run(PACE_SLOW, "-14 days") +} + +function tick_fast_matches() { + // Wait at most one day. + tick_matches(PACE_FAST, 3, 1) + SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_FAST, "-7 days") + SQL_DELETE_TICKET_EXPIRE.run(PACE_FAST, "-7 days") +} + +function tick_live_matches() { + // Wait at most 15 minutes + tick_matches(PACE_LIVE, 2, 0.25 / 24) + SQL_INSERT_TICKET_EXPIRE_LOG.run(PACE_LIVE, "-3 hours") + SQL_DELETE_TICKET_EXPIRE.run(PACE_LIVE, "-3 hours") +} + +if (app.locals.ENABLE_MATCHES) { + setInterval(tick_live_matches, 1000 * 60) + setInterval(tick_fast_matches, 1000 * 60 * 5) + setInterval(tick_slow_matches, 1000 * 60 * 15) + setTimeout(tick_live_matches, 1000 * 10) + setTimeout(tick_fast_matches, 1000 * 20) + setTimeout(tick_slow_matches, 1000 * 30) +} + +/* * MAIL NOTIFICATIONS */ diff --git a/views/about.pug b/views/about.pug index dd12772..85522df 100644 --- a/views/about.pug +++ b/views/about.pug @@ -74,6 +74,26 @@ html If you want to play with friends, check the "private" checkbox and invite your friends from the join page after you have created the game. + h2 Matchmaking + + p. + The match maker will match players up and start games automatically + once there are enough people waiting for the same game. + Players will be matched with opponents of similar Elo ratings when possible. + + p. + Live tickets expire after 3 hours if you don't get a match. + All of your other Live tickets are removed when you get matched for a Live game. + + p. + Fast tickets take the time of day into account. + Queue up when you want to start playing for the best results. + + p. + <i>Don't queue up for too many games!</i> + It can take a while for the matches to start, + so you may end up with more games than you can handle. + h2 Privacy statement p When you create an account we collect the following personal information: diff --git a/views/admin_match.pug b/views/admin_match.pug new file mode 100644 index 0000000..11a6c54 --- /dev/null +++ b/views/admin_match.pug @@ -0,0 +1,53 @@ +//- vim:ts=4:sw=4: + +mixin show_ticket(ticket) + - var setup = SETUP_TABLE[ticket.setup_id] + tr + td= ticket.name + td= ticket.rating + td= setup.setup_name + td #{ticket.time} UTC + +mixin show_ticket_list(list) + table + thead + tr + th User + th Rating + th Title + th Age + tbody + each ticket in list + +show_ticket(ticket) + +doctype html +html + head + include head + title Matches + style. + div.buttons { margin-top: 8px } + body + include header + article + h1 Waiting Room - Admin + + p Time is #{new Date().toISOString()} + + h2 Live Tickets + if live_tickets.length > 0 + +show_ticket_list(live_tickets) + else + p No live tickets. + + h2 Fast Tickets + if fast_tickets.length > 0 + +show_ticket_list(fast_tickets) + else + p No fast tickets. + + h2 Slow Tickets + if slow_tickets.length > 0 + +show_ticket_list(slow_tickets) + else + p No slow tickets. diff --git a/views/header.pug b/views/header.pug index 454c35a..dfeef5c 100644 --- a/views/header.pug +++ b/views/header.pug @@ -6,6 +6,8 @@ header if user if ENABLE_FORUM a(href="/forum") Forum + if ENABLE_MATCHES + a(href="/games/match") Match a(href="/games/public") Public if user.waiting > 0 a(href="/games/active") Games (#{user.waiting}) diff --git a/views/match.pug b/views/match.pug new file mode 100644 index 0000000..504cef5 --- /dev/null +++ b/views/match.pug @@ -0,0 +1,71 @@ +//- vim:ts=4:sw=4: + +mixin show_ticket(ticket) + - var setup = SETUP_TABLE[ticket.setup_id] + label + input(type="checkbox" name="tickets" value=ticket.ticket_id) + case ticket.pace + when 1 + | #{EMOJI_LIVE} #{setup.setup_name} + when 2 + | #{EMOJI_FAST} #{setup.setup_name} + when 3 + | #{EMOJI_SLOW} #{setup.setup_name} + +mixin show_setup(setup) + label + input(type="checkbox" name="setups" value=setup.setup_id) + | #{setup.setup_name} + +mixin show_setup_list(list) + each setup in list + +show_setup(setup) + +doctype html +html + head + include head + title Matches + style. + label { display: block; margin: 2px 0; user-select: none } + div.group, details { margin: 6px 0 } + details > summary { user-select: none } + details > label { margin-left: 24px } + body + include header + article + h1 The Miraculous Match-making Machine + + p People go in one end; games come out the other. + + h2 Tickets + if tickets.length > 0 + form(method="post" action="/api/match/unqueue") + each ticket in tickets + +show_ticket(ticket) + if tickets.length > 7 + p + i Don't sign up for more games than you will be able to handle! + p + button(name="submit") ❌ Delete + else + p You are not queued for any matches. + + h2 Register + if limit + p.error= limit + else + form(method="post" action="/api/match/queue") + each title in TITLE_LIST + if title.setups.length > 2 + details + summary + u= title.title_name + +show_setup_list(title.setups) + else + div.group + +show_setup_list(title.setups) + p + button(name="pace" value=1) #{EMOJI_LIVE} Play Live + button(name="pace" value=2) #{EMOJI_FAST} Play Fast + button(name="pace" value=3) #{EMOJI_SLOW} Play Slow |