Juego serpiente

He estado repasando temas relacionados con los gráficos en la plataforma .NET y para probar algunas cosas se me ha ocurrido programar un juego al que jugaba cuando empecé a meterme en el mundo de la informática. El juego en cuestión es el de la serpiente (yo lo conocí como Nibbles). La idea es bastante sencilla: se trata de mover por la pantalla un elemento gráfico simulando una serpiente que debe pasar por encima de ciertos puntos donde se encuentra su alimento preferido. Cada vez que un alimento es engullido la serpiente aumenta su tamaño y aparece otro alimento en la pantalla. La serpiente no puede salirse de la pantalla ni chocar consigo misma.
Yo he utilizado C# para programarlo, aunque es muy parecido en Visual Basic o Visual C++. A continuación os muestro el código y también un par de imágenes de su ejecución.

using System;
using System.Timers;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Drawing;

namespace nibblesCS01
{
    public partial class fNibbles : Form
    {
        List<Punto> path;
        private const int DESPLAZAMIENTO = 5;
        private const int ANCHO_SERPIENTE = 6;
        private const int ANCHO_INICIAL = 180;
        private const int INCREMENTO_ANCHO = 20;
        private const int ALIMENTOS_NECESARIOS = 12;
        private int INTERVALO_TEMPORIZADOR = 100;

        private List<Alimento> alimentos;
        int alimentosComidos;

        public fNibbles()
        {
            InitializeComponent();
        }

        protected override bool ProcessCmdKey(ref Message msg, Keys keyData)
        {
            const int WM_KEYDOWN = 0x100;
            const int WM_SYSKEYDOWN = 0x104;
            Punto pto = new Punto();

            if ((msg.Msg == WM_KEYDOWN) || (msg.Msg == WM_SYSKEYDOWN))
            {
                switch (keyData)
                {
                    case Keys.Right:
                        if (path[path.Count - 1].d != 0)
                        {
                            pto.d = 0;
                            pto.x = path[path.Count - 1].x;
                            pto.y = path[path.Count - 1].y;
                            path[path.Count - 1].d = 0;
                            path.Add(pto);
                        }
                        break;
                    case Keys.Left:
                        if (path[path.Count - 1].d != 1)
                        {
                            pto.d = 1;
                            pto.x = path[path.Count - 1].x;
                            pto.y = path[path.Count - 1].y;
                            path[path.Count - 1].d = 1;
                            path.Add(pto);
                        }
                        break;
                    case Keys.Up:
                        if (path[path.Count - 1].d != 2)
                        {
                            pto.d = 2;
                            pto.x = path[path.Count - 1].x;
                            pto.y = path[path.Count - 1].y;
                            path[path.Count - 1].d = 2;
                            path.Add(pto);
                        }
                        break;
                    case Keys.Down:
                        if (path[path.Count - 1].d != 3)
                        {
                            pto.d = 3;
                            pto.x = path[path.Count - 1].x;
                            pto.y = path[path.Count - 1].y;
                            path[path.Count - 1].d = 3;
                            path.Add(pto);
                        }
                        break;

                    //Datos depuración
                    //case Keys.Enter:
                    //    for (int i = 0; i < path.Count; i++)
                    //    {
                    //        lbl.Text += "(" + path[i].x + "," + path[i].y + "," + path[i].d +") ";
                    //    }
                    //    lbl.Text += " -- ";
                    //    break;

                    //Opción pausar el juego
                    case Keys.P:
                        tTemp.Enabled = !tTemp.Enabled;
                        break;
                }
            }

            return base.ProcessCmdKey(ref msg, keyData);
        }

        private void fNibbles_Load(object sender, EventArgs e)
        {
            int xAlimento, yAlimento;

            alimentosComidos = 0;

            alimentos = new List<Alimento>();
            //Inicializar la serpiente
            path = new List<Punto>();
            Punto pto = new Punto(0, 200, 0);
            path.Add(pto);
            pto = new Punto(ANCHO_INICIAL, 200, 0);
            path.Add(pto);

            Random r = new Random(DateTime.Now.Millisecond);
            xAlimento = r.Next((this.Width - 5) / DESPLAZAMIENTO) * DESPLAZAMIENTO;
            yAlimento = r.Next((this.Height - 30) / DESPLAZAMIENTO) * DESPLAZAMIENTO;
            Alimento ptoAlimento = new Alimento(xAlimento, yAlimento, Color.Blue);
            alimentos.Add(ptoAlimento);

            lblAlimentosRestantes.Text = ALIMENTOS_NECESARIOS.ToString();

            //Datos depuración
            //lbl.Text = "[" + ptoAlimento.x + "," + ptoAlimento.y + "] ";

            //Inicializar el temporizador
            tTemp.Tick += new System.EventHandler(OnTimerEvent);
            tTemp.Interval = INTERVALO_TEMPORIZADOR;
            tTemp.Enabled = true;
        }

        //Calcula la longitud de la serpiente en función de los puntos que componen su silueta actual
        private int longitudSerpiente()
        {
            int longitud;

            longitud = 0;
            for (int i = 1; i < path.Count; i++)
            {
                if (path[i - 1].x == path[i].x)
                {
                    longitud += Math.Abs(path[i].y - path[i - 1].y);
                }
                else
                {
                    longitud += Math.Abs(path[i].x - path[i-1].x);
                }
            }
            return longitud;
        }

        //Muestra un punto en la pantalla por cada objeto de tipo alimento guardado en la lista
        //de alimentos
        public void MostrarAlimentos()
        {
            Graphics g = this.CreateGraphics();

            foreach (Alimento al in alimentos)
            {
                g.FillEllipse(Brushes.Blue, al.x - 4, al.y - 4, 8, 8);
            }
        }

        //Manejador del evento correspondiente al vencimiento del temporizador
        //Desplaza la serpiente una posición y la redibuja
        public void OnTimerEvent(object source, EventArgs e)
        {
            //Desplazar la serpiente una posición
            if (DesplazarSerpiente())
            {
                //Limpiar la pantalla y redibujar la serpiente
                MostrarSerpiente();
                MostrarAlimentos();
            }
        }

        //Dependiendo de la dirección del último punto añadido a la ruta, modificar el
        //valor de dicho punto. El primer punto de la ruta debe chequearse para ver si
        //coincide con el valor del segundo, y si es así, eliminar el primero de la ruta
        private bool DesplazarSerpiente()
        {
            Punto pto0 = new Punto();
            Punto pto1 = new Punto();
            Punto ultimoPto = new Punto();
            bool noDesplazarCola;
            int xAlimento, yAlimento;

            pto0 = path[0];
            pto1 = path[1];
            ultimoPto = path[path.Count - 1];
            noDesplazarCola = false;

            //Desplazamos la cabeza de la serpiente en la dirección que corresponda
            switch (ultimoPto.d)
            {
                case 0:  //dcha
                    ultimoPto.x += DESPLAZAMIENTO;
                    break;
                case 1:  //izda
                    ultimoPto.x -= DESPLAZAMIENTO;
                    break;
                case 2:  //arriba
                    ultimoPto.y -= DESPLAZAMIENTO;
                    break;
                case 3:  //abajo
                    ultimoPto.y += DESPLAZAMIENTO;
                    break;
            }
            //Comprobamos si la serpiente se sale de los márgenes o se muerde a sí misma
            if (path[path.Count - 1].x > this.Width - 5 || path[path.Count - 1].y > this.Height - 55 || path[path.Count - 1].x < 0 || path[path.Count - 1].y < 0 ||
                SerpienteSeMuerde())
            {
                tTemp.Enabled = false;
                //this.Refresh();
                MostrarMensaje("GAME OVER!!!", 240, 150, Brushes.DarkRed);
                //MessageBox.Show("GAME OVER");
                return false;
            }

            //Comprobamos si la serpiente se come un alimento
            if (alimentos.Count > 0)
            {
                if (path[path.Count - 1].x == alimentos[0].x && path[path.Count - 1].y == alimentos[0].y)
                {
                    //Come un alimento
                    alimentosComidos++;
                    //Actualizamos el contador de alimentos restantes
                    lblAlimentosRestantes.Text = (ALIMENTOS_NECESARIOS - alimentosComidos).ToString();

                    if (alimentosComidos == ALIMENTOS_NECESARIOS)
                    {
                        tTemp.Enabled = false;
                        MostrarMensaje("CONGRATULATIONS! YOU PASSED THIS LEVEL.", 100, 150, Brushes.DarkGreen);
                        return false;
                    }
                    else
                    {
                        alimentos.RemoveAt(0);
                        noDesplazarCola = true;
                        //Colocamos otro alimento en la pantalla
                        Random r = new Random(DateTime.Now.Millisecond);
                        xAlimento = r.Next((this.Width - 5) / DESPLAZAMIENTO) * DESPLAZAMIENTO;
                        yAlimento = r.Next((this.Height - 55) / DESPLAZAMIENTO) * DESPLAZAMIENTO;
                        Alimento ptoAlimento = new Alimento(xAlimento, yAlimento, Color.Blue);
                        alimentos.Add(ptoAlimento);

                        //Datos depuración
                        //lbl.Text += "*" + path[0].x + "," + path[0].y + "* ";
                        //lbl.Text = "[" + ptoAlimento.x + "," + ptoAlimento.y + "] ";

                    }
                }
            }

            if (noDesplazarCola == false)
            {
                //Desplazamos la cola de la serpiente en la dirección que indica el último punto
                switch (pto0.d)
                {
                    case 0:  //derecha
                        if ((pto0.x + DESPLAZAMIENTO == pto1.x) && (pto0.y == pto1.y))
                        {
                            path.RemoveAt(0);
                        }
                        else
                        {
                            path[0].x += DESPLAZAMIENTO;
                        }
                        break;

                    case 1:  //izda
                        if ((pto0.x - DESPLAZAMIENTO == pto1.x) && (pto0.y == pto1.y))
                        {
                            path.RemoveAt(0);
                        }
                        else
                        {
                            path[0].x -= DESPLAZAMIENTO;
                        }
                        break;

                    case 2:  //arriba
                        if ((pto0.y - DESPLAZAMIENTO == pto1.y) && (pto0.x == pto1.x))
                        {
                            path.RemoveAt(0);
                        }
                        else
                        {
                            path[0].y -= DESPLAZAMIENTO;
                        }
                        break;

                    case 3:  //abajo
                        if ((pto0.y + DESPLAZAMIENTO == pto1.y) && (pto0.x == pto1.x))
                        {
                            path.RemoveAt(0);
                        }
                        else
                        {
                            path[0].y += DESPLAZAMIENTO;
                        }
                        break;
                }
            }
            return true;
        }

        //Comprobamos si la cabeza de la serpiente se cruza con el resto del cuerpo en algún punto
        public bool SerpienteSeMuerde()
        {
            for (int i = 0; i < path.Count - 2; i++)
            {
                if (((path[i].x == path[path.Count - 1].x) && (path[path.Count - 1].y >= path[i].y) && (path[path.Count - 1].y <= path[i+1].y))||
                    ((path[i].x == path[path.Count - 1].x) && (path[path.Count - 1].y <= path[i].y) && (path[path.Count - 1].y >= path[i + 1].y)))
                {
                    return true;
                }
                if (((path[i].y == path[path.Count - 1].y) && (path[path.Count - 1].x >= path[i].x) && (path[path.Count - 1].x <= path[i+1].x)) ||
                    ((path[i].y == path[path.Count - 1].y) && (path[path.Count - 1].x <= path[i].x) && (path[path.Count - 1].x >= path[i + 1].x)))
                {
                    return true;
                }
                if ((path[path.Count - 1].x == path[i].x) && (path[path.Count - 1].y == path[i].y))
                    return true;
            }
            return false;
        }

        //Dibujar líneas punto a punto entre cada dos puntos contiguos almacenados en
        //la ruta
        public void MostrarSerpiente()
        {
            Graphics g = this.CreateGraphics();
            Pen p = new Pen(Brushes.BurlyWood, ANCHO_SERPIENTE);

            this.Refresh();
            if (path.Count > 1)
            {
                for (int i = 1; i < path.Count; i++)
                {
                    g.DrawLine(p, path[i - 1].x, path[i - 1].y, path[i].x, path[i].y);
                }
            }

            //Datos para depuración
            //lbl1.Text = "Xn=" + path[path.Count - 1].x;
            //lbl2.Text = "Yn=" + path[path.Count - 1].y;
            //lbl3.Text = "Xn_1=" + path[path.Count - 2].x;
            //lbl4.Text = "Yn_1=" + path[path.Count - 2].y;
            //lblLong.Text = longitudSerpiente().ToString();

        }

        private void fNibbles_KeyDown(object sender, KeyEventArgs e)
        {
            //SE PODRÍA UTILIZAR ESTE EVENTO EN LUGAR DE SOBREESCRIBIR EL MÉTODO ProcessCmdKey DEL
            //FORMULARIO. AQUÍ NO SE UTILIZA ESTA OPCIÓN.

        //    //Comprobamos si se trata de una flecha
        //    if ((e.KeyCode == Keys.Up) || (e.KeyCode == Keys.Down) ||
        //        (e.KeyCode == Keys.Left) || (e.KeyCode == Keys.Right))
        //    {
        //        if (e.KeyCode == Keys.Right)
        //            path[path.Count - 1].d = 0;
        //        if (e.KeyCode == Keys.Left)
        //            path[path.Count - 1].d = 1;
        //        if (e.KeyCode == Keys.Up)
        //            path[path.Count - 1].d = 2;
        //        if (e.KeyCode == Keys.Down)
        //            path[path.Count - 1].d = 3;

        //    }

        }

        private void MostrarMensaje(String mensaje, int x, int y, Brush b)
        {
            Graphics g = this.CreateGraphics();
            Font f = new Font("Arial", 14, FontStyle.Bold);

            this.Refresh();
            g.DrawString(mensaje, f, b , x, y);
        }
    }

 
    //Clase que ayuda a definir la longitud y forma de la serpiente para
    //su impresión en la pantalla

    class Punto
    {
        public int x;
        public int y;
        public int d;  //0(dcha), 1(arriba), 2(abajo), 3(izda)

        public Punto() { }
        public Punto(int _x, int _y, int _d)
        {
            x = _x;
            y = _y;
            d = _d;
        }
    }


    //Esta clase define los alimentos que la serpiente debe ir "comiendo"
    //para avanzar en el juego. En esta versión la propiedad c(color) no
    //se utiliza.

    class Alimento
    {
        public int x;
        public int y;
        public Color c;

        public Alimento() { }
        public Alimento(int _x, int _y, Color _c)
        {
            x = _x;
            y = _y;
            c = _c;
        }
    }

}

Plantillas en C++

En esta ocasión voy a mostrar un par de ejemplos de uso de plantillas en C++. Las plantillas son el modo de crear clases genéricas en C++ y, como vais a ver, pueden resultar muy útiles. Yo he estado viendo unos vídeos de una asignatura de la universidad de Stanford en la que trabajan con C++. En esta asignatura tienen una librería de funciones para facilitar a los alumnos el desarrollo de los algoritmos que plantean durante el curso. En los vídeos muestran la definición de varias plantillas pero no su implementación, así que decidí implementar algunos de ellos. En primer lugar creé la plantilla de la clase genérica Vector que se puede ver a continuación.

#include <iostream>
#include <vector>

using namespace std;

//DEFINICIÓN DE LA PLANTILLA VECTOR (le llamo Vecto para no confundir con la
//clase vector de STL)
template <typename ElemType>
class Vecto{
  protected:
    vector<ElemType> v;

  public:
    //Vecto() {}
    Vecto(vector<ElemType> vect) {
        v.assign(vect.begin(),vect.end());
    }
    ~Vecto() {
        v.erase(v.begin(),v.end());
    }

    int size() {
        return v.size();
    }

    bool isEmpty() {
        if (size()>0) return false;
        else return true;
    }

    ElemType getAt(int index) {
        return v.at(index);
    }

    void setAt(int pos, ElemType value) {
        v.insert(pos, value);
    }

    void add(ElemType value) {
        v.push_back(value);
    }

    void insertAt(int pos, ElemType value) {
        setAt(pos, value);
    }

    void removeAt(int pos) {
        v.erase(pos);
    }
};

//EJEMPLO DE USO DE LA PLANTILLA VECTOR

int main()
{
    vector<int> vect;

    for (int i=0; i<10; i++) {
        vect.push_back(i);
    }
    for (int i=0; i<10; i++) {
        cout << "vect[" << i << "]= " << vect.at(i) << endl;
    }

    Vecto<int> v(vect);

    cout << "size: " << v.size() << endl << endl;
    for (int i=0; i<v.size(); i++) {
        cout << "vector[" << i << "]= " << v.getAt(i) << endl;
    }
    return 0;
}

En segundo lugar, os muestro la plantilla definida para definir tablas de valores. En este caso la clase se llama Grid y permite crear una tabla de datos del tipo de datos que el programador decida en el momento de declarar el objeto.

#include <iostream>
#include <vector>

using namespace std;

//DEFINICIÓN DE LA PLANTILLA GRID
template <typename ElemType>
class Grid {
  public:
    Grid() {
        rows=0;
        cols=0;
    }
    Grid(int numRows, int numCols): tabla(numRows){
        rows=numRows;
        cols=numCols;
        for (int i=0; i<numRows; ++i) {
            tabla[i].resize(numCols);
        }
    }
    ~Grid(){}

    const vector<ElemType> & operator[](int r) const {return tabla[r];}
    vector<ElemType> & operator[](int r) {return tabla[r];}

    int numRows() {return rows;}
    int numCols() {return cols;}


    ElemType getAt(int row, int col){
        return tabla[row][col];
    }
    void setAt(int row, int col, ElemType value) {
        tabla[row][col] = value;
    }

    void resize(int numRows, int numCols) {
        rows = numRows;
        cols = numCols;
        tabla.resize(rows);
        for (int i=0; i<numRows; ++i) {
            tabla[i].resize(numCols);
        }
    }
  protected:
    vector<vector<ElemType> > tabla;
    int rows, cols;
};


//EJEMPLO DE USO DE LA PLANTILLA GRID

int main()
{
    Grid<int> A(3,3);

    A[0][0] = 1;
    A[1][1] = 1;
    A[2][1] = 3;

    for (int i=0; i<3; i++) {
        for (int j=0; j<3; j++) {
            cout << A.getAt(i,j) << "  ";
        }
        cout << endl;
    }

    cout << endl << endl;
    A.resize(4,4);
    cout << "Columnas: " << A.numCols() << "    Filas: " << A.numRows() << endl << endl;

    for (int i=0; i<4; i++) {
        for (int j=0; j<4; j++) {
            cout << A.getAt(i,j) << "  ";
        }
        cout << endl;
    }

    return 0;
}

Hay que indicar que pese a que yo he utilizado el tipo int en los ejemplos, es posible utilizar otro tipo de dato u objeto definido previamente.

Gestión de libros

Hemos tenido que realizar una aplicación para poner a prueba nuestros conocimientos en lenguaje C en el curso. Esta aplicación tiene una extensión bastante mayor que las realizadas hasta la fecha y, aunque su complejidad no es mayor, puso a prueba nuestra capacidad para organizar el código utilizando funciones y comentándolo adecuadamente. Algunas veces resulta incómodo comentar el código y podemos volvernos perezosos con respecto a ello en cuanto el programa realiza las tareas requeridas. Por esto, es recomendable ir comentando el código según se va escribiendo. Asimismo, resulta tremendamente importante identar las líneas para que la lectura del código no se convierta en una tarea infernal o incluso imposible.

En este enlace a Codepad podéis ver el código que yo he realizado en esta ocasión:
http://codepad.org/EgtlUxrc

En la siguiente imagen se puede ver el menú del programa y un listado de los libros almacenados.

Ordenación (método MergeSort)

Profundizando un poco más en el tema de los algoritmos de ordenación y después de ver unos videos disponibles en la página web del MIT  he programado el algoritmo MergeSort utilizando listas enlazadas con punteros. Este algoritmo se comporta mucho mejor que el de selección cuando el número de elementos a ordenar crece. La idea que aplica este algoritmo es la de "divide y vencerás" y lo hace de modo recursivo.

struct tipo_dato {
    int num;
    struct tipo_dato *sig;
};



struct tipo_dato *mergeSort(struct tipo_dato *lista) {
    struct tipo_dato *lista1=NULL, *lista2=NULL, *listaOrd1=NULL, *listaOrd2=NULL, *listaOrd=NULL;


    if (longitud_lista(lista) <= 1) {
        return lista;
    }
    else {
        //Este es el puntero a la primera mitad de la lista.
        lista1 = lista;
        //Obtenemos la segunda parte de la lista (la segunda mitad).
        lista2 = obtener_lista2(lista);
        //Ordenamos recursivamente cada mitad del algoritmo
        listaOrd1 = mergeSort(lista1);
        listaOrd2 = mergeSort(lista2);

        //Mezclamos las dos mitades ordenadas previamente
        listaOrd = mezclar(listaOrd1, listaOrd2);

        return listaOrd;
    }
}

Para ver el código de un ejemplo de uso del algoritmo y los resultados de la ejecución podéis visitar este enlace en Codepad:
http://codepad.org/B3EOCoi8

Ordenación (método de selección)

Hemos estado hablando sobre los algoritmos de ordenación en clase y tuvimos que implementar el algoritmo de ordenación por selección para poder mostrar unos listados de datos ordenados en una aplicación que estamos realizando. A continuación muestro el código correspondiente a la función que realiza la tarea de la ordenación y la definición de la estructura de datos que representa los nodos de la lista enlazada.

struct tipo_lista_libro {
    char titulo[20];
    char autor[25];
    float precio;
    struct tipo_lista_libro *sig;
};

struct tipo_lista_libro *ordenar_lista_libros_seleccion(struct tipo_lista_libro *lista) {
    struct tipo_lista_libro *lista_aux = NULL, *lista_aux2 = NULL;
    struct tipo_lista_libro libro;

    lista_aux = lista;
    if (lista != NULL) {
        while (lista_aux->sig != NULL) {
            lista_aux2 = lista_aux->sig;
            while (lista_aux2 != NULL) {
                if (strcmp(lista_aux->titulo, lista_aux2->titulo)>0) {
                    //Copiamos el contenido de lista_aux a una variable temporal
                    strcpy(libro.titulo, lista_aux->titulo);
                    strcpy(libro.autor, lista_aux->autor);
                    libro.precio = lista_aux->precio;
                    //Copiamos el contenido de lista_aux2 a lista_aux
                    strcpy(lista_aux->titulo, lista_aux2->titulo);
                    strcpy(lista_aux->autor, lista_aux2->autor);
                    lista_aux->precio = lista_aux2->precio;
                    //Copiamos en lista_aux2 el contenido de la variable auxiliar
                    strcpy(lista_aux2->titulo, libro.titulo);
                    strcpy(lista_aux2->autor, libro.autor);
                    lista_aux2->precio = libro.precio;
                }
                lista_aux2 = lista_aux2->sig;
            }
            lista_aux = lista_aux->sig;
        }
    }
    return lista;
}

Para ver el resultado de una prueba de la ejecución de este programa visita el siguiente enlace:
http://codepad.org/qkNxYv08 en Codepad. Allí podéis ver el código completo y los resultados de la ejecución.