By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
458,083 Members | 1,274 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 458,083 IT Pros & Developers. It's quick & easy.

Some working code for a change...

P: n/a
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

Feb 17 '06 #1
Share this Question
Share on Google+
19 Replies


P: n/a

<fe**********@hotmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
: 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 {
NB: anonymous struct members are not a
standard/portable feature of C++

: unsigned short z:Log2;
: unsigned short y:Log2;
: unsigned short x:Log2;
: };
: unsigned long long id:Log2*3;
: };
You are indeed playing with fire here.
Furthermore, using bit-fields might be
a performance pessimization rather than
an optimization. Have you checked ?

: } pos;
: short rand_int(short i) {
: return rand() % i;
Using upper bits of the value returned by
rand() usually provides better 'randomness',
but this might not a big deal here...

: }
: void new_grid() {
: std::vector<Stack> stack(1);
: bool loop = true;
NB: in C++, it is seen as a best practice to
declare local variables just before use,
as late as possible.

: YZ.set();
: XZ.set();
: XY.set();
: V.set();
: V.flip();
NB: V.reset() is equivalent to set() + flip()

: srand(time(0));
: pos.x = rand_int(6);
: pos.y = rand_int(6);
: pos.z = rand_int(6);
'6' is not the range of values you want
for pos ! --> 'Size' instead

: V[pos.id] = 1;
If this works on your platform, it is by
pure chance.
It is much better to use direcly:
V[ pos.x + Size*(pos.y+Size*pos.z) ]
( possibly have an inline function
to write V[ makeIndex(x,y,z)] )
And you could get rid of the 'pos' variable
altogether (replace with:
unsigned short posx, posy, posz; )

: stack.back().x = pos.x;
: stack.back().y = pos.y;
: stack.back().z = pos.z;
: stack.resize(stack.size()+1);
What you need to do is first create an
element of type 'Stack' (really a stack item),
and then call:
Stack item;
item.x = pos.x;
item.y = pos.y;
item.z = pos.z;
stack.push_back( item );
Even better: add a constructor to struct Stack
that takes the x,y,z position as a parameter.

: while (stack.size() > 0) {
or: while( ! stack.empty() ) // cleaner IMO

: for (int choice = rand_int(6), loop = true;
: loop == true;
: choice = rand_int(6)) {
Get rid of this inner loop (see below).
Keep 'choice' as a first statement:
int choice = rand_int(6);
Also:
bool loop = true; // if needed...

: stack.back().dir[choice] = 1;
You should first check that dir[choice] is zero,
otherwise you can skip all the rest:
if( stack.back().dir[choice]!=0 ) continue;

Instead of the chain of if-s, you really
should use:
switch( choice ) {
case 0: ...
case 1: ...
etc.
}
: 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);
: }
if( ! loop ) {
V.set( makeInd[posx,posy,posz] );
stack.push_back( StackItem(posx,posy,posz) )
{
else if( ... all directions are clear ... ) {
stack.pop_back();
}
// no need for the additional inner loop,
// all happens through the stack

: }
: //// 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.
It's a no-no. Use a member function that returns an
index, or a separate index-making function.
The bitfields are an unnecessary pessimization.

: 2) the resize(size()+1)
Use push_back, add a constructor for your stack element.

: 3) the Log2, Size
Log2 is unnecessary if you get rid of all the bitfields.

: 4) the last if loop witch doesnt look good at all ;-)
Get rid of it.
Also keep in mind that you can use continue; / break;

: 5) the grid generation code that is does indeed need some optimizing.
See notes in the code to make shallower 'mis-hits'.
Insead of a bool dir[6] array, you could use
some bit arithmetic:
unsigned char dirFlags;
First initialize it with 0 (all bits cleared).
Then:
bool dirWasVisited = 0!=( dirFlags&(1<<choice) );
To set as visited:
dirFlags |= (1<<choice);
To check if all was visited:
bool allVisited = ( dirFlags == (1<<6)-1 );

: 6) any other issue that you should find interesting.
In the worst case, you could recurce (i.e. add items
to the stack) as deeply as pow(Size,3), which could
be a performance problem, and might not be what you want.
There could be other approaches...

: 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.
Not bad at all for someone who just got started ;)
I hope this helps,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Feb 17 '06 #2

P: n/a

Ivan Vecerina skrev:
<fe**********@hotmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
: 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 {
NB: anonymous struct members are not a
standard/portable feature of C++
ok, have seen it used alot, so i didnt see this of it as a problem, it
does however have solution.

: unsigned short z:Log2;
: unsigned short y:Log2;
: unsigned short x:Log2;
: };
: unsigned long long id:Log2*3;
: };
You are indeed playing with fire here.
Furthermore, using bit-fields might be
a performance pessimization rather than
an optimization. Have you checked ?
In this case where the bitfield is 2, let me explain why i have done
it.
@code start
pos.x = 3;
pos.x++;
// pos x should contain the value 0 now.
@code end

I know its now the wises way to go around that problem, but i my
oppinion the easyest.
Otherwise i have to check the number everytime i want to increement or
decreement it.

: } pos;
: short rand_int(short i) {
: return rand() % i;
Using upper bits of the value returned by
rand() usually provides better 'randomness',
but this might not a big deal here...
i asure you this is not a problem.

: }
: void new_grid() {
: std::vector<Stack> stack(1);
: bool loop = true;
NB: in C++, it is seen as a best practice to
declare local variables just before use,
as late as possible.
Ok, you learn every day; ;-)

: YZ.set();
: XZ.set();
: XY.set();
: V.set();
: V.flip();
NB: V.reset() is equivalent to set() + flip()
ofcourse.

: srand(time(0));
: pos.x = rand_int(6);
: pos.y = rand_int(6);
: pos.z = rand_int(6);
'6' is not the range of values you want
for pos ! --> 'Size' instead
a little typo, thanks for noticing ;-)

: V[pos.id] = 1;
If this works on your platform, it is by
pure chance.
It is much better to use direcly:
V[ pos.x + Size*(pos.y+Size*pos.z) ]
( possibly have an inline function
to write V[ makeIndex(x,y,z)] )
And you could get rid of the 'pos' variable
altogether (replace with:
unsigned short posx, posy, posz; )
Ya, i allready know this, and ill change it when feel like it, however
i need a solution for bitfield problem before i can get rit of 'pos'
alltogether.

: stack.back().x = pos.x;
: stack.back().y = pos.y;
: stack.back().z = pos.z;
: stack.resize(stack.size()+1);
What you need to do is first create an
element of type 'Stack' (really a stack item),
and then call:
Stack item;
item.x = pos.x;
item.y = pos.y;
item.z = pos.z;
stack.push_back( item );
Even better: add a constructor to struct Stack
that takes the x,y,z position as a parameter.
Here im just confused, i have ofcourse hear the expression
"constructor" but isnt it something to use in classes and how cant it
solve the problem?

: while (stack.size() > 0) {
or: while( ! stack.empty() ) // cleaner IMO
Indeed...
: for (int choice = rand_int(6), loop = true;
: loop == true;
: choice = rand_int(6)) {
Get rid of this inner loop (see below).
Keep 'choice' as a first statement:
int choice = rand_int(6);
Also:
bool loop = true; // if needed...
i have tryed, but i keep failing...
: stack.back().dir[choice] = 1;
You should first check that dir[choice] is zero,
otherwise you can skip all the rest:
if( stack.back().dir[choice]!=0 ) continue;
Im somewhat confused here...

Instead of the chain of if-s, you really
should use:
switch( choice ) {
case 0: ...
case 1: ...
etc.
}
allready done ;-)
: 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);
: }
if( ! loop ) {
V.set( makeInd[posx,posy,posz] );
stack.push_back( StackItem(posx,posy,posz) )
{
else if( ... all directions are clear ... ) {
stack.pop_back();
}
// no need for the additional inner loop,
// all happens through the stack

: }
: //// 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.
It's a no-no. Use a member function that returns an
index, or a separate index-making function.
The bitfields are an unnecessary pessimization.
Some stuff ecplained above...

: 2) the resize(size()+1)
Use push_back, add a constructor for your stack element.
Did that, but i ended up with twice the lengt it is now, dont ask me
why, never the less it seemed like a bad idea at the time.

: 3) the Log2, Size
Log2 is unnecessary if you get rid of all the bitfields.
But until i find a solution for the ++/-- problem explained above...

: 4) the last if loop witch doesnt look good at all ;-)
Get rid of it.
Also keep in mind that you can use continue; / break;
Again pretty confused...

: 5) the grid generation code that is does indeed need some optimizing.
See notes in the code to make shallower 'mis-hits'.
Insead of a bool dir[6] array, you could use
some bit arithmetic:
unsigned char dirFlags;
First initialize it with 0 (all bits cleared).
Then:
bool dirWasVisited = 0!=( dirFlags&(1<<choice) );
To set as visited:
dirFlags |= (1<<choice);
To check if all was visited:
bool allVisited = ( dirFlags == (1<<6)-1 );
ya....

: 6) any other issue that you should find interesting.
In the worst case, you could recurce (i.e. add items
to the stack) as deeply as pow(Size,3), which could
be a performance problem, and might not be what you want.
There could be other approaches...
Im listening...

: 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.
Not bad at all for someone who just got started ;)
While thank you ;-)

I hope this helps,
Ivan


This must have taken a great deal of time to go trough, so i just want
to say thank you ;-)

Best
Zacariaz

Feb 17 '06 #3

P: n/a
Code altered a bit.

@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.reset();
srand(time(0));
pos.x = rand_int(Size);
pos.y = rand_int(Size);
pos.z = rand_int(Size);
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.empty()) {
for (int choice = rand_int(6), loop = true;
loop; choice = rand_int(6)) {
stack.back().dir[choice] = 1;
switch(choice) {
case 0:
pos.x++;
if (V[pos.id] == 1) pos.x--;
else {
loop = false;
pos.x--;
YZ[pos.id] = 0;
pos.x++;
}
break;
case 1:
pos.y++;
if (V[pos.id] == 1) pos.y--;
else {
loop = false;
pos.y--;
XZ[pos.id] = 0;
pos.y++;
}
break;
case 2:
pos.z++;
if (V[pos.id] == 1) pos.z--;
else {
loop = false;
pos.z--;
XY[pos.id] = 0;
pos.z++;
}
break;
case 3:
pos.x--;
if (V[pos.id] == 1) pos.x++;
else {
loop = false;
YZ[pos.id] = 0;
}
break;
case 4:
pos.y--;
if (V[pos.id] == 1) pos.y++;
else {
loop = false;
XZ[pos.id] = 0;
}
break;
case 5:
pos.z--;
if (V[pos.id] == 1) pos.z++;
else {
loop = false;
XY[pos.id] = 0;
}
break;
}
if (!loop) {
V[pos.id] = 1;
stack.back().x = pos.x;
stack.back().y = pos.y;
stack.back().z = pos.z;
stack.resize(stack.size()+1);
}
else if (stack.back().dir[0] == 1 && stack.back().dir[1] == 1 &&
stack.back().dir[2] == 1 && stack.back().dir[3] == 1 &&
stack.back().dir[4] == 1 && stack.back().dir[5] == 1) {
loop = false;
stack.pop_back();
pos.x = stack.back().x;
pos.y = stack.back().y;
pos.z = stack.back().z;
}
}
//// 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 (true)
new_grid();
}
@code end

Feb 17 '06 #4

P: n/a
<fe**********@hotmail.com> wrote in message
news:11**********************@g44g2000cwa.googlegr oups.com...
: In this case where the bitfield is 2, let me explain
: why i have done it.
: @code start
: pos.x = 3;
: pos.x++;
: // pos x should contain the value 0 now.

Right. But it is easier and more portable to write:
pos.x = (pos.x+1)%Size;
or:
pos.x = (pos.x==Size-1) ? 0 : pos.x+1;
Why would you require Size to be a power of 2 ?

: @code end
:
: I know its now the wises way to go around that problem, but i my
: oppinion the easyest.
: Otherwise i have to check the number everytime i want to increement or
: decreement it.
Not such a big deal, really.

: > : stack.back().x = pos.x;
: > : stack.back().y = pos.y;
: > : stack.back().z = pos.z;
: > : stack.resize(stack.size()+1);
: > What you need to do is first create an
: > element of type 'Stack' (really a stack item),
: > and then call:
: > Stack item;
: > item.x = pos.x;
: > item.y = pos.y;
: > item.z = pos.z;
: > stack.push_back( item );
: > Even better: add a constructor to struct Stack
: > that takes the x,y,z position as a parameter.
:
: Here im just confused, i have ofcourse hear the expression
: "constructor" but isnt it something to use in classes and how cant it
: solve the problem?

struct StackItem {
unsigned short x,y,z;
unsigned char testedDirs;

StackItem( unsigned short ix, unsigned short iy, unsigned short iz )
: x(ix), y(iy), z(iz)
, testedDirs(0)
{ }
};

std::vector<StackItem> stack;

stack.push_back( StackItem(posx,posy,posz) );

: >
: > : while (stack.size() > 0) {
: > or: while( ! stack.empty() ) // cleaner IMO
:
: Indeed...
: >
: > : for (int choice = rand_int(6), loop = true;
: > : loop == true;
: > : choice = rand_int(6)) {
: > Get rid of this inner loop (see below).
: > Keep 'choice' as a first statement:
: > int choice = rand_int(6);
: > Also:
: > bool loop = true; // if needed...
:
: i have tryed, but i keep failing...
: >
: > : stack.back().dir[choice] = 1;
: > You should first check that dir[choice] is zero,
: > otherwise you can skip all the rest:
: > if( stack.back().dir[choice]!=0 ) continue;
:
: Im somewhat confused here...

By calling repeatedly picking a random direction,
you will be checking the same direction a few
times again and again. Since you are remembering
already which directions where visited, you
can test it directly.

: > : 4) the last if loop witch doesnt look good at all ;-)
: > Get rid of it.
: > Also keep in mind that you can use continue; / break;
:
: Again pretty confused...

Pseudocode:
stack.push_back( start_pos );
for(;;) { // infinite loop, will exit with break
if( stack.back().allDirectionsWereVisited() )
{
stack.pop_back();
if( stack.empty() ) break; else continue;
}

// pick a neighbor and process it

if( need to further explore from neighbor )
{
stack.push_back( neighbor_pos );
}
}

: >
: > : 5) the grid generation code that is does indeed need some
optimizing.
: > See notes in the code to make shallower 'mis-hits'.
: > Insead of a bool dir[6] array, you could use
: > some bit arithmetic:
: > unsigned char dirFlags;
: > First initialize it with 0 (all bits cleared).
: > Then:
: > bool dirWasVisited = 0!=( dirFlags&(1<<choice) );
: > To set as visited:
: > dirFlags |= (1<<choice);
: > To check if all was visited:
: > bool allVisited = ( dirFlags == (1<<6)-1 );
:
: ya....
:
: >
: > : 6) any other issue that you should find interesting.
: > In the worst case, you could recurce (i.e. add items
: > to the stack) as deeply as pow(Size,3), which could
: > be a performance problem, and might not be what you want.
: > There could be other approaches...
:
: Im listening...

It is also about choosing the 'branchingness' of your
labyrinth: instead of looking from the top of the stack,
you could more randomly pick a cell (on the stack) from
which to extend your visit. (wouldn't guarantee a better
worst-case memory usage, only better average mem use).
There could be other ways to represent the backtracking
info, but in fact, at this stage, you probably shouldn't
worry about this...
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Feb 17 '06 #5

P: n/a

Ivan Vecerina skrev:
<fe**********@hotmail.com> wrote in message
news:11**********************@g44g2000cwa.googlegr oups.com...
: In this case where the bitfield is 2, let me explain
: why i have done it.
: @code start
: pos.x = 3;
: pos.x++;
: // pos x should contain the value 0 now.

Right. But it is easier and more portable to write:
pos.x = (pos.x+1)%Size;
or:
pos.x = (pos.x==Size-1) ? 0 : pos.x+1;
Why would you require Size to be a power of 2 ?
wasnt aware of those options and the second one i simply doesnt
understand.
If im not using bitfields it does have to be the power of 2.
: @code end
:
: I know its now the wises way to go around that problem, but i my
: oppinion the easyest.
: Otherwise i have to check the number everytime i want to increement or
: decreement it.
Not such a big deal, really.
I know now ;-)
: > : stack.back().x = pos.x;
: > : stack.back().y = pos.y;
: > : stack.back().z = pos.z;
: > : stack.resize(stack.size()+1);
: > What you need to do is first create an
: > element of type 'Stack' (really a stack item),
: > and then call:
: > Stack item;
: > item.x = pos.x;
: > item.y = pos.y;
: > item.z = pos.z;
: > stack.push_back( item );
: > Even better: add a constructor to struct Stack
: > that takes the x,y,z position as a parameter.
:
: Here im just confused, i have ofcourse hear the expression
: "constructor" but isnt it something to use in classes and how cant it
: solve the problem?

struct StackItem {
unsigned short x,y,z;
unsigned char testedDirs;

StackItem( unsigned short ix, unsigned short iy, unsigned short iz )
: x(ix), y(iy), z(iz)
, testedDirs(0)
{ }
};

std::vector<StackItem> stack;

stack.push_back( StackItem(posx,posy,posz) );
hmm, have to give this a thought...

: >
: > : while (stack.size() > 0) {
: > or: while( ! stack.empty() ) // cleaner IMO
:
: Indeed...
: >
: > : for (int choice = rand_int(6), loop = true;
: > : loop == true;
: > : choice = rand_int(6)) {
: > Get rid of this inner loop (see below).
: > Keep 'choice' as a first statement:
: > int choice = rand_int(6);
: > Also:
: > bool loop = true; // if needed...
:
: i have tryed, but i keep failing...
: >
: > : stack.back().dir[choice] = 1;
: > You should first check that dir[choice] is zero,
: > otherwise you can skip all the rest:
: > if( stack.back().dir[choice]!=0 ) continue;
:
: Im somewhat confused here...

By calling repeatedly picking a random direction,
you will be checking the same direction a few
times again and again. Since you are remembering
already which directions where visited, you
can test it directly.
Now i understand you.
Again i tryed, and came up with something should have worked, but it
didnt, have yet to come up with the right code.

: > : 4) the last if loop witch doesnt look good at all ;-)
: > Get rid of it.
: > Also keep in mind that you can use continue; / break;
:
: Again pretty confused...

Pseudocode:
stack.push_back( start_pos );
for(;;) { // infinite loop, will exit with break
if( stack.back().allDirectionsWereVisited() )
{
stack.pop_back();
if( stack.empty() ) break; else continue;
}

// pick a neighbor and process it

if( need to further explore from neighbor )
{
stack.push_back( neighbor_pos );
}
}

: >
: > : 5) the grid generation code that is does indeed need some
optimizing.
: > See notes in the code to make shallower 'mis-hits'.
: > Insead of a bool dir[6] array, you could use
: > some bit arithmetic:
: > unsigned char dirFlags;
: > First initialize it with 0 (all bits cleared).
: > Then:
: > bool dirWasVisited = 0!=( dirFlags&(1<<choice) );
: > To set as visited:
: > dirFlags |= (1<<choice);
: > To check if all was visited:
: > bool allVisited = ( dirFlags == (1<<6)-1 );
:
: ya....
:
: >
: > : 6) any other issue that you should find interesting.
: > In the worst case, you could recurce (i.e. add items
: > to the stack) as deeply as pow(Size,3), which could
: > be a performance problem, and might not be what you want.
: > There could be other approaches...
:
: Im listening...

It is also about choosing the 'branchingness' of your
labyrinth: instead of looking from the top of the stack,
you could more randomly pick a cell (on the stack) from
which to extend your visit. (wouldn't guarantee a better
worst-case memory usage, only better average mem use).
There could be other ways to represent the backtracking
info, but in fact, at this stage, you probably shouldn't
worry about this...

k then, havent got time for more comment right now, but thank again.

Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form


Feb 17 '06 #6

P: n/a
<fe**********@hotmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
:
: Ivan Vecerina skrev:
:
: > <fe**********@hotmail.com> wrote in message
: > news:11**********************@g44g2000cwa.googlegr oups.com...
: > : In this case where the bitfield is 2, let me explain
: > : why i have done it.
: > : @code start
: > : pos.x = 3;
: > : pos.x++;
: > : // pos x should contain the value 0 now.
: >
: > Right. But it is easier and more portable to write:
: > pos.x = (pos.x+1)%Size;
: > or:
: > pos.x = (pos.x==Size-1) ? 0 : pos.x+1;
: > Why would you require Size to be a power of 2 ?
:
: wasnt aware of those options and the second one i simply doesnt
: understand.
: If im not using bitfields it does have to be the power of 2.

With bitfields you have to.
With the above you can use any wrap-around size.

The ( x ? a : b ) expression is interpreted as follows:
- if x is true, then use the value a
- if x is false, then use the value b

So you can write, when incrementing:
newPos = (pos==Size-1) ? 0 : pos+1 ;
when decrementing:
newPos = (pos==0) ? Size-1 : pos-1 ;
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Feb 17 '06 #7

P: n/a

Ivan Vecerina skrev:
<fe**********@hotmail.com> wrote in message
news:11**********************@z14g2000cwz.googlegr oups.com...
:
: Ivan Vecerina skrev:
:
: > <fe**********@hotmail.com> wrote in message
: > news:11**********************@g44g2000cwa.googlegr oups.com...
: > : In this case where the bitfield is 2, let me explain
: > : why i have done it.
: > : @code start
: > : pos.x = 3;
: > : pos.x++;
: > : // pos x should contain the value 0 now.
: >
: > Right. But it is easier and more portable to write:
: > pos.x = (pos.x+1)%Size;
: > or:
: > pos.x = (pos.x==Size-1) ? 0 : pos.x+1;
: > Why would you require Size to be a power of 2 ?
:
: wasnt aware of those options and the second one i simply doesnt
: understand.
: If im not using bitfields it does have to be the power of 2. sry, i meant to write doesnt
With bitfields you have to.
With the above you can use any wrap-around size.

The ( x ? a : b ) expression is interpreted as follows:
- if x is true, then use the value a
- if x is false, then use the value b

So you can write, when incrementing:
newPos = (pos==Size-1) ? 0 : pos+1 ;
when decrementing:
newPos = (pos==0) ? Size-1 : pos-1 ;
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form


Feb 17 '06 #8

P: n/a
I have tryed to do some class thingy, my first time, and it seems to
work, however im somewhat stuck, dont really know where to go from
here.
I guess ill figure it out sooner or later, but if anyone want to
help/comment, heres the code:

@code start
#include <iostream>
#include <bitset>
#include <vector>
class Grid {
private:
static const unsigned int Size = 3; // max 1625 (0xffffffff^(1/3))
std::bitset<Size*Size*Size> YZ;
std::bitset<Size*Size*Size> XZ;
std::bitset<Size*Size*Size> XY;
std::bitset<Size*Size*Size> V;
unsigned int x,y,z;
unsigned int Rand_int(unsigned int i) {return rand() % i;}
void Inc_x() {x = (x==Size-1) ? 0 : x+1;}
void Inc_y() {y = (y==Size-1) ? 0 : y+1;}
void Inc_z() {z = (z==Size-1) ? 0 : z+1;}
void Dec_x() {x = (x==0) ? Size-1 : x-1;}
void Dec_y() {y = (y==0) ? Size-1 : y-1;}
void Dec_z() {z = (z==0) ? Size-1 : z-1;}
unsigned long Get_id() {return x*Size*Size+y*Size+z;}
public:
void New();
};
void Grid::New() {
srand(time(0));
x = Rand_int(Size);
y = Rand_int(Size);
z = Rand_int(Size);
YZ.set();
XZ.set();
XY.set();
V.reset();
std::vector<unsigned char> stack;
unsigned char back_stack;
}
/////////////////////////////////////////////////
// I've desided that i can get by with eigth //
// bits only. 3 to keep track on where we came //
// from and 5 to keep track on the rooms we //
// have/havent investigated, its a tricky one, //
// but i think i cant be done. Somehow... //
/////////////////////////////////////////////////
@code end

Best reagards
Zacariaz

Feb 18 '06 #9

P: n/a
<fe**********@hotmail.com> wrote in message
news:11*********************@g43g2000cwa.googlegro ups.com...
:I have tryed to do some class thingy, my first time, and it seems to
: work, however im somewhat stuck, dont really know where to go from
: here.
I think it's time for you to do some reading and studying.
If you're not ready to buy a dead-tree book, you can start with
some that are available online, such as "Thinking in C++" from
Bruce Eckel:
http://www.mindview.net/Books/TICPP/...ngInCPP2e.html

: I guess ill figure it out sooner or later, but if anyone want to
: help/comment, heres the code:
:
: @code start
: #include <iostream>
: #include <bitset>
: #include <vector>
: class Grid {
: private:
: static const unsigned int Size = 3; // max 1625 (0xffffffff^(1/3))
: std::bitset<Size*Size*Size> YZ;
: std::bitset<Size*Size*Size> XZ;
: std::bitset<Size*Size*Size> XY;
: std::bitset<Size*Size*Size> V;
: unsigned int x,y,z;
: unsigned int Rand_int(unsigned int i) {return rand() % i;}
: void Inc_x() {x = (x==Size-1) ? 0 : x+1;}
: void Inc_y() {y = (y==Size-1) ? 0 : y+1;}
: void Inc_z() {z = (z==Size-1) ? 0 : z+1;}
: void Dec_x() {x = (x==0) ? Size-1 : x-1;}
: void Dec_y() {y = (y==0) ? Size-1 : y-1;}
: void Dec_z() {z = (z==0) ? Size-1 : z-1;}
: unsigned long Get_id() {return x*Size*Size+y*Size+z;}
: public:
: void New();
NB: you actually want this to be a constructor:
Grid();
: };
: void Grid::New() {
: srand(time(0));
: x = Rand_int(Size);
: y = Rand_int(Size);
: z = Rand_int(Size);
: YZ.set();
: XZ.set();
: XY.set();
: V.reset();
: std::vector<unsigned char> stack;
: unsigned char back_stack;
: }
: /////////////////////////////////////////////////
: // I've desided that i can get by with eigth //
: // bits only. 3 to keep track on where we came //
: // from and 5 to keep track on the rooms we //
: // have/havent investigated, its a tricky one, //
: // but i think i cant be done. Somehow... //
: /////////////////////////////////////////////////
: @code end
Read chapter 4 and following in vol. 1 above.

First of all, each object/class needs to have a single
purpose/responsibility.
It probably makes sense to have one class that stores
the structure of your labyrinth.
A position in the labyrinth probably should be an
independent class/object. Because, for example, you
could have multiple entities moving through the same
labyrinth.
If it is simple, the labyrinth-generator does not
need to be an object, but could be a single function.
Enjoy the journey,
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form
Feb 18 '06 #10

P: n/a

Ivan Vecerina skrev:
<fe**********@hotmail.com> wrote in message
news:11*********************@g43g2000cwa.googlegro ups.com...
:I have tryed to do some class thingy, my first time, and it seems to
: work, however im somewhat stuck, dont really know where to go from
: here.
I think it's time for you to do some reading and studying.
If you're not ready to buy a dead-tree book, you can start with
some that are available online, such as "Thinking in C++" from
Bruce Eckel:
i have allready done lots of reading, however i have been in need of
some quality net books so thak you for the link.
http://www.mindview.net/Books/TICPP/...ngInCPP2e.html

: I guess ill figure it out sooner or later, but if anyone want to
: help/comment, heres the code:
:
: @code start
: #include <iostream>
: #include <bitset>
: #include <vector>
: class Grid {
: private:
: static const unsigned int Size = 3; // max 1625 (0xffffffff^(1/3))
: std::bitset<Size*Size*Size> YZ;
: std::bitset<Size*Size*Size> XZ;
: std::bitset<Size*Size*Size> XY;
: std::bitset<Size*Size*Size> V;
: unsigned int x,y,z;
: unsigned int Rand_int(unsigned int i) {return rand() % i;}
: void Inc_x() {x = (x==Size-1) ? 0 : x+1;}
: void Inc_y() {y = (y==Size-1) ? 0 : y+1;}
: void Inc_z() {z = (z==Size-1) ? 0 : z+1;}
: void Dec_x() {x = (x==0) ? Size-1 : x-1;}
: void Dec_y() {y = (y==0) ? Size-1 : y-1;}
: void Dec_z() {z = (z==0) ? Size-1 : z-1;}
: unsigned long Get_id() {return x*Size*Size+y*Size+z;}
: public:
: void New();
NB: you actually want this to be a constructor:
Ya, i though of that too, however, im only trying to learn how classes
funtion, by converting this code, so bare with me it is my first class
;-)
Grid();
: };
: void Grid::New() {
: srand(time(0));
: x = Rand_int(Size);
: y = Rand_int(Size);
: z = Rand_int(Size);
: YZ.set();
: XZ.set();
: XY.set();
: V.reset();
: std::vector<unsigned char> stack;
: unsigned char back_stack;
: }
: /////////////////////////////////////////////////
: // I've desided that i can get by with eigth //
: // bits only. 3 to keep track on where we came //
: // from and 5 to keep track on the rooms we //
: // have/havent investigated, its a tricky one, //
: // but i think i cant be done. Somehow... //
: /////////////////////////////////////////////////
: @code end
Read chapter 4 and following in vol. 1 above.
I will definently do that.

First of all, each object/class needs to have a single
purpose/responsibility.
It probably makes sense to have one class that stores
the structure of your labyrinth.
A position in the labyrinth probably should be an
independent class/object. Because, for example, you
could have multiple entities moving through the same
labyrinth.
If it is simple, the labyrinth-generator does not
need to be an object, but could be a single function.
Thanks for the hint.
Enjoy the journey,
He, im sure i will ;)
Ivan
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form


Feb 18 '06 #11

P: n/a
This actually work quite well...
Any comments?

@code start
#include <iostream>
#include <ctime>
#include <bitset>
#include <vector>
#include <cmath>
const unsigned int Size = 16;
class Random {
public:
Random() {srand(time(0));}
~Random() {}
unsigned int N(unsigned int n) {return rand() % n;}
};
class Coordinate {
private:
unsigned int n;
public:
Coordinate() {}
~Coordinate() {}
unsigned int Get() {return n;}
void Put(unsigned int i) {n = i;}
void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
};
class Position {
private:
Coordinate x, y, z;
public:
Position() {
Random *R = 0;
R = new Random;
x.Put(R->N(Size));
y.Put(R->N(Size));
z.Put(R->N(Size));
delete R;
}
~Position() {}
unsigned long Id() {return x.Get()*Size*Size+y.Get()*Size+z.Get();}
};
class Stack {
private:
std::vector<char> stack;
char c;
void Put_Back(){}
unsigned short Get_Back() {}
public:
Stack() {}
~Stack() {}
void Put_Dir() {}
void Put_Door(unsigned short n, bool b) {}
unsigned short Get_Dir() {}
bool Get_Door(unsigned short n) {}
void Next() {}
};
class Grid {
private:
Position Pos;
Random R;
Stack stack;
std::bitset<Size*Size*Size> yz, xz, xy, v;
public:
Grid() {
yz.set();
xz.set();
xy.set();
v.reset();
}
~Grid() {}
};
int main() {
Grid *Cube = 0;
Cube = new Grid;
delete Cube;
}
@code end

Regards

Feb 20 '06 #12

P: n/a
In article <11**********************@g47g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
This actually work quite well...
Any comments?
No, no comments at all. As in you have no comments in your code. :-)

Seriously, I have some style comments.

White space is your friend, use it. More <cr>s between classes, and
horizontal space.
@code start
#include <iostream>
#include <ctime>
#include <bitset>
#include <vector>
#include <cmath> const unsigned int Size = 16;
Bad use of a global. It's used in multiple classes which lock them
together and doesn't allow other sized Grids or Coordinates (within the
same program.) Better would be for Size to be passed into a Grid c_tor
as a parameter, Grid can then pass it on to Coordinate (possibly as a
template parameter.)
class Random {
public:
Random() {srand(time(0));}
~Random() {}
unsigned int N(unsigned int n) {return rand() % n;}
};
I believe calling 'srand' can really screw up the distribution, making
it much less random (I might be wrong on this.) At any rate, it makes
the program harder to test unless we can make the behavior more
deterministic. At least allow the client to set the seed, better would
be to allow the client to provide a list of numbers to use.

Also, I would provide a no-arg version of 'N' that just does "return
rand()"
class Coordinate {
private:
unsigned int n;
public:
Coordinate() {}
Give a default value for 'n' in the above:

Coordinate::Coodinate(): n() { }
~Coordinate() {}
unsigned int Get() {return n;}
void Put(unsigned int i) {n = i;}
void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
};
I would use operator overloading here (op++ and op--). At least have the
functions return a Coordinate& (*this) for chaining.

Also the Put function doesn't guard against the invariant (that -1 < n <
Size) make that either a pre or post condition of Put. For example:

void Coordinate::Put( unsigned int i ) { n = i % Size; }
class Position {
private:
Coordinate x, y, z;
public:
Position() {
Random *R = 0;
R = new Random;
x.Put(R->N(Size));
y.Put(R->N(Size));
z.Put(R->N(Size));
delete R;
}
~Position() {}
unsigned long Id() {return x.Get()*Size*Size+y.Get()*Size+z.Get();}
};
Don't bother with the allocation in the c_tor.
Position::Position() {
Random R;
x.Put( R.N( Size ) );
// etc.
// no need for a delete
}

Actually, I wouldn't do any of that here, Move that up to the client.

class Position {
Coordinate x, y, z;
public:
Position(): x(), y(), z() { }
Position( int x_, int y_, int z_ ): x( x_ ), y( y_ ), z( z_ ) { }
// ...
};

Clients could do:
Position p( R.N(), R.N(), R.N() );

class Stack {
private:
std::vector<char> stack;
char c;
void Put_Back(){}
unsigned short Get_Back() {}
public:
Stack() {}
~Stack() {}
void Put_Dir() {}
void Put_Door(unsigned short n, bool b) {}
unsigned short Get_Dir() {}
bool Get_Door(unsigned short n) {}
void Next() {}
};
Surely something is missing in the above...
class Grid {
private:
Position Pos;
Random R;
Stack stack;
std::bitset<Size*Size*Size> yz, xz, xy, v;
public:
Grid() {
yz.set();
xz.set();
xy.set();
v.reset();
}
~Grid() {}
}; int main() {
Grid *Cube = 0;
Cube = new Grid;
delete Cube;
}


Again, no need to "new" a Grid object, just make it on the stack:

int main() {
Grid Cube;
}

Do you have tests proving that the various methods do what they are
supposed to do? I suspect not, it would be hard to write them because of
the rand function, but you should have such tests.
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 20 '06 #13

P: n/a

Daniel T. skrev:
In article <11**********************@g47g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
This actually work quite well...
Any comments?
No, no comments at all. As in you have no comments in your code. :-)


ya, i thought that i had bother you all with this project so much that
no explaining was needed ;-)
Seriously, I have some style comments.

White space is your friend, use it. More <cr>s between classes, and
horizontal space.
<cr>?
@code start
#include <iostream>
#include <ctime>
#include <bitset>
#include <vector>
#include <cmath>
const unsigned int Size = 16;


Bad use of a global. It's used in multiple classes which lock them
together and doesn't allow other sized Grids or Coordinates (within the
same program.) Better would be for Size to be passed into a Grid c_tor
as a parameter, Grid can then pass it on to Coordinate (possibly as a
template parameter.)


Im aware of the problem with Size, but i havent been able to solve it.
class Random {
public:
Random() {srand(time(0));}
~Random() {}
unsigned int N(unsigned int n) {return rand() % n;}
};
I believe calling 'srand' can really screw up the distribution, making
it much less random (I might be wrong on this.) At any rate, it makes
the program harder to test unless we can make the behavior more
deterministic. At least allow the client to set the seed, better would
be to allow the client to provide a list of numbers to use.


Random works fine, however not without srand.

Also, I would provide a no-arg version of 'N' that just does "return
rand()"
class Coordinate {
private:
unsigned int n;
public:
Coordinate() {}
Give a default value for 'n' in the above:

Coordinate::Coodinate(): n() { }
~Coordinate() {}
unsigned int Get() {return n;}
void Put(unsigned int i) {n = i;}
void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
};


I would use operator overloading here (op++ and op--). At least have the
functions return a Coordinate& (*this) for chaining.

Also the Put function doesn't guard against the invariant (that -1 < n <
Size) make that either a pre or post condition of Put. For example:

void Coordinate::Put( unsigned int i ) { n = i % Size; }


im somwhat confused here
class Position {
private:
Coordinate x, y, z;
public:
Position() {
Random *R = 0;
R = new Random;
x.Put(R->N(Size));
y.Put(R->N(Size));
z.Put(R->N(Size));
delete R;
}
~Position() {}
unsigned long Id() {return x.Get()*Size*Size+y.Get()*Size+z.Get();}
};
Don't bother with the allocation in the c_tor.


Why?
Position::Position() {
Random R;
x.Put( R.N( Size ) );
// etc.
// no need for a delete
}

Actually, I wouldn't do any of that here, Move that up to the client.
ya, ive though about that, but this is only my second class, give me
some time ;)

class Position {
Coordinate x, y, z;
public:
Position(): x(), y(), z() { }
Position( int x_, int y_, int z_ ): x( x_ ), y( y_ ), z( z_ ) { }
// ...
};

Clients could do:
Position p( R.N(), R.N(), R.N() );
indeed
class Stack {
private:
std::vector<char> stack;
char c;
void Put_Back(){}
unsigned short Get_Back() {}
public:
Stack() {}
~Stack() {}
void Put_Dir() {}
void Put_Door(unsigned short n, bool b) {}
unsigned short Get_Dir() {}
bool Get_Door(unsigned short n) {}
void Next() {}
};
Surely something is missing in the above...


what, you sure?
Just kidding, ofcourse something is missing, but im yet to figure out
how to do the code.
class Grid {
private:
Position Pos;
Random R;
Stack stack;
std::bitset<Size*Size*Size> yz, xz, xy, v;
public:
Grid() {
yz.set();
xz.set();
xy.set();
v.reset();
}
~Grid() {}
};
int main() {
Grid *Cube = 0;
Cube = new Grid;
delete Cube;
}


Again, no need to "new" a Grid object, just make it on the stack:


could still use some explaining here.

int main() {
Grid Cube;
}

Do you have tests proving that the various methods do what they are
supposed to do? I suspect not, it would be hard to write them because of
the rand function, but you should have such tests.
Yes, i have actually tested most of it.
That for the wery nice comments, somehow confusing but im in no hurry,
ill understand some day ;-)

regards

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.


Feb 20 '06 #14

P: n/a
In article <11**********************@g14g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
Daniel T. skrev:
In article <11**********************@g47g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
Seriously, I have some style comments.

White space is your friend, use it. More <cr>s between classes, and
horizontal space.


<cr>?


carriage return. In other words, extra vertical whitespace.
@code start
#include <iostream>
#include <ctime>
#include <bitset>
#include <vector>
#include <cmath>

const unsigned int Size = 16;


Bad use of a global. It's used in multiple classes which lock them
together and doesn't allow other sized Grids or Coordinates (within the
same program.) Better would be for Size to be passed into a Grid c_tor
as a parameter, Grid can then pass it on to Coordinate (possibly as a
template parameter.)


Im aware of the problem with Size, but i havent been able to solve it.


class Grid {
int Size;
// everything else
public:
Grid( int size = 16 ): Size( size ) { }
// everything else
};

With the above, each Grid can have a different size.

template < int Size >
class Coordinate {
// everything exactly like your Coordinate class
};

class Random {
public:
Random() {srand(time(0));}
~Random() {}
unsigned int N(unsigned int n) {return rand() % n;}
};


I believe calling 'srand' can really screw up the distribution, making
it much less random (I might be wrong on this.) At any rate, it makes
the program harder to test unless we can make the behavior more
deterministic. At least allow the client to set the seed, better would
be to allow the client to provide a list of numbers to use.


Random works fine, however not without srand.


Try this:

int main() {
for ( int x = 0; x < 100; ++x ) {
srand(time(0));
cout << rand() << '\n';
}
}

And you will see what I mean. Not very random. :-)
Also, I would provide a no-arg version of 'N' that just does "return
rand()"
class Coordinate {
private:
unsigned int n;
public:
Coordinate() {}
~Coordinate() {}
unsigned int Get() {return n;}
void Put(unsigned int i) {n = i;}
void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
};


I would use operator overloading here (op++ and op--). At least have the
functions return a Coordinate& (*this) for chaining.

Also the Put function doesn't guard against the invariant (that -1 < n <
Size) make that either a pre or post condition of Put. For example:

void Coordinate::Put( unsigned int i ) { n = i % Size; }


im somwhat confused here


The way the class is defined currently, clients can:
Coordinate coor;
coor.Put( 128 );
assert( coor.Get() == 128 );

However, coor.Get() should never return a value greater than 15. That
needs to be fixed. This shows you didn't test this method.

class Position {
private:
Coordinate x, y, z;
public:
Position() {
Random *R = 0;
R = new Random;
x.Put(R->N(Size));
y.Put(R->N(Size));
z.Put(R->N(Size));
delete R;
}
~Position() {}
unsigned long Id() {return x.Get()*Size*Size+y.Get()*Size+z.Get();}
};


Don't bother with the allocation in the c_tor.


Why?


Because it's both safer and easer to use a stact based object as I did
below.
Position::Position() {
Random R;
x.Put( R.N( Size ) );
// etc.
// no need for a delete
}


--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 21 '06 #15

P: n/a

Daniel T. skrev:
In article <11**********************@g14g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
Daniel T. skrev:
In article <11**********************@g47g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
Seriously, I have some style comments.

White space is your friend, use it. More <cr>s between classes, and
horizontal space.
<cr>?


carriage return. In other words, extra vertical whitespace.
> @code start
> #include <iostream>
> #include <ctime>
> #include <bitset>
> #include <vector>
> #include <cmath>

> const unsigned int Size = 16;

Bad use of a global. It's used in multiple classes which lock them
together and doesn't allow other sized Grids or Coordinates (within the
same program.) Better would be for Size to be passed into a Grid c_tor
as a parameter, Grid can then pass it on to Coordinate (possibly as a
template parameter.)


Im aware of the problem with Size, but i havent been able to solve it.


class Grid {
int Size;
// everything else
public:
Grid( int size = 16 ): Size( size ) { }
// everything else
};

With the above, each Grid can have a different size.


But i need the variable other places too, fx Position(), ive trye
everythingwith enhearitin/friends and stuff, but it doesnt work.

template < int Size >
class Coordinate {
// everything exactly like your Coordinate class
};

> class Random {
> public:
> Random() {srand(time(0));}
> ~Random() {}
> unsigned int N(unsigned int n) {return rand() % n;}
> };

I believe calling 'srand' can really screw up the distribution, making
it much less random (I might be wrong on this.) At any rate, it makes
the program harder to test unless we can make the behavior more
deterministic. At least allow the client to set the seed, better would
be to allow the client to provide a list of numbers to use.
Random works fine, however not without srand.


Try this:

int main() {
for ( int x = 0; x < 100; ++x ) {
srand(time(0));
cout << rand() << '\n';
}
}

And you will see what I mean. Not very random. :-)


i must admit your right, it has however worked before, dont know why it
doesnt now..
Calling rand alone wont work though, ill just end up with the same grid
every time.
(pseudo rand)
Also, I would provide a no-arg version of 'N' that just does "return
rand()"

> class Coordinate {
> private:
> unsigned int n;
> public:
> Coordinate() {}
> ~Coordinate() {}
> unsigned int Get() {return n;}
> void Put(unsigned int i) {n = i;}
> void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
> void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
> };

I would use operator overloading here (op++ and op--). At least have the
functions return a Coordinate& (*this) for chaining.

Also the Put function doesn't guard against the invariant (that -1 < n <
Size) make that either a pre or post condition of Put. For example:

void Coordinate::Put( unsigned int i ) { n = i % Size; }
im somwhat confused here


The way the class is defined currently, clients can:
Coordinate coor;
coor.Put( 128 );
assert( coor.Get() == 128 );

However, coor.Get() should never return a value greater than 15. That
needs to be fixed. This shows you didn't test this method.


I am aware og these things, but i dont know of any good way to fix it
yet (heard something of "limits" but havent been able to find some good
references)
> class Position {
> private:
> Coordinate x, y, z;
> public:
> Position() {
> Random *R = 0;
> R = new Random;
> x.Put(R->N(Size));
> y.Put(R->N(Size));
> z.Put(R->N(Size));
> delete R;
> }
> ~Position() {}
> unsigned long Id() {return x.Get()*Size*Size+y.Get()*Size+z.Get();}
> };

Don't bother with the allocation in the c_tor.
Why?


Because it's both safer and easer to use a stact based object as I did
below.


K then, just asking.
Position::Position() {
Random R;
x.Put( R.N( Size ) );
// etc.
// no need for a delete
}

regards
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.


Feb 21 '06 #16

P: n/a
In article <11**********************@f14g2000cwb.googlegroups .com>,
fe**********@hotmail.com wrote:
Daniel T. skrev:
In article <11**********************@g14g2000cwa.googlegroups .com>,
fe**********@hotmail.com wrote:
Daniel T. skrev:

> In article <11**********************@g47g2000cwa.googlegroups .com>,
> fe**********@hotmail.com wrote:
>
>
> > @code start
> > #include <iostream>
> > #include <ctime>
> > #include <bitset>
> > #include <vector>
> > #include <cmath>
>
> > const unsigned int Size = 16;
>
> Bad use of a global. It's used in multiple classes which lock them
> together and doesn't allow other sized Grids or Coordinates (within the
> same program.) Better would be for Size to be passed into a Grid c_tor
> as a parameter, Grid can then pass it on to Coordinate (possibly as a
> template parameter.)

Im aware of the problem with Size, but i havent been able to solve it.


class Grid {
int Size;
// everything else
public:
Grid( int size = 16 ): Size( size ) { }
// everything else
};

With the above, each Grid can have a different size.


But i need the variable other places too, fx Position(), ive trye
everythingwith enhearitin/friends and stuff, but it doesnt work.


If you fix Coordinate, you won't need 'Size' in Position. However, if
you need it in Position, then pass it in, just like for Grid above, or
as in the Fixed Coordinate I show below.
template < int Size >
class Coordinate {
// everything exactly like your Coordinate class
};

> > class Random {
> > public:
> > Random() {srand(time(0));}
> > ~Random() {}
> > unsigned int N(unsigned int n) {return rand() % n;}
> > };
>
> I believe calling 'srand' can really screw up the distribution, making
> it much less random (I might be wrong on this.) At any rate, it makes
> the program harder to test unless we can make the behavior more
> deterministic. At least allow the client to set the seed, better would
> be to allow the client to provide a list of numbers to use.

Random works fine, however not without srand.


Try this:

int main() {
for ( int x = 0; x < 100; ++x ) {
srand(time(0));
cout << rand() << '\n';
}
}

And you will see what I mean. Not very random. :-)


i must admit your right, it has however worked before, dont know why it
doesnt now..
Calling rand alone wont work though, ill just end up with the same grid
every time.
(pseudo rand)


You have to call srand, but you only call it once during the program,
not every time a "Random" object is created.
> Also, I would provide a no-arg version of 'N' that just does "return
> rand()"
>
> > class Coordinate {
> > private:
> > unsigned int n;
> > public:
> > Coordinate() {}
> > ~Coordinate() {}
> > unsigned int Get() {return n;}
> > void Put(unsigned int i) {n = i;}
> > void Inc() {n = (n == Size - 1) ? 0 : n + 1;}
> > void Dec() {n = (n == 0) ? Size - 1 : n - 1;}
> > };
>
> I would use operator overloading here (op++ and op--). At least have the
> functions return a Coordinate& (*this) for chaining.
>
> Also the Put function doesn't guard against the invariant (that -1 < n <
> Size) make that either a pre or post condition of Put. For example:
>
> void Coordinate::Put( unsigned int i ) { n = i % Size; }

im somwhat confused here


The way the class is defined currently, clients can:
Coordinate coor;
coor.Put( 128 );
assert( coor.Get() == 128 );

However, coor.Get() should never return a value greater than 15. That
needs to be fixed. This shows you didn't test this method.


I am aware og these things, but i dont know of any good way to fix it
yet (heard something of "limits" but havent been able to find some good
references)


I gave you a good way to fix it above. Look at the "Put" I wrote. It
will make sure that 'n' is in range. This is why you have accessors, so
you can make sure of these things.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 21 '06 #17

P: n/a
Ive desided to take a little big step at the time as im having trouble
keeping track of it all, im still thankfull for all the help though.

I did the coordinate class and it works fine.
Ive desided that N should be limited to 10 bits. max Size 1024,
theoreticly Size could be: floor( pow( 0xffffffff , (1/3) ) ) witch is
around 1500, but 1024 is fine. The reason for this limitation is
ofcourse the ID() function.
I dont like the Put_Size() at all, but everything else i try doesnt
work.
Ive changed Inc() and Dec() even though i dont need then to take
argument.

allso ive read up on data types on various system and got to the
conclusion that if you asume that:
char = 8 bit
short = 8 bit
int = 16 bit
long = 32 bit
float = 16 bit
double = 32 bit
You should pretty much be on the safe side.
Am i right in asuming that?

@code start
class Coordinate {
private:
unsigned int Size;
unsigned short N;
public:
Coordinate() {
N = 0;
}
~Coordinate() {}
void Put_Size(unsigned int a) {
Size = a;
}
unsigned short Get() {
return N;
}
void Put(unsigned short a) {
N = a;
}
void Inc(unsigned short a) {
for (; a > 0; a--) {
N = (N == Size - 1) ? 0 : N+1;
}
}
void Dec(unsigned short a) {
for (; a > 0; a--) {
N = (N == 0) ? Size - 1 : N-1;
}
}
};
class Position {
private:
unsigned int Size;
public:
Coordinate x, y, z;
Position(unsigned int a) {
Size = a;
x.Put_Size(a);
y.Put_Size(a);
z.Put_Size(a);
}
~Position() {}
unsigned long Id() {
return x.Get()*Size*Size+y.Get()*Size+z.Get();
}
};
@code end

work to do:
1) Get rit of the Put_Size() function.
2) Arrange for some limits (N, Size).
3) Allso the Put() function might need some attention.
4) All the other stuff that i have missed.

regards

Feb 22 '06 #18

P: n/a
One more thing.
The ID() function work fine as x, y and z is given the same limit/Size,
but if should want give then different sizes, it doesnt.
i was thinking something like:
(x.Get()*x.Size)+(y.Get()*y.Size)+(z.Get()*z.Size) ;
however if we give the values:
x.size = 256
y.size = 16
z.size = 4
we get the maximum result from ID() of 65532
when it should infack be:
256*16*4-1 = 16383
so obiously this doesnt work...

Feb 22 '06 #19

P: n/a
In article <11**********************@z14g2000cwz.googlegroups .com>,
fe**********@hotmail.com wrote:
class Coordinate {
private:
unsigned int Size;
unsigned short N;
public:
Coordinate() {
N = 0;
}
~Coordinate() {}
void Put_Size(unsigned int a) {
Size = a;
}
unsigned short Get() {
return N;
}
void Put(unsigned short a) {
N = a;
}
void Inc(unsigned short a) {
for (; a > 0; a--) {
N = (N == Size - 1) ? 0 : N+1;
}
}
void Dec(unsigned short a) {
for (; a > 0; a--) {
N = (N == 0) ? Size - 1 : N-1;
}
}
};


I'll show you some magic:

template < int Max >
class Coordinate {
int n;
public:
Coordinate(): n( 0 ) { }
Coordinate( int v ): n( v % Max ) { }

int get() const { return n; }

void set( int v ) { n = v % Max; }
Coordinate& operator++() { if ( ++n == Max ) n = 0; return *this; }
Coordinate& operator--() { if ( --n < 0 ) n = Max - 1; return *this; }
Coordinate operator++(int) {
Coordinate tmp(*this);
++(*this);
return tmp
}
Coordinate operator--(int) {
Coordinate tmp(*this);
--(*this);
return tmp
}
};

int main() {
Coordinate<16> c(24);
assert( c.get() == 8 );
++c;
assert( c.get() == 9 );
--c;
assert( c.get() == 8 );
}
--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.
Feb 22 '06 #20

This discussion thread is closed

Replies have been disabled for this discussion.