Predicción de movimiento para no tiradores

35

Estoy trabajando en un juego isométrico en 2D con multijugador de escala moderada, aproximadamente 20-30 jugadores conectados a la vez a un servidor persistente. He tenido algunas dificultades para implementar una buena predicción de movimiento.

Física / Movimiento

El juego no tiene una implementación física real, pero usa los principios básicos para implementar el movimiento. En lugar de sondear continuamente la entrada, los cambios de estado (es decir, eventos de movimiento hacia abajo / arriba / abajo del mouse) se utilizan para cambiar el estado de la entidad de personaje que el jugador está controlando. La dirección del jugador (es decir, / noreste) se combina con una velocidad constante y se convierte en un verdadero vector 3D: la velocidad de la entidad.

En el bucle principal del juego, se llama "Actualizar" antes de "Dibujar". La lógica de actualización desencadena una "tarea de actualización física" que rastrea todas las entidades con una velocidad distinta de cero utiliza una integración muy básica para cambiar la posición de las entidades. Por ejemplo: entity.Position + = entity.Velocity.Scale (ElapsedTime.Seconds) (donde "Segundos" es un valor de coma flotante, pero el mismo enfoque funcionaría para valores enteros de milisegundos).

El punto clave es que no se usa interpolación para el movimiento: el motor de física rudimentario no tiene un concepto de "estado anterior" o "estado actual", solo una posición y velocidad.

Paquetes de cambio de estado y actualización

Cuando la velocidad de la entidad del personaje que controla el jugador cambia, se envía un paquete de "avatar de movimiento" al servidor que contiene el tipo de acción de la entidad (pararse, caminar, correr), dirección (noreste) y posición actual. Esto es diferente de cómo funcionan los juegos 3D en primera persona. En un juego en 3D, la velocidad (dirección) puede cambiar de cuadro a cuadro a medida que el jugador se mueve. Enviar cada cambio de estado transmitiría efectivamente un paquete por trama, lo que sería demasiado costoso. En cambio, los juegos en 3D parecen ignorar los cambios de estado y enviar paquetes de "actualización de estado" en un intervalo fijo, por ejemplo, cada 80-150 ms.

Dado que las actualizaciones de velocidad y dirección ocurren con mucha menos frecuencia en mi juego, puedo evitar enviar cada cambio de estado. Aunque todas las simulaciones físicas se producen a la misma velocidad y son deterministas, la latencia sigue siendo un problema. Por esa razón, envío paquetes de actualización de posición de rutina (similar a un juego en 3D) pero con mucha menos frecuencia, en este momento cada 250 ms, pero sospecho que con buenas predicciones puedo aumentarlo fácilmente a 500 ms. El mayor problema es que ahora me he desviado de la norma: toda la otra documentación, guías y muestras en línea envían actualizaciones de rutina e interpolan entre los dos estados. Parece incompatible con mi arquitectura, y necesito encontrar un mejor algoritmo de predicción de movimiento que esté más cerca de una arquitectura (muy básica) de "física en red".

El servidor luego recibe el paquete y determina la velocidad de los jugadores a partir de su tipo de movimiento basado en un script (¿El jugador puede correr? Obtenga la velocidad de carrera del jugador). Una vez que tiene la velocidad, la combina con la dirección para obtener un vector: la velocidad de la entidad. Se produce alguna detección de trucos y validación básica, y la entidad en el lado del servidor se actualiza con la velocidad, dirección y posición actuales. La aceleración básica también se realiza para evitar que los jugadores inunden el servidor con solicitudes de movimiento.

Después de actualizar su propia entidad, el servidor transmite un paquete de "actualización de posición de avatar" a todos los demás jugadores dentro del alcance. El paquete de actualización de posición se utiliza para actualizar las simulaciones físicas del lado del cliente (estado mundial) de los clientes remotos y realizar predicciones y compensaciones de retraso.

Predicción y compensación de retraso

Como se mencionó anteriormente, los clientes tienen autoridad para su propia posición. Excepto en casos de trampas o anomalías, el servidor nunca reubicará el avatar del cliente. No se requiere extrapolación ("muévete ahora y corrígelo más tarde") para el avatar del cliente, lo que el jugador ve es correcto. Sin embargo, se requiere algún tipo de extrapolación o interpolación para todas las entidades remotas que se mueven. Se requiere claramente algún tipo de predicción y / o compensación de retraso dentro del motor de simulación / física local del cliente.

Problemas

He estado luchando con varios algoritmos y tengo varias preguntas y problemas:

  1. ¿Debo extrapolar, interpolar o ambos? Mi "instinto" es que debería estar usando una extrapolación pura basada en la velocidad. El cliente recibe el cambio de estado, el cliente calcula una velocidad "pronosticada" que compensa el retraso y el sistema físico normal hace el resto. Sin embargo, parece estar en desacuerdo con todos los demás códigos y artículos de muestra: todos parecen almacenar una serie de estados y realizar interpolaciones sin un motor de física.

  2. Cuando llega un paquete, he intentado interpolar la posición del paquete con la velocidad del paquete durante un período de tiempo fijo (por ejemplo, 200 ms). Luego tomo la diferencia entre la posición interpolada y la posición actual de "error" para calcular un nuevo vector y colocarlo en la entidad en lugar de la velocidad que se envió. Sin embargo, se supone que llegará otro paquete en ese intervalo de tiempo, y es increíblemente difícil "adivinar" cuándo llegará el siguiente paquete, especialmente porque no todos llegan a intervalos fijos (es decir, / cambios de estado también). ¿El concepto es fundamentalmente defectuoso o es correcto pero necesita algunas correcciones / ajustes?

  3. ¿Qué sucede cuando se detiene un reproductor remoto? Puedo detener inmediatamente la entidad, pero se colocará en el lugar "incorrecto" hasta que se mueva nuevamente. Si calculo un vector o intento interpolar, tengo un problema porque no almaceno el estado anterior: el motor de física no tiene forma de decir "debe detenerse después de alcanzar la posición X". Simplemente entiende una velocidad, nada más complejo. Soy reacio a agregar la información del "estado del movimiento del paquete" a las entidades o al motor de física, ya que viola los principios básicos de diseño y sangra el código de red en el resto del motor del juego.

  4. ¿Qué debería suceder cuando las entidades colisionan? Hay tres escenarios: el jugador controlador colisiona localmente, dos entidades chocan en el servidor durante una actualización de posición o una actualización remota de la entidad choca en el cliente local. En todos los casos, no estoy seguro de cómo manejar la colisión, aparte de hacer trampa, ambos estados son "correctos" pero en diferentes períodos de tiempo. En el caso de una entidad remota, no tiene sentido dibujarlo caminando a través de una pared, por lo que realizo la detección de colisión en el cliente local y hago que se "detenga". Basado en el punto # 2 anterior, podría calcular un "vector corregido" que continuamente trata de mover la entidad "a través de la pared" que nunca tendrá éxito: el avatar remoto está atascado allí hasta que el error sea demasiado alto y "encaje" posición. ¿Cómo funcionan los juegos alrededor de esto?

Perseguidor de sombras
fuente
1
¿Qué tiene que ver un juego en 3D o 2D con qué tipo de servidor utilizas? ¿Y por qué un servidor no funciona para tu juego?
AttackingHobo
1
@Roy T. compensaciones de ancho de banda. El ancho de banda es el recurso más valioso en los sistemas informáticos actuales.
FxIII
1
Eso no es cierto, los juegos en línea están dominados en gran medida por el tiempo de respuesta, por ejemplo, en una línea de 10Mbit (1.25MB / s) la latencia entre el servidor y el cliente es de 20 ms, el envío de un paquete de 1.25kb tomará 20 ms + 1 ms. Enviar un paquete de 12.5kb tomará 30ms. En una línea dos veces más rápida, un paquete de 1.25kb todavía tomará 20ms + 0.5ms, y 20ms + 5ms para el paquete de 12.kb. La latencia es el factor limitante, no el ancho de banda. De todos modos, no sé cuántos datos hay, pero enviar 50 vectores3 (posición 25x + rotación 25x) es solo 600 bytes, enviar esto cada 20 ms costará 30kb / s. (+ paquete de gastos generales).
Roy T.
2
El motor Quake tiene predicción desde la primera versión. La predicción del terremoto se describe allí y en otros lugares. Echale un vistazo.
user712092
1
¿Hace esta posición + = velocidad * deltatime para cada entidad en paralelo (imperativo: en el código tiene 2 matrices de parámetros físicos de entidades, un cuadro aparte, actualiza el más antiguo para que sea más nuevo y los intercambia)? Hay algunos problemas con la iteración de Sean Barret, quien hizo la base del motor Thief 1 .
user712092

Respuestas:

3

Lo único que hay que decir es que 2D, isométrico, 3D, son todos iguales cuando se trata de este problema. El hecho de que vea muchos ejemplos de 3D y solo esté utilizando un sistema de entrada de octanaje 2D limitado con velocidad instantánea no significa que pueda descartar los principios de redes que han evolucionado en los últimos 20 años.

¡Los principios de diseño se condenan cuando el juego se ve comprometido!

Al descartar los anteriores y los actuales, está descartando los pocos datos que podrían resolver su problema. A esos datos agregaría marcas de tiempo y retraso calculado para que la extrapolación pueda predecir mejor dónde estará ese jugador y la interpolación puede suavizar mejor los cambios de velocidad con el tiempo.

Lo anterior es una gran razón por la cual los servidores parecen enviar mucha información de estado y no controlar las entradas. Otra gran razón se basa en qué protocolo estás usando. UDP con pérdida de paquetes aceptados y entrega fuera de orden? TCP con entrega asegurada y reintentos? Con cualquier protocolo, obtendrá paquetes en momentos extraños, retrasados ​​o apilados uno encima del otro en una oleada de actividad. Todos esos paquetes extraños deben encajar en un contexto para que el cliente pueda descubrir qué está pasando.

Finalmente, aunque sus entradas están muy limitadas a 8 direcciones, el cambio real puede ocurrir en cualquier momento: aplicar un ciclo de 250 ms frustrará a los jugadores rápidos. 30 jugadores no es nada grande para cualquier servidor. Si habla de miles ... incluso entonces, los grupos de ellos se dividen en varios boxen, por lo que los servidores individuales solo llevan una carga razonable.

¿Alguna vez ha perfilado un motor de física como Havok o Bullet funcionando? Realmente están bastante optimizados y son muy, muy rápidos. Puede caer en la trampa de asumir que la operación ABC será lenta y optimizará algo que no la necesita.

Patrick Hughes
fuente
¡Consejos sabios definitivos aquí! Es fácil perder de vista el panorama general. Estoy usando TCP en este caso. El problema de las "8 direcciones" no es tanto un problema en términos de entradas, sino más bien un problema de interpolación y extrapolación. Los gráficos se limitan a esos ángulos y usan sprites animados: el juego "se ve raro" si el jugador se mueve en un ángulo o velocidad diferente que está demasiado lejos de la norma.
ShadowChaser
1

¿Entonces su servidor es esencialmente un "árbitro"? En este caso, creo que todo en su cliente debe ser determinista; debe asegurarse de que todo en cada cliente siempre dará el mismo resultado.

Para su primera pregunta, una vez que el jugador local recibe la dirección de los otros jugadores, además de poder desacelerar su movimiento a lo largo del tiempo y aplicar colisiones, no veo cómo podría predecir qué dirección tomará el jugador la próxima vez, especialmente en un Ambiente de 8 direcciones.

Cuando reciba la actualización de "posición real" de cada jugador (que tal vez podría intentar tambalearse en el servidor) sí, deberá interpolar la posición y la dirección del jugador. Si la posición "adivinada" es muy incorrecta (es decir, el jugador cambió completamente de dirección justo después de que se envió el último paquete de dirección), tendrá una gran brecha. Esto significa que el jugador salta de posición o puede interpolar a la siguiente posición adivinada . Esto proporcionará una interpolación más suave con el tiempo.

Cuando las entidades colisionan, si puedes crear un sistema determinista, cada jugador puede simular la colisión localmente, y sus resultados no deberían estar muy lejos de la realidad. Cada máquina local debe simular la colisión para ambos jugadores, en cuyo caso, asegurarse de que el estado final sea no bloqueante y aceptable.

Para el lado del servidor, un servidor de árbitros aún puede hacer cálculos simples para verificar, por ejemplo, la velocidad de un jugador en cortos períodos de tiempo para usarlo como un simple mecanismo anti trampa Si recorres el monitoreo de cada jugador durante 1s a la vez, tu detección de trampas será escalable, solo que llevará más tiempo encontrar tramposos.

Jonathan Connell
fuente
Gracias, eso suena bastante cerca de lo que necesito, especialmente en el lado del servidor. Un punto interesante es que, aunque los jugadores están bloqueados en 8 direcciones, el movimiento interno es un vector 3D. Pensé en esto un poco más en los últimos días, y creo que estoy luchando por el hecho de que no tengo la interpolación implementada en absoluto: simplemente uso una integración muy básica, estableciendo la velocidad y actualizando la posición en función de la vector cada actualización
ShadowChaser
No estoy seguro de cómo combinar eso con interpolación o predicción. Intenté tomar la posición actualizada enviada en el paquete, integrándolo durante un período de tiempo fijo (por ejemplo, 200 ms) y luego determinando el vector (velocidad) necesario para alcanzar ese punto en 200 ms. En otras palabras, independientemente de la posición incorrecta actual del jugador en el lado del cliente, aún deben alcanzar la misma "posición correcta estimada" en 200 ms. Terminó enviando a mi personaje en direcciones locas, supongo porque los 200 ms realmente deberían ser el momento para el próximo paquete, que no puedo estimar.
ShadowChaser
¿Se aseguró de integrar primero la posición correcta en t a t + 1 antes de integrar la posición incorrecta en la posición correcta adivinada en t + 1?
Jonathan Connell
Sí, verifiqué que estaba usando la posición correcta para la integración original. Originalmente eso era un error, pero solucionarlo todavía no parecía crear una mejora notable. Mi sospecha es el "+1": debe ser muy dependiente del tiempo entre paquetes. Hay dos problemas: enviar cambios de estado además de las actualizaciones regulares (250 ms) y no puedo predecir cuándo ocurrirán. Además, soy reacio a bloquear en un intervalo específico, ya que tiene sentido que el servidor envíe menos actualizaciones para entidades que están más lejos del reproductor. El tiempo entre paquetes puede cambiar.
ShadowChaser
1
Sí, incluir un tipo fijo de paso de tiempo probablemente no sea una buena idea. Sin embargo, me preocupa que la irregularidad del movimiento de 8 direcciones sea muy difícil (¿si no imposible?) De predecir. Aun así, puede intentar utilizar la latencia promedio del cliente para predecir t + 1 y tener un umbral por encima del cual siempre "teletransporta" a los otros jugadores a sus nuevas posiciones.
Jonathan Connell
0

¿No puedes incluir la velocidad en tus mensajes de cambio de estado y usar eso para predecir el movimiento? por ejemplo, ¿supone que la velocidad no cambia hasta que recibe un mensaje que dice que cambió? Creo que ya está enviando posiciones, por lo que si algo "se sobrepasa" debido a esto, tiene la posición correcta de la próxima actualización de todos modos. Luego, puede avanzar posiciones durante las actualizaciones como ya lo hace usando la velocidad del último mensaje y sobrescribiendo la posición cada vez que se recibe un mensaje con una nueva posición. Esto también significa que si la posición no cambia, pero la velocidad necesita enviar un mensaje (si ese es un caso válido en su juego), pero eso no afectará mucho su uso de ancho de banda, si es que lo hace.

La interpolación no debería importar aquí, es decir, por ejemplo, cuando sabe dónde estará algo en el futuro, si lo tiene, qué método está utilizando, etc. ¿Está confundido con la extrapolación tal vez? (para lo que describo es uno, simple, enfoque)

jheriko
fuente
-1

Mis primeras preguntas serían: ¿Qué hay de malo en usar un modelo donde el servidor tiene autoridad? ¿Por qué importa si el entorno es 2D o 3D? Haría que su protección contra trampas fuera mucho más fácil si su servidor tuviera autoridad.

La mayoría de las muestras que vi estrechamente acoplan la predicción de movimiento directamente en las propias entidades. Por ejemplo, almacenar el estado anterior junto con el estado actual. Me gustaría evitar eso y mantener entidades con su "estado actual" solamente. ¿Hay una mejor manera de manejar esto?

Al realizar la predicción, es necesario mantener varios estados (o al menos deltas) en el cliente para que cuando se reciba el estado / delta autorizado del servidor, se pueda comparar con los del cliente y se pueda hacer lo necesario. correcciones La idea es mantener tanto determinismo como sea posible para minimizar la cantidad de correcciones requeridas. Si no mantiene los estados anteriores, no puede saber si sucedió algo diferente en el servidor.

¿Qué debería pasar cuando el jugador se detiene? No puedo interpolar a la posición correcta, ya que podrían tener que caminar hacia atrás u otra dirección extraña si su posición está demasiado adelante.

¿Por qué necesitas interpolar? El servidor autorizado debe anular cualquier movimiento erróneo.

¿Qué debería suceder cuando las entidades colisionan? Si el jugador actual choca con algo, la respuesta es simple: simplemente evita que el jugador se mueva. Pero, ¿qué sucede si dos entidades ocupan el mismo espacio en el servidor? ¿Qué sucede si la predicción local hace que una entidad remota choque con el jugador u otra entidad? ¿También los detengo? Si la predicción tuvo la desgracia de pegarlos frente a una pared que el jugador ha recorrido, la predicción nunca podrá compensar y una vez que el error llegue a un nivel alto, la entidad saltará a la nueva posición.

Estas son las situaciones en las que habría un conflicto entre el servidor y el cliente y es por eso que debe mantener los estados en el cliente para que el servidor pueda corregir cualquier error.

Perdón por las respuestas rápidas, tengo que irme. Lea este artículo , menciona tiradores, pero debería funcionar para cualquier juego que requiera redes en tiempo real.

Gyan alias Gary Buyn
fuente
Algunas respuestas: * Si el servidor tiene autoridad, sería responsable de rastrear todas las entidades en movimiento y actualizar sus posiciones en un intervalo regular. En otras palabras, necesita ejecutar el motor de física, lo que podría ser costoso. La escalabilidad es uno de mis principales objetivos de diseño. * Necesito interpolar en el lado del cliente, de lo contrario, cada actualización del servidor enviada a los clientes hará que las entidades salten. En este momento mi interpolación se realiza en el motor de física, solo establece la velocidad. No hay estados ni deltas.
ShadowChaser
He leído todos los artículos de Glenn, pero afirma en los comentarios que solo están orientados a los tiradores (es decir, / altas frecuencias de actualización). Algunos de sus artículos hablan sobre clientes autorizados, que es la implementación por la que me esfuerzo. No quiero hacer ninguna interpolación / física en el servidor, pero estoy dispuesto a cambiar de opinión si esa es realmente la única forma :)
ShadowChaser
1
-1. Lo que escribiste solo toca vagamente el tema; se siente ambiguo Las respuestas se sienten por debajo de lo normal cuando esencialmente "leen este artículo largo", mientras no contienen información útil del artículo en cuestión.
AttackingHobo
1
@AttackingHobo Tendría que estar de acuerdo contigo. Mencioné que tenía prisa, pero eso no es excusa. Si no tuviera tiempo hubiera sido mejor dejarlo solo. Lección aprendida.
Gyan alias Gary Buyn