Jump to content
  • Advertisement
Sign in to follow this  
mike74

maze reduction

This topic is 4872 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm creating a maze game and a maze is currently represented by a simple 2d array like so: 11111111111111111 11100000000000111 11100000000000111 11111111111111111 11111111111111111 The 1's represent cube walls, and the 0's are empty space. Does anyone know an easy and elegant way to convert this into the minimum number of polygons possible? For instance this one would convert into 4 polygons that comprise the rectangle bordering the 1's and 0's. Right now, my program would convert it into 26 polygons, which is too much (due to some ray tracing culling I am doing). Mike C. http://www.coolgroups.com/zoomer/

Share this post


Link to post
Share on other sites
Advertisement
There won't be a very easy and elegant way, you will probably have to just brute force it.

If you could somehow walk the maze, each straight line could be a quad.

ace

Share this post


Link to post
Share on other sites
Hmmm... I have an idea that I think might work.
Basically, I can just toss the maze into a vector of Quad objects.

repeat a lot {

I can choose two distinct random Quad objects from the vector. For simplicity I'll remove them from the vector and put them in two objects q1 and q2.

If the quads are not coplanar, I'll just throw them back in the vector.

otherwise {
If the first and last points of one Quad q1 are equal to the 2nd and third points of q2 respectively,

{then I'll insert a new Quad back into the vector. It will have the 2nd and 3rd points of q1 and the 1st and 4th points of q2. Hmmm... The points will have to be ordered (1st of q2, 2nd of q2, 3rd of q1, 4th of q2).
}
Otherwise I'll just throw q1 and q2 back in the vector.

}

}

Sorry if this sounds like gibberish - it's late and I'm low on caffeine.

Mike C.
http://www.coolgroups.com/zoomer/

Share this post


Link to post
Share on other sites
Here's some code that seems to successfully reduce those mazes:

for (int ctr = 0; ctr < 10000000; ctr++)
{
int rand1 = rand() % v.size();
Quad q1 = v[rand1];

int rand2 = rand() % v.size();
Quad q2 = v[rand2];

// if it's not co-planar, forget it
if ((q2.isparalleltox() && !q1.isparalleltox())
|| (!q2.isparalleltox() && q1.isparalleltox())) continue;

if (vertequal(q1.vert0, q2.vert1)
&& vertequal(q1.vert3, q2.vert2))
{
int smallrand, bigrand;
if (rand1 < rand2) {smallrand=rand1; bigrand=rand2;}
else {smallrand=rand2; bigrand=rand1;}
v.erase(v.begin()+bigrand);
v.erase(v.begin()+smallrand);

Quad q3 = Quad(q2.vert0, q1.vert1, q1.vert2, q2.vert3);
v.insert(v.begin(), q3);
}

}

Mike C.
http://www.coolgroups.com/zoomer/

Share this post


Link to post
Share on other sites
Not optimal, but should be good enough.


#include <iostream>
#include <vector>
#include <algorithm>

struct Rectangle
{
public:
int x1, y1, x2, y2;

Rectangle(int x1, int y1, int x2, int y2): x1(x1), y1(y1), x2(x2), y2(y2)
{}
};

class Maze: public std::vector<Rectangle>
{
public:
Maze(const char * const *data)
{
if(data && *data)
{
std::vector<Rectangle> last, current;

for(int y = 0; ; )
{
int x = 0;

for(const char *cell = *data; *cell;) if(*cell != ' ')
{
Rectangle &rect(*current.insert(current.end(),
Rectangle(x, y, 0, 0)));

for(++cell, ++x; *cell && *cell != ' '; ++cell, ++x) {}

rect.x2 = x;
}
else ++cell, ++x;

for(std::vector<Rectangle>::iterator a(current.begin()), b(last.begin()); b != last.end(); )
{
if(a->x2 >= b->x1)
{
if(a->x1 == b->x1 && a->x2 == b->x2)
a->y1 = b->y1;
else
{
b->y2 = y;
insert(end(), *b);
}

++b;
}

if(++a == current.end())
{
for(; b != last.end(); ++b)
{
b->y2 = y;
insert(end(), *b);
}

break;
}
}

++y;

if(*++data)
{
current.swap(last);
current.clear();
}
else
{
for(std::vector<Rectangle>::iterator a(current.begin()); a != current.end(); ++a)
{
a->y2 = y;
insert(end(), *a);
}

break;
}
}
}
}
};

int main()
{
const char *maze_data[] =
{" # #",
" # #### ###",
" # #### # ",
" # ######## ",
" # # # ",
"###### # ",
"# ########",
0};

Maze maze(maze_data);

std::cout << "Created " << maze.size() << " rectangles:\n\n" << std::endl;

/* Testing:

Numbers are the number of times a rectangle intersects that cell.
Should be 1, anything else means something went fubar. */


char output[20][20];

for(int y = 0; y < 20; ++y)
for(int x = 0; x < 20; ++x)
output[x][y] = ' ';

for(Maze::const_iterator i(maze.begin()); i != maze.end(); ++i)
for(int y = i->y1; y < std::min(20, i->y2); ++y)
for(int x = i->x1; x < std::min(20, i->x2); ++x)
if(output[x][y] == ' ')
output[x][y] = '1';
else
++output[x][y];

for(int y = 0; y < 20; ++y)
{
for(int x = 0; x < 20; ++x)
std::cout << output[x][y];

endl(std::cout);
}
}




Output:


Created 12 rectangles:


1 1
1 1111 111
1 1111 1
1 11111111
1 1 1
111111 1
1 11111111

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!