Cómo Serious Sam manejaba grandes cantidades de enemigos con una conexión por módem de 56k
(staniks.github.io)- Serious Engine 1 montaba single-player, multiplayer y reproducción de demos sobre la misma simulación determinista, registrando y transmitiendo las acciones de los jugadores y bloques del stream del juego en lugar de todo el estado en cada tick
- Las demos y el multiplayer comparten el estado inicial del juego y luego aplican deltas de entrada como
CPlayerAction, por lo que la determinación de la semilla aleatoria y de la lógica del juego se vuelve clave para la sincronización - La capa de red manejaba directamente números de secuencia, ACK, retransmisiones, límites de ancho de banda y buffers por conexión sobre UDP, intentando mantener la partida incluso en líneas lentas
CNetworkMessageofrece serialización, compresión LZ77/LZRW1 y codificación delta basada en XOR, pero los mensajes, incluido el chat, no están cifrados y puede que solo se les aplique compresión- El modelo cliente-servidor de Serious Sam ahorra ancho de banda haciendo que cada cliente mantenga su propia simulación, pero a cambio necesita mecanismos auxiliares como verificación de sincronización, predicción, retransmisión y comprobación CRC
Estructura de simulación común de Serious Engine
- El código fuente de Serious Engine 1 fue publicado en 2016 bajo GNU GPL v2, y el análisis se basa en la lectura y depuración de esa base de código pública
- Serious Sam fue diseñado desde el principio como un juego multiplayer, y la campaña single-player también funciona internamente como un caso especial de la estructura multiplayer
- Los modos que soporta el engine son los siguientes
- Campaña single-player offline
- Cooperativo online, LAN y local, además de varios modos de juego
- Pantalla dividida con varios jugadores participando desde un solo cliente
- Grabación y reproducción de demos
Grabación de demos: registrar acciones en vez de todo el estado
- Si una demo guardara todo el estado del juego en cada tick, el archivo crecería mucho; por eso Serious Engine guarda una vez el estado completo del juego al inicio de la grabación y luego registra en cada tick bloques del stream del juego
- Los bloques del stream del juego incluyen los siguientes tipos de mensaje
MSG_SEQ_ALLACTIONS: acciones de los jugadoresMSG_SEQ_ADDPLAYER: agregar jugadorMSG_SEQ_REMPLAYER: eliminar jugadorMSG_SEQ_PAUSE: pausar o reanudarMSG_SEQ_CHARACTERCHANGE: cambio de atributos del personaje del jugador
- La pieza central es
MSG_SEQ_ALLACTIONS: el engine deserializa un objetoCPlayerActionpor cada jugador activo y lo aplica aCPlayerTarget CPlayerActioncontiene el estado del jugador- Velocidad de movimiento en coordenadas del mundo
pa_vTranslation - Rotación del personaje en coordenadas del mundo
pa_aRotation - Rotación de la vista en coordenadas del mundo
pa_aViewRotation - Botones presionados actualmente
pa_ulButtons - Timestamp en milisegundos basado en TSC
pa_llCreated
- Velocidad de movimiento en coordenadas del mundo
- Durante la reproducción, se lee el estado inicial del juego y se aplican las acciones de los jugadores de cada tick como si fuera una partida real
Por qué se necesita determinismo
- Esta estructura parte de la premisa de que todo dentro del juego es completamente predecible y que solo las acciones de los jugadores cambian el juego
- La aleatoriedad también se maneja mediante un generador pseudoaleatorio que usa una semilla como parte del estado del juego
CEntity::IRnd()usaCSessionState::Rnd()ses_ulRandomSeedse inicializa durante la deserialización del estado del juego
- Si se usa un generador de números realmente aleatorios o semillas distintas, incluso al reproducir la misma demo el resultado puede cambiar, lo que lleva a una desincronización
Punto flotante y procesamiento de ticks
- Como la versión de PC de Serious Sam se lanzó originalmente solo para Windows, la suposición de usar el mismo compilador y runtime reducía los problemas de sincronización por punto flotante
- El renderer es una DLL, y las llamadas a las API OpenGL o DirectX podían cambiar la precisión de la FPU, por lo que Serious Engine usa guardas de precisión como
CSetFPUPrecision FPUPrecision(FPT_24BIT) - No se encontró un lugar donde se configure explícitamente el control de redondeo, pero sí existe un assert que verifica el estado
_RC_NEARcon_controlfp - La lógica del juego está separada del framerate de renderizado
- El renderizado varía según el hardware y la configuración, y parece estar limitado internamente a 500 FPS
- La lógica del juego está fija en 20 ticks por segundo
- El movimiento suave se logra con interpolación lineal entre el tick actual y el anterior, y desde la consola se puede desactivar la interpolación con
/net_bLerping=0
Una capa propia de paquetes sobre UDP
- Aunque en el multiplayer de Serious Engine quedaron nombres de funciones como
StartPeerToPeer_t, el modelo real es una estructura cliente-servidor - El servidor recibe y procesa los mensajes de los clientes, y transmite la información relevante a todos los clientes
- Cada jugador ejecuta su propia simulación, de forma parecida al sistema de demos, y avanza el estado con la información de acciones de otros jugadores
- La red usa UDP y añade encima un protocolo propio para resolver reordenamientos y pérdidas
CPacketadministra el orden y la confiabilidad de los paquetespa_ulSequence: realiza ordenamiento y eliminación de duplicados con un número de secuenciapa_ubReliable: contiene el flag de confiabilidadpa_ubRetryNumber: rastrea la cantidad de retransmisionespa_tvSendWhen: se usa para la hora programada de envío y el control de congestión
- Los paquetes confiables esperan un ACK y se retransmiten si no llega
- El número máximo de reintentos se configura con
net_iMaxSendRetries, y el valor por defecto parece ser10 - El intervalo de retransmisión se configura con
net_fSendRetryWait, y el valor por defecto parece ser0.5f
- El número máximo de reintentos se configura con
- Los paquetes confiables pueden formar un stream dividido en varios paquetes
- El primer paquete es
UDP_PACKET_RELIABLE_HEAD - El último paquete es
UDP_PACKET_RELIABLE_TAIL - Un paquete confiable único tiene ambos flags
- El primer paquete es
- Los paquetes no confiables no forman streams, porque si se pierden el stream podría romperse
Ciclo de vida de la conexión y ruteo de paquetes
CCommunicationInterfacese encarga de la comunicación de la capa de paquetes y tiene funciones de interfaz para servidor, cliente y broadcast- Las interfaces de servidor y cliente asumen que el destino de la conexión ya se conoce, y la interfaz de broadcast se usa para enviar y recibir con direcciones arbitrarias
CCommunicationInterfacemantiene dos buffers maestroscci_pbMasterInput: deserializa los paquetes UDP entrantes comoCPackety los guardacci_pbMasterOutput: serializa losCPacketa enviar y los transmite mediante la API de sockets
- La abstracción real de comunicación por cliente la maneja
CClientInterface- El servidor tiene una interfaz por cada jugador en el arreglo
cm_aciClients - El cliente se comunica con el servidor mediante
cm_ciLocalClient - Tanto el cliente como el servidor usan
cm_ciBroadcastpara establecer la conexión
- El servidor tiene una interfaz por cada jugador en el arreglo
adr_uwIDdeCAddressse usa como identificador único del cliente o como marca de paquete de broadcast- Si el valor es
'//'o0, es un paquete de broadcast - Cualquier otro valor es el ID del cliente dentro de la sesión
- Si el valor es
Establecimiento de conexión y medidas básicas de seguridad
- Para conectarse al servidor, el cliente envía un paquete confiable de broadcast con el flag
UDP_PACKET_CONNECT_REQUEST - Si ya hay un cliente conectado con la misma dirección y puerto, el servidor ignora la solicitud
- Si es un cliente nuevo, el servidor busca una interfaz de cliente vacía y realiza lo siguiente
- Genera el identificador único de ese cliente
- Envía el identificador al cliente mediante un paquete confiable de broadcast
UDP_PACKET_CONNECT_RESPONSE
- El identificador no usa solo un índice fijo, sino que combina parte del valor del timer con el índice del cliente
- Para hacerse pasar por otro jugador habría que adivinar el
uwID, lo que reduce la superficie de ataque - Si un jugador no conectado envía un paquete que no es de broadcast, Serious Engine puede imprimir una advertencia en la consola
Single-player y demos como casos especiales de conexión local
- La reproducción single-player y de demos también tienen internamente un servidor y un cliente, pero corren dentro del mismo proceso
- Como no hace falta usar sockets dentro del mismo proceso,
Client_OpenLocal()conecta entre sí la interfaz del cliente local y la interfaz del lado del servidor - Dos
CClientInterfaceconectadas mueven conExchangeBufferslos paquetes del buffer de salida de un lado al buffer de entrada del otro - El juego local no necesita pasar por los buffers maestros de entrada/salida ni por sockets de red reales
Capa de mensajes de red
CNetworkMessagees una abstracción de mensajes encima de los paquetes y puede leerse y escribirse como un stream- Los mensajes se serializan y deserializan con
Read,Write,ReadBits,WriteBitsy los operadores<<,>> - También puede contener submensajes, y después de escribir los datos necesarios puede ajustar el tamaño del buffer al tamaño de los datos con
Shrink - El buffer de
CNetworkMessagese asigna medianteAllocMemory, que internamente parece llamar amalloc - Existe
CLinearAllocator, pero no se encontró dónde se usa; los buffers de mensajes se asignan y reasignan con frecuencia
Compresión y codificación delta
- Los mensajes se pueden comprimir con un compresor especificado o con el compresor por defecto según el tipo de mensaje
- En
MESSAGETYPE, los 6 bits inferiores son el tipo y los 2 bits restantes indican el método de compresión- LZ77
CzlibCompressor - LZRW1
CLZCompressor - Sin compresión
- LZ77
- La compresión por defecto parece ser LZRW1, y se puede cambiar con la variable de shell
net_iCompression CPlayerActionno se envía tal cual, sino que se crea y transmite un delta haciendo XOR entre la acción actual y la última acción- El receptor restaura el
CPlayerActionoriginal haciendo XOR nuevamente entre la última acción y el delta - El delta se comprime mejor cuando los cambios en los datos son pequeños
- Las teclas presionadas suelen mantenerse durante varios frames
- La velocidad y la rotación de la vista tampoco recorren grandes rangos completos de punto flotante
- Cuando el servidor envía las acciones de varios jugadores juntas con
MSG_SEQ_ALLACTIONS, este método puede ser aún más efectivo
Cifrado de mensajes y chat
- Los mensajes de Serious Engine no están cifrados
- Si se desactiva la compresión con
net_iCompression=0, los mensajes del chat dentro del juego aparecen en texto plano en el payload de los paquetes UDP - En una situación real, si la compresión está activada, quien capture paquetes tendría que identificar y descomprimir el stream LZ, pero los datos necesarios están dentro del paquete
- Los juegos de esa época muchas veces no manejaban cifrado, y agregar mecanismos como autenticación e intercambio de claves podía aumentar la complejidad
- En esa época, la web también era mayormente HTTP
Capa de sesión de juego
CNetworkLibrary, pese a su nombre, administra la sesión de juego, incluido el estado del juegoCSessionStateCNetworkLibraryhereda deCMessageDispatcher, mencionado antes- Al iniciar un servidor, el engine realiza el siguiente procedimiento
- Inicializa la recopilación de CRC para prepararse a verificar que los clientes conectados tengan los mismos archivos que el servidor
- Crea un nuevo
CSessionState, lo serializa y lo guarda como estado basega_pubDefaultState - Carga la instancia del mundo local
- Inicializa la interfaz global de comunicación
- Inicializa el estado de la sesión local, y deja listo el envío de un delta de estado entre el estado base y el estado actual del servidor cuando se conecte un cliente
- Termina la recopilación de CRC y la guarda en
ga_ulCRC
- La verificación CRC se parece más a una detección temprana de desincronizaciones que a una medida anti-cheat
- El procedimiento de entrada de un cliente sigue este flujo
- Inicializa un estado de sesión local vacío y la interfaz de comunicación
- Envía con
MSG_REQ_CONNECTREMOTESESSIONSTATEla versión del build, el nombre del modo, la contraseña del servidor, la cantidad de jugadores locales yCSessionSocketParams - Recibe con
MSG_REP_CONNECTREMOTESESSIONSTATEun mensaje, el nombre del archivo del mundo, los flags de dificultad y modo de juego, y los atributos de la sesión - Inicializa el estado base del juego
- Envía
MSG_REQ_STATEDELTApara pedir la diferencia con el estado actual del servidor - Tras recibir
MSG_REP_STATEDELTA, reconstruye el stream del estado del juego mediante un diff inverso - Inicializa el estado de sesión local con
CSessionState::Read_t() - Realiza la verificación CRC y se desconecta si hay una discrepancia
Loop principal y retransmisión del stream del juego
- El loop principal del cliente y del servidor es en general parecido, pero el servidor realiza trabajo adicional
- El loop actualiza la interfaz del cliente local y la interfaz de broadcast, y el estado de la sesión local procesa los mensajes de red entrantes
- El servidor también se encarga del intercambio de buffers entre interfaces de cliente emparejadas, la actualización de las interfaces de cliente del lado del servidor, la actualización de GameAgent y el procesamiento de comandos de shell de administración remota
SessionStateLoop()procesa por separado mensajes no confiables y confiables- No confiables:
MSG_GAMESTREAMBLOCKS,MSG_KEEPALIVE,MSG_INF_PINGS,MSG_CHAT_OUT - Confiables:
MSG_INF_DISCONNECTED,MSG_ADMIN_RESPONSE
- No confiables:
MSG_GAMESTREAMBLOCKSes un mensaje no confiable, pero si se pierde puede romper la sincronización- Serious Engine verifica secuencias faltantes durante la etapa de procesamiento del stream del juego y solicita retransmisión
- Si está el siguiente bloque de secuencia esperado, lo procesa
- Si no está el siguiente bloque ni hay bloques más recientes, no hace nada en ese loop
- Si falta el siguiente bloque pero hay uno más reciente, puede haber una pérdida, así que configura un timeout
- Después del timeout, solicita con
MSG_REQUESTGAMESTREAMRESENDla secuencia del bloque faltante y la cantidad de bloques
- El servidor vuelve a enviar los bloques del stream del juego solicitados
Procesamiento de bloques del stream del juego
MSG_SEQ_ADDPLAYERse envía cuando un jugador entra al juego e incluye el índice del jugador y el descriptorCPlayerCharacterMSG_SEQ_REMPLAYERse envía cuando un jugador se desconecta e incluye solo el índice del jugadorMSG_SEQ_CHARACTERCHANGEtransmite cambios de nombre, equipo y apariencia del jugador- En Serious Sam, el buffer de apariencia contiene la estructura
CPlayerSettings - Esta incluye el nombre del archivo del modelo del jugador, la política de selección automática de armas, el tipo de mira y varios flags
- En Serious Sam, el buffer de apariencia contiene la estructura
MSG_SEQ_PAUSEtransmite pausa o reanudación, e imprime en la consola el nombre del jugador que lo solicitóMSG_SEQ_ALLACTIONScontiene el tiempo del tick actual y las acciones de todos los jugadores- Aplica un
CPlayerActiona cadaCPlayerTarget - Luego procesa timers, eventos, entidades móviles y física
- Aplica un
- La verificación de sincronización se realiza con
MakeSynchronisationCheck()- Crea un
CSyncCheckmedianteChecksumForSync()de entidades, targets de jugadores, etc. - El cliente envía
MSG_SYNCCHECKal servidor, y si no coincide con el estado del servidor, se desconecta
- Crea un
Reducir el input lag mediante predicción
- La predicción es un mecanismo para reducir el problema de que un juego rápido se sienta lento por la latencia de internet
- La predicción del jugador local usa las acciones enviadas al servidor
- La predicción de jugadores remotos usa la última acción recibida del servidor
- Si el cliente avanza directamente el estado real del juego sin esperar la respuesta del servidor, no conoce las acciones de otros jugadores y puede romper la sincronización
- Serious Engine usa predictors para no mezclar el estado real con el estado predicho
- Un predictor es casi una copia “fantasma” conectada a una entidad normal
- Un predictor temporal se crea durante la predicción y no tiene una entidad conectada en el estado real del juego
- Al procesar un tick de predicción, solo se procesan entidades predictor
- Cuando el cliente recibe acciones de jugadores desde el servidor, destruye el predictor existente e inicia un nuevo ciclo de predicción
- Al renderizar, no dibuja la entidad original que está siendo predicha, sino el predictor, para que parezca que el movimiento avanza sin cambiar mucho el estado real
- El jugador local solo puede predecir tantas acciones como acciones enviadas al servidor estén almacenadas en
plt_abPrediction - En la predicción de jugadores remotos, si
cli_bLerpActionsestá desactivado, se repite la última acción recibida - Si
cli_bLerpActionsestá activado, se interpola linealmente entre las últimas dos acciones, pero el valor por defecto es desactivado
Comparación con Doom y Quake
- El networking de Doom era en realidad peer-to-peer, pero los clientes intercambiaban una estructura parecida a
CPlayerActiony cada uno corría una simulación independiente - Doom también usaba un sistema similar para grabar y reproducir demos
- Quake usaba una estructura distinta, más cercana a un modelo en el que el cliente no procesa gran parte de la lógica del juego directamente, sino que recibe actualizaciones de estado del servidor
- Con el enfoque de Quake hay menos preocupación por los problemas de sincronización, y también puede ser más fácil prevenir trampas si el servidor no envía información de entidades detrás de paredes
- En Serious Sam eran comunes sesiones con muchos más enemigos y objetos activos que en Quake, así que enviar el estado de muchos objetos en cada tick podría haber implicado una carga grande de ancho de banda
Portabilidad y límites estructurales
- Algunos mensajes de red serializan estructuras de una forma cercana a un
reinterpret cast - Puede funcionar si se asume un solo compilador y una sola plataforma, pero en un juego multiplataforma el layout de las estructuras y el padding pueden variar
- Un ejecutable de 32 bits puede intentar alinear a límites de 4 bytes, y uno de 64 bits a límites de 8 bytes
- También existe el problema del endianness
- Las PC x86 son little-endian
- PS3 es big-endian
- La estructura de Serious Engine es elegante en el sentido de que abstrae para la lógica del juego las diferencias entre medios de transmisión como red y archivos, pero como el modelo hace que todos los clientes tengan una copia del estado del juego, permite trampas
- Por ejemplo, un cliente modificado podría mostrar en un deathmatch las siluetas de otros jugadores detrás de las paredes
1 comentarios
Comentarios de Hacker News
Fui uno de los desarrolladores encargados de implementar el código de red de Serious Sam
Solía dormir seguido debajo de un escritorio en la oficina de Croteam mientras revisaba Usenet, y en particular me inspiró un texto que explicaba el sistema de predicción de QuakeWorld
Esa noche armé una implementación mínima y sencilla mientras mi colega Dan hacía pruebas usando una vieja máquina Unix 486 como router para simular latencia
Eso fue mucho antes de que el juego real se construyera sobre esa base
Todavía lo escucho
Siempre me gustaron mucho los juegos cooperativos y los shooters, pero mis amigos siempre querían jugar Counter-Strike
Gracias a Serious Sam, de vez en cuando podía convencerlos de jugar algo que a mí me gustaba
Mi tío fue una persona muy importante en mi vida, y jugar los juegos que le gustaban es una buena forma de seguir conectado con su recuerdo
Quedan como un gran juego, un gran multijugador y muy buenos recuerdos
Serious Sam siempre fue un gran juego para LAN parties
No porque fuera el título más vistoso de la época, ni porque alguien lo planeara con anticipación
Dominaba las LAN parties porque, cuando otros juegos se caían por problemas de drivers, temperatura, actualizaciones y demás, lanzabas Serious Sam y simplemente funcionaba
Eso siguió igual en las secuelas: incluso si la PC de alguien estaba completamente hecha pedazos, seguía soportando pantalla dividida de forma estable y manejaba bien los dispositivos de entrada
La parte de sistemas del juego era realmente sobresaliente en términos de confiabilidad
De forma parecida, Counter-Strike tampoco tenía grandes gráficos, pero corría bien hasta en PCs tostadora, y por eso siguió siendo popular durante tanto tiempo
Era el único shooter en primera persona que corría de forma consistente en las PCs de oficina, y además era muy divertido
En ese tiempo, en EA había bastante solapamiento entre QA y soporte técnico: en verano, la gente de soporte trabajaba como beta testers internos para alcanzar los lanzamientos de fin de año, y en invierno, cuando aumentaban las llamadas por Navidad, volvían a hacer soporte técnico
Cuando implementamos multijugador en el port de Game Boy Color de Vigilante 8, usamos gameplay determinista
El cable link de GBC enviaba y recibía 1 byte en ambas direcciones al mismo tiempo, y funcionaba como un par de registros de desplazamiento que se rellenaban mutuamente a través del cable
El juego estaba fijado a la tasa de cuadros de la GBC, y en la práctica había mucho trabajo de refresco de pantalla que hacer en cada V-Blank; si eso fallaba, el desplazamiento suave se rompía
Al comenzar una partida multijugador intercambiábamos las seeds, y la ejecución era así: en el frame A se leían los inputs, se comprimían en 1 byte y se colocaban en el buffer de envío. La transmisión ocurría mientras se renderizaba el frame B. Al inicio del frame C, ya tenías el input local enviado en el frame A y el input remoto recibido en el frame B
Aplicábamos esos inputs al estado del juego y renderizábamos el frame C, así que tanto el input local como el remoto se aplicaban con 1 frame de retraso
En el juego local no había input lag, así que si perdiste en multijugador, puedes echarle la culpa a la latencia o, si hace falta, culparme específicamente a mí
Es un muy buen juego, y la explicación técnica de cómo implementaron el multijugador también está buenísima
Croteam es un equipo de desarrollo de juegos realmente talentoso
Disfruté muchísimo The Talos Principle 1 y 2, y con el primero fueron de los pioneros en crear temprano un motor de juego completamente personalizado con Vulkan
Me pregunto si es la misma idea que “1500 arqueros en 28.8K” de Age of Empires
https://www.gamedeveloper.com/programming/1500-archers-on-a-...
Muchísimos juegos usaron este tipo de sistema durante mucho tiempo, aunque hoy parece menos común que antes por varias razones
Debería bastar con tener o no tener recursos; no hace falta imponer límites solo por imponerlos
Incluso juegos con 10 veces más ancho de banda tienen dificultades para soportar tantos enemigos
Recién caigo en que el aumento de recursos técnicos parece tener un efecto contrario sobre la eficiencia y la creatividad en ciencias de la computación
Cuanto más crecen el ancho de banda, el almacenamiento, la memoria y la capacidad de cómputo, más parece reaccionar el software volviéndose más lento, más inflado y más incompetente por unidad de recurso
Podría llamarse el efecto Benjamin Button del diseño de software
Si el artículo da una cifra, no la encontré
Incluso entre los juegos modernos hay varios multijugador con cantidades de enemigos que podrían considerarse suficientemente “masivas”, y si lo importante es la cantidad de jugadores, también existen juegos que soportan números enormes de jugadores
Yo diría que era un juego en el que pasabas más tiempo moviéndote hacia atrás que hacia adelante
Está en Steam; no sé si es del mismo estudio, pero pertenece al universo de Serious Sam
La arquitectura de Factorio es parecida: transmite casi solo eventos de entrada y depende de un núcleo de simulación lockstep
Hay algunas excepciones visibles, como la herramienta de planificación ferroviaria
Parece una restricción de diseño satisfactoria y fácil de probar
Recuerdo haber jugado Serious Sam de niño en un demo de PC Gamer
Incluso entonces ya se consideraba un juego retro que parecía volver a la época de DOOM y Quake
Ahora ya pasaron literalmente 20 años, y se volvió un clásico por derecho propio
Starsiege: Tribes era enorme y ridículamente divertido incluso con una conexión de 56K
https://www.gamedevs.org/uploads/tribes-networking-model.pdf
De hecho, hace poco volví a descargar Tribes 2 y jugué contra bots hace unos meses
Es un juego viejo, pero sigue siendo divertido, y a menudo pienso que me gustaría rehacerlo en algo como Unity
Tal vez algún día lo haga
En 1999 ya te permitía deslizarte por terreno generado proceduralmente como si estuvieras esquiando, ver a otras personas subir por esas colinas de la misma forma, y además tenía mapas grandes y muchos jugadores