Descripción de las estructuras de datos desarrolladas - AdrianTEC/Proyecto-No1-Datos1 GitHub Wiki

Tipos de casilla

1 Las casillas del tablero se dividen en dos tipos: simples y dobles. La razón por la que se dividen de esta forma es para poder crear listas enlazadas o doblemente enlazadas, esto se hace mediante una indicación que se da donde se especifica que tipo de casillas son con las que estamos trabajando. 2. Las casillas simples son las que únicamente tienen un puntero viendo hacia el nodo que sigue, cuando se indica que una matriz de posiciones es simple el código crea una lista enlazada con los datos otorgados. 3. Las casillas dobles hacen referencia a los nodos que tienen dos punteros (puntero hacia la siguiente, puntero hacia la anterior), al indicarle al código que la matriz de posiciones otorgada es doble se inicia la creación de una lista doblemente enlazada. 4. Esta misma analogía se aplica si se van a crear listas circulares o listas circulares doblemente enlazadas.

Lista Enlazada

¿Que es una lista enlazada?

Una lista enlazada (en nuestro código) es un conjunto de casillas conectadas entre si que tienen un puntero que marca cual es la casilla que sigue para permitirle que un indicador (puede ser un jugador) avance por ella.

¿Porqué la implementamos?

Se usa una lista enlazada para hacer la fase A, un camino de una sola dirección que es un desvío del camino original.

¿Cómo la implementamos?

Para empezar, se crea una instancia de camino, dándole una matriz con las coordenadas de cada casilla y consecuente se crea una lista enlazada usando el método de camino (convertir la matriz en diferentes nodos y enviándolos a lista lineal para que los añada a la lista enlazada).

Se empieza añadiendo el primer nodo a la lista, esto se haría haciendo que el ultimo de la lista sea el nuevo nodo, luego se le añade un index (indicador de cual casilla es) y finalmente se le añade la propiedad que la primer posición de la lista enlazada va a ser la ultima (ya que en este momento es la única que hay)
Para seguir colocando el resto de los nodos ya hay una lista enlazada con un nodo, entonces simplemente hay que seguir añadiendo el resto hasta completar la matriz que se le dio a camino, esto hace marcando la siguiente posición de ultimo, y convirtiéndola en un nuevo elemento de la lista enlazada, finalmente se convierte al ultimo elemento añadido en el nuevo ultimo elemento para seguir añadiendo el resto de los nodos después de este.
Finalmente para implementar esta lista enlazada en la lista circular que es el camino principal lo que se hace es marcar la casilla que es el inicio de la faseA como la nueva anterior de la primer casilla de la lista enlazada (faseA) y para salir de este camino alterno se marca que el siguiente del ultimo elemento de la lista enlazada (faseA) es la casilla del camino principal donde esta choca.

Lista Doblemente Enlazada

¿Que es una lista doblemente enlazada?

Una lista doblemente enlazada es lo mismo que una lista enlazada normal pero con la característica que los nodos también apuntan hacia el anterior y esto le permite al puntero (puede ser un jugador) avanzar en ambas direcciones de la lista.

¿Porque la implementamos?

La fase C es un camino por el que se pueda ingresar por cualquier de los dos lados y se puede recorrer en cualquier dirección.

¿Como la implementamos?

Se le otorga una matriz de posiciones a la clase camino, pero esta vez se le indica con un Booleano que esta matriz son casillas dobles, haciendo que al entregar a la clase lista, esta sepa que no esta trabajando con casillas simples.
Una vez que se le entrega a la clase lista el conjunto de nodos (casillas dobles) la misma empieza a trabajar en construir la lista doblemente enlazada, como se menciono anteriormente la clase lista sabe que debe trabajar en construir una lista doblemente enlazada dado que los datos que esta recibiendo son casillas dobles.
Para crear la lista doblemente enlazada al inicio se añade el primer elemento y simplemente se le asigna la posición de primero y ultimo a dicho elemento añadido.
Para el resto de los elementos se repite un proceso, antes de añadir este elemento a la lista primero se le aplica la propiedad de que su anterior elemento es el actual ultimo elemento de la lista, de esta forma su puntero hacia el anterior ya va a estar conectado a la lista y finalmente se le coloca como el siguiente valor del ultimo y se le convierte a este en el ultimo. Se repite este proceso hasta haber terminado de convertir la matriz de posiciones en una lista doblemente enlazada de casillas dobles.

- Lista Circular

¿Porqué la implementamos?

El uso de la lista circular se hace cuando se crea el camino principal, tiene esta forma por el hecho que los jugadores necesitan poder avanzar por el camino sin detenerse, dado el juego es un tablero no se va a crear un camino sino que se va a avanzar dando vueltas por el mismo.

¿Que es una lista circular?

Una lista circular es muy parecida a una lista enlazada, pero la diferencia es que el ultimo elemento de esta lista esta señalando al primer elemento, esto permite que se pueda recorrer sin detenerse. La única limitación es que se puede recorrer en una única dirección.

¿Como la implementamos?

La creación de la lista circular se lleva a cabo de la siguiente forma:

Para empezar (Se crea una instancia de Camino)y se le inserta una matriz de posiciones en forma de array , se invoca al método de camino de conversión de matriz a lista para convertir las posiciones en nodos (según el tipo de casilla: simple o doble).
La lista circular al principio es una lista vacía, así que lo que se hace es añadir el primer nodo a la lista, siendo este el primero y el ultimo al mismo tiempo, teniendo un doble indicador de posición (index de primero = 0, index de ultimo = 1). Finalmente, el siguiente del ultimo seria el primero, otorgándole así la característica principal de las listas circulares.
Una vez la primer posición no es vacía nada más se deben seguir añadiendo los siguientes nodos, para conseguir esto se debe hacer que el siguiente de ultimo sea el nuevo nodo, entonces se hace que el nuevo nodo señale al primer nodo de la lista y finalmente se le asigna el valor de ultimo al nodo más reciente añadido.
Esto se aplicaría hasta que la matriz otorgada sea convertida en una lista circular y finalmente sea utilizada como el camino principal de nuestro tablero.

Lista Circular Doblemente enlazada

¿Que es una lista circular doblemente enlazada?

Es lo mismo que una lista doblemente enlazada, al igual que una lista circular simple, esta se diferencia por estar señalando a el primer elemento con el ultimo elemento. Esta lista no tiene la misma limitación que una lista circular simple, esta lista circular se puede recorrer en cualquier dirección.

¿Porque la implementamos?

La fase D es un camino circular, esto quiere decir que se necesita que el ultimo elemento señale al primero, pero se necesita que este camino sea posible recorrerlo en cualquier dirección, así que además de crearla circular se tiene que hacer doblemente enlazada.

¿Como la implementamos?

A diferencia de las otras fases, esta fase se encuentra completamente separada del camino principal, la única manera de llegar a este camino es mediante un evento que teletransporta a el jugador a este camino.

Se le da la matriz de posiciones a camino, nuevamente se le indica que las casillas son dobles.
Cuando se le entregan los nodos a lista esta se da cuenta que son casillas dobles, además también se le indica que debe ser una lista circular, así que finalmente crea una lista circular doblemente enlazada.
Así que se empieza añadiendo el primer elemento de la lista, siendo este el primer y ultimo elemento de la lista, además que al ser el ultimo este tiene que estar señalando al primero (ya que es circular) y también el primero tiene que tener de anterior al ultimo (ya que es circular doblemente enlazado), así que finalmente este primer elemento se señala a si mismo dos veces.
El siguiente paso se repite hasta haber convertido la matriz de posiciones completa en una lista circular doblemente enlazada. Lo que se hace es convertir el nuevo elemento en el siguiente del ultimo elemento, posteriormente se hace que el siguiente del nuevo elemento sea el primer elemento de la lista y luego se hace que el anterior elemento del nuevo sea el antiguo ultimo (de esta forma el nuevo elemento ya estaría "ensartado" en la lista, se hace que el primer elemento marque como anterior el nuevo elemento y finalmente se le da el valor de ultimo a este nuevo elemento.
Se agrega este camino al tablero.