Estoy escribiendo un juego de laberinto dinámico en el que después de cada cambio la estructura del laberinto cambiará (Algunas puertas se cerrarán y algunas puertas se abrirán. Algo así como Triwazard en HP4). ¿Alguien puede sugerirme qué estructura de datos será la más adecuada para representar esto?Estructura de datos para representar un laberinto
¿El laberinto será una cuadrícula rectangular? ¿Algo más?
También depende de cuánto del mapa contendrá información útil (pases u objetos).
Si es una cuadrícula rectangular y la mayoría de los cuadrados de cuadrícula contendrán ALGO, una buena estructura de datos es una matriz 2D (matriz de matrices), cada elemento de la matriz representa 1 fila, cada elemento de las matrices interiores representa 1 celda en esa fila, que es un objeto que contiene datos pertenecientes a esa celda (a qué celdas vecinas se puede mover, qué contiene la celda, hay un carácter en ella).
Sin embargo, si el laberinto no es un rectángulo O si la mayoría de las celdas de un gran laberinto no contienen ninguna utilidad (por ejemplo, bloques no transitables), una buena estructura de datos es un gráfico.
Cada vértice del gráfico es una celda que es aceptable. Los bordes representan los pares de celdas entre los que puede moverse (puede convertirlo en un gráfico dirigido si algunas puertas son unidireccionales). Cada vértice/celda es un objeto que contiene información en esa celda (por ejemplo, su ubicación en el laberinto físico que se dibujará, etc.).
La ventaja de la estructura del conjunto de matrices es que es MUY fácil de dibujar, y bastante sencillo de procesar (cualquier movimiento es solo en/de-cremento de un índice). Agregar/eliminar paredes es tan fácil como cambiar datos en 2 elementos de matriz de celdas vecinas.
El beneficio de la estructura gráfica es que ocupa mucho menos espacio si los laberintos son muy escasos (por ejemplo, solo se pasa 1/100 del campo); es la única estructura que puede representar una geometría aleatoria (por ejemplo, una cuadrícula no rectangular) y el procesamiento es bastante sencillo. Añadir/quitar paredes es fácil ya que solo agrega un borde a un gráfico.
1) ¿Qué estructuras de datos HA TENIDO en cuenta? 2) Nunca asumas que las personas conocen todas las pequeñas abreviaturas que haces. HP4 no es exactamente una abreviatura conocida mundialmente para el cuarto libro de la serie Harry Potter. – DVK