Extensibility (NxN board, multiple players) in LLD - System Design Exercise

Design: Extensible Board Game System

Design focuses on the core game engine and architecture for extensibility. UI, network communication, and persistence are out of scope.

Functional Requirements

FR1: Support a board game with a flexible NxN board size.

FR2: Allow multiple players (more than two) to participate in a game.

FR3: Players can join, leave, and take turns in order.

FR4: Game rules should be adaptable to different board sizes and player counts.

FR5: Provide a way to track game state and determine the winner or draw.

FR6: Support basic game actions like placing a piece or moving a piece.

Non-Functional Requirements

NFR1: The system should handle board sizes from 3x3 up to 100x100.

NFR2: Support up to 10 players in a single game.

NFR3: Game state updates should be processed with low latency (<100ms).

NFR4: The design should allow easy addition of new game rules or player types.

NFR5: The system should be maintainable and testable with clear separation of concerns.

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Board representation module

Player management and turn controller

Game rules engine or strategy pattern

Game state manager

Move validator

Design Patterns

Strategy pattern for game rules

Observer pattern for state changes

Command pattern for player actions

Factory pattern for creating players and pieces

Reference Architecture

 +--------------------+       +--------------------+       +--------------------+
 |   Player Manager   |<----->|   Turn Controller  |<----->|   Game State       |
 +--------------------+       +--------------------+       +--------------------+
          ^                             ^                             ^
          |                             |                             |
          |                             |                             |
 +--------------------+       +--------------------+       +--------------------+
 |   Board Module     |<----->|  Rules Engine      |<----->|  Move Validator    |
 +--------------------+       +--------------------+       +--------------------+

Components

Player Manager

Object-oriented classes

Manage player information, joining, leaving, and player order.

Turn Controller

State machine or controller class

Control turn order and notify players when it's their turn.

Game State

In-memory data structures

Store current board state, player states, and game progress.

Board Module

2D array or matrix abstraction

Represent the NxN board and provide methods to update and query cells.

Rules Engine

Strategy pattern classes

Encapsulate game rules and logic for different board sizes and player counts.

Move Validator

Validation logic module

Check if player moves are valid according to current rules and game state.

Request Flow

1. 1. Player Manager registers players and assigns unique IDs.

2. 2. Turn Controller determines which player's turn is next.

3. 3. Player submits a move command to the system.

4. 4. Move Validator checks if the move is valid based on the Rules Engine and current Game State.

5. 5. If valid, Board Module updates the board state.

6. 6. Game State updates player statuses and checks for win/draw conditions via Rules Engine.

7. 7. Turn Controller advances to the next player.

8. 8. Observers or UI components are notified of state changes.

Database Schema

Entities: - Player {player_id (PK), name, status} - Game {game_id (PK), board_size, current_turn_player_id, status} - BoardCell {game_id (FK), row, column, occupant_player_id (nullable)} - Move {move_id (PK), game_id (FK), player_id (FK), from_position (nullable), to_position, timestamp} Relationships: - Game has many Players (N players per game) - Game has many BoardCells (NxN cells) - Player makes many Moves - Moves update BoardCells

Scaling Discussion

Bottlenecks

Large board sizes increase memory and processing time for move validation.

Multiple players increase complexity of turn management and state synchronization.

Rules Engine complexity grows with more game variants and player interactions.

Real-time updates may cause latency if many players act simultaneously.

Solutions

Optimize board representation using sparse data structures for large boards.

Use efficient turn scheduling algorithms and event-driven notifications.

Modularize Rules Engine with plug-in architecture to isolate complexity.

Implement caching and incremental state updates to reduce processing load.

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing components and data flow, 10 minutes discussing scaling and extensibility, 5 minutes summarizing.

Explain how the design supports flexible board sizes and multiple players.

Describe the use of design patterns for extensibility and maintainability.

Discuss how turn management works with many players.

Highlight how the system validates moves and updates game state consistently.

Address potential bottlenecks and scaling strategies.