¿Solución eficiente para partición espacial multijugador?

10

Esta pregunta es un poco complicada, pero intentaré aclararla.

Digamos que estoy construyendo un juego en línea (no a escala MMO), pero que admite tantos jugadores como sea posible, en un enfoque de servidor autorizado. Quiero mundos realmente grandes con muchos enemigos simulados por IA.

Soy consciente de algunas estrategias para ahorrar CPU del servidor subdividiendo el espacio y no procesando lo que no necesita procesamiento. Ya he dividido el mundo por regiones, lo que requerirá tiempos de carga y pequeñas transiciones, lo que creo que es importante para mantener la calidad del juego cuando se juega localmente (solo o incluso con un par de amigos). No espero que los jugadores estén en más de una o dos regiones.

El problema es que una región puede llegar a ser bastante grande y tener muchos NPC simulando a la vez. ¿Cómo manejo esto sin afectar la experiencia de los jugadores? Enfoques como un servidor por región y similares no están en la tabla.

Estoy buscando principalmente estructuras de datos para contener hordas de enemigos, e incluso NPC pacíficos. Para finalizar la pregunta, tenga en cuenta que existen vehículos, por lo tanto, es bastante rápido viajar dentro de una región, lo que influye en el "cuándo" para eliminar áreas.

Grimshaw
fuente
¿Está restringido a un solo servidor físico?
Patrick Hughes
En definitiva no. Pero por el bien de la sencillez y la viabilidad, por ahora, no puedo complicar el proyecto aún más :)
Grimshaw
Comience simple. Algo así como WoW que opera en múltiples cajas físicas por "servidor" simplemente divide su mundo en una cuadrícula y toda actualización se basa en quién está en las mismas cajas que usted. Muy simple, fácil de ajustar, funciona bien y puede usarlo con solo una caja para controlar el procesamiento.
Patrick Hughes
Estoy totalmente de acuerdo con tu punto de vista, y tal vez me perdí algo en mi pregunta. ¿Qué pasa si hay un jugador a la derecha de la celda de la casilla y otro a la izquierda de la celda vecina derecha? ¡Deberían verse! El mundo parece continuar para un juego como WoW ... Esto es lo que no entiendo, ¿cómo hacer una grilla mundial continua, mientras la mantengo eficiente? Ciertamente, hay situaciones en las que los jugadores de dos "servidores" deberían verse :)
Grimshaw
1
Y sí, si vas a tener muchas cosas por todas partes y muchos jugadores por todas partes, realmente tienes que planificar para que todo esté activo en todas partes y todo el tiempo, no hay forma mágica de evitarlo. Esta es la razón por la cual las cajas individuales de un grupo de servidores MMO solo dan servicio a un máximo de 200-500 jugadores Y por qué MMO AI para NPC es patéticamente estúpido (también conocido como barato de calcular).
Patrick Hughes

Respuestas:

5

Por lo que entiendo, tendrás algún tipo de física ejecutándose en tu servidor.

Si ese es el caso, también hay otras técnicas disponibles para IA / física además de la partición espacial. De más a menos obvio:

  • prioridad: los NPC sin interacción directa con los jugadores pueden recibir menos tiempo de CPU al reducir su frecuencia de actualización. Puede usar colas de prioridad y ejecutar colas con la prioridad más alta de la primera a la última, mientras que otras colas ejecutarán solo 1/2, 1/4 o 1/8 de la cola en cada ciclo. De esta manera, se asegura de que cada objeto se ejecute en algún momento, pero reduce la cantidad de veces que consume CPU.
  • la física también se puede bajar (solo se pueden usar las cajas de colisión y las esferas mientras se está en itinerancia y lejos de la vista).
  • simplificando la IA / simulación asignando comportamientos muy básicos a los NPC y al entorno mientras los jugadores están lejos. Por lo general, vagará o buscará enemigos en lugar de cazar, recolectar, cultivar ...
  • También se puede delegar algo de física e IA a los clientes. Si realmente carece de CPU en los servidores, puede etiquetar el objeto como parcialmente resuelto y los clientes ajustarán la física y la posición de esos objetos localmente (para evitar NPC flotantes). Los clientes pueden tener cierta responsabilidad en la ejecución de IA (durante el combate contra un jugador, el dispositivo del jugador objetivo puede ejecutar directamente los NPC atacantes)
  • Para los jugadores, la física también puede reducirse en el servidor y los clientes recibirán más responsabilidad en la resolución de colisiones. Por ejemplo: golpea un objeto con su vehículo, el servidor solo resolverá la colisión en los cuadros de colisión y etiquetará los objetos como potencialmente en colisión. El cliente enviará la resolución al servidor con una marca de tiempo que la aceptará si los objetos están etiquetados y la solución parece correcta.

Una vez que haya implementado estos mecanismos, puede decidir cuánto y con qué frecuencia los necesita. Lo mejor de esto es que más tarde puede agregar algunos servidores que podrán hacerse cargo de algunas de las tareas en lugar de las aplicaciones del cliente.

Por supuesto, la detección de colisión aproximada creará algunas aberraciones, pero podrá resolverlas agregando más precisión de vez en cuando.

También con respecto a la física, debería echar un vistazo a las bibliotecas que admiten algún tipo de sistema GPGPU como OpenCL o CUDA si tiene acceso a un servidor que lo admite.

Coyote
fuente
Combinar la partición espacial de una región con actualizaciones prioritarias debería ser exactamente lo que necesito, óptimo para pequeñas cantidades de jugadores y aún optimizado cuando se cargan muchas áreas. Gracias.
Grimshaw
@DevilWithin Debería ayudar, y no requiere cambios en el lado del cliente. También agregué algunos detalles más a la respuesta.
Coyote
La IA simplificada es una idea maravillosa. Si bien los NPC están lejos de ser jugadores, no necesitan hacer nada más que moverse en la mayoría de los casos. Eso significa que puedo hacer una aproximación de lo que están haciendo, cada 1 minuto o algo así, solo para hacer que deambulen por el mundo ... imaginándolos como zombies, ¡lo harían!
Grimshaw