1. ## the maze

hi techies

i needed a game program that generates a maze using c++ with all its lines parralel to either x-axis or y-axis
iwhat i did was to type individual line commands

eg. line(540,67,540,67);
but the program was too lengthy
can you suggest a shorter way and i don't prefer using class concept which i don't know

2. Originally Posted by nikhil_trichy
hi techies

i needed a game program that generates a maze using c++ with all its lines parralel to either x-axis or y-axis
iwhat i did was to type individual line commands

eg. line(540,67,540,67);
but the program was too lengthy
can you suggest a shorter way and i don't prefer using class concept which i don't know

3. i had given an example
its too long to be typed here i typed individual line(x1,y1,x2,y2) commands
for example
:
line(20,40,20,60);
line(40,80,80,120);
and so on

4. Store all the endpoints in an array of some sort, then use a loop to iterate over the array to draw all the lines
Code:
```typedef struct point {
int x;
int y;
} point;
typedef struct line {
point start;
point end;
} line;

line lineArray[] = {
{ { 20, 40 }, { 20, 60 } },
{ { 40, 80 }, { 80, 120 } },
};

for ( i = 0 ; i < 2 ; i++ ) {
line ( lineArray[i].start.x, lineArray[i].start.y,
lineArray[i].end.x, lineArray[i].end.y );
}```

5. First each maze cell can have the following common characteristics.

1. Each one can have up to 4 border lines.
2. Each one is a perfect square.
3. The determining factor if a line is drawn is whether or not the neighboring cell for the line is empty or can be moved into/onto.

So:

Code:
```struct MazeCell
{
bool bNorth;
bool bSouth;
bool bEast;
bool bWest;

MazeCell(void):bNorth(true),bSouth(true),bEast(true),bWest(true) {}
};

void RenderMaze(int iStartX,int iStartY,int iMazeWidth,int iMazeHeight,int iCellSize,MazeCell *pMaze)
{
int iMapOffset=0;

iStartX+=(iCellSize)>>1;
iStartY+=(iCellSize)>>1;

int x=0;
int x2=0;
int y=0;
int y2=0;

for (int i=iStartY;i<(iStartY+iMazeHieght)-iCellSize;i+=iCellSize)
{
for (int j=iStartX;j<(iStartX+iMazeWidth)-iCellSize;j+=iCellSize)
{
x=j;
y=i,
x2=j+iCellSize;
y2=i+iCellSize;

if (pMaze[iMapOffset].bNorth) DrawLine(x,y,x2,y);
if (pMaze[iMapOffset].bSouth) DrawLine(x,y2,x2,y2);
if (pMaze[iMapOffset].bEast) DrawLine(x2,y,x2,y2);
if (pMaze[iMapOffset].bWest) DrawLine(x,y,x,y2);

iMapOffset++;
}
}
}```
I leave it to you to create the maze. Note that the following must be true:

(iMazeWidth/iCellSize) == iMazeMapWidth
(iMazeHeight/iCellSize) == iMazeMapHeight

Or the code will crash.

6. As far as generating the maze, I think you could do pretty good with a bfs kind of algorithm. One way to do it would be to keep a stack of paths and expand them into a tree using several constraints that you determine. I would implement it like this:
Code:
```struct Point {
int x, y;
};

Point* expandPoint(Point& point, int dir) {
static int dx[4] = {1,0,-1,0};
static int dy[4] = {0,1,0,-1};

Point* ret = new Point;
ret->x = point.x + dx[dir%4];
ret->y = point.y + dy[dir%4];
return ret;
}

struct path {
int pointCount, childrenCount;
Point pointList[BUFSIZE];
Path* childrenList[BUFSIZE];

Path* parent;
};

Path* makeChildPath(Path* parent) {
Path *path = new Path;
path->pointCount = 1;
path->childrenCount = 0;
path->parent = parent;
parent->children[parent->childrenCount++] = path;
return path;
}

bool pointCollidesWithPath(Point& point, Path& path) {
for (int i = 0; i < path.pointCount; ++i)
if (pointList[i].x == point.x && pointList[i].y == point.y)
return true;
return false;
}

Path* genMaze(int w, int h, Point startPoint) {
int i, j;

int branchProb = 5, maxBranchLength = 5;

int pathListLength = 1, pathStackLength = 1;
Path *pathList[BUFSIZE]; //list of all paths for collision direction
Path *pathStack[BUFSIZE]; //stack of paths for traversal

Path* startPath = new Path;
startPath->pointList[0] = startPoint;
startPath->pointCount = 1;
startPath->childrenCount = 0;

pathList[0] = startPath;
pathStack[0] = startPath;

while (pathStackLength > 0) {
Path* path  = pathStack[rand()%pathStack.length];

//branch
if (!(rand()%branchProb)) {
Path* newPath = makeChildPath(path);
pathList[pathListLength++] = newPath;
pathStack[pathStackLength++] = newPath;
path = newPath;
}

//expand
int branchLength = rand()%maxBranchLength/2+maxBranchLength/2;
bool turned = true;
for (i = 0; i < branchLength && true; ++i) {
turned = false;
int turnOffset = rand()%4;
for (j = turnOffset; j < turnOffset+4 && !turned; ++j) {
Point* newPoint = expandPoint(path->pointList[path->pointCount-1],j);
bool collides = newPoint->x >= w || newPoint->x < 0 || newPoint->y >= h || newPoint->y < 0;
for (k = 0; k < pathListLength && !collides; ++k)
if (pointCollidesWithPath(*newPoint,pathList[k]))
collides = true;
if (!collides) {
path->pointList[path->pointCount++] = *newPoint;
turned = true;
} else
delete newPoint;
}
}
if (i < branchLength) { //got stuck
remove path from pathStack
}

return pathList[0]; //return root of maze tree
}```
I hope that's helpful. It's just a traversal across the tree picking a random path to expand and expanding it in random directions without colliding until you get stuck or go a certain distance, then it stops when it can't expand any more paths (ie the board is full). This has will always generate a maze that covers every available place, and returns the maze as a tree of paths. To render to maze, you would just have to do something like this:
Code:
```void renderPath(Path* path) {
int i, j;
//render this path
for (j = 0; j < path->pointCount-1; ++j)
remove the edge between path->pointList[j] and path->pointList[j+1]

//render children
for (j = 0; j < path->childrenCount; ++j) {
remove the edge between path->children[j]->pointList[0] and path->children[j].linkPoint to connect the paths
renderPath(path->children[j]);
}
}

void renderMaze(Path* mazeRoot) {
render the board as a grid of boxes
renderPath(mazeRoot); //start rendering paths with the root
}```
There are definitely better ways to write this (I would especially look at dynamically allocating and managing all your lists so that you don't overrun your arrays), but the idea should work. I think.

edit:
I just rewrote this whole thing to not use classes. See? It's easy to switch back and forth, don't be intimidated!

7. i trie d this
Code:
```#include<graphics.h>
#define player circle(x1,y1,10)

int x2={ 40,80,37,....}
int y2={48,82,93...}
int x3={40,87,290,93...}
int y3={........}

void main()
{

display maze();
check();//to check whether the line is touching any lines of the maze
}

display maze
{
for(some loop)
{line[x2[i],y2[i],x3[i],y3[i])
}

void check(void)
{

if (x2[i]==x3[i])  //if the line is parallel to y axis
{
if y2[i]>y3[i]
{
if(x1==(x2[i]-10)||x`==x2[i]+10)&&(y1>=y3{i]&&(y1<=y2[i])

{
something will happen
}

// to check whether the y   coordinate of the circle is in between the y coordinates of the line```
similarly y2<y3 andfor line parallel to x axis and x2>x3 and x3>x2
display maze is working properly but not the function check()

in short(??)
i want to move a circle through the maze maze and find out whether the circle
is touching the lines or not
can you please suggest corrections or alternatives to the above coding

8. We already told you several ways to do it. Try those. I can't even understand what yours is doing.

9. u all have told me how to generate a maze and thanx a lot for it
but i had a brainwave(???) and decided to render the maze in the way i hav already mentioned but now comes the problem .
i want to check if the object i am moving is touching the lines of the maze or not
can you help me??

i am moving the circle by using the code given below
Code:
```:
:
ch=getch();
if(ch==some ascii value)
{
increment or decrement x or y coordinates
}
similarly for other cases
}```

10. Not with that kind of information I can't.

11. i will post my problem in short for u all once again(how many agains more)
i use a function to display a maze. the working of thye function i have already explained.
then i tried to check whether the object i am moving is touching lines of the maze or not,
by calling the function check() the working of which i explained in my prev messages
but the object is being checked only for certain lines and not for the others
can you help me??

12. i am a student and has to complete a project in which i have to generate amaze and
check whether the object i am moving is touching the lines of the maze or not . the rule is that i can use only c++ functions and not classes structures or anyother concepts
i tried a program but it is workuing only partly

using only c++)
Code:
```#define player circle(x1,y1,10)
x1=20;
y1=415;
int x2={ 40,80,37,....}  //array to store initial x coordinates of lines
int y2={48,82,93...}	//array tro store initial y coordinates of lines that form the maze
int x3={40,87,290,93...}//final points
int y3={........}//final points

void main()
{
char ch;
while(1)
{
display_maze();
ch=getch();
if(ch==27)//ASCII value for esc
exit(0);
if(ch==72)	//
etc..
//different ASCII values are checked and the coordinates x1 y1 are incremented
//to move the circle

check();//to check whether the line is touching any lines of the maze
}

void display_maze(void)
{
for(int i=0; i<60; ++i)

{line[x2[i],y2[i],x3[i],y3[i])
}

void check(void)
{
for(int i=0 ; i<60; i++)
{
if (x2[i]==x3[i])  //if the line is parallel to y axis
{
if y2[i]>y3[i]
{
if(x1==(x2[i]-10)||x`==x2[i]+10)&&(y1>=y3{i]&&(y1<=y2[i])

{
x1=20;//initial positions
y1=415;//of the circle
chances--;
}

// to check whether the y   coordinate of the circle is in between the y coordinates of the line```
similarly the loop contains code for checking y2<y3 and for line parallel to x axis and x2>x3 and x3>x2

}

the function display maze()is working but not the function check()- it is only checking some lines
and not the others

in short(??)
i want to move a circle through the maze maze and find out whether the circle
is touching the lines or not
can you please suggest corrections or alternatives to the above coding

13. ...only c++ functions
Ok.....

I will help one more time. Anything more than this and I might as well write the program for you.

Just for kicks you can alter the structure approach I used and instead use bit masks to represent directions.

Code:
```#define DIR_NORTH 0x01
#define DIR_SOUTH 0x02
#define DIR_EAST 0x04
#define DIR_WEST 0x08

#define DIR_ALL  (NORTH) | (SOUTH) | (EAST) | (WEST)```
And just in case your teacher wont let you use bit masks you can look at this map in memory and use a different approach.

1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 1
1 2 1 1 1 1 0 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1
0 = empty
1 = wall
2 = player position

Code:
```#define PLAYER_PIECE 0x02

....
int offset=iMapWidth+2;
int x=0,y=0;

for (int i=1;i<iMapHeight-2;i+=2)
{
for (int j=1;j<iMapWidth-2;j+=2)
{
int offsetLeft=offset-1;
int offsetUp=offset-iMapWidth;
int offsetDown=offset+iMapWidth;
int offsetRight=offset+1;

if (Map[offsetLeft]) DrawLine(x,y,x,y+iCellSize);
if (Map[offsetRight) DrawLine(x+iCellSize,y,x+iCellSize,y+iCellSize);
if (Map[offsetUp)) DrawLine(x,y,x+iCellSize,y);
if (Map[offsetDown) DrawLine(x,y+iCellSize,x+iCellSize,y+iCellSize);

if (Map[offset]==PLAYER_PIECE) DrawCircle(x,y,iCellSize/2);

x+=iCellSize;
}
x=0;
y+=iCellSize;
}
...```
You could use both methods and use the above routine to instead use bitwise operations to compute the directions and save them in another map. Then it would be easier to check for directions.

Code:
```bool MoveLeft(int px,int py,int iMapWidth,int &outOffset)
{
//Bail on error
if ((px-1)<1) return true;

int offset=py*iMapWidth_px;

if ((DirectionMap[offset-1] & DIR_EAST) == DIR_EAST)
{
return true;  //Cannot move here
}
else outOffset=offset-1;

return false;
}```
No matter what limits your teacher puts on the project, I could code this. It would just be uglier and less efficient the more tools they took away from me.

So stick it to your teacher and code this using several methods. Make it look easy.

14. what if i wanted to put hte player to the initial position when he touches the wall of the maze??

and of course as it always happens with me another brainwave( oh my god!! not again)
can getpixel() be of any help???