Módulo 3

TUS en Diseño de Videojuegos

Ayose Lomba Pérez (LinkedIn)

Módulo 4. Introducción a las Estructuras de Datos y Algoritmos

Programación I (24/25)

Ayose Lomba Pérez

Universidad del Atlántico Medio

Enlace principal  

📌 Programacion I

Tema 1: Estructuras de Datos

¿Qué son las estructuras de datos?

Las estructuras de datos son formas de organizar y almacenar datos para facilitar su uso y manipulación en la programación.

¿Para que sirven las estructuras en programación?

Las estructuras de datos juegan un papel fundamental en la programación, ya que permiten organizar, manipular y almacenar información de manera eficiente.

En el contexto de C# y Unity, su uso es clave para optimizar el rendimiento y facilitar la gestión de los elementos dentro de un videojuego.

Abordemos con más detalle

Las estructuras de datos son formas de organizar la información para que sea fácil de manipular. Se pueden imaginar como distintos tipos de cajas donde guardamos objetos de una manera ordenada, dependiendo de cómo queremos acceder a ellos más adelante.

Ejemplo cotidiano

  • Si tienes una pila de platos en casa, el último plato que colocas es el primero que tomas para usar. Esto es una estructura de tipo pila (Stack).
  • Si haces una fila en el supermercado, la persona que llegó primero es la primera en ser atendida. Esto es una cola (Queue).
  • Si tienes una lista de reproducción de música donde puedes añadir, quitar o reorganizar canciones, tienes algo parecido a una lista enlazada (Linked List).

Estas estructuras nos ayudan a optimizar los procesos dentro de un programa o videojuego, permitiendo que la información fluya de manera ordenada y eficiente.

Tipos de estructuras de datos

– Estructuras Lineales

  • Arrays
  • Listas enlazadas
  • Pilas (Stacks)
  • Colas (Queues)

– Estructuras No Lineales

  • Árboles
  • Grafos

Tema2. Estructuras Lineales

Arrays

¿Qué es un array?

Un array es una colección de elementos del mismo tipo almacenados en ubicaciones contiguas de memoria.

int[] numeros = {1, 2, 3, 4, 5};

Acceso a elementos en un array

int valor = numeros[2]; // Obtiene el tercer elemento (índice 2)

Listas enlazadas

¿Qué es una lista enlazada?

Una lista enlazada es una colección de elementos donde cada uno de ellos está conectado con el siguiente. Se diferencia de un array porque sus elementos no están almacenados en una memoria contigua.

Ejemplo cotidiano

Imagina que tienes una cadena de papel donde cada eslabón está unido al siguiente. Puedes quitar o agregar eslabones fácilmente sin necesidad de mover los demás.

Características de una lista enlazada:

  • Cada elemento se llama nodo.
  • Cada nodo contiene un valor y un enlace al siguiente nodo.
  • No es necesario un bloque contiguo de memoria, por lo que es más flexible que un array.

Implementación de una lista enlazada en C


class Nodo {
    public int dato;
    public Nodo siguiente;
    
    public Nodo(int valor) {
        dato = valor;
        siguiente = null;
    }
}

class ListaEnlazada {
    public Nodo cabeza;
    
    public void Agregar(int valor) {
        Nodo nuevo = new Nodo(valor);
        if (cabeza == null) {
            cabeza = nuevo;
        } else {
            Nodo actual = cabeza;
            while (actual.siguiente != null) {
                actual = actual.siguiente;
            }
            actual.siguiente = nuevo;
        }
    }
}

Aplicación en Unity: Sistema de Objetos Activos

En Unity, una lista enlazada puede utilizarse para manejar objetos que entran y salen de la escena de manera eficiente. Un ejemplo puede ser un sistema de objetos recolectables en un nivel.

using System.Collections.Generic;
using UnityEngine;

public class AdministradorObjetos : MonoBehaviour {
    private LinkedList<GameObject> objetosActivos = new LinkedList<GameObject>();

    public void AgregarObjeto(GameObject obj) {
        objetosActivos.AddLast(obj);
    }
    
    public void EliminarObjeto(GameObject obj) {
        objetosActivos.Remove(obj);
        Destroy(obj);
    }
}

Pilas (Stacks)

¿Qué es una pila?

Una pila es una estructura de datos que sigue el principio LIFO (Last In, First Out), lo que significa que el último elemento agregado es el primero en ser eliminado. Se puede imaginar como una pila de platos donde solo se puede agregar o retirar elementos desde la parte superior.

Operaciones principales:

  • Push: Agrega un elemento a la parte superior de la pila.
  • Pop: Elimina el elemento superior de la pila.
  • Peek: Devuelve el elemento superior sin eliminarlo.

Implementación de una pila en C

Stack<int> pila = new Stack<int>();
pila.Push(10);
pila.Push(20);
int valor = pila.Pop(); // Elimina y devuelve 20

Implementación de una pila manualmente:

class Pila {
    private List<int> elementos = new List<int>();
    
    public void Push(int valor) {
        elementos.Add(valor);
    }
    
    public int Pop() {
        if (elementos.Count == 0) throw new InvalidOperationException("La pila está vacía");
        int valor = elementos[elementos.Count - 1];
        elementos.RemoveAt(elementos.Count - 1);
        return valor;
    }
}

Aplicación en Unity: Historial de Acciones del Jugador

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class HistorialAcciones : MonoBehaviour {
    private Stack<string> acciones = new Stack<string>();

    public void RealizarAccion(string accion) {
        acciones.Push(accion);
        Debug.Log("Acción realizada: " + accion);
    }
    
    public void DeshacerAccion() {
        if (acciones.Count > 0) {
            string accionDeshecha = acciones.Pop();
            Debug.Log("Acción deshecha: " + accionDeshecha);
        }
    }
}

Colas (Queues)

¿Qué es una cola?

Una cola es una estructura de datos que sigue el principio FIFO (First In, First Out), lo que significa que el primer elemento en ingresar es el primero en salir. Se puede imaginar como una fila en una tienda donde el primer cliente en llegar es el primero en ser atendido.

Operaciones principales:

  • Enqueue: Agrega un elemento al final de la cola.
  • Dequeue: Elimina y devuelve el primer elemento de la cola.
  • Peek: Devuelve el primer elemento sin eliminarlo.

Implementación de una cola en C

Queue<int> cola = new Queue<int>();
cola.Enqueue(10);
cola.Enqueue(20);
int valor = cola.Dequeue(); // Elimina y devuelve 10

Implementación de una cola manualmente:

class Cola {
    private List<int> elementos = new List<int>();
    
    public void Enqueue(int valor) {
        elementos.Add(valor);
    }
    
    public int Dequeue() {
        if (elementos.Count == 0) throw new InvalidOperationException("La cola está vacía");
        int valor = elementos[0];
        elementos.RemoveAt(0);
        return valor;
    }
}

Aplicación en Unity: Manejo de Turnos en un RPG

using System.Collections.Generic;
using UnityEngine;

public class SistemaTurnos : MonoBehaviour {
    private Queue<string> colaTurnos = new Queue<string>();

    void Start() {
        colaTurnos.Enqueue("Jugador 1");
        colaTurnos.Enqueue("Enemigo 1");
        colaTurnos.Enqueue("Jugador 2");
    }

    public void SiguienteTurno() {
        if (colaTurnos.Count > 0) {
            string turnoActual = colaTurnos.Dequeue();
            Debug.Log("Es el turno de: " + turnoActual);
            colaTurnos.Enqueue(turnoActual); // Vuelve a agregar al final
        }
    }
}

Tema3. Estructuras No Lineales

Árboles

¿Qué es un árbol?

Un árbol es una estructura de datos jerárquica donde cada elemento, llamado nodo, tiene un valor y referencias a otros nodos, llamados hijos. El primer nodo del árbol se llama raíz.

Imagina un árbol genealógico donde cada persona puede tener varios hijos. Así funcionan los árboles en informática.

Características de los árboles:

  • Cada nodo puede tener múltiples hijos.
  • El primer nodo es la raíz.
  • Los nodos sin hijos se llaman hojas.
  • Se recorren de manera jerárquica.

Ejemplo en C#:

class NodoArbol {
    public int valor;
    public NodoArbol izquierda, derecha;

    public NodoArbol(int dato) {
        valor = dato;
        izquierda = derecha = null;
    }
}

Aplicación en Unity: Sistema de Diálogos

En Unity, los árboles pueden utilizarse para gestionar sistemas de diálogo donde una pregunta puede tener múltiples respuestas.

using UnityEngine;

public class NodoDialogo {
    public string texto;
    public NodoDialogo opcion1, opcion2;
    
    public NodoDialogo(string mensaje) {
        texto = mensaje;
    }
}

Grafos

¿Qué es un grafo?

Un grafo es una colección de nodos conectados mediante aristas. Se usa para modelar relaciones complejas, como mapas de juegos o redes de conexiones.

Características de los grafos:

  • Pueden ser dirigidos (con flechas indicando dirección) o no dirigidos.
  • Se representan con una lista de nodos y conexiones.

Ejemplo en C#:

using System.Collections.Generic;

class Grafo {
    public Dictionary<string, List<string>> nodos = new Dictionary<string, List<string>>();
}

Aplicación en Unity: Generación de Mapas

En Unity, los grafos pueden representar rutas en un mapa para la inteligencia artificial.

using System.Collections.Generic;
using UnityEngine;

public class NodoMapa {
    public string nombre;
    public List<NodoMapa> conexiones = new List<NodoMapa>();
}

Algoritmos básicos en estructuras de datos

Búsqueda en Arrays

int Buscar(int[] array, int valor) {
    for (int i = 0; i < array.Length; i++) {
        if (array[i] == valor) return i;
    }
    return -1;
}

Recorrido en Árboles

void Recorrer(NodoArbol nodo) {
    if (nodo == null) return;
    Recorrer(nodo.izquierda);
    Console.WriteLine(nodo.dato);
    Recorrer(nodo.derecha);
}

Conclusión

Las estructuras de datos como árboles y grafos permiten modelar escenarios complejos en videojuegos.

En Unity, ayudan a gestionar sistemas como diálogos, inteligencia artificial y navegación de personajes, mejorando el rendimiento y la organización del código en el desarrollo de videojuegos.