《游戏服务端架构·核心系统与契约》3.1 匹配算法与公平性

// file: internal/matchmaking/queue.go
// tier: L1
// verify: go test ./internal/matchmaking/
package matchmaking

import (
	"errors"
	"sort"
	"sync"
	"time"
)

// TeamSize is the 5v5 team size used by 《裂隙战场》.
const TeamSize = 5

var (
	ErrEmptyPlayer = errors.New("matchmaking: empty player id")
	ErrDuplicate   = errors.New("matchmaking: player already queued")
	ErrInvalidMMR  = errors.New("matchmaking: negative mmr or latency")
	ErrPartyTooBig = errors.New("matchmaking: party exceeds team size")
)

// Player is one queued participant; a non-empty Party is indivisible.
type Player struct {
	ID        string
	MMR       int
	LatencyMS int
	Party     string
}

// Window is the relaxation policy at one wait stage.
type Window struct {
	Stage     int
	MMR       int
	LatencyMS int
	MixParty  bool
}

func Expand(wait time.Duration) Window {
	switch sec := int(wait.Seconds()); {
	case sec < 10:
		return Window{Stage: 0, MMR: 50, LatencyMS: 30}
	case sec < 30:
		return Window{Stage: 1, MMR: 100, LatencyMS: 60}
	case sec < 60:
		return Window{Stage: 2, MMR: 200, LatencyMS: 120}
	default:
		return Window{Stage: 3, MMR: 400, LatencyMS: 200, MixParty: true}
	}
}

type Quality struct {
	MMRGap     int
	LatencyGap int
	WaitSec    int
	Score      int
}

func Evaluate(a, b Player, wait time.Duration) Quality {
	mmrGap := abs(a.MMR - b.MMR)
	latGap := abs(a.LatencyMS - b.LatencyMS)
	waitSec := int(wait.Seconds())
	score := 100 - mmrGap/10 - latGap/5 - waitSec/30
	if score < 0 {
		score = 0
	} else if score > 100 {
		score = 100
	}
	return Quality{MMRGap: mmrGap, LatencyGap: latGap, WaitSec: waitSec, Score: score}
}

type Match struct {
	TeamA   []string
	TeamB   []string
	Stage   int
	Quality Quality
}

type ticket struct {
	id      string
	players []Player
	joined  time.Time
}

func (t *ticket) mmr() int {
	sum := 0
	for _, p := range t.players {
		sum += p.MMR
	}
	return sum / len(t.players)
}

func (t *ticket) latency() int {
	max := 0
	for _, p := range t.players {
		if p.LatencyMS > max {
			max = p.LatencyMS
		}
	}
	return max
}

type Queue struct {
	mu       sync.Mutex
	now      func() time.Time
	tickets  []*ticket
	byTicket map[string]*ticket
	byPlayer map[string]string
}

func NewQueue(now func() time.Time) *Queue {
	if now == nil {
		now = time.Now
	}
	return &Queue{now: now, byTicket: map[string]*ticket{}, byPlayer: map[string]string{}}
}

// EnqueueParty adds an indivisible group; a retried party name is a duplicate.
func (q *Queue) EnqueueParty(party string, players []Player) error {
	if len(players) == 0 || len(players) > TeamSize {
		return ErrPartyTooBig
	}
	for _, p := range players {
		if p.ID == "" {
			return ErrEmptyPlayer
		}
		if p.MMR < 0 || p.LatencyMS < 0 {
			return ErrInvalidMMR
		}
	}
	id := party
	if id == "" {
		if len(players) != 1 {
			return ErrPartyTooBig
		}
		id = players[0].ID
	}
	q.mu.Lock()
	defer q.mu.Unlock()
	if _, ok := q.byTicket[id]; ok {
		return ErrDuplicate
	}
	for _, p := range players {
		if _, ok := q.byPlayer[p.ID]; ok {
			return ErrDuplicate
		}
	}
	t := &ticket{id: id, players: append([]Player(nil), players...), joined: q.now()}
	q.tickets = append(q.tickets, t)
	q.byTicket[id] = t
	for _, p := range players {
		q.byPlayer[p.ID] = id
	}
	return nil
}

func (q *Queue) Enqueue(p Player) error { return q.EnqueueParty(p.Party, []Player{p}) }

// TryMatch anchors on the oldest ticket and never splits a party.
func (q *Queue) TryMatch() (Match, bool) {
	q.mu.Lock()
	defer q.mu.Unlock()
	if len(q.tickets) < 2 {
		return Match{}, false
	}
	sort.Slice(q.tickets, func(i, j int) bool {
		if q.tickets[i].joined.Equal(q.tickets[j].joined) {
			return q.tickets[i].id < q.tickets[j].id
		}
		return q.tickets[i].joined.Before(q.tickets[j].joined)
	})
	anchor := q.tickets[0]
	wait := q.now().Sub(anchor.joined)
	w := Expand(wait)

	picked := []*ticket{anchor}
	total, parties := len(anchor.players), 0
	if len(anchor.players) > 1 {
		parties = 1
	}
	for _, t := range q.tickets[1:] {
		if total == 2*TeamSize {
			break
		}
		if len(t.players) > TeamSize || total+len(t.players) > 2*TeamSize {
			continue
		}
		if abs(t.mmr()-anchor.mmr()) > w.MMR || abs(t.latency()-anchor.latency()) > w.LatencyMS {
			continue
		}
		if !w.MixParty && len(t.players) > 1 && parties >= 1 {
			continue
		}
		picked = append(picked, t)
		total += len(t.players)
		if len(t.players) > 1 {
			parties++
		}
	}
	if total != 2*TeamSize {
		return Match{}, false
	}
	teamA, teamB, ok := divide(picked)
	if !ok {
		return Match{}, false
	}
	a, mmrA, latA := summary(teamA)
	b, mmrB, latB := summary(teamB)
	m := Match{TeamA: a, TeamB: b, Stage: w.Stage,
		Quality: Evaluate(Player{MMR: mmrA, LatencyMS: latA},
			Player{MMR: mmrB, LatencyMS: latB}, wait)}
	drop := make(map[*ticket]bool, len(picked))
	for _, t := range picked {
		drop[t] = true
		delete(q.byTicket, t.id)
		for _, p := range t.players {
			delete(q.byPlayer, p.ID)
		}
	}
	kept := q.tickets[:0]
	for _, t := range q.tickets {
		if !drop[t] {
			kept = append(kept, t)
		}
	}
	q.tickets = kept
	return m, true
}

// divide places whole tickets into two teams, highest MMR first.
func divide(tickets []*ticket) ([]*ticket, []*ticket, bool) {
	sort.Slice(tickets, func(i, j int) bool {
		if tickets[i].mmr() == tickets[j].mmr() {
			return tickets[i].id < tickets[j].id
		}
		return tickets[i].mmr() > tickets[j].mmr()
	})
	var a, b []*ticket
	nA, nB, sumA, sumB := 0, 0, 0, 0
	for _, t := range tickets {
		n := len(t.players)
		fitA, fitB := nA+n <= TeamSize, nB+n <= TeamSize
		switch {
		case fitA && (!fitB || sumA <= sumB):
			a, nA, sumA = append(a, t), nA+n, sumA+t.mmr()*n
		case fitB:
			b, nB, sumB = append(b, t), nB+n, sumB+t.mmr()*n
		default:
			return nil, nil, false
		}
	}
	if nA != TeamSize || nB != TeamSize {
		return nil, nil, false
	}
	return a, b, true
}

func summary(ts []*ticket) (ids []string, mmr, latency int) {
	n := 0
	for _, t := range ts {
		n += len(t.players)
		mmr += t.mmr() * len(t.players)
		if v := t.latency(); v > latency {
			latency = v
		}
		for _, p := range t.players {
			ids = append(ids, p.ID)
		}
	}
	sort.Strings(ids)
	if n > 0 {
		mmr /= n
	}
	return ids, mmr, latency
}

func abs(v int) int {
	if v < 0 {
		return -v
	}
	return v
}