530 quests, un grafo y tres espacios.

Advertencia

Rod and Reef todavía no ha sido lanzado, y no se pueden mostrar videos ni GIFs de este sistema hasta que salga.

Resumen. Rod and Reef tiene 530 definiciones de quest. 478 son solo de pesca (“atrapa 5 percas para Morris”) y el resto son encargos: entregar algo, buscar un objeto perdido, llevar a alguien en bote, seguir a otro o hablar con un personaje. Las reparten los NPCs a través de 89 archivos de líneas de quests, organizados en tres pistas: pesca, secundarias e historia. Este artículo describe las decisiones técnicas del sistema. Cada quest es un dato construido con una interfaz encadenada, con tres tipos de objetivo y tres estados. Una sola clase de perfil corre en el servidor, donde escribe en los datos guardados del jugador, y en el cliente, donde es una copia de solo lectura, así que las dos partes hacen las mismas preguntas con el mismo código. Los prerequisitos forman un grafo dirigido, y cuando una quest se desactiva se elimina del grafo conservando las restricciones que había detrás de ella. Los espacios de quest activa se clasifican a partir de los objetivos en vez de escribirse a mano en 530 archivos. Y el diario ordena las quests por un estimado de cuántos lances cuesta terminarlas.

1. El problema

Las quests son el hilo de Rod and Reef. Le dan al jugador algo que pescar, a quién vendérselo y una historia que seguir a lo largo de cuatro islas. Eso deja un sistema con mucho contenido y muchas reglas cruzadas. Un NPC ofrece sus quests en orden y solo cuando el jugador tiene el nivel y terminó las anteriores, pero una quest de la historia puede depender de otra que da un NPC distinto en otra isla. Algunas quests se entregan a un personaje diferente del que las dio. El jugador puede llevar varias a la vez, pero no cualquier combinación. Y durante las pruebas hubo que desactivar quests cuyo contenido no estaba en el mapa, sin romper la cadena de la historia que pasaba por ellas.

2. Una quest como dato

Cada quest es un módulo que devuelve una definición construida con una interfaz encadenada:

return QuestDefinition.new("ChonkyTunaQuest")
	:SetData({
		Name = "Chonky Tuna Quest",
		Description = "Bring 55kg of Tuna total to Paul.",
	})
	:AddObjective(ObjectiveDefinition.new("total_weight_tuna", 5500, {
		Description = "Bring 55kg of Tuna total",
		Kind = "TotalWeight",
	}))
	:AddReward(RewardDefinition.new("Coins", 9560, {}))
	:AddReward(RewardDefinition.new("XP", 8200, {}))

Hay tres tipos de objetivo de pesca. Count cuenta capturas. SingleWeight se cumple con una sola captura que pese al menos el objetivo. TotalWeight acumula el peso de varias. Los pesos se guardan en centésimas de kilo, $⌊ 100 w + 0.5 ⌋$ , así que 55 kg es 5500 y las comparaciones son entre enteros, sin errores de punto flotante en el borde. El progreso se recorta al objetivo, $p^{'} = \min (p + Δ, objetivo)$ , de modo que una captura enorme no deja el contador por encima de lo que pide la quest.

El nombre del objetivo sigue una convención que el resto del juego lee. catch_perch, weight_lunar shiny serpentfin y total_weight_tuna le dicen al sistema de pesca qué pez cuenta, con los modificadores (lunar, shiny, glowing) escritos como palabras delante del nombre. De los 554 objetivos que hay, 482 son de pesca con esas tres formas, 36 son viajes en bote y el resto se reparte entre hablar, buscar, entregar, recoger, seguir y otros.

Una quest pasa por tres estados, Locked, Active y Completed, más una marca aparte de recompensa cobrada. Cancelarla la devuelve a Locked con el progreso en cero. Cada cambio de estado dispara señales (QuestActivated, QuestCompleted, ObjectiveProgressChanged), y todo lo demás, desde la interfaz hasta los barks, reacciona a esas señales.

3. Un perfil, dos almacenes

QuestProfile es la clase que responde preguntas como “¿esta quest está activa?” o “¿se cumplieron todos sus objetivos?”. No guarda nada por sí misma: lee y escribe a través de un almacén, y hay dos.

En el servidor, el almacén escribe en los datos del jugador que maneja ProfileStore, bajo rutas como Quests.<id>.Objectives.<objetivo>. En el cliente, el almacén es una copia de esos mismos datos, alimentada por la replicación general de datos del jugador, y el perfil se crea en modo de solo lectura, así que cualquier escritura en el cliente no hace nada. El código que decide si una quest está lista para entregarse es el mismo en los dos lados, y la interfaz del cliente nunca puede llegar a una conclusión distinta de la del servidor por haber reimplementado una regla.

Los eventos de quests viajan aparte, en paquetes binarios con ByteNet. El servidor conecta las señales del perfil a paquetes (QuestStateChanged, ObjectiveProgressChanged y otros) y al entrar el jugador le manda una foto completa de todas sus quests. Hay una distinción que costó un bug entender. Un QuestStateChanged es un evento: el cliente lo trata como una transición en vivo y reacciona, por ejemplo con el aviso de “quest cancelada”. La foto, en cambio, significa “así están las cosas”. Cuando el cliente movió su interfaz por adelantado y el servidor rechazó el pedido, nada cambió en el servidor y por lo tanto no se dispara ninguna señal, y el cliente se quedaría en un estado que el servidor nunca aceptó. Para ese caso existe SyncQuest, que manda la foto de una sola quest por el camino de “así están las cosas” y no por el de “esto acaba de pasar”.

La copia del cliente se puede llenar por dos caminos: el empujón inicial del servidor o una petición explícita si el empujón se perdió. Al principio solo uno de los dos avisaba que los datos habían llegado, y todos los sistemas que esperaban ese aviso (los diamantes de quest sobre los NPCs, la brújula, el diario) se quedaban con la respuesta vacía que habían leído un momento antes. Ahora los dos caminos avisan, y el aviso se difiere un cuadro, porque el llenado perezoso ocurre dentro de una lectura de otro sistema y disparar ahí volvería a entrar en todos los oyentes a mitad de esa lectura.

4. Líneas de quests

Cada NPC tiene una lista ordenada de entradas. Una entrada dice qué quest es, en qué nodo del diálogo se ofrece y en cuál se revisa, el nivel requerido, las quests que tienen que estar completas antes, y dos marcas opcionales: si la entrada solo sirve para recibir una quest que dio otro NPC, y si en vez de diálogo la quest es una cinemática. La isla de un NPC sale de la carpeta donde está su archivo (Questlines/Island4/Albert.luau es de la isla 4), y eso pone un piso de nivel por isla sin escribirlo en cada entrada.

4.1 Mezclar pistas

Las quests de pesca y las secundarias de un mismo NPC compiten por el mismo lugar en su cola, así que se mezclan en una sola lista ordenada por nivel. Como las dos listas ya vienen ordenadas, la mezcla es el paso de mezcla de un mergesort [3], en tiempo $O (n + m)$ , y es estable: ante un empate de nivel gana la entrada de pesca. Las quests de la historia no se mezclan. Si lo hicieran, una sola quest de historia al principio de la cola taparía todas las ofertas de pesca detrás de ella, y el jugador puede llevar las dos cosas a la vez. Así que la historia es una segunda pista con más prioridad, que se revisa primero en cada paso.

4.2 Qué ofrece un NPC

Al abrir una conversación, el NPC empieza por la revisión de una quest activa suya si la hay, luego por la quest que el jugador está siguiendo en el diario si este NPC la ofrece y ya está disponible, luego por la primera quest disponible de su cola y, si no queda nada, por un nodo de despedida. La quest seguida solo puede adelantarse en la cola si ya estaba abierta para el jugador. Un cliente que nombra una quest que todavía no alcanzó recibe exactamente la cola que habría recibido sin nombrarla.

El diario usa la misma lógica para mostrar la siguiente oferta de cada NPC. Eso nació de un caso concreto: todas las quests generales de Brody se abren en el nivel 1, y el diario las mostraba todas como disponibles. Un jugador que seguía la quinta llegaba a Brody y le ofrecía la primera, porque ese es el orden en que las da.

5. Prerequisitos como grafo

5.1 El grafo

Los prerequisitos forman un grafo dirigido $G = (V, E)$ con una arista $p \to q$ cuando $p$ tiene que estar completa para ofrecer $q$ . Cada quest tiene además un nivel mínimo $L (q)$ . Si $R (q) = {p : p \to q}$ , una entrada está disponible cuando

Locked (q) \land ℓ \geq L (q) \land \underset{p \in R (q)}{⋀} Completed (p)

donde $ℓ$ es el nivel del jugador, y en las quests de viaje además hace falta tener un bote con espacio para un pasajero. El grafo tiene que ser acíclico, porque un ciclo dejaría a sus quests esperándose entre sí, y un grafo acíclico siempre admite un orden topológico [1], que en la práctica es el orden en que el jugador las va desbloqueando. La historia es casi una cadena de prerequisitos simples, así que el grafo es largo y angosto.

5.2 Quitar un vértice sin cortar la cadena

Una quest desactivada nunca se puede completar, y cualquier entrada que la tenga como prerequisito esperaría para siempre. En una cadena, eso corta todo lo que viene después. Desactivar TheLostBracelet por sí sola habría terminado el juego en Finn, porque la quest del hombre de la isla, toda la pista del anciano, el cuchillo de Steiner y la misión del presidente dependen de ella, una tras otra.

La salida obvia, tratar la quest desactivada como cumplida, es el error contrario. Abriría de inmediato lo que venía detrás y dejaría a un jugador de nivel 26 entrar a contenido que estaba tres quests más adentro. Lo que hice fue reemplazar cada prerequisito desactivado por sus propios prerequisitos, de forma recursiva, y conservar su nivel como piso. Con $D$ el conjunto de quests desactivadas:

R^{*} (q) = ⋃_{p \in R (q)} {\begin{matrix} {p} & p \notin D \\ R^{*} (p) & p \in D \end{matrix} L^{*} (q) = \max (L (q), \max_{p \in R (q) \cap D} L^{*} (p))

Es la eliminación de un vértice que conserva la alcanzabilidad entre los que quedan, la misma idea que aparece al calcular clausuras y reducciones transitivas [2]. La cadena conserva cada restricción que todavía tiene una quest real detrás, hereda el ritmo de las que perdió y solo pierde los eslabones que ya no existen. Un ejemplo con LostOnWinterspire desactivada:

\begin{matrix} R (𝚆𝚑𝚊𝚝𝚃𝚑𝚎𝙲𝚑𝚊𝚒𝚛𝚖𝚊𝚗𝚆𝚘𝚗𝚝𝚂𝚊𝚢) & = {𝙻𝚘𝚜𝚝𝙾𝚗𝚆𝚒𝚗𝚝𝚎𝚛𝚜𝚙𝚒𝚛𝚎}, & L & = 0 \\ R (𝙻𝚘𝚜𝚝𝙾𝚗𝚆𝚒𝚗𝚝𝚎𝚛𝚜𝚙𝚒𝚛𝚎) & = {𝙰𝙵𝚊𝚒𝚛𝙰𝚜𝚔, 𝚃𝚑𝚎𝙻𝚒𝚌𝚎𝚗𝚜𝚎𝚃𝚎𝚜𝚝}, & L & = 27 \\ \Rightarrow R^{*} (𝚆𝚑𝚊𝚝𝚃𝚑𝚎𝙲𝚑𝚊𝚒𝚛𝚖𝚊𝚗𝚆𝚘𝚗𝚝𝚂𝚊𝚢) & = {𝙰𝙵𝚊𝚒𝚛𝙰𝚜𝚔, 𝚃𝚑𝚎𝙻𝚒𝚌𝚎𝚗𝚜𝚎𝚃𝚎𝚜𝚝}, & L^{*} & = 27 \end{matrix}

que es el mismo lugar del juego donde siempre estuvo, menos una quest que nadie puede hacer.

El cálculo se memoriza por quest, así que todo el grafo cuesta $O (| V | + | E |)$ la primera vez y una búsqueda en tabla después. Un ciclo solo puede venir de un error al escribir el contenido, pero un ciclo de prerequisitos no puede ser lo que tumbe el servidor al arrancar, así que se lleva un conjunto de vértices en visita, se avisa y se corta. Los resultados que se calculan dentro de esa protección no se guardan, porque serían parciales. Y la lista que se le devuelve a quien pregunta es una copia, porque si alguien la ordenara o la recortara estaría reescribiendo la restricción para todos.

5.3 Una quest, dos entradas

Algunas quests se dan en un NPC y se entregan en otro, así que tienen dos entradas con el mismo identificador: la oferta, con su nivel y sus prerequisitos, y la de entrega, sin nada de eso porque no restringe nada. Al principio las dos se registraban en la misma tabla indexada por quest, y cuál quedaba dependía del orden de iteración de la tabla. La restricción de FinnOnCorvane salía a veces como “nivel 26 y TheZone completa” y a veces como “nada”, y podía cambiar entre dos arranques del mismo servidor. Ahora solo la entrada que ofrece la quest dice lo que la quest exige, y es la única que se registra.

6. Tres espacios

Un jugador puede tener tres quests activas: dos generales y una única. Las generales son las que se cumplen pescando, sin ir a ningún lugar en particular, y por eso se pueden llevar dos en paralelo. Las únicas son las que tienen un lugar al que ir y una cosa que hacer ahí (una entrega, un objeto perdido, alguien a quien llevar), y de esas se lleva una.

La clasificación no está escrita en las 530 quests. Se deriva de los objetivos: una quest es general si todos sus objetivos empiezan con catch_, weight_ o total_weight_, que son exactamente las tres formas que el sistema de pesca sabe avanzar. Leer una convención que ya es portante es más seguro que agregar un campo con el que 530 archivos tendrían que estar de acuerdo. Una quest puede declarar su categoría a mano y eso siempre gana, para la quest de pesca que en realidad es un encargo o al revés. Hoy hay 478 generales y 52 únicas.

El resultado se guarda en caché, pero solo después de que las definiciones cargaron. En el cliente eso pasa unos segundos después de entrar, y una pregunta hecha antes habría guardado “general, porque no tiene objetivos” para una quest de entrega durante toda la sesión. Cuando los espacios de una categoría están llenos y el jugador acepta otra quest de esa categoría, no se cancela ni se rechaza nada: el pedido queda guardado en el servidor y se aplica solo en cuanto se libera un espacio, y el cliente abre el diario sobre las quests que estorban.

7. Ordenar por dificultad

El diario ordena primero por nivel, pero el nivel es grueso: en un mismo nivel de Verdantis, la primera isla, puede haber hasta diecisiete quests, y Khalid solo tiene once en el nivel 41. “Catch a Scottfish” y “Catch a Lunar Shiny Serpentfin over 35 kg” pueden compartir nivel, y es justo cuando el diario más necesita distinguirlas. Por eso cada quest tiene un estimado de esfuerzo en lances.

El costo de una especie sale de su rareza, con pesos de ranking separados como la escalera de rarezas: $c (r) = 4, 13, 60, 200, 700, 2500$ y $8000$ lances desde común hasta secreto. Cada modificador en el nombre multiplica ese costo por el inverso de su probabilidad, $1 / 0.12$ para brillante, $1 / 0.03$ para resplandeciente y $4 / 0.05$ para lunar, donde el 4 representa que lo lunar solo existe en una franja de la noche del juego. Con $m$ el producto de los modificadores, cada forma de objetivo cuesta

E_{catch} = N c m, E_{total} = \max (1, \frac{X}{\overline{w}}) c m, E_{single} = \frac{c m}{\max (P (W \geq X), 0.003)}

con $N$ capturas, $X$ kilos y $\overline{w} = w_{\min} + 0.12 (w_{\max} - w_{\min})$ , el peso típico de la especie con el equipo que se tiene cuando llegan esas quests. El último caso es el de la distribución geométrica [4]: si cada intento sale con probabilidad $p$ , el número esperado de intentos es $1 / p$ . Para calcular $P (W \geq X)$ se usa el equipo de referencia de esa rareza y la misma distribución de tamaños del sistema de suerte. Dentro de cada categoría de tamaño $[a_{k}, b_{k}]$ el peso es uniforme, así que

P (W \geq X) = \sum_{k} ρ_{k} ϕ_{k} (X), ϕ_{k} (X) = {\begin{matrix} 1 & X \leq a_{k} \\ \frac{b_{k} - X}{b_{k} - a_{k}} & a_{k} < X < b_{k} \\ 0 & X \geq b_{k} \end{matrix}

donde $ρ_{k}$ es la probabilidad de la categoría $k$ . El piso de 0.003 evita que un trofeo imposible con el equipo de referencia salga como infinitamente difícil, porque con mejor equipo es posible y “muy difícil” es la respuesta correcta para ordenar. Hablar con alguien cuesta 1 y cualquier otra tarea cuesta 40, unas diez capturas comunes. El esfuerzo de la quest es la suma del de sus objetivos.

Estos números no predicen la sesión de nadie, ni ninguna recompensa los lee. Solo tienen que poner las quests en el orden correcto entre ellas.

8. Contenido generado

Casi ninguna de las 530 quests se escribió a mano. Una herramienta en Python lee transcripciones por NPC en JSON, sacadas de los documentos de diseño, y genera en una corrida la definición de cada quest, el diálogo base del NPC y su línea de quests, así que las tres piezas no se pueden desincronizar. Las 20 quests de historia del documento de diseño original salen de otra herramienta que copia los valores de la tabla del documento de diseño y al final comprueba que las recompensas sumen lo que el documento dice que suman, 242 750 monedas y 207 500 de experiencia, para que un error al copiar no llegue al juego sin que nadie lo note.

9. Limitaciones

El núcleo del framework (definición, objetivo, perfil, almacenes) es de las piezas más viejas del juego y está escrito en Luau sin tipos estrictos, a diferencia de casi todo lo que vino después. La clasificación en espacios depende de los prefijos de los objetivos: si el sistema de pesca empieza a avanzar una cuarta forma de objetivo, hay que agregarla a la lista o sus quests pasan a ser únicas sin avisar. La mezcla de pistas supone que cada lista de quests ya viene ordenada por nivel, y nada lo verifica. Y el estimador de esfuerzo usa pesos de ranking que no se derivan de las tablas de suerte, así que si la economía cambia mucho habría que revisarlos a mano.

10. Lo que me dejó

Las dos decisiones que más me sirvieron tienen la misma forma: derivar en vez de declarar. Los espacios salen de los objetivos, los prerequisitos efectivos salen del grafo y de la lista de desactivadas, y la siguiente oferta del diario sale de la misma función que usa el NPC. Cada vez que algo se declaraba en dos lugares, terminaba en un bug donde los dos lugares no coincidían. La otra fue tratar el grafo de prerequisitos como un grafo y no como una lista de condiciones, porque así desactivar contenido pasó de ser una operación peligrosa a ser una línea en una tabla.

Referencias

A. B. Kahn. “Topological Sorting of Large Networks”. Communications of the ACM, 5(11), 1962.
A. V. Aho, M. R. Garey y J. D. Ullman. “The Transitive Reduction of a Directed Graph”. SIAM Journal on Computing, 1(2), 1972.
D. E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, 2.ª ed. Addison-Wesley, 1998.
W. Feller. An Introduction to Probability Theory and Its Applications, Vol. 1, 3.ª ed. Wiley, 1968.