Representando un mundo de juego que tiene una forma irregular

Question

Estoy trabajando en un proyecto donde el mundo del juego tiene una forma irregular (piense en la forma de un lago). esta forma tiene una cuadrícula con coordenadas colocadas sobre ella. El mundo del juego está solo en el interior de la forma. (Una vez más, piensa Lake)

¿Cómo puedo representar eficientemente el mundo del juego? Sé que muchos mundos son básicamente cuadrados y funcionan bien en una matriz de 2 o 3 dimensiones. Siento que si utilizo una matriz que es cuadrada, básicamente estoy desperdiciando espacio y aumentando la cantidad de tiempo que necesito para recorrer la matriz. Sin embargo, tampoco estoy seguro de cómo funcionaría una matriz irregular.

Ejemplo forma de Mundo

X 
XX 
XX X XX 
XXX XXX 
    XXXXXXX 
XXXXXXXX 
XXXXX XX 
    XX X 
    X 

Editar: El mundo del juego lo más probable es que necesite cada ubicación válida entró. Entonces, un método que hace que sea fácil hacerlo.

Answer 1

Existe una sobrecarga computacional y complejidad asociada con representaciones dispersas, por lo tanto, a menos que el área delimitada sea mucho más grande que su mundo real, probablemente sea más eficiente simplemente aceptar el espacio "desperdiciado". Básicamente está intercambiando el uso de memoria adicional para un acceso más rápido a los contenidos mundiales. Más importante aún, la implementación del 'espacio desperdiciado' es más fácil de comprender y mantener, lo que siempre es preferible hasta el punto donde se requiere una implementación más compleja. Si no tienes buena evidencia de que sea necesario, entonces es mucho mejor que sea simple.

Answer 2

Usa una estructura de datos como una lista o un mapa, y solo inserta las coordenadas válidas del mundo del juego. De esta forma, lo único que está guardando son las ubicaciones válidas, y no desperdicia la memoria al guardar las ubicaciones mundiales que no son de juegos, ya que puede deducirlas de la falta de presencia en su estructura de datos.

Answer 3

Puede presentar el mundo como un gráfico (no dirigido) de parches de tierra (o agua). Cada parche tiene una forma regular y el mundo es la combinación de estos parches. Cada parche es un nodo en el gráfico y tiene bordes de gráfico para todos sus vecinos.

Probablemente también sea la representación más natural de cualquier mundo en general (pero puede que no sea la más eficiente). Desde el punto de vista de la eficiencia, probablemente superará a una matriz o lista de un mapa muy irregular, pero no a uno que encaje bien en un rectángulo (u otra forma regular) con pocas desviaciones.

Un ejemplo de un mapa muy irregular:

x 
x x 
    x x x 
    x  x 
    x xxx 
    x 
    x 
    x 
    x 

Prácticamente no hay forma en que esto se puede montar de manera eficiente (tanto en relación de espacio y tiempo de acceso) en una forma regular. A continuación, por otro lado, encaja muy bien en una forma regular aplicando transformaciones geométricas básicas (es un paralelogramo con pequeños trozos que faltan):

xxxxxx x 
xxxxxxxxx 
    xxxxxxxxx 
    xx xxxx 

Answer 4

Lo más fácil es usar la matriz, y solo marca las posiciones no del espacio de juegos con algún marcador especial. Una matriz dentada también podría funcionar, pero no la uso demasiado.

Answer 5

Puede usar un quadtree para minimizar la cantidad de espacio desperdiciado en su representación. Los árboles cuádruples son buenos para dividir el espacio bidimensional con granularidad variable; en su caso, la granularidad más fina es un juego cuadrado. Si tuviera un área entera de 20x20 sin cuadrados de juego, la representación del árbol cuádruple le permitiría usar solo un nodo para representar esa área completa, en lugar de 400 como en la representación de la matriz.

Answer 6

Usa la estructura que hayas ideado --- siempre puedes cambiarla más tarde. Si te sientes cómodo con el uso de una matriz, úsalo. Deje de preocuparse por la estructura de datos que va a utilizar y comience a codificar.

Mientras codifica, construya abstracciones lejos de esta matriz subyacente, como envolverla en un modelo semántico; luego, si se da cuenta (a través del perfilado) de que es un desperdicio de espacio o lento para las operaciones que necesita, puede cambiarlo sin causar problemas. No intente optimizar hasta que sepa lo que necesita.

Answer 7

Otra forma sería almacenar una lista de bordes: un vector de línea a lo largo de cada regla. Fácil de verificar para la inclusión de esta manera y un árbol cuádruple o incluso un hash de ubicación simple en cada vertice puede acelerar la búsqueda de información. Hicimos esto con un componente de altura por borde para modelar las paredes de un estadio de béisbol y funcionó maravillosamente.

Answer 8

Otra opción que podría permitirte seguir accediendo a las ubicaciones del mundo del juego en O (1) tiempo y no perder demasiado espacio sería una tabla hash, donde las claves serían las coordenadas.

Answer 9

Hay un gran problema que nadie aborda aquí: la gran diferencia entre almacenarlo en el disco y almacenarlo en la memoria.

Suponiendo que estás hablando de un juego world como dijiste, esto significa que va a ser muy grande. No va a almacenar todo en la memoria de una vez, sino que almacenará las inmediaciones en la memoria y las actualizará cuando el jugador camine.

Esta área de vecindad debe ser tan simple, fácil y rápida de acceder como sea posible. Definitivamente debe ser una matriz (o un conjunto de matrices que se intercambian a medida que el jugador se mueve). Será referenciado a menudo y por muchos subsistemas de su motor de juego: gráficos y física se encargarán de cargar los modelos, dibujarlos, mantener al jugador en la parte superior del terreno, colisiones, etc .; el sonido necesitará saber en qué tipo de suelo se encuentra parado el jugador, para reproducir el sonido de paso apropiado; y así. En lugar de transmitir y duplicar estos datos entre todos los subsistemas, si solo lo conservas en matrices globales, pueden acceder a él a voluntad y con una velocidad y eficacia del 100%. Esto realmente puede simplificar las cosas (¡pero tenga en cuenta las consecuencias de las variables globales!).

Sin embargo, en el disco definitivamente desea comprimirlo. Algunas de las respuestas dadas proporcionan buenas sugerencias; puede serializar una estructura de datos como una tabla hash o una lista de las únicas ubicaciones completas. También puedes guardar un octree. En cualquier caso, no desea almacenar ubicaciones en blanco en el disco; de acuerdo con su estadística, eso significaría que el 66% del espacio se desperdicia. Seguro que hay un momento para olvidarse de la optimización y hacer que funcione, pero no desea distribuir un archivo de 66% de vacío a los usuarios finales. También tenga en cuenta que los discos no son máquinas perfectas de acceso aleatorio (excepto para SSD); los discos duros mecánicos aún deberían durar al menos otros varios años, y funcionan mejor de forma secuencial. Vea si puede organizar su estructura de datos para que las operaciones de lectura sean secuenciales, a medida que transmite más terreno de vecindad mientras el jugador se mueve, y probablemente encontrará una diferencia notable. Sin embargo, no creo en mi palabra, realmente no he probado este tipo de cosas, simplemente tiene sentido, ¿verdad?