Zonificación de áreas en un mapa de mosaico grande, así como mazmorras

10

Mi juego es tener un mapa como el de Minecraft, en la forma en que es pseudoinfinito y generado aleatoriamente. Y grande. Digamos que el usuario ha explorado una zona de 1000x1000 (2D aquí), entonces eso es 1,000,000 de mosaicos.

Obviamente no voy a poder almacenarlo todo en la memoria. Tampoco quiero ignorar todo de un mosaico de 10 o cualquier radio: ambos no se actualizarán (todos los NPC, quizás mosaicos reactivos) y tendría que trabajar con posiciones incómodas como 1382,12918.

Entonces, si tuviera que dividirlo en trozos o zonas o lo que sea, por ejemplo, fichas de 64x64, tendría que almacenar cada ficha y la posición del objeto como:

Trozo a, b. Posición x, y.

Pero, ¿y si quisiera mazmorras y cosas por el estilo en mi mapa? Entonces, una sola pieza que conduce a una mazmorra de 40 pisos, cada una con un área de 40x40. No puedo exactamente almacenarlos en el mismo mapa.

Y ahí está el lado de la memoria; ¿cuánto podría almacenar en la memoria al mismo tiempo razonablemente? Podría hacer mosaicos por ID con bastante facilidad, y tener la matriz 2D normal allí. O, de nuevo, ¿hay una solución más efectiva que tener un archivo de datos de tipos de mosaico ? Entonces, para un 64x64 ... eso solo será 20K o lo que sea. Me gustaría que se cargara todo lo posible para la actualización más realista. Pero no sé qué tipo de límites puedo alcanzar sin llegar a acaparar la memoria.

El pato comunista
fuente

Respuestas:

9

Si bien estoy de acuerdo con el sentimiento: "no te preocupes por eso a menos que sea un problema probado", creo que vale la pena pensar desde el principio: la solución de adaptación es mucho más dolorosa. Y sí, solo actualizar mosaicos 'cercanos' es el camino a seguir. Pero el almacenamiento y la capacidad de direccionamiento de los elementos en su mundo de juego de manera eficiente es muy importante por razones de rendimiento.

Lo que realmente está pensando aquí es un conjunto de datos disperso: algo donde los índices potenciales son grandes (o ilimitados), pero solo se utiliza una pequeña proporción. El punto clave es que no sabe exactamente qué proporción se utilizará.

La solución estándar para un problema de conjunto de datos disperso es separar el índice / direccionabilidad del almacenamiento de datos real. Entonces, si el objeto de mosaico es costoso, guárdelo en una forma compacta (por ejemplo, una matriz plana). Pero permita que se indexe a través de un objeto más barato. En su forma más simple, puede ser una matriz 2D (o 3D) que puede indexar fácilmente por coordenadas, pero cada elemento de la matriz es simplemente un índice. Luego usa ese índice para buscar el contenido real del mosaico en una matriz separada y compacta. Si el contenido del mosaico aún no existe, agréguelo al final de la matriz y almacene el índice en la matriz 3D.

La solución se vuelve más compleja si desea admitir la eliminación de contenido (ya que conduce a la fragmentación de la matriz de contenido), y si el contenido de su mosaico es barato, entonces el peso adicional del índice (índices de 32 bits o 64 bits) probablemente abrumará los ahorros de no almacenar cada ficha potencial. También es una búsqueda adicional, que dañará el rendimiento de su caché.

Puede obtener aún más eficiencia de almacenamiento al introducir capas adicionales de indirección. Supongamos que organiza sus mosaicos en trozos, y los trozos tienen una granularidad de 64x64x64. Dado un mosaico en 125, 1, 132, sabes que pertenece en trozo (1,0,2). Entonces tienes un mundo, que consiste en una matriz de fragmentos compacta y una matriz de índices de fragmentos (-1 si el fragmento no existe). El contenido de cada fragmento (si está presente) es una matriz de índices de mosaico de 64x64x64 (-1 si el mosaico aún no existe), y una matriz compacta de mosaicos usados. De esta manera, no se quema una gran cantidad de índices de mosaico para fragmentos que nunca se usan. Al seguir este tipo de enfoque y elegir números razonables para la granularidad del fragmento, puede escalar su universo de forma masiva y mantener el uso de la memoria bajo control. En realidad, si haces tus trozos 32x32x32,

También puede hacer trucos furtivos, como usar el bit de orden superior de su trozo o los índices de mosaico para significar algo especial. Entonces, si una entrada en la matriz de mosaico tiene el conjunto de bits superior, entonces los 31 bits inferiores no significan un índice de mosaico, sino que significan un 'índice de deformación' o algo similar, y puede buscarlo en una lista mantenida por separado para averiguar las coordenadas a las que conduce.

MrCranky
fuente
Advierto a cualquiera que se encuentre con esta pregunta en el futuro: aunque nada en esta publicación es incorrecto, es sinceramente horrible para un juego como Minecraft, que tiene un mundo no escaso. (Y MrCranky dice lo mismo). Su mundo solo se beneficia de esto si tiene algunas cosas y muchas cosas , no pocas cosas y muchos envases .
1
Estoy totalmente de acuerdo en que la sobrecarga involucrada en el mantenimiento de una solución de almacenamiento de conjuntos de datos dispersos es bastante alta, por lo que solo lo haría si el equilibrio estuviera claramente sesgado hacia la escasez. Los factores clave aquí son: costo del artículo de datos y probabilidad de que el artículo de datos no se use. Minecraft tiene un conjunto de datos potenciales masivos y masivos (una gran cantidad de mosaicos en cada dirección). La proporción real del mundo de juego potencial utilizado es pequeña. Aunque reclame grandes extensiones de él a medida que se mueve por el mundo, sigue siendo una pequeña fracción de los elementos de datos potenciales.
MrCranky
1
Lo que hace que Minecraft sea diferente es que el costo por unidad es pequeño, ¿es quizás un solo byte de almacenamiento? Un valor indica 'no hay nada', el resto son tipos de bloque, y podría encajar fácilmente en un byte. Por lo tanto, no tendría un índice para un solo bloque, eso es una locura, el índice es mucho más grande que solo almacenar el valor real del bloque. Pero las reglas de conjunto de datos dispersos aún funcionan en los niveles superiores. Cada porción (por ejemplo, 64x64x64) es costosa de almacenar (256K bloques), por lo que si puede usar un solo valor pequeño para indicar su ausencia, o su dirección si existe, entonces ha guardado un almacenamiento masivo.
MrCranky
6

¿Por qué no puedes almacenar un millón de fichas en la memoria? Incluso mi teléfono tiene 256 MB de RAM; ¿Qué va a ser un millón de mosaicos vacíos, 4-32 MB?


fuente
Simplemente parecía que se estaba almacenando un número tan enorme. Además de eso, también llevará mucho tiempo actualizarlos.
El pato comunista
2
Es mucho más fácil ignorar un conjunto de mosaicos para actualizaciones que tratar con algún tipo de soluciones de paginación de disco. Sólo ingoralos. No actualice mosaicos a más de X distancia de un actor conocido.
2
@TheCommunistDuck Lo único que importa es la cantidad total de memoria utilizada para almacenar los mosaicos, no la cantidad de mosaicos.
Justin
1
De acuerdo con Kragen y Joe. No se preocupe por lo que suena mucho: haga las matemáticas y resuélvalas. Es poco probable que sea un problema.
Kylotan