schemaGameGenerator.c

Go to the documentation of this file.

#include "schemaGameGenerator.h"

/* Start function definition of schemaGameGenerator module */

bool generateSchema( const char *filename,        
                     unsigned int numRow,         
                     unsigned int numCol,         
                     unsigned int difficult  
                   )
{
    D1(printf("\nSCHEMAGAMEGENERATOR.generateSchema() - START\n"));
    
    FILE *newSchemaFile = fopen( filename , "w" );
    
    if( ! check_generateSchema( newSchemaFile, difficult, numRow, numCol ) ){
        D1(printf("\nSCHEMAGAMEGENERATOR.generateSchema() - ERROR & END\n"));
        return false;
    }
    
    assert( newSchemaFile != NULL );
    assert( !( (difficult < MIN_DIFFICULT) || (difficult > MAX_DIFFICULT) ) );
    assert( !( (numRow < MINR) || (numRow > MAXR) ) );
    assert( !( (numCol < MINC) || (numCol > MAXC) ) );
    
    char **gameMap = gameMap_alloc_and_set( numRow, numCol );

    srand((unsigned)time(0));
    
    double execution_time = create_routes( difficult , numRow, numCol , gameMap );
    
    if( execution_time < 0 ){
        D1(printf("\nSCHEMAGAMEGENERATOR.generateSchema() - ERROR & END\n"));
        free( gameMap );
        return false;
    }   
    
    increase_schema_difficult( gameMap , numRow, numCol );
    
    D1(printf("\nWrite schema on file %s\n", filename));
    
    save_schema_to_file( gameMap, numRow, numCol, newSchemaFile );
    
    free( gameMap );
    
    D1(printf("\nSCHEMAGAMEGENERATOR.generateSchema() - END\n"));
    
    return true;
}



bool check_generateSchema( const FILE *newSchemaFile,
                           unsigned int difficult,
                           unsigned int numRow,
                           unsigned int numCol
                         )
{
    
    D5(printf("\nSCHEMAGAMEGENERATOR.check_generateSchema - START\n"));
    
    bool returnValue = true;
    
    if( newSchemaFile == NULL )
    {
        D1(printf("\nERROR in FILE/s OPEN!\n"));
        returnValue = false;
    }

    if( (difficult < MIN_DIFFICULT) || (difficult > MAX_DIFFICULT) )
    {
        D1(printf("\nParameter difficult out of range: %u not in [%u,%u]\n",
                                  difficult , MIN_DIFFICULT , MAX_DIFFICULT ));
        returnValue = false;
    }

    if( (numRow < MINR) || (numRow > MAXR) )
    {
        D1(printf("\nParameter numRow out of range: %u not in [%u,%u]\n",
                                              numRow ,     MINR,MAXR     ));
        returnValue = false;
    }

    if( (numCol < MINC) || (numCol > MAXC) )
    {
        D1(printf("\nParameter numCol out of range: %u not in [%u,%u]\n",
                                             numCol ,      MINC,MAXC     ));
        returnValue = false;
    }


    D5(printf("\nSCHEMAGAMEGENERATOR.check_generateSchema - END\n"));

    return returnValue;
}



char **gameMap_alloc_and_set( unsigned int numRow,
                              unsigned int numCol
                            )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.gameMap_alloc_and_set - START\n"));
    
    char **gameMap = (char **) malloc( sizeof(char *) * numRow );
    
    unsigned int i,j;
    
    for(i=0; i<numRow; i++)
    {
        gameMap[i] = (char *) malloc( sizeof(char) * numCol );
        
        for(j=0; j<numCol; j++)
            gameMap[i][j] = CLOSE;
    }
    
    D5(printf("\nSCHEMAGAMEGENERATOR.gameMap_alloc_and_set - END\n"));
    
    return gameMap;
}



double create_routes( unsigned int difficult,
                      unsigned int numRow,
                      unsigned int numCol,
                      char **gameMap
                    )
{
    D2(printf("\nSCHEMAGAMEGENERATOR.create_routes - START\n"));
    
    /* Execution time variables. */
    double elapsed = -1;
    clock_t tStart, tEnd;
    tStart = clock();
    
    /* Put the START point randomly between (1,1) and ( numRow-1 , numCol-1 ) */
    coordinates start;
    start.row = 1 + floor ( rand() % ( numRow - 2 ) );
    start.col = 1 + floor ( rand() % ( numCol - 2 ) );
    
    gameMap [ start.row ][ start.col ] = START;
   
    D2(printf("\nStart in (Row,Col)=(%u,%u)\n",start.row,start.col));
    
    /* Get the number of routes */
    unsigned int numOfRoute = getRouteNumber( difficult, numRow, numCol );
    
    /* Get the deny area lenghts in selected direction */
    coordinates deny;
    deny.row = get_denyArea( difficult, numRow, start.row );
    deny.col = get_denyArea( difficult, numCol, start.col );
    
    /* Set available cells number in specified direction */
    directions avail;
    avail = set_number_of_available_cells( start, deny, numRow, numCol );
    
    /* Wrong direction probability */
    const double LOW = 0.45;
    
    /* for each way set relative door and generate the route from start */
    unsigned int it = 0;
    for(it = 0; it<numOfRoute ; it++)
    {
        /* Probability to go in that direction.
           Eg. left = 0.3 => right = (1-left) = 0.7 */
        struct direction_probabilities
        {
            double left;
            double up;
        } prob ;

        /* Get the door random coordinates in the schema */
        coordinates door;
        door.row = point_in_random_direction( avail.left  , avail.right,
                                              start.row   , deny.row,
                                              &(prob.left), LOW           );
        
        door.col = point_in_random_direction( avail.up  , avail.down,
                                              start.col , deny.col,
                                              &(prob.up), LOW         );
       
       /* Set the calculate door in it's position */
       gameMap[ door.row ][ door.col ] = DOOR;
       
       D3(printf("\nDoor in (row,col)=(%u,%u)\n",door.row,door.col));
       
       unsigned int routelen;
       
       const unsigned int MAX_ROUTE_LEN = get_MaxRouteLen( numRow, numCol,
                                                           start,  door    );
       
       coordinates route[ MAX_ROUTE_LEN + 1 ];
       
       do{
          /* Current position "start from start" */
          coordinates curr;
          curr.row = start.row;
          curr.col = start.col;
          
          routelen = 0;
          
          /* while current position is not the door and the route length is
             shorter than MAX_ROUTE_LEN */
          while( ( ( curr.row != door.row ) || ( curr.col != door.col ) ) && 
                 ( routelen < MAX_ROUTE_LEN )                                 )
          {
                // Get next route cell coordinates in calculate direction   //******************* void -> coordinates
                get_direction_from_point( numRow    , numCol,
                                          &curr.row , &curr.col, 
                                          prob.left , prob.up      );
                                
                /* Save current position (may be overwrite) */
                route[ routelen ].row = curr.row;
                route[ routelen ].col = curr.col;
                
                routelen++; /* One more step */
          }
          
          D3(printf("\nIters %u of %u%s\n", routelen, MAX_ROUTE_LEN,
                        (routelen>=MAX_ROUTE_LEN)?" ROUTE STOPPED":"." ));
        
       }while( routelen >= MAX_ROUTE_LEN ); /* while the door is not reached */
       
        unsigned int it = 0;
        /* Set the CLOSE postions on the way FREE */
        for(it=0; it<routelen; it++ )
            if( gameMap[ route[ it ].row ][ route[ it ].col ] == CLOSE )
                gameMap[ route[ it ].row ][ route[ it ].col ] =  FREE ;
    }
    
    tEnd = clock();
    elapsed = (double)(tEnd-tStart)/CLOCKS_PER_SEC; // Elapsed time in seconds
    
    D4(printf("\nSchema dimension (%uX%u):",numRow,numCol));
    D5(printf("\nClock at start: %lu",tStart));
    D5(printf("\nClock at   end: %lu",tEnd));
    D5(printf("\nCPU clock per second: %lu",CLOCKS_PER_SEC));
    D4(printf("\nElapsed time: %lf second(s)\n",elapsed));
    D2(printf("\nSCHEMAGAMEGENERATOR.create_routes - END\n"));
    
    return elapsed;
}



unsigned int get_denyArea( unsigned int difficult,
                           unsigned int numDir,
                           unsigned int startDir
                         )
{

    D5(printf("\nSCHEMAGAMEGENERATOR.get_denyArea - START\n"));

    /* 
       ceil( [0.1, 0.2, .. , 1] * 
              rand() from 0 to max dist from start to border 
           )
    */
    
    assert( MAX_DIFFICULT > 0 );
    assert( ( numDir - 1 - startDir ) > 0 );

    const unsigned int deny_area = ceil( 
                                         ( (double)difficult / MAX_DIFFICULT )
                                         * 
                                         ( rand() % ( numDir - 1 - startDir ) )
                                       );

    
    assert( ( 0 <= deny_area ) && ( deny_area <= ( numDir - 1 - startDir ) ) );
    
    D6(printf("\nNumber of deny cells in that direction = %u\n",deny_area));
    
    D5(printf("\nSCHEMAGAMEGENERATOR.get_denyArea - END\n"));
    
    return deny_area;
}



unsigned int getRouteNumber( unsigned int difficult,
                             unsigned int numRow,
                             unsigned int numCol
                           )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.getRouteNumber - START\n"));
    
    assert( MAX_DIFFICULT >= MIN_DIFFICULT );
    assert( MIN_DIFFICULT > 0 );

    /* Number of doors in the schema: 
           1 + round( (0.1 , 0.2, .. , 1) * 
           ( [ (5x5) 1.58 , 7.07 (100x100) ] + 
             rand() from 0 to [ (5X5) 2 , 7 (100x100) ] )
             
       Es. (5x5) -> 1 to 5
       Es. (100X100) -> 2 to 15
    */
    
    unsigned int numOfRoute = 
    (
    
            1 
            + 
            floor
            ( 
                ( (double)difficult 
                  /
                  ( MAX_DIFFICULT - MIN_DIFFICULT )
                )
                *      
                ( 
                    sqrt( (double)(numRow * numCol)/( numRow + numCol ) )
                    + 
                    rand() % (int) floor ( 
                                            sqrt(
                                                    (double)(numRow * numCol)
                                                    /
                                                    ( numRow + numCol )
                                                ) 
                                            )                        
                ) 
            )
    );
    
    assert( ( numOfRoute > 0 ) && ( numOfRoute < ( numRow * numCol ) ) );

    D2(printf("\nNumber of way = %u\n",numOfRoute));
    
    D5(printf("\nSCHEMAGAMEGENERATOR.getRouteNumber - END\n"));
    
    return numOfRoute;
}



directions set_number_of_available_cells( coordinates start,
                                          coordinates deny,
                                          unsigned int numRow,
                                          unsigned int numCol
                                        )

{
   D5(printf("\nSCHEMAGAMEGENERATOR.set_number_of_available_cells - START\n"));
   
   directions avail;
    
   // Warning: make sure postive expression using unsigned int.
   avail.left = ( start.row > deny.row ) ? ( start.row - deny.row ) : 0;
        
   avail.right = ( numRow > ( 1 + start.row + deny.row ) ) ?
                 ( numRow - ( 1 + start.row + deny.row ) ) : 0;
    
   avail.up = (start.col > deny.col) ? ( start.col - deny.col ) : 0;
    
   avail.down = ( numCol > ( 1 + start.col + deny.col ) ) ?
                ( numCol - ( 1 + start.col + deny.col ) ) : 0;
                    
   D3(printf("\nAvailable cells: Left %u, Right %u, Up %u, Down %u",
                                 avail.left,avail.right,avail.up,avail.down ));
   
   D5(printf("\nSCHEMAGAMEGENERATOR.set_number_of_available_cells - END\n"));
   
   return avail;
}



unsigned int get_MaxRouteLen( unsigned int numRow, 
                              unsigned int numCol,
                              coordinates start,
                              coordinates door
                            )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.get_MaxRouteLen - START\n"));

   /* If MINR and MINC are more then 5 function is unused
          EG. 5x5/3 = 8  - start in 0,0 door in 4,4 => max route len=8
          But if changed it's necessary or may cause a infinite loop.
          NB. The number (3) is not a programmers assumption but was calculate
              after a consistent number of tests.
   */
   
   const unsigned int bestParam = 3;
   
   unsigned int optimal = ( ( numRow * numCol ) / bestParam );
   
   const unsigned int minimum = (unsigned int)
                                  ( 
                                    bestParam + 
                                    abs( start.row - door.row ) +
                                    abs( start.col - door.col ) 
                                  );
                           
   if( optimal < minimum )
        optimal = minimum;
   
   D5(printf("\nSCHEMAGAMEGENERATOR.get_MaxRouteLen - END\n"));
        
   return optimal;
}



unsigned int point_in_random_direction( unsigned int avail_dir1,
                                        unsigned int avail_dir2,
                                        unsigned int start_dir ,
                                        unsigned int deny_area ,
                                        double *probability,
                                        const double LOW
                                      )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.point_in_random_direction - START\n"));
   
    // Randomly choose (as first option) dir1 (*) or dir2 (**)
    
    // * dir 1
    if( rand() % 2 )
    {
        // if there is at least one cell
        if(avail_dir1 > 0)
        {
            ( *probability ) = 1 - LOW;
            
            const unsigned int returnValue = ( rand() % avail_dir1 );
            
            D8(printf("\nProbability: %lf Point coordinate: %u", 
                                (*probability) ,       returnValue ));
                                
            D5(printf("\nSCHEMAGAMEGENERATOR.point_in_random_direction - END\n"));
            
            return returnValue;
        }
        
        // else select other side
        ( *probability ) = LOW;
        
        const unsigned int returnValue = ( 1 +
                                           start_dir +
                                           deny_area +
                                           rand() % avail_dir2 );
                                           
        D8(printf("\nProbability: %lf Point coordinate: %u", 
                              (*probability) ,       returnValue ));
                              
        D5(printf("\nSCHEMAGAMEGENERATOR.point_in_random_direction - END\n"));
        
        return returnValue;
    }

    // ** dir2
    
    // if there is at least one cell
    if(avail_dir2 > 0)
    {
        ( *probability ) = LOW;
        
        const unsigned int returnValue = ( 1 +
                                           start_dir +
                                           deny_area +
                                           rand() % avail_dir2 );
                                           
        D8(printf("\nProbability: %lf Point coordinate: %u", 
                            (*probability) ,       returnValue ));
                            
        D5(printf("\nSCHEMAGAMEGENERATOR.point_in_random_direction - END\n"));
        
        return returnValue;
    }
    
    // else select other side
    ( *probability ) = 1 - LOW;
    
    const unsigned int returnValue = ( rand() % avail_dir1 );
    
    D8(printf("\nProbability: %lf Point coordinate: %u", 
                       (*probability) ,       returnValue ));
                       
    D5(printf("\nSCHEMAGAMEGENERATOR.point_in_random_direction - END\n"));
    
    return returnValue;
}



void get_direction_from_point( unsigned int numRow,
                               unsigned int numCol,
                               unsigned int *currentRow,
                               unsigned int *currentCol,
                               double probabilityLeft,
                               double probabilityUp
                             )
{

    D5(printf("\nSCHEMAGAMEGENERATOR.get_direction_from_point - START\n"));
    
    /* Set current probability (from 0 to 1) */
    const double currentProbability = (double)(rand() % 1001)/1000;

    assert( ( 0 <= currentProbability ) && ( currentProbability <= 1 ) );
    
    /* Randomly choose (50%-50%) horizontal or vertical direction.
       Randomly choose (LOW - (1-LOW)) LEFT or RIGHT / UP or DOWN
       from horizontal/veritcal direction first determinated.
    */
    if( rand() % 2)                                 // LEFT - RIGHT
    {    
        if( currentProbability < probabilityLeft )  // First try left
        {
            if( (*currentRow) > 0 )                 // Go left if possible
                (*currentRow) = (*currentRow) - 1;
            else                                    // Go right
                (*currentRow) = (*currentRow) + 1;
        }
        else                                        // First try right
        {
            if( ((*currentRow) + 1) < numRow )      // Go right if possible
                (*currentRow) = (*currentRow) + 1;
            else                                    // Go left
                (*currentRow) = (*currentRow) - 1;
        }
    }
    else                                            // UP - DOWN
    {    
        if( currentProbability < probabilityUp )    // First try up
        {    
            if( (*currentCol) > 0 )                 // Go up if possible
                (*currentCol) = (*currentCol) - 1;
            else                                    // Go down
                (*currentCol) = (*currentCol) + 1;
        }
        else                                        // First try down
        {    
            if( ((*currentCol) + 1) < numCol )           // Go down if possible
                (*currentCol) = (*currentCol) + 1;
            else                                    // Go up
                (*currentCol) = (*currentCol) - 1;
        }
    }
    
    D8(printf("\nCurrent position (%u,%u) Probability %.3lf (>LOW?)",
                        (*currentRow),(*currentCol),currentProbability  ));
    
    D5(printf("\nSCHEMAGAMEGENERATOR.get_direction_from_point - END\n"));
}



void increase_schema_difficult( char **Map,
                                unsigned int numRow,
                                unsigned int numCol
                              )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.increase_schema_difficult - START\n"));
    
    // iterators
    unsigned int i = 0, j = 0;
    
    /* If there is a 'FREE block' in the schema, CLOSE the middle.
       Es.
        . . .         . . .
        . . .   --->  . X .
        . . .         . . .
       
       --> This doesn't block any way! The schema become more complex.
    */
    for(i=1; i<(numRow-1); i++)
      for(j=1; j<(numCol-1); j++)
        if( 
            ( 
              Map[i-1][j-1] & Map[i-1][j] & Map[i-1][j+1] &
              Map[i][j-1]   & Map[i][j]   & Map[i][j+1]   &
              Map[i+1][j-1] & Map[i+1][j] & Map[i+1][j+1]
            )
              == FREE
          )
            Map[ i ][ j ] = CLOSE;  
    
    /* If there is a 'CLOSE block' in the schema, randomly FREE one.
       Es.
        X X   --->   . X    or   X X   --->   X X   or...
        X X          X X         X X          X .
      --> The schema become more complex. (An eventually new way is accepted)
    */      
    for(i=1; i<numRow; i++)
      for(j=1; j<numCol; j++)    
        if( (Map[i-1][j-1]==CLOSE) && (Map[i-1][j]==CLOSE) && 
            (Map[i][j-1]  ==CLOSE) && (Map[i][j]  ==CLOSE) 
          )
            Map[ i - rand()%2 ][ j - rand()%2 ] = FREE;
    
    D5(printf("\nSCHEMAGAMEGENERATOR.increase_schema_difficult - END\n"));
}



void save_schema_to_file( char **gameMap,
                          unsigned int numRow,
                          unsigned int numCol,
                          FILE *newSchemaFile
                        )
{
    D5(printf("\nSCHEMAGAMEGENERATOR.save_schema_to_file - START\n"));
    
    assert( newSchemaFile != NULL );    
    
    fprintf(newSchemaFile , "#Built by: %s v%s\n",PRGNAME,PRGVERS);
    fprintf(newSchemaFile , "#Rows %u, Columns %u\n" ,numRow,numCol);
    fprintf(newSchemaFile , "#Schema:\n");
    
    // iterators
    unsigned int i = 0, j = 0;
    
    D4(printf("\n"));
    for(i=0; i<numRow; i++){
        
        for(j=0; j<numCol; j++){
            
            fprintf(newSchemaFile,"%c",gameMap[i][j]);
            
            D4(printf("%c",gameMap[i][j]));
        }
        
        fprintf(newSchemaFile,"\n");
        
        D4(printf("\n"));
    }

    assert( newSchemaFile != NULL );    

    fclose(newSchemaFile);
    
    D5(printf("\nSCHEMAGAMEGENERATOR.save_schema_to_file - END\n"));
}

/* End function definition of schemaGameGenerator module */

---