Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: dvigon en 19 Diciembre 2013, 01:21 am



Título: AYUDA Función Recursiva
Publicado por: dvigon en 19 Diciembre 2013, 01:21 am
Hola! Bueno, me temo que no tengo más remedio que pedir ayuda en un problema.
Me han pedido que haga una función que resuelva el juego con el máximo de puntos.
Se trata de una versión del juego "snake", la única diferencia es que por donde ha pasado el jugador, no podemos volver a pasar, Adjunto el código.

La función trata de añadir una opción al menú del juego (pulsando ‘r’, por ejemplo) para resolver el panel, esto es, que el programa calcule, dada la situación actual, la secuencia de movimientos del gusano que termine el juego con el
mayor número de puntos posible. :huh: :huh: :huh:


Código:
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>

#define N 10
#define GALLETA '.'
#define JUGADOR 2
#define OBSTACULO '*'
#define OCUPADO '-'

// Solicita el nivel de dificultad de juego
int Solicitar_Dificultad( ){

    int Dificultad;

    system("cls");

    do{
        printf("Introducir nivel (1-3): ");
        scanf("%d", &Dificultad);
        getchar( );
    }while( Dificultad < 1 || Dificultad > 3 );

    return Dificultad;
}

// Rellena la matriz y posiciona los obstaculos y al jugador
void Inicializar_Juego( char Matriz[N][N], int *Filas, int *Columnas, int *Puntos, int Dificultad ){

    int Obstaculos, i, j;

    *Puntos = 0;
    Obstaculos = Dificultad * N;

    // Se rellen la Matriz con galletas
    for( i = 0; i < N; i++ )
        for( j = 0; j < N; j++ )
            Matriz[i][j] = GALLETA;

    // Se introducen obstaculos
    while( Obstaculos > 0 ){
        i = rand() % N;
        j = rand() % N;
        if( Matriz[i][j] == GALLETA ){
            Matriz[i][j] = OBSTACULO;
            Obstaculos --;
        }
    }

    // Busca una posicion aleatoria para el jugador
    do{
        i = rand() % N;
        j = rand() % N;
    }while( Matriz[i][j] != GALLETA );

    Matriz[i][j] = JUGADOR;
    *Filas = i;
    *Columnas = j;
}

// Esta funcion se encarga de imprimir la matriz
void Imprimir( char Matriz[N][N], int *Puntos ){

    system("cls");

    for( int i = 0; i < N; i++ ){
        for( int j = 0; j < N; j++ )
            printf("%2c", Matriz[i][j]);
        printf("\n");
    }

    printf("\n\nPuntuacion actual: %d\n\nCONTROLES:\n  - Cursores para mover al jugador\ni - Iniciar de nuevo el panel\ns - Salir del programa", *Puntos);
}

// Devuelve 1 si el juego finaliza
int Comprobar_Fin( char Matriz[N][N], int *Filas, int *Columnas ){

    int Fin = 1;

    for( int i = 0; i < N; i++)
        for( int j = 0; j < N; j++)
            if( Matriz[i][j] == JUGADOR )
                Fin = 0;

    // Si se atrapa con 4 obstaculos
    if( ( Matriz[(*Filas) + 1][*Columnas] != GALLETA ) && ( Matriz[(*Filas) - 1][*Columnas] != GALLETA ) &&
        ( Matriz[(*Filas)][(*Columnas) + 1] != GALLETA ) && ( Matriz[(*Filas)][(*Columnas) - 1] != GALLETA ) ){
        Fin = 1;

    }else{

        // Si se atrapa con la pared de la izquierda
        if( *Columnas == 0 &&
            ( Matriz[(*Filas) + 1][*Columnas] != GALLETA ) && ( Matriz[(*Filas) - 1][*Columnas] != GALLETA ) &&
            ( Matriz[(*Filas)][(*Columnas) + 1] != GALLETA ) ){
            Fin = 1;

        }else{

            // Si se atrapa con la pared de la derecha
            if( *Columnas == N - 1 &&
                ( Matriz[(*Filas) + 1][*Columnas] != GALLETA ) && ( Matriz[(*Filas) - 1][*Columnas] != GALLETA ) &&
                ( Matriz[(*Filas)][(*Columnas) - 1] != GALLETA ) ){
                Fin = 1;

            }
        }
    }

    return Fin;
}

// Mueve el jugador en la matriz
void Mover_Jugador( char Matriz[N][N], char Tecla, int *Filas, int *Columnas, int *Puntos ){

    int F, C, Posicion[N][N];

    for( int i = 0; i < N; i++ )
        for( int j = 0; j < N; j++ )
            Posicion[i][j] = Matriz[i][j];

    F = *Filas;
    C = *Columnas;

    switch( Tecla ){

        case 72: // Movimiento hacia arriba
            if( *Filas > 0 && Matriz[*Filas - 1][*Columnas] != OBSTACULO ){
                ( *Filas )--;
                ( *Puntos ) ++;
                Posicion[F + 1][*Columnas];
            }
            break;

        case 80: // Movimiento hacia abajo
            if( *Filas < N - 1 && Matriz[*Filas + 1][*Columnas] != OBSTACULO ){
                ( *Filas )++;
                ( *Puntos ) ++;
                Posicion[F - 1][*Columnas];
            }
            break;

        case 75: // Movimiento hacia la derecha
            if( *Columnas > 0 && Matriz[*Filas][*Columnas - 1] != OBSTACULO ){
                ( *Columnas )--;
                ( *Puntos ) ++;
                Posicion[F][C + 1];
            }
            break;

        case 77: // Movimiento hacia la izquierda
            if( *Columnas < N - 1 && Matriz[*Filas][*Columnas + 1] != OBSTACULO ){
                ( *Columnas )++;
                ( *Puntos ) ++;
                Posicion[F][C - 1];
            }
            break;

        }

    // donde antes estaba el jugador ahora esta ocupado
    if( Matriz[F][C] != Posicion[*Filas][*Columnas] )
        Matriz[F][C] = OCUPADO;

    if( Matriz[*Filas][*Columnas] == OCUPADO )
            Matriz[*Filas][*Columnas] = 'X'; // JUGADOR se come a si mismo
    else
        Matriz[*Filas][*Columnas] = JUGADOR; // JUGADOR se mueve de posicion

}

// Inicializa el juego llamando a las anteriores funciones
void Ejecutar_Juego( ){

    char Matriz[N][N], Tecla;
    int Filas, Columnas, Puntos, Nivel;

    srand( time(NULL) );

    Nivel = Solicitar_Dificultad( );
    Inicializar_Juego( Matriz, &Filas, &Columnas, &Puntos, Nivel );
    Imprimir( Matriz, &Puntos );

    do{

        Tecla = getch( );

        if( Tecla == -32 || Tecla == 0 ) // Mueve el jugador
            Tecla = getch( );
        else
            if( Tecla >= 'a' && Tecla <= 'z' ) // Convierte el caracter Tecla a mayuscula
                Tecla -= 32;

        if( Tecla == 'I' )
            Inicializar_Juego( Matriz, &Filas, &Columnas, &Puntos, Nivel );

        Mover_Jugador( Matriz, Tecla, &Filas, &Columnas, &Puntos );
        Imprimir( Matriz, &Puntos );

    }while( Comprobar_Fin( Matriz, &Filas, &Columnas ) == 0 && Tecla != 'S' );

    printf("\n\nTermina el juego con %d puntos\n\n", Puntos);
    system("pause");

}

// Funcion principal
int main( ){

    Ejecutar_Juego( );

    return 0;
}


Gracias por las molestias.


Título: Re: Función Recursiva
Publicado por: Almapa en 19 Diciembre 2013, 10:27 am
Pfff, esto no va a ser nada fácil... Lo primero que se me ha ocurrido es en hacer como un "radar" de la serpiente para identificar obstáculos en 2 o 3 celdas de radio con el fin de que, mediante la correspondiente función, sea capaz de decidir ella sola el recorrido. Pero creo que sin la previa anticipación puede que se quede atrapada sin posibilidad a rectificar.

Un saludo!


Título: Re: Función Recursiva
Publicado por: Almapa en 19 Diciembre 2013, 10:34 am
También podrías hacer una función que iterara con todas las posibilidades y caminos posibles y eligiera la mejor, pero eso es muy cómodo y puede que el tiempo de cálculo sea elevado


Título: Re: Función Recursiva
Publicado por: dvigon en 19 Diciembre 2013, 20:54 pm
Da igual el tiempo mientras se resuelva el problema... la putada es que yo y la recursividad no nos entendemos... ¿Alguna sugerencia?


Título: Re: AYUDA Función Recursiva
Publicado por: amchacon en 19 Diciembre 2013, 23:06 pm
Lo que tú buscas es el algoritmo de Dijkstra.

Tengo una adaptación de Dijkstra (no es el original) en C++, te lo dejo aquí:

Distancia más corta desde un punto A a un punto B evitando obstaculos
Código
  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4.  
  5. using namespace std;
  6.  
  7. class Celda
  8. {
  9.    int x;
  10.    int y;
  11. public:
  12.    int getx()
  13.    {
  14.        return x;
  15.    }
  16.    int gety()
  17.    {
  18.        return y;
  19.    }
  20.    void setx(int x)
  21.    {
  22.        this->x=x;
  23.    }
  24.    void sety(int y)
  25.    {
  26.        this->y=y;
  27.    }
  28.  
  29.    bool operator==(Celda o)
  30.    {
  31.        return x==o.x && y==o.y;
  32.    }
  33.    Celda operator=(Celda o)
  34.    {
  35.        x=o.x;
  36.        y=o.y;
  37.        return *this;
  38.    }
  39.  
  40.    Celda(int x,int y):x(x),y(y) {}
  41.    Celda():x(0),y(0) {}
  42. };
  43. vector<Celda> ObtenerCaminoMasCorto(Celda ori,Celda dest, char array[8][8], int Ancho, int Altura);
  44.  
  45. int main()
  46. {
  47.    char ejemplo[8][8]=
  48.    {
  49.        {0,1,0,1,0,0,0,0}, //0: vacío
  50.        {0,1,0,1,0,0,0,0}, //1: pared
  51.        {0,1,0,1,0,0,0,0},
  52.        {0,1,0,1,0,0,0,0},
  53.        {0,1,0,1,0,0,0,0},
  54.        {0,1,0,1,0,0,0,0},
  55.        {0,0,0,1,0,0,0,0},
  56.        {0,0,0,0,0,0,0,0}
  57.    };
  58.  
  59.    vector<Celda> camino= ObtenerCaminoMasCorto(Celda(0,0),Celda(7,0),ejemplo,8,8);
  60.    for(int i=0; i<camino.size(); i++)
  61.    {
  62.        cout<<"("<<camino[i].getx()<<", "<<camino[i].gety()<<")"<<endl;
  63.    }
  64.  
  65. }
  66.  
  67. vector<Celda> ObtenerCaminoMasCorto(Celda ori,Celda dest, char array[8][8], int Ancho, int Altura)
  68. {
  69.  
  70.    if(ori==dest) return vector<Celda>();
  71.  
  72.    unsigned int *Distancias=new unsigned int[Ancho*Altura];
  73.  
  74.    Celda *anterior=new Celda[Ancho*Altura];
  75.  
  76.    for(int i=0; i<Ancho*Altura; i++)
  77.    {
  78.        Distancias[i]=-1;
  79.        anterior[i]=Celda(-1,-1);
  80.    }
  81.  
  82.    Distancias[ori.getx()+ori.gety()*Ancho]=0;
  83.    anterior[ori.getx()+ori.gety()*Ancho]=ori;
  84.  
  85.  
  86.    queue<Celda> porVisitar;
  87.    porVisitar.push(ori);
  88.  
  89.    while(!porVisitar.empty())
  90.    {
  91.        Celda cur=porVisitar.front();
  92.        porVisitar.pop();
  93.        //cout<<porVisitar.size()<<endl;
  94.        for(int i=-1; i<2; i++)
  95.            for(int j=-1; j<2; j++)
  96.            {
  97.                if ((i == j) || (i == -1 && j == 1) || (i == 1 && j == -1))
  98.                    continue;
  99.                if( (cur.getx()+j)>=0 && (cur.getx()+j)<Ancho && (cur.gety()+i)>=0 && (cur.gety()+i)<Altura && // si no estamos fuera de los limites del array...
  100.                        array[(cur.gety()+i)][(cur.getx()+j)]==0 && // si no es un obstaculo...
  101.                        Distancias[cur.getx()+cur.gety()*Altura]+1 < Distancias[(cur.getx()+j)+(cur.gety()+i)*Ancho] // si no hay otra distancia mejor...
  102.                  )
  103.                {
  104.                    Distancias[(cur.getx()+j)+(cur.gety()+i)*Ancho]= Distancias[cur.getx()+cur.gety()*Ancho]+1;
  105.                    anterior[(cur.getx()+j)+(cur.gety()+i)*Ancho]=Celda(cur.getx(),cur.gety());
  106.                    porVisitar.push(Celda(cur.getx()+j,cur.gety()+i));
  107.                }
  108.  
  109.            }
  110.    }
  111.  
  112.    if(anterior[dest.getx()+dest.gety()*Ancho]==Celda(-1,-1)) return vector<Celda>();
  113.  
  114.    Celda pp=dest;
  115.    vector<Celda> res(Distancias[dest.getx()+dest.gety()*Ancho]+1);
  116.    for(int i=res.size()-1; !(pp==ori); i--)
  117.    {
  118.        res[i]=pp;
  119.        pp=anterior[pp.getx()+pp.gety()*Ancho];
  120.    }
  121.    delete[] Distancias;
  122.    delete[] anterior;
  123.    return res;
  124.  
  125. }

El tamaño del camino es el tamaño del vector.


Título: Re: AYUDA Función Recursiva
Publicado por: Almapa en 19 Diciembre 2013, 23:51 pm
Efectivamente el algoritmo de Dijkstra serviría, en este caso para buscar el camino más largo posible. Parece muy interesante, voy a echarle un vistazo.  ;)

El único problema que le veo es que no se determina el punto final, por lo que se tendría que aplicar dicho algoritmo a todos los nodos y al final elegir de todos los posibles finales el camino más largo...


Título: Re: AYUDA Función Recursiva
Publicado por: dvigon en 20 Diciembre 2013, 02:13 am
¿ Esta ese mismo algoritmo en C ? Como debería adaptarlo? No puedo usar clases en esta ocasión..