AYUDA Función Recursiva

[dvigon]

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.

Código [Seleccionar] Expandir


#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.

[Almapa]

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!

[Almapa]

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

[dvigon]

Da igual el tiempo mientras se resuelva el problema... la putada es que yo y la recursividad no nos entendemos... ¿Alguna sugerencia?

[amchacon]

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 (cpp) [Seleccionar] Expandir

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Celda
{
   int x;
   int y;
public:
   int getx()
   {
       return x;
   }
   int gety()
   {
       return y;
   }
   void setx(int x)
   {
       this->x=x;
   }
   void sety(int y)
   {
       this->y=y;
   }

   bool operator==(Celda o)
   {
       return x==o.x && y==o.y;
   }
   Celda operator=(Celda o)
   {
       x=o.x;
       y=o.y;
       return *this;
   }

   Celda(int x,int y):x(x),y(y) {}
   Celda():x(0),y(0) {}
};
vector<Celda> ObtenerCaminoMasCorto(Celda ori,Celda dest, char array[8][8], int Ancho, int Altura);

int main()
{
   char ejemplo[8][8]=
   {
       {0,1,0,1,0,0,0,0}, //0: vacío
       {0,1,0,1,0,0,0,0}, //1: pared
       {0,1,0,1,0,0,0,0},
       {0,1,0,1,0,0,0,0},
       {0,1,0,1,0,0,0,0},
       {0,1,0,1,0,0,0,0},
       {0,0,0,1,0,0,0,0},
       {0,0,0,0,0,0,0,0}
   };

   vector<Celda> camino= ObtenerCaminoMasCorto(Celda(0,0),Celda(7,0),ejemplo,8,8);
   for(int i=0; i<camino.size(); i++)
   {
       cout<<"("<<camino[i].getx()<<", "<<camino[i].gety()<<")"<<endl;
   }

}

vector<Celda> ObtenerCaminoMasCorto(Celda ori,Celda dest, char array[8][8], int Ancho, int Altura)
{

   if(ori==dest) return vector<Celda>();

   unsigned int *Distancias=new unsigned int[Ancho*Altura];

   Celda *anterior=new Celda[Ancho*Altura];

   for(int i=0; i<Ancho*Altura; i++)
   {
       Distancias[i]=-1;
       anterior[i]=Celda(-1,-1);
   }

   Distancias[ori.getx()+ori.gety()*Ancho]=0;
   anterior[ori.getx()+ori.gety()*Ancho]=ori;


   queue<Celda> porVisitar;
   porVisitar.push(ori);

   while(!porVisitar.empty())
   {
       Celda cur=porVisitar.front();
       porVisitar.pop();
       //cout<<porVisitar.size()<<endl;
       for(int i=-1; i<2; i++)
           for(int j=-1; j<2; j++)
           {
               if ((i == j) || (i == -1 && j == 1) || (i == 1 && j == -1))
                   continue;
               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...
                       array[(cur.gety()+i)][(cur.getx()+j)]==0 && // si no es un obstaculo...
                       Distancias[cur.getx()+cur.gety()*Altura]+1 < Distancias[(cur.getx()+j)+(cur.gety()+i)*Ancho] // si no hay otra distancia mejor...
                 )
               {
                   Distancias[(cur.getx()+j)+(cur.gety()+i)*Ancho]= Distancias[cur.getx()+cur.gety()*Ancho]+1;
                   anterior[(cur.getx()+j)+(cur.gety()+i)*Ancho]=Celda(cur.getx(),cur.gety());
                   porVisitar.push(Celda(cur.getx()+j,cur.gety()+i));
               }

           }
   }

   if(anterior[dest.getx()+dest.gety()*Ancho]==Celda(-1,-1)) return vector<Celda>();

   Celda pp=dest;
   vector<Celda> res(Distancias[dest.getx()+dest.gety()*Ancho]+1);
   for(int i=res.size()-1; !(pp==ori); i--)
   {
       res[i]=pp;
       pp=anterior[pp.getx()+pp.gety()*Ancho];
   }
   delete[] Distancias;
   delete[] anterior;
   return res;

}

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

[Almapa]

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...

[dvigon]

¿ Esta ese mismo algoritmo en C ? Como debería adaptarlo? No puedo usar clases en esta ocasión..