Una fila FIFO que se camina.

Resumen. QueueService es un sistema de filas para Roblox, es decir, una cola FIFO en el servidor que además existe en el mapa, con personajes parados uno detrás de otro. La forma de la fila se define en el Workspace con partes numeradas (Nodos/1, Nodos/2, etc.) que forman una polilínea, y cada puesto se calcula por longitud de arco sobre ella, así que los personajes quedan a la misma distancia aunque la fila doble esquinas. Los jugadores que entran quedan congelados y caminan a su puesto cada vez que la fila se mueve. Unos NPCs de relleno, con la apariencia de usuarios reales, mantienen la fila siempre llena y le ceden el lugar a cualquier jugador que llegue. El turno se pasa por tiempo o llamando a Advance(), y el resto del juego se entera por tres señales. El código es corto. Lo interesante está en la invariante que mantiene a los jugadores delante de los NPCs, en la geometría de los puestos y en cómo se garantiza que un movimiento siempre termina.

1. El problema

El juego para el que hice esto tenía una fila: los jugadores tenían que esperar turno para algo, y el turno lo daba el servidor, a veces cada cierto tiempo y a veces por un evento del juego. Una fila en una interfaz es una lista con un número. Yo quería que estuviera en el mundo, con los personajes parados uno detrás de otro y avanzando un puesto cada vez que alguien pasa, porque eso se entiende sin leer nada.

Eso deja tres problemas. El de datos es una cola FIFO normal, con entradas, salidas y un puesto por jugador. El geométrico es decidir dónde se para cada personaje en una fila que puede tener cualquier forma. Y el de presentación es que una fila con dos jugadores en un servidor vacío no parece una fila, y para eso están los NPCs.

2. La fila como dato

2.1 Ocupantes

La fila es un arreglo de ocupantes. Un ocupante es un jugador o un NPC, y los dos guardan lo que el sistema necesita para moverlos: el Model, su Humanoid, su HumanoidRootPart y la WalkSpeed que tenían al entrar. El índice en el arreglo es el puesto, y el 1 es la cabeza de la fila, el siguiente en pasar.

Una cola FIFO en Lua es directa [1]. Encolar es insertar y desencolar es table.remove(fila, 1), que corre todos los elementos un lugar y por eso cuesta $O (n)$ . Con filas de unas decenas de personajes eso no importa, y a cambio el índice de cada ocupante es directamente su puesto, sin la aritmética de un buffer circular. Buscar el puesto de un jugador también es un recorrido lineal, por la misma razón.

2.2 Jugadores antes que NPCs

La regla que define cómo se comporta la fila es que los NPCs son relleno y nunca hacen esperar a un jugador. El arreglo siempre tiene la forma

\underset{jugadores}{\underset{⏟}{J_{1}, J_{2}, \dots, J_{p}}}, \underset{NPCs}{\underset{⏟}{B_{1}, \dots, B_{q}}}

y ninguna operación la rompe. Un jugador nuevo se inserta en la primera posición que no es de un jugador, o sea, justo detrás del último jugador y delante de todos los NPCs. Los NPCs nuevos siempre se agregan al final. Quitar un elemento cualquiera conserva el orden de los demás, y desencolar quita el primero. Como cada operación conserva la forma, la invariante se cumple siempre por inducción desde la fila inicial, que es solo de NPCs.

Entre jugadores el orden es de llegada, que es lo que se espera de una fila. Entre NPCs también, aunque ahí da igual. Y un jugador siempre pasa antes que cualquier NPC, aunque los NPCs llevaran ahí desde el principio. Todo eso sale de la forma del arreglo, sin ninguna lógica especial en Advance().

2.3 Cuántos NPCs

La fila tiene una capacidad visual $N_{\max}$ que depende de su largo (sección 3.3). Con $p$ jugadores en la fila, el número de NPCs es $q = \max (0, N_{\max} - p)$ , y el tamaño total queda

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

Mientras haya espacio, la fila mide siempre $N_{\max}$ y los jugadores solo reemplazan NPCs. Cuando entra un jugador, el NPC que estaba en la posición donde se inserta se retira, así que el total no cambia. Si llegan más jugadores que $N_{\max}$ , no queda ningún NPC y la fila crece con ellos.

_syncNPCCount es la única función que hace cumplir esa cuenta. Si faltan NPCs los agrega al final, y si sobran los quita recorriendo desde el final, que es donde están.

3. La fila en el mundo

3.1 Una convención de nombres

La forma de la fila se dibuja en Studio. Dentro de Workspace.Nodos van partes llamadas 1, 2, 3, etc., y el sistema las lee en orden numérico hasta el primer número que falte. Hacen falta al menos dos.

Leer por nombre y no por el orden de GetChildren() es necesario porque ese orden no está garantizado. Y detenerse en el primer hueco hace que borrar un nodo intermedio acorte la fila de forma visible, en vez de unir dos tramos que no tenían que ir juntos. El nodo 1 es la entrada, donde se toca para entrar y donde aparecen los NPCs nuevos, y el último nodo es la cabeza de la fila.

3.2 La polilínea

Los nodos se aplanan al plano $X Z$ y se recorren al revés, de la cabeza a la entrada, para formar una polilínea $P_{0}, P_{1}, \dots, P_{m - 1}$ con $P_{0}$ en el último nodo y $P_{m - 1}$ en el nodo 1. Con el largo de cada tramo y las sumas acumuladas

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

el punto que está a una distancia $s$ de la cabeza, medida sobre la fila, es

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

Es la parametrización por longitud de arco de la polilínea [2]: avanzar una distancia $s$ sobre $γ$ siempre recorre $s$ studs de fila, sin importar cuántos tramos haya ni cuánto mida cada uno. El código busca el tramo con un recorrido lineal sobre los $ℓ_{i}$ y cubre tres bordes. Con $s \leq 0$ devuelve la cabeza, una $s$ más allá del final se queda en el último punto porque la fracción se recorta a $[0, 1]$ , y un tramo de largo cero (dos nodos en la misma posición) usa fracción 0 en vez de dividir por cero.

Aplanar tiene una consecuencia, y es que la fila tiene que ser plana. La altura de cada puesto es la del nodo 1 más un stud, así que una fila que sube una escalera no funcionaría sin cambiar eso.

3.3 Puestos uniformes

Con $N$ ocupantes, el puesto $k$ (de 1 a $N$ ) está en

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

es decir, la cabeza en el último nodo, el último ocupante en la entrada y los demás repartidos con una separación $d = L / (N - 1)$ medida sobre la fila. Repartir por longitud de arco es lo que hace que una esquina no amontone gente. La alternativa obvia, repartir por índice de nodo, pondría la misma cantidad de personajes en un tramo de 4 studs que en uno de 40.

La capacidad sale de pedir unos 6 studs por persona:

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

Con $N = N_{\max}$ la separación real queda un poco por encima de 6, porque la fila ocupa sus dos extremos y entonces hay $N - 1$ huecos y no $N$ . En una fila de 60 studs, por ejemplo, caben 10 personajes separados 6.67 studs. Cuando hay más jugadores que $N_{\max}$ , $N$ crece, $d$ baja de 6 y la fila se aprieta en vez de alargarse, porque su largo lo fija el mapa.

Como $d$ depende de $N$ , cualquier cambio de tamaño mueve a todos. Por eso cada operación termina en _redistribute, que recalcula los $N$ puestos y manda a cada ocupante al suyo.

4. NPCs de relleno

Los NPCs salen de una plantilla y se reciclan en un pool [3]. Cuando se retira uno, se ancla, se saca del Workspace (Parent = nil) y se guarda en una lista. Cuando hace falta uno, se saca de esa lista, y solo si está vacía se clona la plantilla. En una fila que crea un NPC en cada avance, eso evita clonar y destruir un modelo completo cada pocos segundos.

Cada NPC nuevo aparece en el nodo 1 mirando al nodo 2, que es por donde entra la gente, y desde ahí camina a su puesto como cualquier otro ocupante. Para que no sean todos iguales, se le aplica la apariencia de un usuario al azar de una lista de UserIds con GetHumanoidDescriptionFromUserId. Esa llamada hace una petición web, por eso corre dentro de una Promise y el NPC empieza a caminar mientras se carga su ropa. Al terminar, las partes del NPC quedan sin colisión, para que no estorben a los jugadores que pasan entre ellos hacia su puesto. ApplyDescription a veces falla con un error de DataModel no disponible, y ese error se atrapa y se ignora, porque un NPC con la apariencia de la plantilla sigue sirviendo de relleno.

5. Pasar el turno

Advance() desencola la cabeza. Si es un jugador, dispara PlayerReachedFront con ese jugador, que es la señal con la que el juego hace lo que tenga que hacer con su turno, y lo saca de la fila. Si es un NPC, lo recicla. Después repone los NPCs, que entran por la cola, y redistribuye.

Hay dos formas de que se llame. Una es un bucle que llama a Advance() y espera AdvanceIntervalSeconds, y la otra es que lo llame el juego. En el juego original el intervalo estaba en 9999 s, que en la práctica deja solo el modo manual. En modo por tiempo, con intervalo $τ$ , un jugador en el puesto $k$ espera

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

según en qué punto del intervalo entró. Como los jugadores siempre van delante de los NPCs, $k$ es simplemente cuántos jugadores tiene delante más uno.

Advance() devuelve una Promise que se resuelve cuando todos los ocupantes terminaron de moverse, con Promise.all sobre los movimientos individuales. Mientras esa promesa no se resuelva, una bandera _busy hace que cualquier otro Advance() vuelva de inmediato. Así, un evento del juego que llama a Advance() dos veces seguidas no saca a dos personas antes de que la fila haya terminado de moverse por la primera.

6. Mover a un ocupante

6.1 Congelar sin anclar

Un ocupante quieto está congelado con WalkSpeed = 0. El jugador conserva su personaje, la cámara y las animaciones, pero no puede caminar. Anclar la HumanoidRootPart también lo inmovilizaría (hay una línea comentada en el código que lo hacía), pero saca al personaje de la simulación. Para moverlo, el sistema restaura la WalkSpeed original, le da Humanoid:MoveTo(destino) y lo vuelve a congelar al llegar. Descongelar además desancla, porque los NPCs del pool se guardan anclados.

6.2 Un movimiento siempre termina

MoveTo no garantiza llegar. Una pared, otro personaje o una esquina que la línea recta corta pueden dejar al Humanoid atascado, y si eso dejara una promesa sin resolver, _busy se quedaría en verdadero para siempre y la fila no volvería a avanzar. Por eso cada movimiento es una carrera con varias salidas, y la primera que llega lo cierra:

MoveToFinished, cuando el Humanoid llega o se rinde.
Un task.delay de 3 s, que es el tope de cualquier movimiento.
El primer cambio de MoveDirection, que desconecta MoveToFinished y reanuda a mano el hilo del task.delay, de modo que el cierre corre en ese momento sin esperar los 3 s.

Todas cierran igual. Ponen la HumanoidRootPart exactamente en el destino, con la orientación que traía, la congelan y resuelven la promesa. Una bandera done asegura que eso pase una sola vez aunque dos salidas se disparen en el mismo cuadro. El resultado es que el camino es aproximado pero el puesto final es exacto. Si alguien quedó atascado o cortó una esquina, el snap lo deja donde debía estar, y la siguiente redistribución parte de posiciones correctas.

Los personajes caminan en línea recta hacia su puesto y no siguen la polilínea. En un avance normal da igual, porque cada uno se mueve un puesto (unos 6 studs) y el atajo en una esquina es pequeño. El caso feo es el del jugador que entra, que camina en línea recta desde la entrada hasta el primer puesto libre, a veces varios tramos más adelante. Que los NPCs no tengan colisión le deja pasar entre ellos, y el tope de 3 s junto con el snap cubren el resto.

7. Jugadores

Un jugador entra a la fila tocando el nodo 1. El servidor guarda su WalkSpeed, lo congela, lo inserta según la sección 2.2 y le pone el atributo Enqueued al personaje, para que otros sistemas del juego puedan saber si alguien está en fila sin depender del módulo. Después dispara PlayerJoinedQueue con el jugador y su puesto, y redistribuye.

Sale de la fila de tres maneras: le llega el turno, abandona el juego o muere. Al salir se le devuelve su WalkSpeed, se le quita el atributo y se dispara PlayerLeftQueue con el puesto que tenía, y luego la fila se repone y se redistribuye.

Morir tiene una excepción que venía del juego original. Si el jugador tiene el atributo Killed, o sea, si lo mató una mecánica del propio juego, no pierde su puesto. Su registro sigue en la fila con referencias a un personaje que ya no existe, y por eso cada movimiento vuelve a leer player.Character (esperando a CharacterAdded si hace falta) antes de usar el Humanoid y la raíz. La próxima vez que la fila se mueve, el personaje nuevo camina al puesto que tenía el viejo.

8. El cliente

El servidor le avisa a cada jugador de su puesto con un RemoteEvent, QueueUpdate, que manda el índice en cada redistribución y nil al salir. El controlador del cliente compara el valor nuevo con el anterior. Si antes era nil y ahora llega un número, primero dispara “entró a la fila”, y después, según el valor nuevo, nil es salir, 1 es llegar a la cabeza y cualquier otro número es un cambio de puesto.

Mandar el estado (el puesto) y no eventos sueltos como “avanzaste uno” hace que el cliente no pueda desincronizarse. Un controlador que arrancó tarde y se perdió mensajes se pone al día con el siguiente, porque el siguiente trae el puesto completo. En el juego original, entrar y salir de la fila intercambiaba dos ProximityPrompt en los personajes de los demás jugadores, y el resto de los eventos quedaron como ganchos para la interfaz.

9. Ciclo de vida

Todo lo que el servicio conecta (el toque del nodo 1, PlayerRemoving y las tres señales) se registra en un Janitor. Destroy() marca el servicio como destruido, con lo que el bucle del intervalo termina en su próxima vuelta, recicla los NPCs, devuelve a los jugadores su WalkSpeed, destruye el pool y limpia el Janitor. El servicio se crea una sola vez en Start(), con la convención de ciclo de vida de Knit, y queda accesible como QueueService.instance. Las dependencias son las de siempre en ese stack: Janitor, Promise, Signal y Net para el RemoteEvent.

10. Limitaciones

Solo Advance() está protegido contra llamadas concurrentes. Entrar y salir de la fila también redistribuyen, sin esa protección, así que un mismo ocupante puede tener dos movimientos en curso. Cada uno guarda su propio destino, y el cierre del más viejo puede dejar al ocupante en un puesto desactualizado hasta la siguiente redistribución. Una versión más sólida cancelaría el movimiento anterior de cada ocupante antes de empezar uno nuevo.

El tope de 3 s empieza a contar después de conseguir el personaje. Si un jugador marcado con Killed se va del juego mientras su movimiento espera CharacterAdded, esa promesa no se resuelve, y si era parte de un Advance(), la fila queda bloqueada. Además, el personaje que reaparece no tiene conexión a Died, así que una segunda muerte normal no lo saca de la fila, y no queda congelado hasta el siguiente movimiento.

La fila tiene que ser plana, porque los puestos se calculan en $X Z$ y toman la altura del nodo 1, y los personajes caminan en línea recta en vez de seguir la polilínea. Algunas piezas, como el atributo Killed y los ProximityPrompt del cliente, son del juego original y no de la fila.

11. Lo que me dejó

Hay dos ideas que volvería a usar. La primera es la invariante de jugadores antes que NPCs. Gracias a ella, los NPCs rellenan la fila sin cambiar nunca el orden en que pasan los jugadores, y eso sale de tres operaciones simples (insertar antes del primer NPC, agregar NPCs al final y quitarlos desde el final) sin ningún caso especial al avanzar. La segunda es separar el camino del resultado. Un movimiento en Roblox puede fallar de muchas formas, y en vez de intentar que no falle, cada movimiento tiene un tope y termina con el personaje en el lugar exacto, de modo que un fallo no se arrastra al siguiente avance.

Referencias

D. E. Knuth. The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3.ª 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.