In
this thread here, Pascalosti came up with a maze algorithm which needed work. So it was refactored in C++, then redone and upgraded in Python and O'Caml. So I figured why not have a Scheme version as well? So the exercise --optional of course-- is to implement this algorithm in Scheme and (again, optional) add some bells and whistles to it as well.
Here's the idea by the author:
Quote:
Original Post by Pascalosti
Its really ugly...
The objective
Make 10x10 square, with a border, start and end spot position.
Inside the square: Setup random squares either wall square or walk square
The walk squares have to be connected so you can walk from start to
end position.
It works but its... ugly
Here's the original code:
int level1[ArraySize*ArraySize] = {
44,44,44,44,44,44,44,44,44,44,
33,44,44,55,55,55,55,55,55,44,
44,44,44,44,55,44,55,44,55,44,
44,44,44,55,55,55,55,55,55,44,
44,44,44,55,55,55,55,55,55,44,
44,44,44,55,55,55,44,44,44,44,
44,44,44,55,55,55,44,44,44,44,
44,44,44,44,44,44,44,44,44,44,
44,44,44,44,44,44,44,44,44,77,
44,77,44,44,44,44,44,44,44,44
};// these numbers all get changed except 33 and 77
// 33 start walk square
// 77 end walk square
// 66 outside border
// 22 walls
// 55 walking squares
int RandNum(int n){
return rand() % n;
}// end random number generator
void SetUpMap(){
srand(time(NULL));
bool RandomNumber;
int x = 0;
int y = 0;
for(int i = 0; i < (ArraySize * ArraySize);i++){
x++;
if(x == ArraySize){
x = 0;
y++;
}
// set up outside walls
if(x == 0 || y == 0)
if(x == 0 && y == 1)// start location
level1[x + y * ArraySize] = 33;
else
// outside borders show as walls
level1[x + y * ArraySize] = 66;
else if(x == (ArraySize-1) || y == (ArraySize-1))
// end location
if(x == (ArraySize-1) && y == (ArraySize-2))
level1[x+y * ArraySize] = 77;
else
//outside border show as walls
level1[x + y * (ArraySize)] = 66;
// make sure squares beside start and end are walking space
else if(level1[x-1 + y * ArraySize] == 33 || level1[x+1 + y * ArraySize] == 77)
// walking space
level1[x+y * ArraySize] = 55;
else{
// rest of the square gets filled with either 22(walls) or 55(walking square)
RandomNumber = RandNum(2);
if(RandomNumber)
// walls
level1[x+y * ArraySize] = 22;
else
level1[x+y * ArraySize] = 55; // walking space
}// end first else
}// end first for loop creates random squares and borders
//a new loop to makes sure walk is connected to anothere
// supposed to connect from the start square to end square
int XX = 0;
int YY = 0;
int count = 0;
bool top = false;
bool bottom = false;
bool right = false;
bool left = false;
bool WallHasNotBeenChanged = true;
for(int i = 0; i < (ArraySize * ArraySize);i++){
XX++;
if(XX == ArraySize){
YY++;
XX = 0;
}
// only check walk blocks
if(level1[XX + YY * ArraySize] == 55){
// check how many walls surround walk block
if(level1[XX-1 + YY * ArraySize] == 22){
count++;
left = true;
}
if(level1[XX+1 + YY * ArraySize] == 22){
count++;
right = true;
}
if(level1[XX + YY-1 * ArraySize] == 22){
count++;
bottom = true;
}
if(level1[XX + YY+1 * ArraySize] == 22){
count++;
top = true;
}
}
// if more walls then ... surround this walk add more walk squares
if(count > 1){// this number should be at 2
// before i had a random number choose them
// which did not work so well
if(left)
level1[XX-1 + YY * ArraySize] = 55;
if(right)
level1[XX+1 + YY * ArraySize] = 55;
if(bottom)
level1[XX + YY-1 * ArraySize] = 55;
if(top)
level1[XX + YY+1 * ArraySize] = 55;
}// end count if
// set numbers back
count = 0;
top = false;
bottom = false;
right = false;
left = false;
}// end second for loop makes sure walking squares are connected
}// end setupmap function
