Real-time Gaming

Real-time Gaming Backend

Проектирование backend для real-time multiplayer игры: matchmaking, синхронизация состояния, компенсация задержек, leaderboards.

Шаг 1: Требования

Функциональные требования

1. Matchmaking: подбор игроков по skill level
2. Game session management: создание, управление, завершение
3. Real-time state synchronization между игроками
4. Leaderboard: глобальный и сезонный рейтинг
5. Replay system: запись и воспроизведение матчей
6. Anti-cheat: валидация действий на сервере

Нефункциональные требования

1. Latency < 50ms (tick rate 20-60 Hz)
2. 1M+ concurrent games
3. Eventual consistency для некритичных данных
4. Strong consistency для результатов матчей

Шаг 2: High-Level архитектура

┌──────────┐    ┌──────────────┐    ┌──────────────────────────────────┐
│  Player  │◄──>│  Gateway     │◄──>│  Game Services                   │
│  Client  │    │  (WebSocket) │    │                                  │
└──────────┘    └──────────────┘    │  ┌────────────┐  ┌────────────┐ │
                                    │  │ Matchmaker │  │ Session    │ │
                                    │  │            │  │ Manager    │ │
                                    │  └─────┬──────┘  └─────┬──────┘ │
                                    │        │               │        │
                                    │  ┌─────▼───────────────▼──────┐ │
                                    │  │     Game Server            │ │
                                    │  │     (Authoritative)        │ │
                                    │  └─────────────┬──────────────┘ │
                                    └────────────────┼────────────────┘
                                                     │
                    ┌────────────────────────────────┼────────────┐
                    │                                │            │
             ┌──────▼──────┐              ┌──────────▼─────┐ ┌───▼──────────┐
             │  State DB   │              │  Leaderboard   │ │  Replay      │
             │  (Redis)    │              │  (Redis)       │ │  Storage     │
             └─────────────┘              └────────────────┘ └──────────────┘

Шаг 3: Детальный дизайн

3.1 Matchmaking Service

<?php

declare(strict_types=1);

final class MatchmakingService
{
    private const INITIAL_RANGE = 100;     // MMR range
    private const MAX_RANGE = 500;          // Max expanded range
    private const EXPAND_INTERVAL = 5;      // Expand every 5 seconds
    private const PLAYERS_PER_MATCH = 10;

    public function __construct(
        private readonly \Redis $redis,
        private readonly GameSessionManager $sessionManager,
    ) {}

    /**
     * Add player to matchmaking queue
     */
    public function enqueue(string $playerId, int $mmr, string $gameMode): void
    {
        $entry = json_encode([
            'player_id' => $playerId,
            'mmr' => $mmr,
            'queued_at' => time(),
            'game_mode' => $gameMode,
        ]);

        // Sorted set by MMR for efficient range queries
        $this->redis->zAdd("matchmaking:{$gameMode}", $mmr, $entry);
    }

    /**
     * Remove player from queue
     */
    public function dequeue(string $playerId, string $gameMode): void
    {
        $members = $this->redis->zRange("matchmaking:{$gameMode}", 0, -1);
        foreach ($members as $member) {
            $data = json_decode($member, true);
            if ($data['player_id'] === $playerId) {
                $this->redis->zRem("matchmaking:{$gameMode}", $member);
                break;
            }
        }
    }

    /**
     * Process matchmaking (called by periodic worker)
     */
    public function processQueue(string $gameMode): array
    {
        $matches = [];
        $now = time();

        // Get all players in queue
        $queue = $this->redis->zRange("matchmaking:{$gameMode}", 0, -1, true);
        $players = [];

        foreach ($queue as $entry => $mmr) {
            $data = json_decode($entry, true);
            $waitTime = $now - $data['queued_at'];

            // Calculate expanded MMR range based on wait time
            $expandedRange = min(
                self::MAX_RANGE,
                self::INITIAL_RANGE + (intdiv($waitTime, self::EXPAND_INTERVAL) * 50),
            );

            $players[] = [
                'entry' => $entry,
                'player_id' => $data['player_id'],
                'mmr' => (int) $mmr,
                'range' => $expandedRange,
            ];
        }

        // Sort by MMR
        usort($players, fn ($a, $b) => $a['mmr'] <=> $b['mmr']);

        // Group compatible players
        $matched = [];
        $currentGroup = [];

        foreach ($players as $player) {
            if (in_array($player['player_id'], $matched, true)) {
                continue;
            }

            $currentGroup[] = $player;

            if (count($currentGroup) >= self::PLAYERS_PER_MATCH) {
                // Verify all players are within range of each other
                if ($this->isGroupCompatible($currentGroup)) {
                    $session = $this->sessionManager->createSession(
                        array_column($currentGroup, 'player_id'),
                        $gameMode,
                    );

                    // Remove from queue
                    foreach ($currentGroup as $p) {
                        $this->redis->zRem("matchmaking:{$gameMode}", $p['entry']);
                        $matched[] = $p['player_id'];
                    }

                    $matches[] = $session;
                }

                $currentGroup = [];
            }
        }

        return $matches;
    }

    private function isGroupCompatible(array $group): bool
    {
        $mmrs = array_column($group, 'mmr');
        $spread = max($mmrs) - min($mmrs);

        // Check if spread is within the widest range
        $maxRange = max(array_column($group, 'range'));
        return $spread <= $maxRange;
    }
}

3.2 Game Server (Authoritative)

<?php

declare(strict_types=1);

final class GameServer
{
    private const TICK_RATE = 20;     // 20 updates per second
    private const TICK_MS = 50;       // 50ms per tick

    /** @var array<string, PlayerState> */
    private array $playerStates = [];

    private GameState $gameState;
    private array $inputBuffer = [];
    private int $tickCount = 0;

    public function __construct(
        private readonly string $sessionId,
        private readonly StatePublisher $publisher,
        private readonly ReplayRecorder $recorder,
        private readonly AntiCheatValidator $antiCheat,
    ) {
        $this->gameState = new GameState();
    }

    /**
     * Receive player input (called from WebSocket)
     */
    public function receiveInput(string $playerId, PlayerInput $input): void
    {
        // 1. Validate input (anti-cheat)
        if (!$this->antiCheat->validateInput($playerId, $input, $this->gameState)) {
            $this->publisher->sendToPlayer($playerId, [
                'type' => 'input_rejected',
                'tick' => $this->tickCount,
                'reason' => 'Invalid input',
            ]);
            return;
        }

        // 2. Buffer input for next tick
        $this->inputBuffer[] = [
            'player_id' => $playerId,
            'input' => $input,
            'received_tick' => $this->tickCount,
        ];
    }

    /**
     * Main game loop tick (called TICK_RATE times per second)
     */
    public function tick(): void
    {
        $this->tickCount++;

        // 1. Process all buffered inputs
        foreach ($this->inputBuffer as $buffered) {
            $this->applyInput(
                $buffered['player_id'],
                $buffered['input'],
            );
        }
        $this->inputBuffer = [];

        // 2. Update game simulation
        $this->gameState->simulate(self::TICK_MS / 1000.0);

        // 3. Check game rules (scoring, collisions, etc.)
        $events = $this->gameState->checkEvents();

        // 4. Record state for replay
        $this->recorder->recordTick($this->sessionId, $this->tickCount, [
            'state' => $this->gameState->serialize(),
            'events' => $events,
        ]);

        // 5. Broadcast state to all players
        $this->broadcastState($events);
    }

    private function applyInput(string $playerId, PlayerInput $input): void
    {
        $state = $this->playerStates[$playerId] ?? null;
        if ($state === null) return;

        // Server-authoritative: apply input and calculate new state
        $state->applyInput($input);

        // Collision detection and resolution
        $this->gameState->resolveCollisions($playerId, $state);

        $this->playerStates[$playerId] = $state;
    }

    private function broadcastState(array $events): void
    {
        $snapshot = [
            'type' => 'state_update',
            'tick' => $this->tickCount,
            'timestamp' => microtime(true),
            'players' => [],
            'events' => $events,
        ];

        foreach ($this->playerStates as $playerId => $state) {
            $snapshot['players'][$playerId] = $state->serialize();
        }

        // Send to all connected players
        foreach (array_keys($this->playerStates) as $playerId) {
            $this->publisher->sendToPlayer($playerId, $snapshot);
        }
    }
}

final class PlayerInput
{
    public function __construct(
        public readonly float $moveX,
        public readonly float $moveY,
        public readonly float $aimAngle,
        public readonly bool $shooting,
        public readonly int $clientTick,
        public readonly float $clientTimestamp,
    ) {}
}

3.3 Leaderboard Service

<?php

declare(strict_types=1);

final class LeaderboardService
{
    public function __construct(
        private readonly \Redis $redis,
    ) {}

    /**
     * Update player score after match
     */
    public function updateScore(string $playerId, int $scoreDelta): int
    {
        $newScore = (int) $this->redis->zIncrBy('leaderboard:global', $scoreDelta, $playerId);

        // Season leaderboard
        $season = $this->getCurrentSeason();
        $this->redis->zIncrBy("leaderboard:season:{$season}", $scoreDelta, $playerId);

        return $newScore;
    }

    /**
     * Get player's rank (1-indexed)
     */
    public function getRank(string $playerId): ?int
    {
        $rank = $this->redis->zRevRank('leaderboard:global', $playerId);
        return $rank !== false ? $rank + 1 : null;
    }

    /**
     * Get top N players
     */
    public function getTopPlayers(int $limit = 100): array
    {
        $results = $this->redis->zRevRange(
            'leaderboard:global',
            0,
            $limit - 1,
            true,
        );

        $leaderboard = [];
        $rank = 1;

        foreach ($results as $playerId => $score) {
            $leaderboard[] = [
                'rank' => $rank++,
                'player_id' => $playerId,
                'score' => (int) $score,
            ];
        }

        return $leaderboard;
    }

    /**
     * Get players around a specific player
     */
    public function getAroundPlayer(string $playerId, int $range = 5): array
    {
        $rank = $this->redis->zRevRank('leaderboard:global', $playerId);

        if ($rank === false) {
            return [];
        }

        $start = max(0, $rank - $range);
        $end = $rank + $range;

        return $this->redis->zRevRange('leaderboard:global', $start, $end, true);
    }

    private function getCurrentSeason(): string
    {
        return date('Y') . '-S' . (int) ceil(date('n') / 3);
    }
}

3.4 Lag Compensation

<?php

declare(strict_types=1);

final class LagCompensation
{
    private const MAX_REWIND_TICKS = 10; // max 500ms rewind at 20Hz

    /** @var array<int, GameStateSnapshot> */
    private array $stateHistory = [];

    /**
     * Store state snapshot for rewind
     */
    public function recordSnapshot(int $tick, GameState $state): void
    {
        $this->stateHistory[$tick] = $state->snapshot();

        // Keep only recent history
        $minTick = $tick - self::MAX_REWIND_TICKS * 2;
        foreach (array_keys($this->stateHistory) as $oldTick) {
            if ($oldTick < $minTick) {
                unset($this->stateHistory[$oldTick]);
            }
        }
    }

    /**
     * Rewind game state to validate a hit
     * (server-side hit validation with lag compensation)
     */
    public function validateHit(
        string $shooterId,
        string $targetId,
        int $clientTick,
        float $aimAngle,
    ): bool {
        // 1. Calculate the tick the client was seeing
        $rewindTick = max(
            min($clientTick, max(array_keys($this->stateHistory))),
            min(array_keys($this->stateHistory)),
        );

        // 2. Get the state at that tick
        $historicState = $this->stateHistory[$rewindTick] ?? null;

        if ($historicState === null) {
            return false; // Too far in the past
        }

        // 3. Check if the shot would hit the target at that time
        $shooterPos = $historicState->getPlayerPosition($shooterId);
        $targetPos = $historicState->getPlayerPosition($targetId);

        if ($shooterPos === null || $targetPos === null) {
            return false;
        }

        // 4. Ray-cast from shooter in aim direction
        return $this->rayIntersectsTarget($shooterPos, $aimAngle, $targetPos);
    }

    private function rayIntersectsTarget(
        array $origin,
        float $angle,
        array $target,
        float $hitRadius = 0.5,
    ): bool {
        // Simplified 2D ray-circle intersection
        $dx = $target['x'] - $origin['x'];
        $dy = $target['y'] - $origin['y'];

        $rayDx = cos(deg2rad($angle));
        $rayDy = sin(deg2rad($angle));

        // Project target onto ray
        $dot = $dx * $rayDx + $dy * $rayDy;
        if ($dot < 0) return false; // Target behind shooter

        $closestX = $origin['x'] + $rayDx * $dot;
        $closestY = $origin['y'] + $rayDy * $dot;

        $distToTarget = sqrt(
            ($closestX - $target['x']) ** 2 + ($closestY - $target['y']) ** 2,
        );

        return $distToTarget <= $hitRadius;
    }
}

Шаг 4: Networking Models

Возможные вопросы интервьюера

1. Authoritative server vs peer-to-peer?

   • Authoritative: сервер -- источник истины (anti-cheat)
   • P2P: один из клиентов -- host (prone to cheating)
   • Для competitive: только authoritative

2. Как обрабатывать disconnect/reconnect?

   • Grace period (30 sec)
   • State snapshot для reconnect
   • AI bot заменяет игрока временно

3. Как масштабировать game servers?

   • Каждый game server обрабатывает N сессий
   • Auto-scaling по количеству активных матчей
   • Regional deployment для latency

4. Tick rate -- почему 20Hz, а не 60Hz?

   • 20Hz = 50ms -- достаточно для большинства игр
   • 60Hz = 16ms -- нужно для competitive FPS
   • Trade-off: bandwidth vs responsiveness