¿Una forma de almacenar datos de mapas 2D potencialmente infinitos?

29

Tengo un juego de plataformas en 2D que actualmente puede manejar fragmentos con 100 por 100 fichas, con las coordenadas de los fragmentos almacenados como largos, por lo que este es el único límite de mapas (maxlong * maxlong). Todas las posiciones de la entidad, etc., etc. son relevantes en trozos, por lo que no hay límite allí.

El problema que tengo es cómo almacenar y acceder a estos fragmentos sin tener miles de archivos. ¿Alguna idea para un formato de archivo de alta definición preferiblemente rápido y de bajo costo que no necesite abrir todo a la vez?

Blam
fuente
2
Algunas estructuras de datos que podría buscar para obtener más inspiración son las matrices dispersas y las tablas de páginas (multinivel) .
Andrew Russell
Prioridad baja: ¿podría aclarar si el tipo de datos "largo" es de 32 o 64 bits?
Randolf Richardson
2
@Randolf dado que se trata de C #, presumiblemente se refiere a C #, longque es de 64 bits (entonces maxlong es Int64.MaxValue).
Andrew Russell
Notch tiene algunas cosas interesantes que decir sobre los mapas infinitos en Minecraft en su blog aquí: notch.tumblr.com/post/3746989361/terrain-generation-part-1
dlras2

Respuestas:

17

Crea un formato de mapa personalizado para tu juego. Es más fácil de lo que piensas. Solo usa la clase BinaryWriter. Primero escriba el encabezado en unos pocos ints o uints. Información a incluir en el encabezado:

  • La cadena mágica / número mágico de su formato de archivo.
  • El inicio / fin / tamaño de los fragmentos descritos en este archivo

y también (y aquí viene la parte crítica del rendimiento

  • entradas que describen la posición inicial dentro del archivo. Por lo tanto, no tiene que buscar fragmentos específicos.

Con el método anterior, puede (y debe) crear un índice del contenido de sus archivos, que contenga algún tipo de descripción (un nombre especificado por el usuario para la región / fragmento, o solo las coordenadas) y, como segundo valor, la posición en el archivo.

Luego, cuando desee cargar un fragmento específico, solo tendrá que buscar dentro del índice. Cuando tenga la posición, simplemente configure fileStream.Position = PositionOfChunkFromIndex y podrá cargarla.

Se trata del diseño del formato de archivo con el encabezado que describe el contenido del archivo de manera más eficiente.

Simplemente guarde los archivos con una extensión personalizada que creó y listo.

BONIFICACIÓN: agregue compresión BZip2 a regiones específicas del archivo / todo el contenido (¡no el encabezado!), Para que pueda descomprimir fragmentos específicos del archivo, para una huella de memoria muy pequeña.

Riki
fuente
12
Vale la pena señalar que, si va a modificar este archivo sobre la marcha, querrá un encabezado / índice de tamaño fijo o externo, de modo que pueda agregar fragmentos al archivo sin tener que volver a escribir el archivo archivo completo (debido al cambio de compensaciones).
Andrew Russell
En ese momento, ¿no estás implementando una base de datos de archivos planos?
Ape-inago
13

Me encontré con un problema similar y decidí crear mi propia estructura para manejar los datos. Se basa libremente en un árbol cuádruple, pero tiene una capacidad de expansión infinita (al menos tan grande como una Int) en todas las direcciones. Fue diseñado para manejar datos basados ​​en cuadrículas que se expandieron desde un punto central, al igual que Minecraft ahora. Es espacio eficiente en memoria, y muy rápido.

Puede especificar una magnitud mínima para cada nodo (una magnitud de 7 sería 128x128) y una vez que cualquier nodo tenga un porcentaje específico de sus subnodos poblados, se aplana automáticamente en una matriz bidimensional. Esto significa que una porción muy densamente poblada (p. Ej., Un continente completamente explorado) tendrá el rendimiento de una matriz (muy rápida) pero una porción escasamente poblada (p. Ej., Una costa que alguien recorrió hacia arriba y hacia abajo pero no exploró tierra adentro) tienen buen rendimiento y un bajo uso de memoria.

Mi código se puede encontrar aquí . El código está completo, probado (pruebas unitarias y de carga) y bastante optimizado. Sin embargo, el funcionamiento interno aún no está muy bien documentado, pero todos los métodos públicos sí lo están, por lo que deberían ser utilizables. Si alguien decide probarlo, no dude en ponerse en contacto conmigo si tiene preguntas o comentarios.

Todavía no lo he usado para almacenar datos en un archivo, pero es un problema interesante y puedo abordarlo a continuación.

dlras2
fuente
Entonces este es básicamente un árbol expandible, ¿verdad? ¿Qué me estoy perdiendo?
kaoD
2
La mayor mejora sobre un árbol expandible es que 'aplana' ciertos nodos del árbol que están muy poblados (70% por defecto) en matrices 2D, en lugar de mantenerlos estructurados como árboles. Esto le da la velocidad de una búsqueda de matriz, sin el tamaño (infinito) de una matriz infinita.
dlras2
Tanto la hoja como los nodos internos, ¿verdad? Una idea interesante, podría dar buenos resultados, lo intentaré si alguna vez necesito esto. Por cierto, +1 por dar el código y la respuesta rápida! Ah, y las pruebas unitarias también, (tristemente) nunca hago eso en mis proyectos personales :)
kaoD
No hacemos pruebas unitarias en mi trabajo, así que lamentablemente es mi forma de rebelarme. Creé una aplicación de demostración para ello, que muestra cómo se llena y se aplana, así que si puedo limpiar eso en los próximos días así que es presentable, lo publicaré aquí también. Tiene mucho más sentido cuando lo ves.
dlras2
1
Lo perdí de vista, lo siento! Todavía me gustaría limpiarlo, pero estoy revisando lentamente parte del código entre la clase y la tarea, por lo que no será por un tiempo. Por ahora, la demostración antigua y poco bonita está aquí: j.mp/qIwKYt Por poco bonita, quiero decir que requiere mucha explicación, así que no olvides leer el archivo README y no dudes en hacer preguntas aquí o vía correo electrónico.
dlras2
3

En su lugar, podría usar una base de datos: PostgreSQL tiene algunas capacidades de indexación especiales optimizadas para este tipo de datos que se ubican mediante coordenadas X e Y. También puede especificar que los datos devueltos se encuentren dentro de un cierto radio en lugar de en un área cuadrada u oblonga.

  PostgreSQL (fuente libre y abierta)
  http://www.postgresql.org/

También hay otras bases de datos, y para el lado del cliente, puede encontrar ciertos tipos que se adaptan mejor a esto, ya que pueden ejecutarse de forma independiente (iniciada por su aplicación cliente del juego) o pueden incluirse como parte de una biblioteca de códigos que puedes "usar". La ventaja es que no tiene que diseñar un esquema de indexación porque la mayoría de los motores de bases de datos SQL ya lo hacen bastante bien.

Una ventaja con el enfoque de la base de datos es que puede hacer que sus fragmentos sean más pequeños (o deshacerse de los fragmentos por completo y solo usar mosaicos directamente, pero el uso de al menos pequeños fragmentos / grupos de muchos mosaicos puede ser más eficiente dependiendo de su diseño), y luego use la consulta SQL para traer un área más grande de lo que se puede ver. Al precargar para superponer áreas cercanas no visibles, las fichas se pueden preparar antes de que el jugador mueva su personaje, lo que resulta en una mejor experiencia de juego (con suerte más suave).

Me di cuenta de que algunos juegos mantienen un "caché" de los datos del mapa en el disco duro local después de obtenerlo por primera vez (esto es sin duda para reducir las E / S de la red), como Ashen Empires:

  Ashen Empires (gratis para jugar, hermosa implementación 2D)
  http://www.ashenempires.com/

Hacer un seguimiento de las marcas de tiempo de "última actualización" con cada fragmento / mosaico también será útil, ya que, para los datos disponibles localmente almacenados, la consulta SQL podría incluir una cláusula adicional "WHERE timestamp_column> $ local_timestamp" para que solo se obtengan fragmentos / mosaicos actualizados descargado (dos beneficios de ahorrar ancho de banda como este son menores costos de conectividad y menos retraso para sus jugadores, lo que será más obvio cuando su juego se vuelva popular).

Una captura de pantalla de Ashen Empires (algunos personajes están en un banco local, y por el aspecto de esos huesos en el piso parece que algunos monstruos esqueletos deben haber entrado y probablemente fueron asesinados por los guardias de la ciudad local):

ingrese la descripción de la imagen aquí

Randolf Richardson
fuente
2

No almacene ni acceda a ellos, almacene solo las semillas aleatorias necesarias, así como los cambios del jugador en el mapa. Luego genere las porciones requeridas en tiempo de ejecución (ejecute su algoritmo de generación, luego aplique los cambios del jugador). Con un procedimiento de generación correcto y consistente, el mapa resultante siempre será el mismo para la misma semilla inicial.

Teóricamente, puedes hacer literalmente un mapa infinito que se guardará en un archivo muy pequeño de esta manera.

código sh
fuente
@ Josh Petrie, gracias por el gran y significativo lenguaje / correcciones estilísticas a mi publicación. lástima que no pueda votar una edición :-D
sh code
1

¿Hay alguna manera de dividir fragmentos (algún tipo de 'subcontinentes / países' en su mundo)? Entonces, tal vez pueda tener algún tipo de archivo de índice que le permita encontrar rápidamente qué subarchivo / parte del archivo más grande necesita cargar para tener un fragmento en la memoria ...

phtrivier
fuente
siempre hay una forma de particionar fragmentos. SIEMPRE. ya sean visibles para el jugador / relevantes para el resto del sistema o no, siempre hay una forma de particionar los datos mundiales en fragmentos, generalmente de varias maneras diferentes.
código sh
0

Podrías tomar la idea de Minecraft. Originalmente tenían un archivo por trozo. Ahora usan el formato MCRegion, que agrupa fragmentos en áreas de 32x32 y almacena uno de esos por archivo.

El pato comunista
fuente