resueltos - ¿Una forma eficiente de almacenar y recuperar objetos complejos en C++?

miembros de una clase en programacion orientada a objetos (6)

Actualmente estoy trabajando en un pequeño juego de simulación de mazmorras. El juego es bastante detallado y estoy planeando tener, con el tiempo, más de 200k instancias de una clase que represente a un "monstruo". Contienen ventajas, habilidades e historia de ese monstruo. Cosas como cuántas pociones ha usado, dónde vive, cuáles son sus rutas de patrulla, etc.

Comencé a implementar esto con SQLite y usando una tabla simple llamada "monstruos", que contenía todos los datos. Esto me permitió usar consultas SQL para encontrar los monstruos necesarios para el cálculo de simulación en cada marco. Por ejemplo: encontrar a todos los monstruos que patrullaban el punto A, o encontrar a todos los monstruos que usaron Potion X, etc. Desafortunadamente, al consultar SQLite varias veces en cada fotograma, el juego se ralentizó rápidamente. Aunque es un juego en 2D, necesito los preciosos milisegundos para los cálculos de simulación.

Además, iba a necesitar unirte en el futuro para hacer gráficos: necesito saber si un monstruo ha atacado a otro monstruo o si un monstruo es parte del equipo de otro monstruo. Eso ralentizaría aún más las cosas.

¿Alguien tiene alguna sugerencia sobre cómo abordar esto?

Mis datos se asemejan a algo como esto:

Basándome en las respuestas / comentarios anteriores y sus respuestas, asumo que decidió continuar utilizando SQL pero desea una mejor manera de leerlo / procesarlo. Por lo tanto, mi respuesta se centra solo en ese aspecto y se relaciona únicamente con el diseño, en lugar de otras sugerencias (como el uso de diferentes motores SQL).

El problema principal en tu DB, como se refleja en tu pregunta original, es que todos los aspectos de un monstruo dado están en un solo registro, todos en la misma tabla . Eso hace que la mesa sea enorme con el tiempo. Además de eso, este diseño hace que su base de datos y código sean difíciles de mantener y evolucionar.

Si bien puede parecer "correcto" mantener todos los detalles de un monstruo en un solo registro (y, tal vez, un solo objeto que lo refleje en el propio código), esto rara vez es una buena decisión. Debe tener una separación clara entre los atributos de un objeto como se modela en su "mundo" a los atributos modelados en software. Por ejemplo, la ubicación de un monstruo probablemente se cambia con mucha frecuencia, mientras que su nombre no lo es. Dado que tiene todos los datos en una sola tabla, cualquier cambio en la ubicación se realiza en la misma tabla que contiene todos los demás atributos, lo que la convierte en una acción muy pesada.

Lo que debes hacer, en cambio, es:

Separar los datos en diferentes tablas.
Elegir buenos índices para cada tabla.
Utilice uniones según sea necesario (basado, por ejemplo, en la ID del monstruo)

De esa manera, cualquier lectura y cambio se realiza solo en el contexto relevante; por ejemplo, cambiar la ubicación de un monstruo solo cambiará la tabla de ubicaciones, sin afectar las tablas de detalles más persistentes. Las combinaciones no deben tomar mucho tiempo, siempre y cuando tenga un buen índice y filtre solo los datos que le interesen. Además de acelerar sus consultas, este diseño es mucho más flexible. Por ejemplo, si desea agregar un nuevo tipo de atributo a los monstruos, simplemente puede agregar una nueva tabla, o usar una tabla existente con datos similares (por ejemplo, el equipo del monstruo) para agregarla.

Si sus consultas dependen mucho de las ubicaciones "geográficas" y aún desea manejarlas utilizando un DB relacional, podría considerar otros tipos de DB que tengan mejor soporte en consultas espaciales.

HTH!

Como entendí, el principal problema para ti es encontrar una forma optimizada de almacenar tus monstruos. Por ejemplo, puedes usar algunas estructuras de datos de árbol para encontrar monstruos efectivamente necesarios en el avión. Una de estas estructuras de datos es BSP (partición de búsqueda binaria) árbol. Es una breve descripción https://en.wikipedia.org/wiki/Binary_space_partitioning . El marco de la vista gráfica de Qt utiliza este enfoque. Para obtener más información al respecto, puede ver en http://doc.qt.io/qt-4.8/graphicsview.html

Hay 2 formas de limitar lo que está sucediendo y se pueden utilizar juntas.

Programación de los eventos.
Limitando los datos a la pantalla visible.

Programar los eventos

Suponiendo que los monstruos no actúen en cada fotograma, la siguiente acción de un monstruo puede programarse para N fotogramas en el futuro, resolviendo solo las acciones que se deben realizar en este fotograma, y luego la cantidad de monstruos a tratar. -frame, se puede reducir.

Limitando los datos a la pantalla visible

sqlite tiene un árbol R * para admitir la selección de solo esos elementos dentro de una región geográfica.

La pantalla solo puede mostrar aquellos monstruos que están visibles, esto permite que solo aquellos dentro del área de la pantalla tengan una simulación precisa y otros monstruos obtengan una simulación más gruesa.

Por lo que puedo decir, World of Warcraft tiene una ecuación de tiempo para la posición de un monstruo ...

MyXY = getPosition( me, currentTime );

Este sería el estado natural del monstruo cuando está en su estado estable "no visto". Esto significa que las acciones para el monstruo no necesitan ser simuladas en absoluto cuando no son visibles.

No consultaría la base de datos SQL en cada fotograma, sino que almacenaría en caché los monstruos que creas que son más probables en los cálculos.

¿Cuántos monstruos debo guardar en caché?

Si hay alguien que sabe, ese eres tú! Sin embargo, creo que solo experimentando encontrarás un punto dulce para el tamaño de tu caché. Buscas implementaciones de caché y te inspiras así.

¿Por qué usar SQL en primer lugar? Considere escribir en el disco.

Su imagen sugiere un gráfico, entonces ¿por qué no almacenar lo que necesita como un gráfico? Como sugirió, la biblioteca de gráficos de Boost (BGL) puede ser útil. Verifique esto también: https://.com/questions/2751826/which-c-graph-library-should-i-use

No ha habido una respuesta aceptada, así que daré una oportunidad a tu pregunta. Pero seré honesto contigo ;-)

Primero: no especificaste demasiados detalles, esto hace que una respuesta realmente adecuada sea difícil, si no imposible. Para mí, no está claro cuántos datos desea procesar en qué momento. Menciona marcos, pero ¿es esto un marco como cuadros por segundo o es más como lo que yo llamaría "un tic del mundo"? En caso de que quiera ejecutar el juego a> 30 fps y actualizar todo el estado del mundo 30 veces por segundo: No , supongo que puede olvidarse de hacerlo (hicimos una simulación de pánico con aproximadamente 1,000 nodos / personas como parte de una conferencia de CUDA. Y aunque eso es mucho más simple que su simulación, apenas pudo ejecutarse en tiempo real en un GTX780, así que supongo que un desarrollador de CUDA experimentado probablemente alcanzará un límite con 10,000 nodos en ese hardware, y usted quiere tener > 20x los nodos con una forma de IA / simulación más compleja que "huir del fuego a la siguiente salida visible y pisotear a otras personas si su nivel de pánico es demasiado alto + colisión de pared 2D simple").

Pero si por marco te refieres a la marca de simulación mundial, entonces sí, esto podría ser factible .

Nuevamente, faltan algunos detalles en sus preguntas: ¿planea desarrollar un servidor MMO dedicado con más de 200 mil monstruos y mil jugadores, o es un jugador local anfitrión? ¿O algo intermedio (RPG multijugador en red, digamos max 16 jugadores)?

Si solo tienes unos pocos jugadores (supongo que sí, ya que dijiste 2D, y no hay una gran diferencia entre uno o cuatro jugadores): no hagas toda la simulación con todo detalle al mismo tiempo. Para una inmersión total, es suficiente tener una simulación detallada cerca del (de los) jugador (s) . Al igual que en lápiz y papel: como maestro del juego (GM), por lo general, solo se suceden algunos eventos clave en todo el mundo, y se hace el resto a medida que se avanza. Si eres un buen gerente general, eso es lo suficientemente convincente para los jugadores, porque ¿a quién le importa si se trata de la posición actual de un guardia en una sala del trono a 50 millas de distancia?

Tengo la sensación de que quieres hacer un "juego adecuado y totalmente simulado con una interacción social completa entre los NPC / monstruo, porque nadie más está haciendo algo así" (corrígeme si me equivoco), pero hay una buena Razón por la que nadie está haciendo eso: es bastante difícil.

Idea: Si piensas en "zonas", solo necesitas ejecutar la simulación en esas zonas donde los jugadores están activos actualmente. Todas las demás zonas están congeladas. Una vez que el (los) jugador (s) cambia de zona, puede simplemente descongelar y hacer avanzar la nueva zona. Puede hacerlo con todo detalle o aproximarlo. Si no quieres cargar pantallas, puedes descongelar y adelantar zonas en las proximidades de los jugadores en los que puedan ingresar.

Además de eso, deberías pensar en tu arquitectura. Por ejemplo, mencionas que quieres saber qué monstruo trajo la poción X. Por supuesto, esto es fácil de escribir en SQL, pero no estarás contento con el rendimiento. O al menos no creo que lo haría, y eso es después de una conferencia de base de datos básica y una conferencia avanzada "escribamos un servidor SQL de alto rendimiento" [revelación completa: soy malo en escribir consultas SQL de alto rendimiento ya que no no suele utilizar SQL]. Plus: ¿Quién necesita ACID completo para un juego? De acuerdo, para simplificar, puede poner cosas que realmente no necesita a menudo en una base de datos SQL (altura de monstruo, peso, textos de sabor, ...?), O ECS, o la técnica que usted considere mejor. Pero todo lo que quieras tocar cada pocos segundos podría ir a la memoria. Quiero decir, si almacenas 1kByte por monstruo, entonces estás en una memoria de ~ 200MByte para 200k monstruos.

De todos modos, volvamos a la pregunta "¿qué monstruos trinkearon la poción X?": ¿Por qué querrías saber eso? ¿Para aplicar efectos? Para comprobar si los efectos de desgaste? Estaría usando una cola de eventos para eso: un monstruo bebe una poción de fuerza -> Actualizar inventario, otorgarle STR extra, calcular un tiempo de espera y poner en cola un evento "desgaste de STR extra" para ". Probablemente sea incluso más rápido que procesar 200 MB de memoria, ya que solo está haciendo "lo que hay que hacer", por tic, y no "verificando todo para cada condición posible, cada tic".

Además, piense que tenga cuidado con los algoritmos: ¿Tiene la persona X la relación con la persona Y, anotada con "público / privado"? Dependiendo de lo que quiera hacer en ese gráfico, podría tener problemas de NP-difícil . Por ejemplo, puede pasar un mal momento si intenta resolver un problema derivado de la clica .

Podría agregar más, pero como la pregunta es un poco vaga, simplemente me detendré aquí y espero que pueda tener algunas buenas ideas.

Si no está utilizando un sistema de componentes de entidad, considere migrar su juego para usar uno. Cada bit de datos relacionados puede almacenarse en un componente autónomo, y la entidad en sí es un identificador opaco que identifica el componente. Cuando usas un ECS, en lugar de tener una entidad de juego con un montón de datos que cuelgan de él, inviertes la relación. Todos los componentes de un tipo específico existen en un grupo grande juntos, y su entidad es solo un identificador que especifica qué componente de este grupo les interesa. Lo que esto le permite hacer es actualizaciones de componentes por lotes. Si tiene un componente de Inventario en cada monstruo con un inventario, todos sus componentes de Inventario se pueden almacenar de forma más o menos contigua en la memoria. Esto significa que cuando los procesa, tiene una alta coherencia de caché que puede ser un aumento significativo del rendimiento.

También puede ser que estés intentando hacer demasiado cada fotograma. Con un sistema de componentes de entidad puede acelerar los subsistemas específicos a cada X cuadros o cada X segundos si lo necesita. Tal vez el componente AI solo necesita ejecutarse una vez por segundo para pensar qué hacer a continuación, pero necesitan seguir moviéndose continuamente para actualizar la posición en cada fotograma. O tal vez armar uno de los cuadros y los gráficos demore demasiado en completarse en un cuadro para que lo calculen en cada segundo cuadro, o dividir el procesamiento en dos cuadros para iterar más de la mitad de sus entidades en el cuadro y el resto en el segundo cuadro. Hay muchas maneras de dividirlo.

Aquí hay más lecturas sobre los sistemas de componentes si no los ha visto antes.