Partición de espacio binario de alta densidad óptima para cuadrículas

Estoy escribiendo un juego en el que un personaje se mueve en un mapa generado aleatoriamente en tiempo real (como se revela). Esto me lleva a un interesante problema de estructuras de datos. El mapa se genera a medida que se ve, en un círculo alrededor del carácter (probablemente 20-60 mosaicos), de modo que donde hay datos, es muy denso y todo está en una cuadrícula. Sin embargo, donde no hay datos, podría haber espacios enormes, no generados. El personaje podría caminar en un gran círculo, por ejemplo, creando un anillo de fichas alrededor de un vasto espacio vacío.

Una matriz simple crearía cantidades masivas de gastos generales innecesarios y desperdiciaría mucho espacio. Sin embargo, los BSP típicos parecen causar una gran caída en el rendimiento debido a la densa naturaleza de los datos, similar a una cuadrícula.

¿Que sugieres? Matrices – quadtrees – ¿Algunos híbridos de los dos?

Estoy pensando en implementar algo similar en mi juego en el que estoy trabajando. Voy a crear una clase personalizada a la que se puede acceder como una matriz 2D ex. map[x][y] pero el tipo de datos subyacente estaría más cerca de una tabla hash. Algo parecido a los data[x.Value.ToString() + "," + y.Value.ToString()]

Mi juego es bastante básico, ya que mis fichas solo serán transitables, mortales o invocables.

Sin embargo, estoy interesado en una solución más elegante: D

He estado abordando esto durante el último mes, y he encontrado lo que creo que es una solución bastante buena. No es tan rápido como una matriz pura, pero tiene la ventaja de ser infinitamente extensible (dentro de los límites de un int .)

Básicamente, es una partición de espacio binario que se construye hacia arriba (en lugar de hacia abajo, como un quadtree). Si escribe en un punto fuera del espacio de matriz asignado actualmente, genera un nodo más grande y se expande. Si a la mayoría de los nodos hijos de un nodo se les asignan matrices, las agregará a sí mismas y eliminará sus referencias. Esto significa que cuanto más definidos sean los límites que use, mejor será el rendimiento que obtendrá, ya que la estructura actuará como una matriz.

He publicado mi código aquí , y trataré de escribir algún tipo de demostración en el futuro, y me mudaré a un sitio de alojamiento mejor.

No dude en hacerme saber lo que piensa, o si tiene alguna pregunta al respecto.