javascript - programar - Juego multijugador-¿Cálculo de interpolación de clientes?

programacion de videojuegos pdf

Question

Estoy creando un juego multijugador usando socket io en javascript. El juego funciona perfectamente en este momento aparte de la interpolación del cliente. En este momento, cuando recibo un paquete del servidor, simplemente establezco la posición de los clientes en la posición enviada por el servidor. Esto es lo que he tratado de hacer:

getServerInfo(packet) {
     var otherPlayer = players[packet.id]; // GET PLAYER
     otherPlayer.setTarget(packet.x, packet.y); // SET TARGET TO MOVE TO
     ...
}

Así que establezco la posición del objetivo de los jugadores. Y luego en el método de actualización de jugadores simplemente hice esto:

var update = function(delta) {
    if (x != target.x || y != target.y){
        var direction = Math.atan2((target.y - y), (target.x - x));
        x += (delta* speed) * Math.cos(direction);
        y += (delta* speed) * Math.sin(direction);
        var dist = Math.sqrt((x - target.x) * (x - target.x) + (y - target.y)
                * (y - target.y));
        if (dist < treshhold){
            x = target.x;
            y = target.y;
        }
    }   
}

Esto básicamente mueve al jugador en la dirección del objetivo a una velocidad fija. El problema es que el jugador llega al objetivo antes o después de que llegue la siguiente información del servidor.

Edit: Acabo de leer el Article Gabriel Bambettas sobre este tema, y ​​él menciona esto:

Digamos que recibes datos de posición en t = 1000. Ya recibiste datos en t = 900, así que sabes dónde estaba el jugador en t = 900 yt = 1000. Entonces, desde t = 1000 yt = 1100, muestras lo que el otro jugador lo hizo desde t = 900 hasta t = 1000. De esta manera, siempre se muestran los datos de movimiento reales del usuario, excepto que se muestra 100 ms "tarde".

Esto nuevamente asumió que es exactamente 100 ms tarde. Si su ping varía mucho, esto no funcionará.

¿Podrías proporcionar algún pseudo código para que pueda obtener una idea de cómo hacer esto?

He encontrado esta pregunta en línea here . Pero ninguna de las respuestas proporciona un ejemplo de cómo hacerlo, solo sugerencias.

Answer 1

Actualización 1

Como ha dicho que el sistema ya está sincronizado, creo que solo necesita que cada cliente reciba un mejor corte de los eventos en su juego para reducir el error de posición de los jugadores. Esto significa que se necesita un servidor para enviar mensajes a cada 50 ms en lugar de cada 100 ms. Puede probar diferentes valores reduciendo gradualmente su paso de tiempo actual para ver qué funciona mejor para usted. Una vez que haya fijado el paso de tiempo, para facilitar la carga, cuando no hay cambios importantes, el servidor puede omitir un mensaje como optimización.

Si sus clientes (jugadores) se actualizan más rápido, sus jugadores llegarán al objetivo (casi) a tiempo.

Respuesta original

Suposiciones

1. Cada paquete tiene una información atómica sobre el juego.
2. Cada paquete tendrá un número de secuencia único que el servidor estampará en el paquete.

La importancia de estos supuestos será visible a medida que avancemos en la solución.

Definiciones

1. MessageQueue: cada vez que un cliente recibe un paquete del servidor, esta es la cola en la que los clientes almacenan el paquete.
2. SequenceQueue: el servidor también sigue cada paquete al cliente con otra información llamada SequenceNumber . Esta es la cola en la que el cliente los almacena.
3. SequenceNumber: es un GUID y es comparable, por lo que podemos ordenar los SequenceNumbers.
4. Recibiendo un paquete: es el evento del cliente que recibe un paquete del servidor.
5. Entrega de un paquete: es el evento cuando el cliente realmente lee y procesa un paquete recibido del servidor.

La cuestión

Los eventos de tu juego no están sincronizados. Y eso se debe a que no se garantiza que los paquetes de su servidor estén sincronizados porque en TCP (que creo que está utilizando para el paso de paquetes entre el servidor y el cliente) puede recibir paquetes fuera de orden.

Las soluciones

Solución # 1

Una solución barata puede ser que incluso si recibimos paquetes desordenados, siempre que todos los clientes sigan el mismo orden en el procesamiento de los paquetes, el juego estará sincronizado (porque cada paquete contiene un solo evento atómico del juego). Esta idea se deriva de la serializabilidad de las transacciones de base de datos . Si deduce 100 de la cuenta de A seguido de 50 de la cuenta de A O si deduce 50 de la cuenta de A seguido de una deducción de 100, se obtendrá el mismo resultado. El único requisito es que las dos deducciones deben ocurrir atómicamente.

( No estoy proporcionando el método de implementación de este enfoque, a menos que usted lo solicite ) .

Solución # 2

Resumen

Los clientes pueden recibir dos tipos de mensajes: paquete o número de secuencia. Cuando el cliente recibe un paquete, envía un mensaje al servidor informando que recibió el paquete. Solo cuando el servidor recibe una confirmación de que todos los clientes han recibido un paquete, el servidor envía el mensaje SequenceNumber para que el paquete notifique a los clientes que procesen ese paquete en particular. Esto mantiene a los jugadores sincronizados.

-

Pseudocódigo / Implementación de la Solución 2

Un cliente puede recibir dos tipos de mensajes del servidor a saber. paquete y número de secuencia .

Caso: Se recibe un paquete.

1. Si es GUID ya está presente en el SequenceQueue
   1. Si el GUID del paquete es el más pequeño de todos en el SequenceQueue , entregamos (lea las definiciones anteriores) este paquete y eliminemos la información de la SequenceQueue del SequenceQueue
2. Si el GUID no está presente en SequenceQueue , entonces
   1. El cliente pone este paquete en el MessageQueue
   2. El cliente también envía un mensaje al servidor informando que recibió este GUID en particular

Caso: Se recibe un número de secuencia

1. Si este número es el más pequeño de todos los números de secuencia recibidos hasta el momento y si ninguno de los paquetes tiene un número de secuencia menor
   1. Descartar este número de secuencia
   2. Entregar el paquete para este SequenceNumber desde el MessageQueue
2. De lo contrario, este Número de secuencia no será el Número de secuencia más pequeño
   1. Simplemente agréguelo a la SequenceQueue

Los dos casos escritos arriba son suficientes para mantener a los jugadores sincronizados.

Notas de Cierre

La Solución 2 es una implementación de "Sequencer". El propósito es lograr la Ordenación Total de eventos. Estos son conceptos de sistemas distribuidos. Dado que su juego se ejecuta con varios clientes junto con un servidor, es esencialmente un sistema distribuido. Los siguientes enlaces pueden aclarar conceptos para usted:

1. Pregunta de pedido parcial de eventos en SO
2. Tiempo y orden de los eventos en el sistema distribuido

Answer 2

Dependiendo de tu juego, es posible que prefieras un movimiento suave del jugador en lugar de una ubicación súper precisa. Si es así, entonces sugeriría apuntar a una "consistencia eventual". Creo que su idea de mantener puntos de datos "reales" y "simulados" es buena. Solo asegúrese de que de vez en cuando obligue a lo simulado a converger con lo real, de lo contrario la brecha se volverá demasiado grande.

Con respecto a su preocupación acerca de la diferente velocidad de movimiento, le sugiero que incluya la velocidad actual y la dirección del jugador además de la posición actual en su paquete. Esto le permitirá predecir con mayor facilidad dónde se basará el reproductor en su propia frecuencia de cuadros / actualización.

Esencialmente, calcularía la velocidad y dirección simuladas actuales teniendo en cuenta la última ubicación y velocidad simuladas , así como la última ubicación y velocidad conocidas (ponga más énfasis en la segunda) y luego simulará una nueva posición basada en eso.

Si la brecha entre lo simulado y lo conocido se vuelve demasiado grande, simplemente ponga más énfasis en la ubicación conocida y el otro jugador se pondrá al día más rápido.

Answer 3

Esta pregunta se está dejando abierta con una solicitud de más detalles, así que intentaré llenar los vacíos de la respuesta de Patrick Klug. Sugirió, razonablemente, que transmita la posición actual y la velocidad actual en cada punto de tiempo.

Dado que las mediciones de dos posiciones y dos velocidades dan un sistema de cuatro ecuaciones, nos permite resolver un sistema de cuatro incógnitas, es decir, una spline cúbica (que tiene cuatro coeficientes, a , b , c y d ). Para que esta spline sea suave, la primera y la segunda derivadas (velocidad y aceleración) deben ser iguales en los puntos finales. Hay dos formas estándar y equivalentes de calcular esto: Hermine splines ( https://en.wikipedia.org/wiki/Cubic_Hermite_spline ) y Bézier splines ( http://mathfaculty.fullerton.edu/mathews/n2003/BezierCurveMod.html ) . Para un problema bidimensional como este, sugerí separar variables y encontrar splines tanto para x como para y en función de los datos de la tangente en las actualizaciones, lo que se denomina spline hermite cúbico de Hermite. Esto tiene varias ventajas sobre las splines en el enlace anterior, como las splines cardinales, que no aprovechan esa información. Las ubicaciones y las velocidades en los puntos de control coincidirán, puedes interpolar hasta la última actualización en lugar de la anterior, y puedes aplicar este método con la misma facilidad a las coordenadas polares si el mundo del juego es inherentemente polar como las guerras espaciales. (Otro enfoque que se usa a veces para datos periódicos es realizar una FFT y realizar una interpolación trigonométrica en el dominio de la frecuencia, pero eso no suena aplicable aquí).

Lo que apareció originalmente aquí fue una derivación de la spline Hermite utilizando álgebra lineal de una manera un tanto inusual que (a menos que cometiera un error al ingresar) hubiera funcionado. Sin embargo, los comentarios me convencieron de que sería más útil dar los nombres estándar de lo que estaba hablando. Si está interesado en los detalles matemáticos de cómo y por qué funciona esto, esta es una mejor explicación: https://math.stackexchange.com/questions/62360/natural-cubic-splines-vs-piecewise-hermite-splines

Un mejor algoritmo que el que proporcioné es representar los puntos de muestra y las primeras derivaciones como una matriz tridiagonal que, multiplicada por un vector de coeficientes de la columna, produce las condiciones de contorno y resuelve los coeficientes. Una alternativa es agregar puntos de control a una curva de Bézier donde las líneas tangentes en los puntos muestreados se intersecan y en las líneas tangentes en los puntos finales. Ambos métodos producen la misma spline cúbica, única y suave.

Una situación que podría evitar si eligiera los puntos en lugar de recibir actualizaciones es si obtiene una mala muestra de puntos. Por ejemplo, no puede cruzar líneas tangentes paralelas o decir qué sucedió si está de vuelta en el mismo lugar con una primera derivada distinta de cero. Nunca elegirías esos puntos para una spline por partes, pero podrías obtenerlos si un objeto se desvía entre las actualizaciones.

Si mi computadora no estuviera rota en este momento, aquí es donde pondría gráficos de lujo como los que publiqué en TeX.SX. Desafortunadamente, tengo que retirarme de esos por ahora.

¿Es esto mejor que la interpolación lineal recta? Definitivamente: la interpolación lineal te dará caminos en línea recta, las splines cuadráticas no serán suaves y es probable que los polinomios de orden superior estén sobre adaptados. Las splines cúbicas son la forma estándar de resolver ese problema.

¿Son mejores para la extrapolación, donde intentas predecir a dónde irá un objeto del juego? Posiblemente no: de esta manera, estás asumiendo que un jugador que está acelerando seguirá acelerando, en lugar de que dejará de acelerar de inmediato, y eso podría alejarte mucho más. Sin embargo, el tiempo entre las actualizaciones debe ser corto, por lo que no debe alejarse demasiado.

Finalmente, podrías hacer las cosas mucho más fáciles para ti al programar un poco más la conservación del impulso. Si hay un límite a la rapidez con que los objetos pueden girar, acelerar o desacelerar, sus caminos no podrán desviarse tanto de donde predice en función de sus últimas posiciones y velocidades.

Answer 4

Soy completamente nuevo para la arquitectura cliente / servidor de juego multijugador y los algoritmos, sin embargo, al leer esta pregunta, lo primero que se me ocurrió fue implementar filtros de Kalman de segundo orden (o superior) en las variables relevantes para cada jugador.

Específicamente, los pasos de predicción de Kalman que son mucho mejores que el simple cálculo de cuentas. También el hecho de que los pasos de predicción y actualización de Kalman funcionan de alguna manera como interpoladores ponderados u óptimos. Y además, la dinámica de los jugadores podría codificarse directamente en lugar de jugar con parametrizaciones abstractas utilizadas en otros métodos.

Mientras tanto, una búsqueda rápida me llevó a esto:

Una mejora del algoritmo de cómputo muerto usando el filtro kalman para minimizar el tráfico de red de los juegos en línea 3D

El abstracto:

Los juegos en línea en 3D requieren un soporte eficiente y rápido de interacción del usuario a través de la red, y el soporte de redes generalmente se implementa utilizando el motor de juegos en red. El motor del juego en red debe minimizar el retraso de la red y mitigar la congestión del tráfico de la red. Para minimizar el tráfico de red entre los usuarios del juego, se utiliza una predicción basada en el cliente (algoritmo de cómputo muerto). Cada entidad del juego utiliza el algoritmo para estimar su propio movimiento (también el movimiento de otras entidades) y, cuando el error de estimación supera el umbral, la entidad envía el paquete ACTUALIZACIÓN (incluida la posición, la velocidad, etc.) a otras entidades. A medida que aumenta la precisión de la estimación, cada entidad puede minimizar la transmisión del paquete ACTUALIZADO. Para mejorar la precisión de la predicción del algoritmo de cómputo muerto, proponemos el enfoque de cómputo muerto basado en el filtro de Kalman. Para mostrar una demostración real, usamos un juego de red popular (BZFlag) y mejoramos el algoritmo de cómputo muerto optimizado del juego usando el filtro de Kalman. Mejoramos la precisión de la predicción y reducimos el tráfico de red en 12 por ciento.

Puede parecer una cuestión de palabras y como un problema completamente nuevo para aprender de qué se trata ... y el espacio de estado discreto, para el caso.

En pocas palabras, diría que un filtro de Kalman es un filtro que tiene en cuenta la incertidumbre , que es lo que tiene aquí. Normalmente funciona en la incertidumbre de medición a una frecuencia de muestreo conocida, pero se puede volver a equipar para trabajar con incertidumbre en el período / fase de medición.

La idea es que en lugar de una medida adecuada, simplemente actualice con las predicciones de kalman. La táctica es similar a las aplicaciones de seguimiento de objetivos .

Yo mismo me recomendaron en el intercambio de pila: me tomó aproximadamente una semana averiguar cómo eran relevantes, pero desde entonces las he implementado con éxito en el trabajo de procesamiento de la visión.

(... ¡Me está haciendo querer experimentar con tu problema ahora!)

Como quería un control más directo sobre el filtro, copié la implementación de rollo-propio de otra persona de un filtro de Kalman en matlab en openCV (en C ++):

void Marker::kalmanPredict(){

    //Prediction for state vector 
    Xx = A * Xx;
    Xy = A * Xy;
    //and covariance
    Px = A * Px * A.t() + Q;
    Py = A * Py * A.t() + Q;
}

void Marker::kalmanUpdate(Point2d& measuredPosition){

    //Kalman gain K:
    Mat tempINVx = Mat(2, 2, CV_64F);
    Mat tempINVy = Mat(2, 2, CV_64F);
    tempINVx = C*Px*C.t() + R;
    tempINVy = C*Py*C.t() + R;
    Kx = Px*C.t() * tempINVx.inv(DECOMP_CHOLESKY);
    Ky = Py*C.t() * tempINVy.inv(DECOMP_CHOLESKY);

    //Estimate of velocity
    //units are pixels.s^-1
    Point2d measuredVelocity = Point2d(measuredPosition.x - Xx.at<double>(0), measuredPosition.y - Xy.at<double>(0));  
    Mat zx = (Mat_<double>(2,1) << measuredPosition.x, measuredVelocity.x);
    Mat zy = (Mat_<double>(2,1) << measuredPosition.y, measuredVelocity.y);

    //kalman correction based on position measurement and velocity estimate:
    Xx = Xx + Kx*(zx - C*Xx);
    Xy = Xy + Ky*(zy - C*Xy);
    //and covariance again
    Px = Px - Kx*C*Px;
    Py = Py - Ky*C*Py;
}

Sin embargo, no espero que puedas usar esto directamente, pero si alguien lo descubre y entiende qué ''A'', ''P'', ''Q'' y ''C'' están en el espacio del estado (pista de pista, estado - la comprensión del espacio es un requisito previo aquí) es probable que vean cómo se conectan los puntos.

(Tanto matlab como openCV tienen sus propias implementaciones de filtros de Kalman incluidas por cierto ...)