Cómo manejar una gran cantidad de pastillas en un juego MMO

¿Cómo los manejan juegos como Minecraft, o realmente cualquier juego MMO que tenga pastillas?

Digamos que el terreno genera 3 gotas de "suciedad" cada vez que excavas dicho terreno. Digamos que cada elemento tiene una animación de rotación calculada en cada cuadro. Si el número de recolecciones en el mundo es muy alto, eso sería una sobrecarga masiva inútil en el cómputo de trama para un cliente en un servidor dado, ya que es probable que muchos de esos artículos de recolección estén a años luz de usted.

Entonces, lo que pensé es que tienes que "hacer cosas" solo con las pastillas cerca del jugador local, pero aún así esto implicaría que cada cuadro que tengo que verificar si algún otro elemento de la pastilla está lo suficientemente cerca como para comenzar a animar.

Mi pregunta real es: ¿cómo han resuelto este problema otros MMO?

Simplemente cargando esas partes del mundo en la memoria que están cerca del jugador. Cualquier otra cosa está suspendida en el disco duro. Cuando hay un pequeño objeto a unos dos kilómetros de distancia, el jugador no puede verlo y no puede interactuar con él. Por lo tanto, no hay razón para actualizarlo o enviarlo a la GPU para su representación. Cuanto más pequeño es el objeto y su rango de interacción, menor es el rango alrededor del jugador donde necesita cargarlo.

En cuanto a descubrir qué hay cerca del jugador: eso se reduce principalmente a almacenar el mundo en una estructura de datos optimizada para la búsqueda espacial. Los buenos candidatos para eso son el hashing espacial y los árboles multidimensionales .

Tienes dos cosas muy diferentes para administrar:

1. El servidor debe administrar todo el mundo, de manera autoritaria. Para eso, es necesaria la comunicación con N clientes (donde N es "masivo").

2. El cliente podría , en principio, saber sobre el mundo entero, pero no es necesario . Para el cliente, es suficiente saber qué hay cerca del jugador. Suponiendo, por ejemplo, una partición bastante gruesa en forma de cuadrícula, necesitaría conocer solo la celda del jugador y las 26 celdas alrededor del jugador (u 8 celdas en caso de que tenga una cuadrícula 2D). Una cuadrícula algo más fina es mejor, pero entiendes la idea.

Ahora, muchas pastillas, ¿qué es "mucho"? Cavas quizás 5 cosas por segundo, eso es quizás dos docenas de números que deben actualizarse en el servidor, y el servidor puede tener que transmitirlos a algún otro jugador cuya área de interés se superponga a tu celular. Para una computadora, esta es una cantidad de datos bastante ridícula, y una cantidad de cálculo despreciable. Puede convertirse en un desafío cuando hay cientos / miles de jugadores en la misma celda (entonces su partición es demasiado tosca).

El servidor no necesita saber, ni preocuparse por la rotación de las pastillas o dichos detalles. ¿Por qué lo haría?

Al cliente tampoco le importa, ya que esto es solo un dulce visual que el cliente puede inventar sobre la marcha.

Lo que es necesario desde el punto de vista del servidor es saber que estaba cavando en (30, 40, 50) en el nodo en el que se encuentra, y decide que esto genera, por ejemplo, tres objetos de tipo 5 o un objeto de tipo 7 con un recuento de 3. Eso es todo lo que le importa, y es todo lo que te dice. También incluirá esa información en los datos enviados a alguien que mueva su área de interés a través de la celda de la cuadrícula más tarde (suponiendo que todavía esté allí para entonces).

Al cliente le dicen tres objetos engendrados allí, bla, bla. Ahora, ya sea que el cliente muestre un mapa de arte ASCII donde ahora hay una 'D' o si muestra un montón de tierra en rotación, es lo mismo. Si las pilas tienen diferentes rotaciones o si solo las que están cerca de tu jugador rotan, son todas iguales. Es solo algo que se muestra en su monitor, no afecta a nadie más.

Por lo tanto, en el caso concreto en el que desea rotar solo montones de tierra cercanos, puede hacer una verificación de rango de todos los objetos que conoce. Como el conjunto de datos no es grande, incluso la fuerza bruta sobre todo funcionará.

Puede (y debería), dependiendo del tamaño de su partición, podar trivialmente las celdas de la cuadrícula que están demasiado lejos.

Por supuesto, puede subdividir aún más su celda y usar algo súper inteligente. Usa un árbol kd si lo deseas, pero no esperes grandes ganancias. Puede podar cosas con distancia de Manhattan, o puede ordenar sus cosas en una pequeña cuadrícula propia ... pero ¿por qué?

Una verificación de distancia (distancia realmente cuadrada, pero es lo mismo para usted) son solo dos multiplicaciones y una suma (optimizada para MUL, MADD, por lo que en realidad solo son dos operaciones), seguidas de una rama o movimiento condicional. Eso es casi tan rápido como cualquier otra operación que no pode celdas de cuadrícula completas a la vez. De hecho, esto es algo que incluso podrías hacer en la GPU ...

Al ver cómo tendrá unos pocos cientos, o como máximo algunos miles de comprobaciones de distancia en la misma posición (la distancia al cuadrado funciona bien), realmente no tiene muchos problemas solo para hacer ese cálculo, incluso más, ya que es más bien un caché. iteración amigable sobre memoria contigua, y con movimientos condicionales, es muy barato. Algo como (pseudocódigo) rot = r[i] + 1; r[i] = ((dx*dx+dy*dy) < DIST_SQ) ? rot : r[i];. Esa es una iteración sobre una matriz de unos cientos de valores por cuadro. A la computadora no podría importarle menos hacer eso, son cargas y tiendas contiguas, ALU simple, sin ramas, y solo unos pocos miles de iteraciones.

Esto (muchos a uno) no es la misma clase de problema (muchos a muchos) que en el servidor. Realmente, el cliente no es el problema.

@ T.Sar escribe en un comentario que debe consultar el concepto de "trozo cargado" de Minecrafts para obtener más información. Si lo haces, ten en cuenta que esto es bastante complicado en Minecraft debido a que las personas construyen máquinas en el juego.

Sigue una versión muy simplificada:

El mundo está dividido en regiones cuadradas (trozos). En Minecraft también hay una división de altura, pero la mayoría de los mmos no necesitan eso.

El cliente del juego solo se preocupa por las regiones cercanas al jugador. Esto es mucho más simple que dibujar un círculo alrededor del jugador, pero es lo suficientemente bueno.

En Minecraft, las regiones son bloques de 16x16, y el cliente sabe acerca de las regiones de 9x9, 4 regiones en cada dirección. (4 regiones este + región jugador está en + 4 regiones oeste = 9 regiones en total. Mismo norte / sur)

No hay nada mágico en estos números, usa lo que tenga sentido en tu juego.

El cliente solo anima cosas dentro de esta área. El servidor solo calcula cosas como monstruos errantes en regiones cercanas a algún jugador.

Cuando un jugador camina dentro de una región, no sucede nada especial, cuando cruza el borde de una región, el "borde de la animación" se empuja una región. El cliente debe preguntarle al servidor sobre las regiones que ahora ve.

No hay nada de malo en tener varios límites de animación anidados. Por ejemplo, un objeto animado cae en un área de 3x3, monstruos errantes en un área de 5x5 y solo muestra el paisaje en un área de 9x9.

El servidor mantiene una "versión congelada" de regiones que ningún jugador ve. Si esto requiere mucha memoria, es posible que desee descargarlos después de un tiempo. La próxima vez que llega un jugador, la región se vuelve a cargar sin que el objeto caiga. Necesitas ser más rápido la próxima vez, Jugador 1.