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
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
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
00070
00071 if( Orientation )
00072 {
00073 wallPos = rand() % (width - 1);
00074
00075
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
00097 if( (int) (100.0 * ( rand() / (RAND_MAX + 1.0) ) ) < 30 && j <= (height / MazeMinSize) )
00098 j++;
00099 }
00100
00101
00102
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
00121 else
00122 {
00123 wallPos = rand() % (height - 1);
00124
00125
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
00147 if( (int) (100.0 * ( rand() / (RAND_MAX + 1.0) ) ) < 30 && j <= (width / MazeMinSize) )
00148 j++;
00149 }
00150
00151
00152
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
00176
00177
00178
00179
00180
00181
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
00200 for(int i = 0; i < dimensions.second; i++)
00201 {
00202
00203 allExits.insert(make_pair(i, minY));
00204
00205 allExits.insert(make_pair(i, maxY));
00206 }
00207
00208 for(int i = 0; i < dimensions.first; i++)
00209 {
00210
00211 allExits.insert(make_pair(minX, i));
00212
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
00231
00232
00233
00234 allExits.erase( make_pair((*it).first - 1, (*it).second) );
00235
00236
00237 allExits.erase( make_pair((*it).first + 1, (*it).second) );
00238
00239
00240 allExits.erase( make_pair((*it).first, (*it).second - 1) );
00241
00242
00243 allExits.erase( make_pair((*it).first, (*it).second + 1) );
00244
00245
00246 allExits.erase( make_pair((*it).first - 1, (*it).second - 1) );
00247
00248
00249 allExits.erase( make_pair((*it).first - 1, (*it).second + 1) );
00250
00251
00252 allExits.erase( make_pair((*it).first + 1, (*it).second - 1) );
00253
00254
00255 allExits.erase( make_pair((*it).first + 1, (*it).second + 1) );
00256
00257
00258 allExits.erase( *it );
00259 }
00260
00261 }
00262
00263
00264
00265
00266
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
00284
00285
00286
00287
00288
00289
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
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
00327
00328
00329
00330
00331
00332
00333
00334 bool Maze::IsThereWallAhead(pair<int,int> position, int direction)
00335 {
00336
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
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
00382
00383 double Maze::FindMetric(pair<int,int> currentPosition)
00384 {
00385 set<pair<int,int>>::iterator it;
00386
00387
00388 double shortest = 100, tmp;
00389
00390 for(it = exits.begin(); it != exits.end() ; it++)
00391 {
00392
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 }