A FIFO queue you can walk.

Abstract. QueueService is a queue system for Roblox, meaning a FIFO queue on the server that also exists on the map, with characters standing one behind the other. The shape of the line is defined in Workspace with numbered parts (Nodos/1, Nodos/2 and so on) that form a polyline, and every spot is computed by arc length along it, so characters stay evenly spaced even when the line turns corners. Players who join are frozen and walk to their spot every time the line moves. Filler NPCs, wearing the appearance of real users, keep the line full at all times and give up their place to any player who arrives. Turns are passed on a timer or by calling Advance(), and the rest of the game finds out through three signals. The code is short. The interesting parts are the invariant that keeps players ahead of NPCs, the geometry of the spots and how every move is guaranteed to finish.

1. The problem

The game I built this for had a line: players had to wait their turn for something, and the server handed out turns, sometimes on a timer and sometimes on a game event. A queue in a UI is a list with a number. I wanted it in the world, with characters standing one behind the other and stepping forward one spot every time someone goes through, because that reads without anyone having to read anything.

That leaves three problems. The data one is a plain FIFO queue, with joins, leaves and a spot per player. The geometric one is deciding where each character stands in a line that can have any shape. And the presentation one is that a line with two players on an empty server doesn’t look like a line, which is what the NPCs are for.

2. The queue as data

2.1 Occupants

The queue is an array of occupants. An occupant is either a player or an NPC, and both keep what the system needs to move them: the Model, its Humanoid, its HumanoidRootPart and the WalkSpeed it had when it joined. The array index is the spot, and 1 is the head of the line, the next one to go.

A FIFO queue in Lua is straightforward [1]. Enqueueing is an insert and dequeueing is table.remove(queue, 1), which shifts every element down one place and therefore costs $O (n)$ . With lines of a few dozen characters that doesn’t matter, and in exchange every occupant’s index is directly its spot, with no circular-buffer arithmetic. Finding a player’s spot is a linear scan too, for the same reason.

2.2 Players before NPCs

The rule that defines how the line behaves is that NPCs are filler and never make a player wait. The array always has the shape

\underset{players}{\underset{⏟}{P_{1}, P_{2}, \dots, P_{p}}}, \underset{NPCs}{\underset{⏟}{B_{1}, \dots, B_{q}}}

and no operation breaks it. A new player is inserted at the first position that isn’t a player’s, meaning right behind the last player and ahead of every NPC. New NPCs are always appended at the end. Removing any element keeps the others in order, and dequeueing removes the first one. Since every operation preserves the shape, the invariant always holds by induction from the initial line, which is all NPCs.

Among players the order is arrival order, which is what you’d expect from a line. Among NPCs too, though there it doesn’t matter. And a player always goes before any NPC, even if the NPCs had been there from the start. All of that comes out of the array’s shape, with no special logic in Advance().

2.3 How many NPCs

The line has a visual capacity $N_{\max}$ that depends on its length (section 3.3). With $p$ players in the line, the number of NPCs is $q = \max (0, N_{\max} - p)$ , and the total size comes out to

N = p + \max (0, N_{\max} - p) = \max (N_{\max}, p)

As long as there’s room, the line is always $N_{\max}$ long and players only replace NPCs. When a player joins, the NPC at the position where they’re inserted is retired, so the total doesn’t change. If more than $N_{\max}$ players show up, there are no NPCs left and the line grows with them.

_syncNPCCount is the only function that enforces that count. If NPCs are missing it appends them, and if there are too many it removes them scanning from the end, which is where they are.

3. The queue in the world

3.1 A naming convention

The shape of the line is drawn in Studio. Inside Workspace.Nodos go parts named 1, 2, 3 and so on, and the system reads them in numeric order up to the first missing number. At least two are required.

Reading by name instead of by GetChildren() order is necessary because that order isn’t guaranteed. And stopping at the first gap means deleting a node in the middle visibly shortens the line, instead of joining two stretches that weren’t supposed to connect. Node 1 is the entrance, where you touch to join and where new NPCs spawn, and the last node is the head of the line.

3.2 The polyline

The nodes are flattened onto the $X Z$ plane and walked in reverse, from the head to the entrance, to form a polyline $Q_{0}, Q_{1}, \dots, Q_{m - 1}$ with $Q_{0}$ at the last node and $Q_{m - 1}$ at node 1. With each segment’s length and the running sums

ℓ_{i} = ‖ Q_{i + 1} - Q_{i} ‖, S_{i} = \sum_{j < i} ℓ_{j}, L = S_{m - 1}

the point at distance $s$ from the head, measured along the line, is

γ (s) = Q_{i} + \frac{s - S_{i}}{ℓ_{i}} (Q_{i + 1} - Q_{i}), S_{i} \leq s \leq S_{i + 1}

That’s the arc-length parametrization of the polyline [2]: moving a distance $s$ along $γ$ always covers $s$ studs of line, no matter how many segments there are or how long each one is. The code finds the segment with a linear scan over the $ℓ_{i}$ and covers three edge cases. With $s \leq 0$ it returns the head, an $s$ past the end stays at the last point because the fraction is clamped to $[0, 1]$ , and a zero-length segment (two nodes at the same position) uses a fraction of 0 instead of dividing by zero.

Flattening has a consequence, which is that the line has to be flat. Every spot’s height is node 1’s plus one stud, so a line going up a staircase wouldn’t work without changing that.

3.3 Evenly spaced spots

With $N$ occupants, spot $k$ (from 1 to $N$ ) is at

𝐱_{k} = γ (\frac{k - 1}{N - 1} L)

which puts the head at the last node, the last occupant at the entrance and everyone else spread out with a spacing of $d = L / (N - 1)$ measured along the line. Spreading by arc length is what keeps a corner from bunching people up. The obvious alternative, spreading by node index, would put as many characters on a 4-stud segment as on a 40-stud one.

The capacity comes from asking for about 6 studs per person:

N_{\max} = ⌊ \frac{L}{6} ⌋

With $N = N_{\max}$ the actual spacing ends up a little over 6, because the line occupies both of its ends, so there are $N - 1$ gaps and not $N$ . On a 60-stud line, for example, 10 characters fit with 6.67 studs between them. When there are more players than $N_{\max}$ , $N$ grows, $d$ drops below 6 and the line packs tighter instead of getting longer, because its length is set by the map.

Since $d$ depends on $N$ , any change in size moves everyone. That’s why every operation ends in _redistribute, which recomputes the $N$ spots and sends each occupant to theirs.

4. Filler NPCs

NPCs come from a template and are recycled through a pool [3]. When one is retired it’s anchored, taken out of Workspace (Parent = nil) and stored in a list. When one is needed it comes out of that list, and the template is only cloned when the list is empty. In a line that creates an NPC on every advance, that avoids cloning and destroying a whole model every few seconds.

Every new NPC spawns at node 1 facing node 2, which is where people come in, and from there it walks to its spot like any other occupant. So they don’t all look the same, each one gets the appearance of a random user from a list of UserIds through GetHumanoidDescriptionFromUserId. That call makes a web request, which is why it runs inside a Promise and the NPC starts walking while its clothes load. Once it’s done, the NPC’s parts lose their collision, so they don’t get in the way of players walking between them to their spot. ApplyDescription sometimes fails with a DataModel not available error, and that error is caught and ignored, because an NPC with the template’s appearance still works as filler.

5. Passing the turn

Advance() dequeues the head. If it’s a player, it fires PlayerReachedFront with that player, which is the signal the game uses to do whatever the turn is for, and takes them out of the line. If it’s an NPC, it gets recycled. Then the NPCs are topped up, entering at the back, and everyone is redistributed.

There are two ways it gets called. One is a loop that calls Advance() and waits AdvanceIntervalSeconds, and the other is the game calling it. In the original game the interval was set to 9999 s, which in practice leaves only manual mode. In timed mode, with interval $τ$ , a player at spot $k$ waits

W_{k} \in ((k - 1) τ, k τ]

depending on where in the interval they joined. Since players are always ahead of NPCs, $k$ is simply the number of players ahead of them plus one.

Advance() returns a Promise that resolves once every occupant has finished moving, using Promise.all over the individual moves. Until that promise resolves, a _busy flag makes any other Advance() return right away. That way, a game event that calls Advance() twice in a row doesn’t send two people through before the line has finished moving for the first one.

6. Moving an occupant

6.1 Freezing without anchoring

An occupant standing still is frozen with WalkSpeed = 0. The player keeps their character, camera and animations, but can’t walk. Anchoring the HumanoidRootPart would also keep them in place (there’s a commented-out line in the code that did that), but it takes the character out of the simulation. To move them, the system restores the original WalkSpeed, calls Humanoid:MoveTo(target) and freezes them again on arrival. Unfreezing also unanchors, because NPCs are stored anchored in the pool.

6.2 A move always finishes

MoveTo doesn’t guarantee arrival. A wall, another character or a corner the straight line cuts through can leave the Humanoid stuck, and if that left a promise unresolved, _busy would stay true forever and the line would never advance again. That’s why every move is a race with several exits, and the first one to fire closes it:

MoveToFinished, when the Humanoid arrives or gives up.
A 3 s task.delay, which is the upper bound on any move.
The first change of MoveDirection, which disconnects MoveToFinished and manually resumes the task.delay thread, so the closing code runs right then without waiting the 3 s.

They all close the same way. They put the HumanoidRootPart exactly on the target, keeping its orientation, freeze it and resolve the promise. A done flag makes sure that happens only once even if two exits fire on the same frame. The result is that the path is approximate but the final spot is exact. If someone got stuck or cut a corner, the snap puts them where they should be, and the next redistribution starts from correct positions.

Characters walk to their spot in a straight line and don’t follow the polyline. For a normal advance that doesn’t matter, because each one moves a single spot (about 6 studs) and the shortcut at a corner is small. The ugly case is a player joining, who walks in a straight line from the entrance to the first free spot, sometimes several segments ahead. NPCs having no collision lets them pass through, and the 3 s cap together with the snap covers the rest.

7. Players

A player joins the line by touching node 1. The server saves their WalkSpeed, freezes them, inserts them as described in section 2.2 and sets the Enqueued attribute on the character, so other systems in the game can tell whether someone is in line without depending on the module. Then it fires PlayerJoinedQueue with the player and their spot, and redistributes.

They leave the line in one of three ways: their turn comes, they leave the game or they die. On the way out they get their WalkSpeed back, the attribute is cleared and PlayerLeftQueue fires with the spot they had, and then the line is topped up and redistributed.

Dying has an exception that came from the original game. If the player has the Killed attribute, meaning one of the game’s own mechanics killed them, they keep their spot. Their record stays in the line pointing at a character that no longer exists, which is why every move reads player.Character again (waiting on CharacterAdded if needed) before using the Humanoid and the root. The next time the line moves, the new character walks to the old one’s spot.

8. The client

The server tells each player their spot through a RemoteEvent, QueueUpdate, which sends the index on every redistribution and nil on leaving. The client controller compares the new value with the previous one. If it was nil before and a number arrives, it first fires “joined the line”, and then, based on the new value, nil means leaving, 1 means reaching the head and any other number is a change of spot.

Sending the state (the spot) rather than loose events like “you moved up one” means the client can’t fall out of sync. A controller that started late and missed messages catches up with the next one, because the next one carries the full spot. In the original game, joining and leaving the line swapped two ProximityPrompts on the other players’ characters, and the rest of the events were left as hooks for the UI.

9. Lifecycle

Everything the service connects (the touch on node 1, PlayerRemoving and the three signals) is registered in a Janitor. Destroy() marks the service as destroyed, which ends the interval loop on its next pass, recycles the NPCs, gives players back their WalkSpeed, destroys the pool and cleans up the Janitor. The service is created once in Start(), following Knit’s lifecycle convention, and is reachable as QueueService.instance. The dependencies are the usual ones for that stack: Janitor, Promise, Signal and Net for the RemoteEvent.

10. Limitations

Only Advance() is guarded against concurrent calls. Joining and leaving the line also redistribute, without that guard, so the same occupant can have two moves in flight. Each one keeps its own target, and the older one closing can leave the occupant at an outdated spot until the next redistribution. A sturdier version would cancel each occupant’s previous move before starting a new one.

The 3 s cap only starts counting once the character is available. If a player marked Killed leaves the game while their move is waiting on CharacterAdded, that promise never resolves, and if it was part of an Advance(), the line gets stuck. On top of that, the respawned character has no Died connection, so a second regular death doesn’t take them out of the line, and it isn’t frozen until the next move.

The line has to be flat, because spots are computed in $X Z$ and take node 1’s height, and characters walk in straight lines instead of following the polyline. Some pieces, like the Killed attribute and the client’s ProximityPrompts, belong to the original game and not to the queue.

11. What the project left me with

There are two ideas I’d use again. The first is the players-before-NPCs invariant. Thanks to it, NPCs fill the line without ever changing the order in which players go through, and that comes out of three simple operations (insert before the first NPC, append NPCs at the end and remove them from the end) with no special case when advancing. The second is separating the path from the result. A move in Roblox can fail in many ways, and instead of trying to keep it from failing, every move has a cap and ends with the character in the exact spot, so a failure never carries over into the next advance.

References

D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed. Addison-Wesley, 1997.
M. P. do Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, 1976.
R. Nystrom. Game Programming Patterns. Genever Benning, 2014.