maze reduction
Author
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/
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
If you could somehow walk the maze, each straight line could be a quad.
ace
Author
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/
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/
Author
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/
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/
Not optimal, but should be good enough.
Output:
#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 1111111 11 11111111This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
