Table of Contents

Note: Post is In-Progress

Motivation (Quick Bio-Story)

I finally got my first part-time job (first ever) which is at The Coder School’s Irvine location. My specialization as put on my resume would be coaching young students Roblox Scripting. It has been a while since I have done anything Roblox related (for more than 3 years). While I was away from Roblox, I developed much as a programmer because I learned general programming concepts, developing a web app, interacting with database, and now simultaneously trying to learn about microcontrollers because I want to touch embedded systems in the future. In the intermission between my first and second quarter at UC Irvine, I decided I wanted to implement a feature in Roblox, which would wash away the Roblox’s rust so that I am able to fulfill my job well with ease. Beyond, that, I have a great idea for a Roblox game based on my favorite game on Roblox, Empire Clash.

What is Server Sharding?

As a distributed server architecture, server sharding is splitting one logical game world across multiple server processes so more players can participate. The implementation of server sharding as part of my project is spatial sharding or map partitioning, which is prevalent in games such Foxhole, EVE Online sectors… Each server region is divided into grids. Each zone runs on its own server while players move between zones seemlessly. The inclusion of the term ‘Non-Layered’ means to say that individual grid is one server that force many players of that grid to share the same state: to be simple and concise there will be just one trunk (the server region) and concurrent branches (grids). Note that even though Foxhole’s has designated region zones, they are not instanced. State is shared across one grid. State is saved in a database solution.

Let’s Clarify Our Terms, Borrowing Foxhole’s

  • We’ll designate a collection of server regions as “World”
  • Each grid is one instanced server.

→ Every word has grids.

What Kind of Game Can You Make on Roblox with Grid-Based Server Sharding?

Imagine a procedurally generated game based on rules and assets made by the developer. The players are allowed more freedom but at the same time they can feel their worlds linked together. Their collective actions have consequences on the collective victory. This is game where players can build facilities in order to achieve their collective objective, and with things to build that means resource management, and implementation of economy or system of labor and resources.

My original idea for a game that utilizes region server sharding is derived from Roblox Empire Clash, a game about 4 Monarchic-Napoleonic factions competing for domination, holding the majority of territories. Grid-Based server sharding is perfect for games like this. Domination points can be simply regions with some mechanics to determine domination. Most Roblox games like Empire clash in their mid-to-late stage relies on new-content updates to change the user’s environment (aka. new maps) sacrificing on important game features that will actually drastically change their game like changes to logistics → as complex of a Roblox game as Empire Clash is, it has more “quantity” than “quality”; the developers can add so much more e.g. merchants can only take part in backline logistics and not midline or frontline because they only have one stall. Empire clash’s major update on December 12th reveals the introduction of the calvary class, change to the core mechanics and the overall flow of the game, which is great, doubling the game’s player count in the week of release.

Notwithstanding, instead of adding a new map and only then implement the core mechanics change, make the core mechanics change good so that it contributes to the player’s environment and hence dictating the player’s behavior, not the other way around. The environment does not dictate the player’s behavior as strongly as the core mechanics while implementing new environments take much more resources and time. CFrontInteractive (Empire clash’s development studio) is doing a good job given budget and time constraint but the game’s core mechanics is still not refined because of the attention on the new map. Anyways, the main point is to consider procedurally generated environment given resource constraint and to focus on core mechanics instead. Providing a dynamic environment for players can be achieved through server sharding + procedural generation like that of FoxHole’s exemplary model.

Technical Implementation

That was all talk, let’s get to doing. https://github.com/minh-p/roblox-grid-based-server-sharding

Roblox API

First, let us see what the Roblox Engine offers. Because we are going to be using multiple servers, TeleportService has to be used. Furthermore, the nature of Roblox servers do not allow us to keep a server running for more than a week. Therefore, state must be preserved. To do that, we have to use DataStoreService for storing the server’s state later down the line (e.g. objects/landmarks placed down by players later). Alongside DataStoreService, MemoryStoreService should also be used for cross server operations like storing grids as well as caching while the server is still running.

Basic World and Grids Model

This model assumes that the grids share the same place / code, only differeing in procedural generation and data saved. Physically, of course the World does not exist in the game, it is merely a conceptual classifier for a collection of regions with necessary properties stored. As for the regions they will have several properties needed to be stored in the data store.

Note that each region have to be soft-capped, which means that if the server cap is 100, the region should be capped to 85 so that routers are not hard stopped by Roblox constraints.

Terms

  • Keys

    PK means Primary Key, FK means Foreign Key.

  • Server Status indications:

    1. active → safe to route player here
    2. full → don’t route new players
    3. draining → server is preparing to shut down / migrate. allow exits, avoid new joins.
    4. idle → data exists but no server running → needs to start new one when a player walk to grid.

Data Store vs Memory Store

Data Store should only be updated very sparingly. Memory Store is used as caching for cross-server operations. They’ll be used according to the design. So let’s get started.

Region

What if two players approach a new region grid? What if they create two different places? This is a classic race condition issue. Well, in MemoryStore, we could create a sorted map to store regions that are locked.

Task List

This is where we get to implement world and region model. Here is a task list:

  1. DataStore → setup persisent values like worldID, gridID, gx, gy. These values shouldn’t be updated regularly.
  2. MemoryStore → Region locking (preliminary setup)
  3. Implement region crossing math, get q and r in axial coordinates.
  4. From one region, make it so when the user goes to a certain bound approaching another grid, they ask to teleport and/or create that new grid.
  5. Pass the player’s position put them at the position most sensible in the new region.

Geometry

This project will implement the hexagonal system that FoxHole has.

  • q axis goes ↘ / ↖
  • r axis goes ↙ / ↗

Hence these the hexagon’s neighbors:

(q+1, r)
(q+1, r-1)
(q,   r-1)
(q-1, r)
(q-1, r+1)
(q,   r+1)

We are using the Axial Coordinates system to organize the different server regions: Knowing what region the player has crossed to will be a problem to be solved.

The Math for Region Crossing - Is player crossing? To what grid?

Goal: We want to know whether the player has passed to another region or not (and hence they should be teleported). And as well for routing, we need to know the direction of crossing.

Thankfully, a lot of this math can be generated by AI. Here are the steps I learned from prompt engineering:

  • Step 1

    Converting player world position to fractional axis.

    Let \(s\) be the radius of each hexagonal grid.

    \(q_f = \frac{\sqrt{3}}{3} \frac{x}{s} - \frac{1}{3} \frac{z}{s}\)

    \(r_f = \frac{2}{3} \frac{z}{s}\)

  • Step 2

    Fractional axis → Fractional cube \(x_f = q_f\)

    \(z_f = r_f\)

    \(y_f = -x_f - z_f\)

    Such that: \(x_f + y_f + z_f = 0\)

  • Step 3

    • Cube rounding and constraint enforcing

      \(r_x = round(x_f)\), \(r_y = round(y_f)\), \(r_z = round(z_f)\)

    • Our errors:

      \(d_x = |r_x - x_f|\), \(d_y = |r_y - y_f|\), \(d_z = |r_z - y_z|\)

    • Constraint enforcement

      • If \(d_x > d_y\) and \(d_x > d_z\): \(r_x = -r_y - r_z\)
      • Else if \(d_y > d_x\) and \(d_y > d_z\): \(r_y = -r_x - r_z\)
      • Else: \(r_z = -r_x - r_y\)
      • This enforces the constraint: \(r_x + r_y + r_z = 0\)

  • Step 4

    Cube → Axial We’ll just drop the hidden axis: \(q = r_x\) \(r = r_z\)

  • Region Crossing Check

    Let world’s region be \((0, 0)\). Player entered a new region if the one axial coordinate component from step 4 does not match 0.

  • Neighbor Delta

    The neighbor delta is the axial coordinate returned from step 4. Add neighbor delta to the current world’s gridX, gridY and we’ll get the new grid.

The Math for Region Crossing - Player’s Relative Position on New Shard

Again, a lot of this math was aided by ChatGPT: From the first math excursion, we already have:

  1. How to get the fractional hex axial coordinates
  2. The hex axial coordinates snapped to the nearest grid

Conversion to cartesian from a pointy-top hex axial coordinate where \(s\) is the radius:

  • \(x = s\sqrt{3} (q + \frac{r}{2})\)
  • \(z = s \frac{3}{2}r\)

The hex axial coordinate of the player relative to the snapped hex axial coordinate is simply the difference between the fractional hex axial coordinate and the snapped hex axial coordinate:

  • \(\Delta{}q = q_f - q_s,\quad \Delta{}r = r_f - r_s\)

Hence, our final derived formula is:

  • \(x_{new} = s\sqrt{3} (\Delta{}q + \frac{\Delta{}r}{2})\)
  • \(z_{new} = s \frac{3}{2}\Delta{}r\)

The Math for Region Crossing - Player’s Orientation In New Shard (LEFT UNFINISHED)

→ Don’t implement this. I’ve moved to another interest. This does not work! Roblox already has

x.CFrame.LookVector

Which is a Vector3 value. However, when we cross shards, this value is going to have to be offset by a x angle to snap to the nearest hex direction.

Again, the math is generated by ChatGPT, and AI is here to take our jobs.

  • Let \(\theta_s\) be the source yaw in radians. (Yaw is rotation in the x-z plane).
  • \(d \in{} (0, 1, 2, 3, 4, 5)\)
  • \(\Delta{} = \frac{\pi}{3}\)

The formula is:

  • \(\theta_d = \theta_s + d\Delta\)

Implementation, CFrame formula is:

  • \(C_d = T(p) R_y(\theta_d)\)

    Where \(T(p)\) is translational position and \(R_y(\theta_d)\) is rotation about Y (or the yaw).

Codified, we need to serialize and pass in the position, the lookAt vector of the previous shard, and the enterDir (hex-edge direction index from 0-5):

enterDir = 0  →  (dr, dq) = ( 0, +1)
enterDir = 1  →  (dr, dq) = (-1, +1)
enterDir = 2  →  (dr, dq) = (-1,  0)
enterDir = 3  →  (dr, dq) = ( 0, -1)
enterDir = 4  →  (dr, dq) = (+1, -1)
enterDir = 5  →  (dr, dq) = (+1,  0)

local cf = CFrame.lookAt(position, position + lookVector)
cf *= CFrame.Angles(0, teleportData.enterDir * math.pi/3, 0)
hrp.CFrame = cf

How convienient is my role just plugging in value :))) :((( :)))