• Main Page
  • Modules
  • Namespaces
  • Classes
  • Files
  • File List

D:/Projekt/ECF_trunk/examples/GPMaze/Maze.cpp

00001 #include "Maze.h"
00002 
00003 #include <ctime>
00004 #include <cmath>
00005 #include <fstream>
00006 
00007 #define HORIZONTAL 0
00008 #define VERTICAL 1
00009 
00010 
00011 
00012 Maze::Maze(void)
00013 {
00014     srand( (unsigned int) time(NULL) );
00015 }
00016 
00017 void Maze::ClearMaze()
00018 {
00019     int i, j;
00020     for(i = 0; i < MazeMaxSize ; i++)
00021         for(j = 0; j < MazeMaxSize ; j++)
00022             maze[i][j] = 0;
00023 }
00024 
00025 /*
00026                     Generating maze interior (walls)
00027     arguments:  maze            - array describing maze
00028                 submazeDim      - dimensions od submaze
00029                         first   - width of submaze
00030                         second  - height of submaze
00031                 submazeStartXY  - starting point of submaze in maze
00032                         first   - starting row of submaze in maze
00033                         second  - starting column of submaze in maze
00034     variables:
00035                 Orientation
00036                             1 - vertical
00037                             0 - horizontal
00038                 wallPos         - position of wall in current submaze (horizontal/vertical)
00039                 passagePos      - set of positions of passages in wall in current submaze (horizontal/vertical)
00040                 maze[i][j]
00041                             0 - without wall
00042                             1 - vertikal wall
00043                             2 - horizontal wall
00044                             3 - vertical and horizontal wall
00045     */
00046 
00047 void Maze::GenerateWalls(pair<int,int> submazeDim, pair<int,int> submazeStartXY)
00048 {
00049     int wallPos = 0, Orientation = 0, i, width, height;
00050 
00051     set<int> passagePos;
00052     set<int> possiblePassage;
00053     set<int>::iterator it;
00054 
00055     pair<int,int> submazeNewDim;
00056     pair<int,int> submazeNewStartXY;
00057 
00058     width = submazeDim.first;
00059     height = submazeDim.second;
00060 
00061     if( !(width < 2 || height < 2) )
00062     {
00063         if( width >= 2 * height )
00064             Orientation = VERTICAL;
00065         else if( height >= 2 * width )
00066             Orientation = HORIZONTAL;
00067         else Orientation = rand() % 2;
00068 
00069         //      Vertical wall
00070 
00071         if( Orientation )
00072         {
00073             wallPos = rand() % (width - 1);
00074             
00075             //      Position of possible passages (whole wall)
00076             for( int j = 0; j < height; j++)
00077                 possiblePassage.insert(j);
00078             
00079             for( int i = 0, j = 1; i < j ; i++)
00080             {
00081                 int temp, tmpPos;
00082                 
00083                 it = possiblePassage.begin();
00084                 tmpPos =  rand() % possiblePassage.size();
00085 
00086                 for( int k = 0; k < tmpPos; k++)
00087                     it++;
00088                 
00089                 temp = *it;
00090                 possiblePassage.erase(temp);
00091                 possiblePassage.erase(temp - 1);
00092                 possiblePassage.erase(temp + 1);
00093                 
00094                 passagePos.insert(temp);
00095 
00096                 //      20% probbability to add 1 more passage if there isnt max number of passage (wall lenght / min maze size)
00097                 if( (int) (100.0 * ( rand() / (RAND_MAX + 1.0) ) ) < 30 && j <= (height / MazeMinSize) )
00098                     j++;
00099             }
00100 
00101 
00102             //      Add wall with passage
00103             for(i = 0; i < height; i++)
00104                 if(passagePos.find(i) != passagePos.end())
00105                     continue;
00106                 else
00107                     maze[submazeStartXY.first + i][submazeStartXY.second + wallPos] += 1;
00108             
00109             submazeNewDim.first = wallPos + 1;
00110             submazeNewDim.second = height;
00111 
00112             GenerateWalls( submazeNewDim, submazeStartXY );
00113             
00114             submazeNewDim.first = width - (wallPos + 1);
00115             submazeNewStartXY.first = submazeStartXY.first;
00116             submazeNewStartXY.second = submazeStartXY.second + wallPos + 1;
00117 
00118             GenerateWalls( submazeNewDim, submazeNewStartXY );
00119         }
00120         //      Horizontal wall
00121         else
00122         {
00123             wallPos = rand() % (height - 1);
00124             
00125             //      Position of possible passages (whole wall)
00126             for( int j = 0; j < width; j++)
00127                 possiblePassage.insert(j);
00128             
00129             for( int i = 0, j = 1; i < j ; i++)
00130             {
00131                 int temp, tmpPos;
00132                 
00133                 it = possiblePassage.begin();
00134                 tmpPos =  rand() % possiblePassage.size();
00135 
00136                 for( int k = 0; k < tmpPos; k++)
00137                     it++;
00138                 
00139                 temp = *it;
00140                 possiblePassage.erase(temp);
00141                 possiblePassage.erase(temp - 1);
00142                 possiblePassage.erase(temp + 1);
00143                 
00144                 passagePos.insert(temp);
00145 
00146                 //      20% probbability to add 1 more passage if there isnt max number of passage (wall lenght / min maze size)
00147                 if( (int) (100.0 * ( rand() / (RAND_MAX + 1.0) ) ) < 30 && j <= (width / MazeMinSize) )
00148                     j++;
00149             }
00150 
00151 
00152             //      Add wall with passage
00153             for(i = 0; i < width ; i++)
00154                 if(passagePos.find(i) != passagePos.end())
00155                     continue;
00156                 else
00157                     maze[submazeStartXY.first + wallPos ][submazeStartXY.second + i] += 2;
00158 
00159             submazeNewDim.first = width;
00160             submazeNewDim.second = wallPos + 1;
00161 
00162             GenerateWalls( submazeNewDim, submazeStartXY );
00163             
00164             submazeNewDim.second = height - (wallPos + 1);
00165             submazeNewStartXY.first = submazeStartXY.first + wallPos + 1;
00166             submazeNewStartXY.second = submazeStartXY.second;
00167 
00168             GenerateWalls( submazeNewDim, submazeNewStartXY );
00169         }
00170     }
00171 
00172 }
00173 
00174 /*
00175                         Create exits
00176     Variables:
00177             maxCreateExits          - max number of exits generator can create (20% of all)
00178             minY, minX              - coords. of outer walls (left/west wall (n,-1), top/north wall (-1,n))
00179             maxY, maxX              - coords. of outer walls (right/east wall (n, dimensions.first), bottom/south wall (dimensions.second, n))
00180             numberOfExits           - randomly gen. number of exits [1, maxCreateExits]
00181             allExits                - set of all possible exits in a maze
00182     */
00183 
00184 void Maze::CreateExits()
00185 {
00186     int minX, maxX, minY, maxY;
00187     
00188     int maxExits = ( dimensions.first + dimensions.second ) * 2;
00189     int minExits = 1, maxCreateExits = maxExits * 0.2;
00190     int numberOfExits;
00191     int chooseAnExit;
00192 
00193     set< pair<int,int> > allExits;
00194     set< pair<int,int> >::iterator it;
00195     minX = minY = -1;
00196     maxX = dimensions.second;
00197     maxY = dimensions.first;
00198 
00199     //      adding all possible side (left/right outer wall) exits to allExits
00200     for(int i = 0; i < dimensions.second; i++)
00201     {
00202         // all exits of left outer wall
00203         allExits.insert(make_pair(i, minY));
00204         // all exits of right outer wall
00205         allExits.insert(make_pair(i, maxY));
00206     }
00207     //      adding all possible side (top/bottom outer wall) exits to allExits
00208     for(int i = 0; i < dimensions.first; i++)
00209     {
00210         // all exits of top outer wall
00211         allExits.insert(make_pair(minX, i));
00212         // all exits of bottom outer wall
00213         allExits.insert(make_pair(maxX, i));
00214     }
00215 
00216     numberOfExits = rand() % maxCreateExits + 1;
00217 
00218     for(int i = 0; i < numberOfExits; i++)
00219     {
00220         it = allExits.begin();
00221         
00222         chooseAnExit = rand() % allExits.size();
00223         
00224         for(int j = 0; j < chooseAnExit; j++)
00225             it++; 
00226         
00227         exits.insert(*it);
00228         
00229         /*
00230                 There musnt be two adjoining exits (adjoinig exits all also considered exits on corners of maze) - restricted in the task
00231         */
00232 
00233         // discarding top neighbor of choosen exit (if it exists) as possible exit
00234             allExits.erase( make_pair((*it).first - 1, (*it).second) );
00235         
00236         // discarding bottom neighbor of choosen exit (if it exists) as possible exit
00237             allExits.erase( make_pair((*it).first + 1, (*it).second) );
00238         
00239         // discarding left neighbor of choosen exit (if it exists) as possible exit
00240             allExits.erase( make_pair((*it).first, (*it).second - 1) );
00241         
00242         // discarding right neighbor of choosen exit (if it exists) as possible exit
00243             allExits.erase( make_pair((*it).first, (*it).second + 1) );
00244         
00245         // discarding top-left neighbor of choosen exit (if it exists) as possible exit
00246             allExits.erase( make_pair((*it).first - 1, (*it).second - 1) );
00247             
00248         // discarding top-right neighbor of choosen exit (if it exists) as possible exit
00249             allExits.erase( make_pair((*it).first - 1, (*it).second + 1) );
00250             
00251         // discarding bottom-left neighbor of choosen exit (if it exists) as possible exit
00252             allExits.erase( make_pair((*it).first + 1, (*it).second - 1) );
00253             
00254         // discarding bottom neighbor of choosen exit (if it exists) as possible exit
00255             allExits.erase( make_pair((*it).first + 1, (*it).second + 1) );
00256 
00257         // erasing choosen exit from set of possible exits
00258             allExits.erase( *it );
00259     }
00260 
00261 }
00262 
00263 /*
00264                 Function that generates a maze (with dimensions: mazeDimensions.first x mazeDimensions.second)
00265     mazeStart00     - starting coordinates of maze ( (0,0) - row == 0 && column == 0)
00266     dimensions      - dimensions of maze (width, height)
00267     */
00268 
00269 void Maze::GenerateMaze(pair<int,int> mazeDimensions)
00270 {
00271     pair<int,int> mazeStart00;
00272     mazeStart00 = make_pair(0,0);
00273     
00274     dimensions = mazeDimensions;
00275 
00276     ClearMaze();
00277     GenerateWalls(dimensions, mazeStart00);
00278     CreateExits();
00279 
00280 }
00281 
00282 /*  
00283                 Saves maze in file in format:
00284 
00285                 line 1: "%d %d" - width, height of maze
00286                 line 2: string that consists of 0,1,2,3 which represent walls in each cell od maze starting from [0,0][0,1]..[1,0][1,1]...
00287                 line 3: "%d %d %d" -startig row and column of agent and its direction
00288                 line 4: "%d" number of exits
00289                 line 5 - line x (x number of exits): "%d %d" - row, column 
00290                 */
00291 void Maze::SaveMazeToFile(string name, pair<int,int> startingCoords, int direction)
00292 {
00293     set< pair<int,int> >::iterator it;
00294     ofstream myFile;
00295     myFile.open (name.c_str(), ios::trunc);
00296     
00297     myFile << dimensions.first << " " << dimensions.second << endl;
00298     
00299     for(int i = 0; i < dimensions.second; i++)
00300         for(int j = 0; j < dimensions.first; j++)
00301             myFile << maze[i][j];
00302     
00303     myFile << endl;
00304 
00305     myFile << startingCoords.first << " " << startingCoords.second << " " << direction << endl; 
00306 
00307     myFile << exits.size() << endl;
00308 
00309     for(it = exits.begin(); it != exits.end(); it++)
00310         myFile << (*it).first << " " << (*it).second << endl;
00311 
00312     myFile.close();
00313 }
00314 
00315 /*
00316                 IsExit is a function which verifies that the requested field is in an exit. It returns true if fields is an exit, else false.
00317     */
00318 bool Maze::IsExit(pair<int,int> position)
00319 {
00320     if( exits.find( position ) != exits.end() )
00321         return true;
00322     else return false;
00323 }
00324 
00325 /*
00326                 This function returns true if there is a wall in front of a agent
00327         position    - position od an agent
00328         direction   - direction in which agent faces    
00329                         - 0: North (if agent in (0,1) than he can see (0,0))
00330                         - 1: East
00331                         - 2: South
00332                         - 3: West
00333     */
00334 bool Maze::IsThereWallAhead(pair<int,int> position, int direction)
00335 {
00336     // check if there should be an exit ahead, if so check if it is an exit
00337     if( direction == 0 )
00338         if( position.first == 0 )
00339             return !IsExit( make_pair( position.first - 1, position.second ) );
00340     if( direction == 1 )
00341         if( position.second + 1 == dimensions.first )
00342             return !IsExit( make_pair( position.first, position.second + 1 ) );
00343     if( direction == 2 )
00344         if( position.first + 1 == dimensions.second )
00345             return !IsExit( make_pair( position.first + 1, position.second ) );
00346     if( direction == 3 )
00347         if( position.second == 0 )
00348             return !IsExit( make_pair( position.first, position.second - 1 ) );
00349 
00350     
00351     // postioning in maze in order to find information if there is a wall that separates two fields  
00352     if( direction == 0 )
00353         position.first = position.first - 1;
00354     if( direction == 3 )
00355         position.second = position.second - 1;
00356 
00357     
00358 
00359     if( direction % 2 )
00360         if( maze[position.first][position.second] == 1 || maze[position.first][position.second] == 3 )
00361             return true;
00362         else return false;
00363     else
00364         if( maze[position.first][position.second] == 2 || maze[position.first][position.second] == 3 )
00365             return true;
00366         else return false;
00367 
00368 }
00369 
00370 int Maze::GetHeight()
00371 {
00372     return dimensions.second;
00373 }
00374 
00375 int Maze::GetWidth()
00376 {
00377     return dimensions.first;
00378 }
00379 
00380 /*
00381             Function returns shortest Euclidean distance to exit
00382             */
00383 double Maze::FindMetric(pair<int,int> currentPosition)
00384 {
00385     set<pair<int,int>>::iterator it;
00386     
00387     //      max distance in maze 30x30 is approx. 42
00388     double shortest = 100, tmp;
00389 
00390     for(it = exits.begin(); it != exits.end() ; it++)
00391     {
00392         //      tmp = ( (x2-x1)^2 + (y2-y1)^2 )^1/2
00393         tmp = sqrt( pow( (double)((*it).first - currentPosition.first), 2 ) + pow( (double)((*it).second - currentPosition.second), 2 ) ) ;
00394         
00395         if(tmp < shortest)
00396             shortest = tmp;
00397     }
00398     return shortest;
00399 }
00400 
00401 Maze::~Maze(void)
00402 {
00403 }

Generated on Fri Jul 13 2012 10:53:29 for ECF by  doxygen 1.7.1