Cómo gestionar dependencias entre el mapa de mosaico y las unidades

11

Tengo una estrategia basada en mosaicos 2D en las obras. Me pregunto cómo manejar la relación entre el mapa y las unidades en el mapa.

Dada una coordenada de mosaico, tendré que ser capaz de poner la unidad sobre ella, si la hay. Al mismo tiempo, si me dan una unidad, querré poder obtener la coordenada de la unidad.

He visto dos soluciones para esto. La primera solución sería que las unidades almacenen una coordenada y el mapa almacene referencias de unidades en sus mosaicos. Esto crea una dependencia cíclica entre el mapa y las unidades. Necesitaría asegurarme de que el mapa y cualquier unidad se mantengan sincronizados si la unidad se mueve.

La segunda solución sería hacer que las unidades solo rastreen sus coordenadas. Para saber si un mosaico contiene una unidad y para obtener esa unidad, recorro todo el conjunto de unidades de unidad y encuentro una con coordenadas coincidentes. Eso elimina la dependencia cíclica, pero pierde la propiedad O (1) que tenía la primera solución para buscar unidades del mapa. Esto puede sumar, ya que quiero poder escanear el mapa regularmente en busca de cosas como encontrar el camino, determinar el rango de movimiento y encontrar objetivos válidos para una unidad determinada.

Tampoco puedo almacenar las unidades en el mapa (¿o sí?). Las unidades están asociadas con "ejércitos", ya sea jugador o IA. Un ejército debería poder acceder fácilmente e iterar sobre todas sus unidades.

Dado que esto parece ser un problema común en los juegos de estrategia, ¿existen otros patrones además de los dos que describí para administrar las relaciones unidad / mapa?

tiles maps character AJM
fuente

Respuestas:

3

No es un patrón popular, pero el mundo de la base de datos relacional ofrece una tercera forma: usar una estructura de datos que tenga múltiples claves. En forma tabular, podría verse así:

Unit id    Location
-------------------
  1309     13,15
  2357      7,93
  8552      7,93

Quiere poder preguntar, "¿dónde está la unidad 2357?" y volver 7,93. También desea poder preguntar, "¿qué hay en la ubicación 7,93?" y regrese 2357 y 8552. Existen estructuras de datos que permiten múltiples claves para buscar cosas. Puede almacenar esto fuera de las unidades y fuera del mapa si desea eliminar dependencias.

Sin embargo, en la práctica es más común almacenar la ubicación en cada unidad, y luego usar una estructura de datos de partición espacial que le indica qué unidades hay en una región determinada. Como es una estructura separada, las regiones no tienen que ser espacios de cuadrícula; Pueden ser áreas más grandes.

Recomiendo hacer lo que sea más fácil (su segunda solución) y luego, si es un problema de rendimiento, puede agregar una partición espacial para agilizar las búsquedas.

amitp
fuente
Entonces, la estructura de datos de partición espacial que mencionas podría ser solo el mapa (que en mi caso es aparentemente una cuadrícula 2D de mosaicos). Supongo que cuando una unidad se mueve (o se agrega o se elimina), aún necesito actualizar tanto la unidad como la estructura de partición espacial para mantenerlas sincronizadas. ¿Quizás es una de esas cosas con las que tendré que vivir?
AJM
1
Sí, el mapa es la partición espacial de grano más fino que usarías. La lista global de todas las unidades es la partición de grano más grueso. ;) Solo necesita actualizar la partición antes de usarla. Si lo usa todo el tiempo, probablemente quiera actualizarlo cada vez que mueva la unidad. Sin embargo, si solo lo está utilizando para algunas fases de la lógica de actualización, puede revisar la lista de unidades de una sola vez y calcular la estructura de datos de la partición, luego descartarla cuando haya terminado. De esa manera no tienes que mantenerlos sincronizados todo el tiempo.
amitp
5

Bueno, a menos que tengas varios miles de unidades por jugador, no me preocuparía por el uso de memoria y usaría la primera solución. Parece que la memoria es más barata que la CPU.

De hecho, incluso si tuvieras 4000 unidades por jugador, usando dos enteros para almacenar su ubicación y 8 jugadores, eso solo toma 2 MB, pero con la primera solución, puedes usar un captador coordinado O (1), en lugar de O (n) (suponiendo no clasificado), que con muchas unidades podría ser lento.

La mayoría de los juegos parecen estar basados ​​en píxeles, en lugar de mosaicos, hoy en día, por lo que solo necesitan que la unidad almacene los códigos.

Ray Britton
fuente
No estoy preocupado por el uso de memoria, estoy más interesado en administrar dependencias (en el sentido del diseño orientado a objetos). No es la memoria extra que conlleva la primera solución lo que me preocupa, es la dependencia cíclica de la que desconfío, por mucho que me guste el captador de coordenadas O (1). Además, sé que muchos juegos están basados ​​en píxeles ahora, pero me gustan los mosaicos, así que eso es lo que estoy usando. : P
AJM
@AJM, lo mismo, las aplicaciones pagas que lanzaré en Android usarán mosaicos.
Ray Britton