F
felixnielsen
Some might remember that i, not so long ago, started a treath or two
about a weird 3d labyrinth. I now have a working code, that i want to
share, hear comments, advice, ect., but first let me explain what its
all about.
The whole labyrinth is a cubic in its self and it contains x^3 cubic
rooms.
The labyrinth is infinite/finite, it has no borders, but still have a
size.
fx. if the size of the labytrint is 2^3 and you find yourself at
coordinate 3,3,3 you're really finding your self at the coordinate
1,1,1.
Each room has 6 wall/possible doors, however, adjacent rooms shares a
wall, so we only need to keep track of three wall per room.
A wall can be set or unset, if unset, ofcourse there is nowall and your
free to move to the next room.
The grid pattern follow one simple room: "you must, at all time be able
to find a path from one room to another."
This tricky problem is solved by setting all walls in the labyrinth and
setting a start position at random, then picking a direction at random.
If the room in that direction have'nt been visited yet, brake down the
wall and move there and start over, else try again. If you cant move
any further, pop back to last position and start over from there. The
grid is ready when you are stuck at the start position.
The only question left should be: "what to use it for?"
Well, i can think of many options, but for a start lets just this of a
mouse in a labyrint ;-)
Last i would like to thank two people:
"Kai-Uwe Bux"
For helping me alot with the datastructure.
"someone i cant remember the name of"
For suplying the idea for the grid generation.
And ofcourse i want to thank everyone else for cutting a total n00b
some slag. ;-)
Now for the code:
@code start
#include <iostream>
#include <vector>
#include <bitset>
#include <ctime>
const unsigned short Size = 4; // 2^N
const unsigned short Log2 = 2; // N, log2(Size)
std::bitset<Size*Size*Size> YZ;
std::bitset<Size*Size*Size> XZ;
std::bitset<Size*Size*Size> XY;
std::bitset<Size*Size*Size> V;
struct Stack {
unsigned short z:Log2;
unsigned short y:Log2;
unsigned short x:Log2;
bool dir[6];
};
struct {
union {
struct {
unsigned short z:Log2;
unsigned short y:Log2;
unsigned short x:Log2;
};
unsigned long long id:Log2*3;
};
} pos;
short rand_int(short i) {
return rand() % i;
}
void new_grid() {
std::vector<Stack> stack(1);
bool loop = true;
YZ.set();
XZ.set();
XY.set();
V.set();
V.flip();
srand(time(0));
pos.x = rand_int(6);
pos.y = rand_int(6);
pos.z = rand_int(6);
V[pos.id] = 1;
stack.back().x = pos.x;
stack.back().y = pos.y;
stack.back().z = pos.z;
stack.resize(stack.size()+1);
while (stack.size() > 0) {
for (int choice = rand_int(6), loop = true;
loop == true;
choice = rand_int(6)) {
stack.back().dir[choice] = 1;
if (choice == 0) {
pos.x++;
if (V[pos.id] == 1) pos.x--;
else {
loop = false;
pos.x--;
YZ[pos.id] = 0;
pos.x++;
}
}
else if (choice == 1) {
pos.y++;
if (V[pos.id] == 1) pos.y--;
else {
loop = false;
pos.y--;
XZ[pos.id] = 0;
pos.y++;
}
}
else if (choice == 2) {
pos.z++;
if (V[pos.id] == 1) pos.z--;
else {
loop = false;
pos.z--;
XY[pos.id] = 0;
pos.z++;
}
}
else if (choice == 3) {
pos.x--;
if (V[pos.id] == 1) pos.x++;
else {
loop = false;
YZ[pos.id] = 0;
}
}
else if (choice == 4) {
pos.y--;
if (V[pos.id] == 1) pos.y++;
else {
loop = false;
XZ[pos.id] = 0;
}
}
else if (choice == 5) {
pos.z--;
if (V[pos.id] == 1) pos.z++;
else {
loop = false;
XY[pos.id] = 0;
}
}
if (loop == true &&
stack.back().dir[0]+stack.back().dir[1]+stack.back().dir[2]+
stack.back().dir[3]+stack.back().dir[4]+stack.back().dir[5]
== 6) {
loop = false;
stack.pop_back();
pos.x = stack.back().x;
pos.y = stack.back().y;
pos.z = stack.back().z;
}
else if (loop == false) {
V[pos.id] = 1;
stack.back().x = pos.x;
stack.back().y = pos.y;
stack.back().z = pos.z;
stack.resize(stack.size()+1);
}
}
//// temp progress overview ///////////
/**/ system("cls"); /**/
/**/ std::cout << YZ << std::endl; /**/
/**/ std::cout << XZ << std::endl; /**/
/**/ std::cout << XY << std::endl; /**/
/**/ std::cout << V; /**/
///////////////////////////////////////
}
}
int main() {
while (0==0)
new_grid();
}
@code end
Now, this code is ofcouse far from finished, but this actually work,
that is progress and should be celebrated.
Now the most important things to discuss would be:
1) the somewhat inapropiate union.
2) the resize(size()+1)
3) the Log2, Size
4) the last if loop witch doesnt look good at all ;-)
5) the grid generation code that is does indeed need some optimizing.
6) any other issue that you should find interesting.
NB.
This code does indeed need optimizing and altering but haven programed
for no longer than a month, theres still alot i dont know/understand,
so please give me some input.
Best
Zacariaz
about a weird 3d labyrinth. I now have a working code, that i want to
share, hear comments, advice, ect., but first let me explain what its
all about.
The whole labyrinth is a cubic in its self and it contains x^3 cubic
rooms.
The labyrinth is infinite/finite, it has no borders, but still have a
size.
fx. if the size of the labytrint is 2^3 and you find yourself at
coordinate 3,3,3 you're really finding your self at the coordinate
1,1,1.
Each room has 6 wall/possible doors, however, adjacent rooms shares a
wall, so we only need to keep track of three wall per room.
A wall can be set or unset, if unset, ofcourse there is nowall and your
free to move to the next room.
The grid pattern follow one simple room: "you must, at all time be able
to find a path from one room to another."
This tricky problem is solved by setting all walls in the labyrinth and
setting a start position at random, then picking a direction at random.
If the room in that direction have'nt been visited yet, brake down the
wall and move there and start over, else try again. If you cant move
any further, pop back to last position and start over from there. The
grid is ready when you are stuck at the start position.
The only question left should be: "what to use it for?"
Well, i can think of many options, but for a start lets just this of a
mouse in a labyrint ;-)
Last i would like to thank two people:
"Kai-Uwe Bux"
For helping me alot with the datastructure.
"someone i cant remember the name of"
For suplying the idea for the grid generation.
And ofcourse i want to thank everyone else for cutting a total n00b
some slag. ;-)
Now for the code:
@code start
#include <iostream>
#include <vector>
#include <bitset>
#include <ctime>
const unsigned short Size = 4; // 2^N
const unsigned short Log2 = 2; // N, log2(Size)
std::bitset<Size*Size*Size> YZ;
std::bitset<Size*Size*Size> XZ;
std::bitset<Size*Size*Size> XY;
std::bitset<Size*Size*Size> V;
struct Stack {
unsigned short z:Log2;
unsigned short y:Log2;
unsigned short x:Log2;
bool dir[6];
};
struct {
union {
struct {
unsigned short z:Log2;
unsigned short y:Log2;
unsigned short x:Log2;
};
unsigned long long id:Log2*3;
};
} pos;
short rand_int(short i) {
return rand() % i;
}
void new_grid() {
std::vector<Stack> stack(1);
bool loop = true;
YZ.set();
XZ.set();
XY.set();
V.set();
V.flip();
srand(time(0));
pos.x = rand_int(6);
pos.y = rand_int(6);
pos.z = rand_int(6);
V[pos.id] = 1;
stack.back().x = pos.x;
stack.back().y = pos.y;
stack.back().z = pos.z;
stack.resize(stack.size()+1);
while (stack.size() > 0) {
for (int choice = rand_int(6), loop = true;
loop == true;
choice = rand_int(6)) {
stack.back().dir[choice] = 1;
if (choice == 0) {
pos.x++;
if (V[pos.id] == 1) pos.x--;
else {
loop = false;
pos.x--;
YZ[pos.id] = 0;
pos.x++;
}
}
else if (choice == 1) {
pos.y++;
if (V[pos.id] == 1) pos.y--;
else {
loop = false;
pos.y--;
XZ[pos.id] = 0;
pos.y++;
}
}
else if (choice == 2) {
pos.z++;
if (V[pos.id] == 1) pos.z--;
else {
loop = false;
pos.z--;
XY[pos.id] = 0;
pos.z++;
}
}
else if (choice == 3) {
pos.x--;
if (V[pos.id] == 1) pos.x++;
else {
loop = false;
YZ[pos.id] = 0;
}
}
else if (choice == 4) {
pos.y--;
if (V[pos.id] == 1) pos.y++;
else {
loop = false;
XZ[pos.id] = 0;
}
}
else if (choice == 5) {
pos.z--;
if (V[pos.id] == 1) pos.z++;
else {
loop = false;
XY[pos.id] = 0;
}
}
if (loop == true &&
stack.back().dir[0]+stack.back().dir[1]+stack.back().dir[2]+
stack.back().dir[3]+stack.back().dir[4]+stack.back().dir[5]
== 6) {
loop = false;
stack.pop_back();
pos.x = stack.back().x;
pos.y = stack.back().y;
pos.z = stack.back().z;
}
else if (loop == false) {
V[pos.id] = 1;
stack.back().x = pos.x;
stack.back().y = pos.y;
stack.back().z = pos.z;
stack.resize(stack.size()+1);
}
}
//// temp progress overview ///////////
/**/ system("cls"); /**/
/**/ std::cout << YZ << std::endl; /**/
/**/ std::cout << XZ << std::endl; /**/
/**/ std::cout << XY << std::endl; /**/
/**/ std::cout << V; /**/
///////////////////////////////////////
}
}
int main() {
while (0==0)
new_grid();
}
@code end
Now, this code is ofcouse far from finished, but this actually work,
that is progress and should be celebrated.
Now the most important things to discuss would be:
1) the somewhat inapropiate union.
2) the resize(size()+1)
3) the Log2, Size
4) the last if loop witch doesnt look good at all ;-)
5) the grid generation code that is does indeed need some optimizing.
6) any other issue that you should find interesting.
NB.
This code does indeed need optimizing and altering but haven programed
for no longer than a month, theres still alot i dont know/understand,
so please give me some input.
Best
Zacariaz
