Design a Real-Time Robot Chase Game on a Weighted Terrain Grid

Design the backend for a real-time chase game. A player moves across a 500×500 terrain grid toward a goal cell. Each cell has a height, and moving between cells takes a different amount of time depending on the terrain heights. Several AI-controlled robots continuously find paths toward the player. The player wins by reaching the goal and loses if a robot catches them. Each game has a single human player, but the service must host a large number of concurrent games. The history of every game must be persisted. ### Constraints and Clarifications - The grid size (500×500) comes from the prompt; the number of concurrent games, the robot count, and the tick rate are not given. Estimate them explicitly and let the numbers drive your decisions. - The server, not the client, decides where the player and robots are and whether the game is won or lost. - A move is not instantaneous: its duration depends on terrain, so a player or robot can be partway through a move when something changes. ### Clarifying Questions - Is the game strictly single-player, or could several humans ever share a map later? - Is the robot count per game fixed or configurable, and how large can it get? - Is the terrain pre-generated before the game starts, or generated or changed while the game runs? - How exactly does movement cost depend on height (absolute height, height difference, direction), and are moves 4-directional or 8-directional? - What should happen when the player changes direction in the middle of a move? ### Part 1 — Real-Time Protocol and Game State Choose the client-server communication mechanism and justify it. Then define the in-memory state of one game, including how you represent a move that takes several ticks and how a mid-move direction change is handled. ```hint Model time in the state Think about how a unit that is between two cells can be described with a small amount of data that the server advances every tick and can discard when the player turns. ``` #### What This Part Should Cover - Why the transport must support low-latency, bidirectional messages with the server holding authoritative state. - A concrete state model for terrain, player, goal, and every robot, including in-progress moves. - Tick processing order, input handling, and the win and loss checks. ### Part 2 — Robot Pathfinding at Grid Scale Each robot must move toward the player every tick, and the player keeps moving. Design how robots choose their next step on the weighted terrain. One tempting approach is to precompute, at game creation, the next-step direction for every (start cell, target cell) pair so that each robot does a table lookup per tick. Evaluate that approach with numbers and propose what you would actually build. ```hint Do the arithmetic first Count the cells, then count the (start, target) pairs, and compare the result with the memory available per game when thousands of games run at once. ``` #### What This Part Should Cover - Treating the terrain as a weighted graph and choosing a shortest-path method that respects non-uniform costs. - A quantitative feasibility check of the all-pairs precomputation. - An approach whose per-tick cost scales with the number of robots and the player's movement, and when to recompute. ### Part 3 — Many Concurrent Games and Persistent History Explain how the service hosts many independent games at once and how game history is stored for later retrieval. ```hint Games are independent Consider what a single game needs to share with any other game, and what that implies for where a game's state lives and how connections reach it. ``` #### What This Part Should Cover - Placement of games on servers, routing a player's connection to the server that owns the game, and capacity estimates. - What is written to durable storage, when, and the history schema. - Behavior when a game server crashes or a client disconnects mid-game. ### What a Strong Answer Covers - Requirements clarified before design, with the unresolved rules turned into explicit assumptions. - Numbers computed and used to reject or accept approaches, especially for pathfinding memory and per-tick CPU. - A server-authoritative tick loop with clear state, correct handling of in-progress moves, and deterministic win and loss detection. - Horizontal scaling by game, durable history, and failure handling with observability. ### Follow-up Questions 1. If the terrain could change during a game, which parts of your pathfinding design would break, and how would you adapt them? 2. How would you make robots feel less predictable without letting them become unfairly fast? 3. How would you replay a finished game exactly from the stored history? 4. What metrics would tell you that a game server is falling behind its tick schedule?